Can we improve the linear scan part of skipping to possibly compile to CMOVcc?
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
@fulmicoton (Tantivy creator) reached out to me after our [fun discussion about how to tap into branchless CPU instructions (CMOVcc on x86-64)](https://markmail.org/message/rqktbp7qgzegvdti) from way up a in javaland far above the bare metal.
Because Lucene (and Tantivy) encode postings in blocks of 128 docids (+freqs) at once, when skipping, after using the skiplist to find the block that may or may not contain the target doc, there is inevitably a "within block" scan (of up to 128 docs) that is needed to find it.
@fulmicoton pointed out that the [linear scan phase of Lucene's skipping](https://t.co/kg7JZ8ICEH) could maybe be rewritten "just so" in a way that Hotspot would recognize it and would compile to CMOVcc. We could turn on "print assembly" from Hotspot to iterate until it does or does not produce CMOVcc and then measure which way is "typically" more performant.
Contributor guide
Research direction
Start by locating Lucene's linear scan phase when skipping within a 128-docid block, then review the linked discussion about branchless CPU instructions and CMOVcc. Use HotSpot assembly output to compare candidate scan forms and benchmark whether CMOVcc improves typical performance; done means a measured, justified implementation or evidence that it does not help.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- search
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100