[
https://issues.apache.org/jira/browse/LUCENE-4867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13610608#comment-13610608
]
Commit Tag Bot commented on LUCENE-4867:
----------------------------------------
[branch_4x commit] Adrien Grand
http://svn.apache.org/viewvc?view=revision&revision=1459853
LUCENE-4867: Allow custom SorterTemplates to override merge (merged from
r1459851).
> 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]
