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: [email protected]
For additional commands, e-mail: [email protected]
