Uploaded image for project: 'Lucene - Core'
  1. Lucene - Core
  2. LUCENE-7097

Can we increase the stack depth before Introsorter switches to heapsort?

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: trunk, 6.1
    • Component/s: None
    • Labels:
      None
    • Lucene Fields:
      New

      Description

      Introsort is a "safe" quicksort: it uses quicksort but detects when an adversary is at work and cuts over to heapsort at that point.

      The description at https://en.wikipedia.org/wiki/Introsort shows the cutover as 2X log_2(N) but our impl (IntroSorter) currently uses just log_2.

      So I tested using 2X log_2 instead, and I see a decent (~5.6%, from 98.2 sec to 92.7 sec) speedup in the time for offline sorter to sort when doing the force merge of 6.1 LatLonPoints from the London UK benchmark.

      Is there any reason not to switch? I know this means 2X the stack required, but since this is log_2 space that seems fine?

        Attachments

        1. LUCENE-7097.patch
          0.8 kB
          Michael McCandless

          Activity

            People

            • Assignee:
              mikemccand Michael McCandless
              Reporter:
              mikemccand Michael McCandless
            • Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: