You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "kaivalnp (via GitHub)" <gi...@apache.org> on 2026/02/11 19:22:43 UTC
[PR] Unpack nibbles in dimension order [lucene]
kaivalnp opened a new pull request, #15698:
URL: https://github.com/apache/lucene/pull/15698
### Description
Addresses #15697
Individual dimensions of 4-bit quantized vectors are stored as packed nibbles (i.e. two dimensions in a single byte).
Example: `[1 2][3 4][5 6][7 8]`
These need to be "unpacked" to perform vector comparisons. Currently, we [take the second nibble from each byte and place them 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][3][5][7][2][4][6][8]`
Sometimes, we need to compare a "packed" vector with an "unpacked" one. We [read one byte from the "packed" vector and corresponding dimensions from the "unpacked" one](https://github.com/apache/lucene/blob/448c7d8e2414eaae43b68cc398fcb3e2191b4132/lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java#L171-L182).
Because of the layout of the "unpacked" vector, it can lead to CPU cache line misses (two consecutive dimensions are apart by `dimension count / 2` bytes).
Proposing to unpack nibbles in dimension order.
Example: `[1][2][3][4][5][6][7][8]`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Unpack nibbles in dimension order [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15698:
URL: https://github.com/apache/lucene/pull/15698#issuecomment-3886817132
> this changes the on-disk format and consequently cannot be done without protections
@benwtrent I don't think we persist the "unpacked" vector in the index?
I think it's just an intermediate representation of the "packed" vector, and we only store the latter on disk (which is unchanged in this PR) -- please let me know if I'm mistaken!
> The 10.4 release is currently in progress and should only be committed to for critical bugs.
In any case, I'll hold off on merge until 10.4 is released! (and put this in 10.5)
> What CPU are you benchmarking on?
I'm using a Graviton3 host. `lscpu` says:
```
Architecture: aarch64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 64
On-line CPU(s) list: 0-63
Thread(s) per core: 1
Core(s) per socket: 64
Socket(s): 1
NUMA node(s): 1
Vendor ID: ARM
Model: 1
Stepping: r1p1
BogoMIPS: 2100.00
L1d cache: 64K
L1i cache: 64K
L2 cache: 1024K
L3 cache: 32768K
NUMA node0 CPU(s): 0-63
Flags: fp asimd evtstrm aes pmull sha1 sha2 crc32 atomics fphp asimdhp cpuid asimdrdm jscvt fcma lrcpc dcpop sha3 sm3 sm4 asimddp sha512 sve asimdfhm dit uscat ilrcpc flagm paca pacg dcpodp svei8mm svebf16 i8mm bf16 dgh rng
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Unpack nibbles in dimension order [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15698:
URL: https://github.com/apache/lucene/pull/15698#issuecomment-3886507731
JMH benchmarks using:
```
java --module-path lucene/benchmark-jmh/build/benchmarks --module org.apache.lucene.benchmark.jmh "VectorUtilBenchmark.binaryHalfByte.*SinglePacked.*" -p size=1024
```
Baseline:
```
Benchmark (size) Mode Cnt Score Error Units
VectorUtilBenchmark.binaryHalfByteDotProductSinglePackedScalar 1024 thrpt 15 2.443 ± 0.016 ops/us
VectorUtilBenchmark.binaryHalfByteDotProductSinglePackedVector 1024 thrpt 15 2.605 ± 0.010 ops/us
VectorUtilBenchmark.binaryHalfByteSquareSinglePackedScalar 1024 thrpt 15 2.020 ± 0.013 ops/us
VectorUtilBenchmark.binaryHalfByteSquareSinglePackedVector 1024 thrpt 15 2.587 ± 0.025 ops/us
```
Notice that the vector implementations don't provide a large performance improvement over the scalar ones.
Here is the JMH run of `binaryHalfByteDotProductSinglePackedVector`:
```
# Warmup Iteration 1: 11.063 ops/us
# Warmup Iteration 2: 15.398 ops/us
# Warmup Iteration 3: 2.589 ops/us
# Warmup Iteration 4: 2.586 ops/us
Iteration 1: 2.598 ops/us
Iteration 2: 2.606 ops/us
Iteration 3: 2.596 ops/us
Iteration 4: 2.602 ops/us
Iteration 5: 2.606 ops/us
```
Notice that we initially get good performance from the vectorized function, but I'm guessing it eventually gets deoptimized because of cache line misses?
Candidate:
```
Benchmark (size) Mode Cnt Score Error Units
VectorUtilBenchmark.binaryHalfByteDotProductSinglePackedScalar 1024 thrpt 15 2.079 ± 0.003 ops/us
VectorUtilBenchmark.binaryHalfByteDotProductSinglePackedVector 1024 thrpt 15 10.338 ± 0.105 ops/us
VectorUtilBenchmark.binaryHalfByteSquareSinglePackedScalar 1024 thrpt 15 2.203 ± 0.002 ops/us
VectorUtilBenchmark.binaryHalfByteSquareSinglePackedVector 1024 thrpt 15 9.979 ± 0.103 ops/us
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Unpack nibbles in dimension order [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on code in PR #15698:
URL: https://github.com/apache/lucene/pull/15698#discussion_r2795610495
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene104/OffHeapScalarQuantizedVectorValues.java:
##########
@@ -177,19 +177,19 @@ public int getVectorByteLength() {
return vectorValue.length;
}
- static void packNibbles(byte[] unpacked, byte[] packed) {
+ public static void packNibbles(byte[] unpacked, byte[] packed) {
assert unpacked.length == packed.length * 2;
for (int i = 0; i < packed.length; i++) {
- int x = unpacked[i] << 4 | unpacked[packed.length + i];
+ int x = unpacked[i * 2] << 4 | unpacked[i * 2 + 1];
packed[i] = (byte) x;
}
}
Review Comment:
Sorry, you're right -- I was under the _false_ impression that dimensions are packed one after another as:
`[1 2][3 4][5 6][7 8]`
Indeed the dimensions are packed as:
`[1 5][2 6][3 7][4 8]`
..and this would change things on disk
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Unpack nibbles in dimension order [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on PR #15698:
URL: https://github.com/apache/lucene/pull/15698#issuecomment-3887330446
> Individual dimensions of 4-bit quantized vectors are stored as packed nibbles (i.e. two dimensions in a single byte).
Example: `[1 2][3 4][5 6][7 8]`
Sorry for the confusion, I was mistaken here^ -- the "upper" half bits contain the first N/2 dimensions, and the "lower" half bits contain the next N/2 dimensions like:
`[1 5][2 6][3 7][4 8]`
However, the sudden drop in performance in the JMH benchmark still seems interesting -- but I'll pursue it separately
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Unpack nibbles in dimension order [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on code in PR #15698:
URL: https://github.com/apache/lucene/pull/15698#discussion_r2795362391
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene104/OffHeapScalarQuantizedVectorValues.java:
##########
@@ -177,19 +177,19 @@ public int getVectorByteLength() {
return vectorValue.length;
}
- static void packNibbles(byte[] unpacked, byte[] packed) {
+ public static void packNibbles(byte[] unpacked, byte[] packed) {
assert unpacked.length == packed.length * 2;
for (int i = 0; i < packed.length; i++) {
- int x = unpacked[i] << 4 | unpacked[packed.length + i];
+ int x = unpacked[i * 2] << 4 | unpacked[i * 2 + 1];
packed[i] = (byte) x;
}
}
Review Comment:
I don't understand how this doesn't change the packed bytes.
The "new" vector scorers would then assume things are in this layout (the scorer would just be loaded because of the format name). Consequently, scoring on old segments would completely break.
packing `[0-15]` ends up in completely different bytes.
Old way `byte[8] { 8, 25, 42, 59, 76, 93, 110, 127 }`
New way `byte[8] { 1, 35, 69, 103, -119, -85, -51, -17 }`
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Unpack nibbles in dimension order [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp closed pull request #15698: Unpack nibbles in dimension order
URL: https://github.com/apache/lucene/pull/15698
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Unpack nibbles in dimension order [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #15698:
URL: https://github.com/apache/lucene/pull/15698#issuecomment-3886612008
@kaivalnp this changes the on-disk format and consequently cannot be done without protections. The 10.4 release is currently in progress and should only be committed to for critical bugs.
> Notice that we initially get good performance from the vectorized function, but I'm guessing it eventually gets deoptimized because of cache line misses?
I honestly don't know if that is how things work. What CPU are you benchmarking on?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org