[
https://issues.apache.org/jira/browse/HADOOP-3442?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=12601778#action_12601778
]
Chris Douglas commented on HADOOP-3442:
---------------------------------------
bq. Can you try testing my version in your environment to see if you get a
performance change?
I tried running the test case with 10M elements and saw only very slight
performance improvements over the original, excluding the sequential test case,
where it degraded. I'm running 1.5.0_13 on a Mac, so YMMV.
bq. Introsort still uses insertionSort instead of quicksort for low n. It uses
heapsort when quicksort has recursed deeply
Ah, I understand. Still, the issue here is not performance, but correctness.
Until we verify that the implementation of QuickSort is correct but pushed into
a degenerate case, I think we should assume that some aspect of the framework
is incorrect and try to determine why we're topping out the stack. Once we
isolate the issue, then we can look into new sorting strategies if they solve
the problem, but I'm not sure we can say without fear of refutation that the
recursion alone is causing this, yet. Clearly the two are related, but we need
a reproducible test case before we can start proposing remedies, no? If there's
a problem with the Quicksort implementation but we switch to heapsort after it
hits the maximum recursion depth, then we mask a bug with the optimization.
> 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.
