[
https://issues.apache.org/jira/browse/LUCENE-4867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13609011#comment-13609011
]
Uwe Schindler edited comment on LUCENE-4867 at 3/21/13 3:02 PM:
----------------------------------------------------------------
Making the merge method protected would offer the possibility to speed up
merging. If you dont implement a custom merge, the code works only with swap
and/or setPivot.
Why do we need a seperate getSorter() in ArrayUtils? Could the default
SorterTemplate used also for quicksort not simply provide the faster merge? Or
did you implement it separate to not allocate the extra array, if only
quicksort is called?
Otherwise I am fine with doing it that way, if we do not enforce users to
implement the merge code.
was (Author: thetaphi):
Making the merge mtehd protected would offer the possibility to speed up
merging. If you dont implement a custom merge, the code works only with swap
and/or setPivot.
Why do we need a seperate getSorter() in ArrayUtils? Could the default
SorterTemplate used also for quicksort not simply provide the faster merge? Or
did you implement it separate to not allocate the extra array, if only
quicksort is called?
Otherwise I am fine with doing it that way, if we do not enforce users to
implement the merge code.
> SorterTemplate.merge is slow
> ----------------------------
>
> Key: LUCENE-4867
> URL: https://issues.apache.org/jira/browse/LUCENE-4867
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Adrien Grand
> Assignee: Adrien Grand
> Priority: Minor
> Attachments: LUCENE-4867.patch, SortBench.java
>
>
> SorterTemplate.mergeSort/timSort can be very slow. For example, I ran a quick
> benchmark that sorts an Integer[] array of 50M elements, and mergeSort was
> almost 4x slower than quickSort (~12.8s for quickSort, ~46.5s for mergeSort).
> This is even worse when the cost of a swap is higher (e.g. parallel arrays).
> This is due to SorterTemplate.merge. I first feared that this method might
> not be linear, but it is, so the slowness is due to the fact that this method
> needs to swap lots of values in order not to require extra memory. Could we
> make it faster?
> For reference, I hacked a SorterTemplate instance to use the usual merge
> routine (that requires n/2 elements in memory), and it was much faster: ~17s
> on average, so there is room for improvement.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
