Details

    • Type: Improvement Improvement
    • Status: Resolved
    • Priority: Minor Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      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.

      1. SortBench.java
        1 kB
        Adrien Grand
      2. LUCENE-4867.patch
        8 kB
        Adrien Grand
      3. LUCENE-4867.patch
        15 kB
        Adrien Grand

        Activity

        Hide
        Adrien Grand added a comment -

        Here is the program I used for testing.

        Show
        Adrien Grand added a comment - Here is the program I used for testing.
        Hide
        Uwe Schindler added a comment -

        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.

        Show
        Uwe Schindler added a comment - 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.
        Hide
        Adrien Grand added a comment -

        If you want a faster algorithm, you have to move away from in-place.

        In that case, could we make SorterTemplate.merge overridable (protected) so that custom templates can use extra memory to merge? The attached patch modifies ArrayUtil to show how it could be used to implement a faster merge, which makes mergeSort more than 2x faster (~21s on average on my 50M array) although it only requires 1% of additional memory. What do you think?

        Show
        Adrien Grand added a comment - If you want a faster algorithm, you have to move away from in-place. In that case, could we make SorterTemplate.merge overridable (protected) so that custom templates can use extra memory to merge? The attached patch modifies ArrayUtil to show how it could be used to implement a faster merge, which makes mergeSort more than 2x faster (~21s on average on my 50M array) although it only requires 1% of additional memory. What do you think?
        Hide
        Uwe Schindler added a comment - - edited

        Making the merge method protected would offer the possibility to speed up merging. If you dont implement a custom merge, the code works only with swap and/or setPivot.

        Why do we need a seperate getSorter() in ArrayUtils? Could the default SorterTemplate used also for quicksort not simply provide the faster merge? Or did you implement it separate to not allocate the extra array, if only quicksort is called?

        Otherwise I am fine with doing it that way, if we do not enforce users to implement the merge code.

        Show
        Uwe Schindler added a comment - - edited Making the merge method protected would offer the possibility to speed up merging. If you dont implement a custom merge, the code works only with swap and/or setPivot. Why do we need a seperate getSorter() in ArrayUtils? Could the default SorterTemplate used also for quicksort not simply provide the faster merge? Or did you implement it separate to not allocate the extra array, if only quicksort is called? Otherwise I am fine with doing it that way, if we do not enforce users to implement the merge code.
        Hide
        Adrien Grand added a comment -

        Or did you implement it separate to not allocate the extra array, if only quicksort is called?

        Exactly.

        Show
        Adrien Grand added a comment - Or did you implement it separate to not allocate the extra array, if only quicksort is called? Exactly.
        Hide
        Adrien Grand added a comment -

        Otherwise I am fine with doing it that way, if we do not enforce users to implement the merge code.

        OK. I'll update the patch to port the same behavior to CollectionUtil.

        Show
        Adrien Grand added a comment - Otherwise I am fine with doing it that way, if we do not enforce users to implement the merge code. OK. I'll update the patch to port the same behavior to CollectionUtil.
        Hide
        Adrien Grand added a comment -

        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 sorts.

        I'll open a separate issue to use the same optimizations for the sorter API's timsorts.

        Show
        Adrien Grand added a comment - 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 sorts. I'll open a separate issue to use the same optimizations for the sorter API's timsorts.
        Hide
        Commit Tag Bot added a comment -

        [branch_4x commit] Adrien Grand
        http://svn.apache.org/viewvc?view=revision&revision=1459853

        LUCENE-4867: Allow custom SorterTemplates to override merge (merged from r1459851).

        Show
        Commit Tag Bot added a comment - [branch_4x commit] Adrien Grand http://svn.apache.org/viewvc?view=revision&revision=1459853 LUCENE-4867 : Allow custom SorterTemplates to override merge (merged from r1459851).
        Hide
        Commit Tag Bot added a comment -

        [trunk commit] Adrien Grand
        http://svn.apache.org/viewvc?view=revision&revision=1459851

        LUCENE-4867: Allow custom SorterTemplates to override merge.

        Show
        Commit Tag Bot added a comment - [trunk commit] Adrien Grand http://svn.apache.org/viewvc?view=revision&revision=1459851 LUCENE-4867 : Allow custom SorterTemplates to override merge.

          People

          • Assignee:
            Adrien Grand
            Reporter:
            Adrien Grand
          • Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development