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

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: trunk, 6.1
• Lucene Fields: New
• Assignee: Michael McCandless
• Reporter: Michael McCandless
• Created: 11/Mar/16 15:44
• Updated: 28/Aug/22 14:52
• Resolved: 14/Mar/16 10:03

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?