Details

    • Type: Improvement Improvement
    • Status: Closed
    • Priority: Trivial 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?

      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:
              Adrien Grand
              Reporter:
              Adrien Grand
            • Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development