[
https://issues.apache.org/jira/browse/LUCENE-4867?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Adrien Grand resolved LUCENE-4867.
----------------------------------
Resolution: Fixed
> 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, 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]
