[ https://issues.apache.org/jira/browse/LUCENE-4867?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13610611#comment-13610611 ]
Commit Tag Bot commented on LUCENE-4867: ---------------------------------------- [trunk commit] Adrien Grand http://svn.apache.org/viewvc?view=revision&revision=1459851 LUCENE-4867: Allow custom SorterTemplates to override merge. > 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: dev-unsubscr...@lucene.apache.org For additional commands, e-mail: dev-h...@lucene.apache.org