[jira] [Created] (LUCENE-7097) Can we increase the stack depth before Introsorter switches to heapsort?

["Michael McCandless (JIRA)" <ji...@apache.org>]

Michael McCandless created LUCENE-7097:
------------------------------------------

             Summary: Can we increase the stack depth before Introsorter switches to heapsort?
                 Key: LUCENE-7097
                 URL: https://issues.apache.org/jira/browse/LUCENE-7097
             Project: Lucene - Core
          Issue Type: Improvement
            Reporter: Michael McCandless
            Assignee: Michael McCandless
             Fix For: trunk, 6.1


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?




--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org