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?

      1. LUCENE-7097.patch
        0.8 kB
        Michael McCandless

        Activity

        Hide
        jpountz Adrien Grand added a comment -

        If we change it to add this 2x factor then maybe we should also take the floor of the log2 instead of the ceil to be on par with the paper.

        Show
        jpountz Adrien Grand added a comment - If we change it to add this 2x factor then maybe we should also take the floor of the log2 instead of the ceil to be on par with the paper.
        Hide
        mikemccand Michael McCandless added a comment -

        Thanks Adrien Grand, that's a good idea, here's a patch using the existing MathUtil.log.

        Show
        mikemccand Michael McCandless added a comment - Thanks Adrien Grand , that's a good idea, here's a patch using the existing MathUtil.log .
        Hide
        jpountz Adrien Grand added a comment -

        +1

        Show
        jpountz Adrien Grand added a comment - +1
        Hide
        jira-bot ASF subversion and git services added a comment -

        Commit 8cbe4713775565a3194e29b90747f59fe2ffe3f1 in lucene-solr's branch refs/heads/master from Mike McCandless
        [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=8cbe471 ]

        LUCENE-7097: let IntroSorter go 2X deeper in quicksort before switching to heapsort

        Show
        jira-bot ASF subversion and git services added a comment - Commit 8cbe4713775565a3194e29b90747f59fe2ffe3f1 in lucene-solr's branch refs/heads/master from Mike McCandless [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=8cbe471 ] LUCENE-7097 : let IntroSorter go 2X deeper in quicksort before switching to heapsort
        Hide
        jira-bot ASF subversion and git services added a comment -

        Commit d1ba89959137c120be5cf116e72f43b26339cb6e in lucene-solr's branch refs/heads/branch_6x from Mike McCandless
        [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=d1ba899 ]

        LUCENE-7097: let IntroSorter go 2X deeper in quicksort before switching to heapsort

        Show
        jira-bot ASF subversion and git services added a comment - Commit d1ba89959137c120be5cf116e72f43b26339cb6e in lucene-solr's branch refs/heads/branch_6x from Mike McCandless [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=d1ba899 ] LUCENE-7097 : let IntroSorter go 2X deeper in quicksort before switching to heapsort
        Hide
        mikemccand Michael McCandless added a comment -

        Thanks Adrien Grand.

        Show
        mikemccand Michael McCandless added a comment - Thanks Adrien Grand .

          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:

              Development