hadoop-common-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Chris Douglas (JIRA)" <j...@apache.org>
Subject [jira] Commented: (HADOOP-3442) QuickSort may get into unbounded recursion
Date Mon, 02 Jun 2008 22:35:45 GMT

    [ 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.

View raw message