[
https://issues.apache.org/jira/browse/LUCENE-3054?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13027948#comment-13027948
]
Uwe Schindler commented on LUCENE-3054:
---------------------------------------
Studying the C++ STL code showed that they use 2 * log2(n) as depth limit. I
implemented that. It showed that for the most cases in Lucene (BytesRefHash),
it uses quicksort (so no change to performance). The other cases use already
mergeSort and the "bad" test in TestArrayUtil switches sucessfully to mergeSort.
> SorterTemplate.quickSort stack overflows on broken comparators that produce
> only few disticnt values in large arrays
> --------------------------------------------------------------------------------------------------------------------
>
> Key: LUCENE-3054
> URL: https://issues.apache.org/jira/browse/LUCENE-3054
> Project: Lucene - Java
> Issue Type: Task
> Affects Versions: 3.1
> Reporter: Robert Muir
> Assignee: Uwe Schindler
> Priority: Critical
> Fix For: 3.1.1, 3.2, 4.0
>
> Attachments: LUCENE-3054-dynamic.patch,
> LUCENE-3054-stackoverflow.patch, LUCENE-3054.patch, LUCENE-3054.patch,
> LUCENE-3054.patch, LUCENE-3054.patch, LUCENE-3054.patch, LUCENE-3054.patch
>
>
> Looking at Otis's sort problem on the mailing list, he said:
> {noformat}
> * looked for other places where this call is made - found it in
> MultiPhraseQuery$MultiPhraseWeight and changed that call from
> ArrayUtil.quickSort to ArrayUtil.mergeSort
> * now we no longer see SorterTemplate.quickSort in deep recursion when we do a
> thread dump
> {noformat}
> I thought this was interesting because PostingsAndFreq's comparator
> looks like it needs a tiebreaker.
> I think in our sorts we should add some asserts to try to catch some of these
> broken comparators.
--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
