lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Adrien Grand (JIRA)" <>
Subject [jira] [Updated] (LUCENE-4867) SorterTemplate.merge is slow
Date Thu, 21 Mar 2013 16:03:16 GMT


Adrien Grand updated LUCENE-4867:

    Attachment: LUCENE-4867.patch

Patch that makes SorterTemplate.merge protected and makes ArrayUtil and CollectionUtil use
specialized SorterTemplate instances that use up to 1% extra memory for faster merge-based

I'll open a separate issue to use the same optimizations for the sorter API's timsorts.
> SorterTemplate.merge is slow
> ----------------------------
>                 Key: LUCENE-4867
>                 URL:
>             Project: Lucene - Core
>          Issue Type: Improvement
>            Reporter: Adrien Grand
>            Assignee: Adrien Grand
>            Priority: Minor
>         Attachments: LUCENE-4867.patch, LUCENE-4867.patch,
> 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:

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message