Details

    • Type: Improvement
    • Status: Closed
    • Priority: Trivial
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 4.4
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      When working on TimSort (LUCENE-4839), I was a little frustrated of not being able to add galloping support because it would have required to add new primitive operations in addition to compare and swap.

      I started working on a prototype that uses inheritance to allow some sorting algorithms to rely on additional primitive operations. You can have a look at https://github.com/jpountz/sorts/tree/master/src/java/net/jpountz/sorts (but beware it is a prototype and still misses proper documentation and good tests).

      I think it would offer several advantages:

      • no more need to implement setPivot and comparePivot when using in-place merge sort or insertion sort,
      • the ability to use faster stable sorting algorithms at the cost of some memory overhead (our in-place merge sort is very slow),
      • the ability to implement properly algorithms that are useful on specific datasets but require different primitive operations (such as TimSort for partially-sorted data).

      If you are interested in comparing these implementations with Arrays.sort, there is a Benchmark class in src/examples.

      What do you think?

        Attachments

        1. LUCENE-4946.patch
          130 kB
          Adrien Grand
        2. LUCENE-4946.patch
          130 kB
          Adrien Grand
        3. LUCENE-4946.patch
          130 kB
          Adrien Grand

          Issue Links

            Activity

              People

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

                Dates

                • Created:
                  Updated:
                  Resolved: