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

        Adrien Grand created issue -
        Adrien Grand made changes -
        Field Original Value New Value
        Attachment SortBench.java [ 12574794 ]
        Adrien Grand made changes -
        Attachment LUCENE-4867.patch [ 12574800 ]
        Adrien Grand made changes -
        Attachment LUCENE-4867.patch [ 12574819 ]
        Adrien Grand made changes -
        Status Open [ 1 ] Resolved [ 5 ]
        Resolution Fixed [ 1 ]

          People

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

            Dates

            • Created:
              Updated:
              Resolved:

              Development