For 4-bit quantized vectors, should we change the scheme of unpacking nibbles?
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
4-bit quantized vectors are stored as nibbles, two packed in a single byte -- where the "upper" half bits in the byte contain the first `N / 2` dimensions, and the "lower" half bits contain the remaining ones.
Example: `[1 5][2 6][3 7][4 8]`
For performing individual vector computations, we "unpack" the nibbles into a `byte[]` -- [where we take the second nibble from each byte and place it at the end](https://github.com/apache/lucene/blob/448c7d8e2414eaae43b68cc398fcb3e2191b4132/lucene/core/src/java/org/apache/lucene/codecs/lucene104/OffHeapScalarQuantizedVectorValues.java#L188-L194)
Example: `[1][2][3][4][5][6][7][8]`
Now for individual dot-product computations b/w a packed and unpacked vector: we [read the first byte of the packed vector (dimensions 1, 5) and multiply individual nibbles against byte number 1 and 5 of the unpacked vector](https://github.com/apache/lucene/blob/448c7d8e2414eaae43b68cc398fcb3e2191b4132/lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java#L171-L182).
For higher dimension vectors, can this lead to CPU cache line misses?
If so, can we "unpack" the nibbles in dimension order for performance gains?
Contributor guide
Research direction
Start with OffHeapScalarQuantizedVectorValues.java and DefaultVectorUtilSupport.java, focusing on the linked unpacking and dot-product code. Measure whether the current layout causes cache-line misses for higher-dimensional vectors, then compare it with dimension-order unpacking; done means a supported performance conclusion and an agreed implementation direction.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- performance
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100