apache / apache/lucene

Can we improve the linear scan part of skipping to possibly compile to CMOVcc?

Open
#12,476 1 comment 0 reactions 0 assignees View on GitHub
type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.