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] Updated: (HADOOP-3442) QuickSort may get into unbounded recursion
Date Mon, 02 Jun 2008 21:11:45 GMT

     [ https://issues.apache.org/jira/browse/HADOOP-3442?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Chris Douglas updated HADOOP-3442:
----------------------------------

    Attachment: 3442-0.patch

Alternatively, we could just effect the tail recursion with a loop (see attached; credit to
Nicholas for the idea). I'm not wild about creating new java.util.Stack instances, but it's
not likely to be a performance issue either way. As for switching to heapsort from insertion
sort for < K/log\(n) values, though I'd be surprised to learn that was a bottleneck, it
sounds like a cool idea to try.

The recursion itself doesn't seem to be the problem, though; that there's a case where it
becomes unbounded is. This is showing up often enough that there is likely a framework problem,
but nobody has explained how they reproduce it, yet.

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


Mime
View raw message