[
https://issues.apache.org/jira/browse/LUCENE-4867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13608923#comment-13608923
]
Uwe Schindler commented on LUCENE-4867:
---------------------------------------
The main problem is: The universal possinility to use SorterTemplate is the
fact that you only have to define the swap operation and nothing more. If you
need an additional array to buffer the merging, the API gets much more complex,
as you would need to define the whole merge process for your "custom buffer
implementation", the easy "compare-and-swap-with-pivot" would be gone.
SorterTemplate is something in the middle: Its not using the fastest merge, but
it is in-place and has a very limited set of operations to implement. If you
want a faster algorithm, you have to move a way from in-place. All the fast
merge/timsort/quicksort algoth are working with arrays only and SorterTemplate
wants to work around this in a simple generic way.
> 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: 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: dev-unsubscr...@lucene.apache.org
For additional commands, e-mail: dev-h...@lucene.apache.org
