[LUCENE-10196] Improve IntroSorter with 3-ways partitioning

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 8.11
• Lucene Fields: New
• Assignee: Unassigned
• Reporter: Bruno Roustant
• Created: 21/Oct/21 18:31
• Updated: 28/Aug/22 16:29
• Resolved: 01/Nov/21 15:56

Description

I added a SorterBenchmark to evaluate the performance of the various Sorter implementations depending on the strategies defined in BaseSortTestCase (random, random-low-cardinality, ascending, descending, etc).

By changing the implementation of the IntroSorter to use a 3-ways partitioning, we can gain a significant performance improvement when sorting low-cardinality lists, and with additional changes we can also improve the performance for all the strategies.

Proposed changes:

• Sort small ranges with insertion sort (instead of binary sort).
• Select the quick sort pivot with medians.
• Partition with the fast Bentley-McIlroy 3-ways partitioning algorithm.
• Replace the tail recursion by a loop.

Issue Links

• relates to: LUCENE-10225 Improve IntroSelector with 3-way partitioning
• links to: GitHub Pull Request #404