[ https://issues.apache.org/jira/browse/LUCENE-4867?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Adrien Grand updated LUCENE-4867: --------------------------------- Attachment: SortBench.java Here is the program I used for testing. > 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