[
https://issues.apache.org/jira/browse/HADOOP-3442?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12601768#action_12601768
]
whipkey edited comment on HADOOP-3442 at 6/2/08 2:24 PM:
--------------------------------------------------------------
Can you try testing my version in your environment to see if you get a
performance change? I'm thinking that there may be some JIT thing going on
that makes the no-recursion version better. I did get a significant (like,
20%+ less time), repeatable, performance gain when using my version.
Introsort still uses insertionSort instead of quicksort for low n. It uses
heapsort when quicksort has recursed deeply; unlike quicksort, heapsort has
guaranteed worst-case performance of O(n log n), avoiding both the huge
recursion (it's not recursive) and the O(n*n) runtime that such a recursion
produces. But it's generally slower, so introsort uses it only when quicksort
has hit a bad case.
Thanks!
was (Author: whipkey):
Can you try testing my version in your environment to see if you get a
performance change? I'm thinking that there may be some JIT thing going on
that makes the no-recursion version better. I did get a significant (like,
20%+ less time), repeatable, performance gain when using my version.
Introsort still uses insertionSort instead of quicksort for low n. It uses
heapsort when quicksort has recursed deeply; unlike quicksort, heapsort has
guaranteed worst-case performance of O(n*log(n)), avoiding both the huge
recursion (it's not recursion) and the O(n*n) runtime that such a recursion
produces. But it's generally slower, so introsort uses it only when quicksort
has hit a bad case.
Thanks!
> QuickSort may get into unbounded recursion
> ------------------------------------------
>
> Key: HADOOP-3442
> URL: https://issues.apache.org/jira/browse/HADOOP-3442
> Project: Hadoop Core
> Issue Type: Bug
> Components: mapred
> Affects Versions: 0.17.0
> Reporter: Runping Qi
> Assignee: Chris Douglas
> Attachments: 3442-0.patch, HADOOP-3442.patch
>
>
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
