apache / apache/lucene

Improve hash mixing in FST's double-barrel LRU hash

Open
#12,704 4 comments 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

Spinoff from [this cool comment](https://github.com/apache/lucene/pull/12633#discussion_r1366847986), thanks to hashing guru @bruno-roustant:

```
Instead, we should multiply with the gold constant BitMixer#PHI_C64 (make it public).
This really makes a difference in the evenness of the value distribution. This is one of the secrets of the HPPC hashing. By applying this, we get multiple advantages:

* lookup should be improved (less hash collision)
* we can try to rehash at 3/4 occupancy because the performance should not be impacted until this point.
* in case of hash collision, we can lookup linearly with a pos = pos + 1 instead of quadratic probe (lines 95 and 327); this may avoid some mem cache miss.
*
(same for the other hash method)
```

This is a simple change, we just need to test on some real FST building cases to confirm good mixing "in practice". The new `IndexToFST` tool in `luceneutil` is helpful for this.

Contributor guide

Open the contributing guide

Research direction

Locate FST's double-barrel LRU hash and the BitMixer#PHI_C64 definition, including the hash methods referenced around lines 95 and 327. Start by reviewing how the new IndexToFST tool builds real FST cases, then validate that the revised mixing produces good value distribution and does not regress lookup behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
3/5
Estimated time
1-2 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.