Adrien Grand created LUCENE-4867:
------------------------------------
Summary: 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
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
