You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "benwtrent (via GitHub)" <gi...@apache.org> on 2024/04/23 14:20:36 UTC
[PR] Improve int4 compressed comparisons performance [lucene]
benwtrent opened a new pull request, #13321:
URL: https://github.com/apache/lucene/pull/13321
This updates the int4 dot-product comparison to have an optimized one for when one of the vectors are compressed (the most common search case). This change actually makes the compressed search on ARM faster than the uncompressed. However, on AVX512/256, it still slightly slower than uncompressed, but it still much faster now with this optimization than before (eagerly decompressing).
This optimized is tied tightly with how the vectors are actually compressed and stored, consequently, I added a new scorer that is within the lucene99 codec.
So, this gives us 8x reduction over float32, well more than 2x faster queries than float32, and no need to rerank as the recall and accuracy are excellent.
Here are some lucene-util numbers over CohereV3 at 1024 dimensions:
New compressed numbers on ARM
```
recall latency nDoc fanout maxConn beamWidth visited
0.891 1.02 500000 0 64 250 4182
0.910 1.05 500000 0 64 250 4348
0.925 1.06 500000 0 64 250 4511
0.974 1.29 500000 0 64 250 5782
0.986 1.72 500000 0 64 250 7285
```
Compared with uncompressed on ARM:
```
recall latency nDoc fanout maxConn beamWidth visited
0.891 1.18 500000 0 64 250 4182
0.910 1.24 500000 0 64 250 4348
0.925 1.25 500000 0 64 250 4511
0.974 1.57 500000 0 64 250 5782
0.986 2.15 500000 0 64 250 7285
```
Here are some JMH numbers as well (note, I am excluding odd number of indices as these don't support compression).
NOTE: `PackedUnpacked` is eagerly decompressing the vectors and then using dot-product, what is occurring now.
ARM:
```
VectorUtilBenchmark.binaryHalfByteScalar 128 thrpt 5 25.072 ± 0.364 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 256 thrpt 5 12.534 ± 0.152 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 300 thrpt 5 10.715 ± 0.116 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 512 thrpt 5 6.275 ± 0.019 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 702 thrpt 5 4.577 ± 0.019 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 1024 thrpt 5 3.113 ± 0.010 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 128 thrpt 5 24.161 ± 0.183 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 256 thrpt 5 12.261 ± 0.356 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 300 thrpt 5 10.535 ± 0.264 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 512 thrpt 5 6.157 ± 0.062 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 702 thrpt 5 4.505 ± 0.022 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 1024 thrpt 5 3.104 ± 0.013 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 128 thrpt 5 15.179 ± 0.307 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 256 thrpt 5 7.883 ± 0.126 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 300 thrpt 5 6.826 ± 0.014 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 512 thrpt 5 3.996 ± 0.013 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 702 thrpt 5 2.934 ± 0.010 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 1024 thrpt 5 2.008 ± 0.026 ops/us
VectorUtilBenchmark.binaryHalfByteVector 128 thrpt 5 69.386 ± 0.371 ops/us
VectorUtilBenchmark.binaryHalfByteVector 256 thrpt 5 51.016 ± 0.180 ops/us
VectorUtilBenchmark.binaryHalfByteVector 300 thrpt 5 40.186 ± 0.117 ops/us
VectorUtilBenchmark.binaryHalfByteVector 512 thrpt 5 33.453 ± 0.096 ops/us
VectorUtilBenchmark.binaryHalfByteVector 702 thrpt 5 23.627 ± 0.429 ops/us
VectorUtilBenchmark.binaryHalfByteVector 1024 thrpt 5 19.833 ± 0.065 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 128 thrpt 5 66.502 ± 0.335 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 256 thrpt 5 47.178 ± 0.546 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 300 thrpt 5 36.942 ± 0.122 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 512 thrpt 5 29.735 ± 0.328 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 702 thrpt 5 21.145 ± 0.085 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 1024 thrpt 5 17.103 ± 0.050 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 128 thrpt 5 25.077 ± 0.459 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 256 thrpt 5 15.033 ± 0.041 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 300 thrpt 5 12.681 ± 0.222 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 512 thrpt 5 8.240 ± 0.461 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 702 thrpt 5 6.034 ± 0.022 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 1024 thrpt 5 4.320 ± 0.509 ops/us
```
AVX512:
```
VectorUtilBenchmark.binaryHalfByteScalar 128 thrpt 15 17.767 ± 0.123 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 256 thrpt 15 9.248 ± 0.112 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 300 thrpt 15 8.095 ± 0.102 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 512 thrpt 15 4.723 ± 0.054 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 702 thrpt 15 3.580 ± 0.030 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 1024 thrpt 15 2.346 ± 0.047 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 128 thrpt 15 14.119 ± 0.069 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 256 thrpt 15 6.478 ± 0.037 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 300 thrpt 15 4.157 ± 0.048 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 512 thrpt 15 2.490 ± 0.017 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 702 thrpt 15 1.817 ± 0.011 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 1024 thrpt 15 1.240 ± 0.009 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 128 thrpt 15 10.022 ± 0.068 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 256 thrpt 15 5.583 ± 0.048 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 300 thrpt 15 4.667 ± 0.083 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 512 thrpt 15 2.698 ± 0.034 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 702 thrpt 15 1.931 ± 0.019 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPackedUnpacked 1024 thrpt 15 1.294 ± 0.019 ops/us
VectorUtilBenchmark.binaryHalfByteVector 128 thrpt 15 84.577 ± 2.424 ops/us
VectorUtilBenchmark.binaryHalfByteVector 207 thrpt 15 44.973 ± 0.448 ops/us
VectorUtilBenchmark.binaryHalfByteVector 256 thrpt 15 51.049 ± 0.379 ops/us
VectorUtilBenchmark.binaryHalfByteVector 300 thrpt 15 39.401 ± 0.527 ops/us
VectorUtilBenchmark.binaryHalfByteVector 512 thrpt 15 27.654 ± 0.145 ops/us
VectorUtilBenchmark.binaryHalfByteVector 702 thrpt 15 20.007 ± 0.120 ops/us
VectorUtilBenchmark.binaryHalfByteVector 1024 thrpt 15 14.378 ± 0.070 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 128 thrpt 15 58.249 ± 0.375 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 256 thrpt 15 30.865 ± 0.164 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 300 thrpt 15 22.795 ± 0.280 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 512 thrpt 15 16.406 ± 0.506 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 702 thrpt 15 9.555 ± 0.167 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 1024 thrpt 15 8.638 ± 0.095 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 128 thrpt 15 15.507 ± 0.122 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 256 thrpt 15 9.079 ± 0.068 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 300 thrpt 15 7.788 ± 0.083 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 512 thrpt 15 4.992 ± 0.064 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 702 thrpt 15 3.622 ± 0.033 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPackedUnpacked 1024 thrpt 15 2.488 ± 0.019 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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on code in PR #13321:
URL: https://github.com/apache/lucene/pull/13321#discussion_r1576351827
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99ScalarQuantizedVectorScorer.java:
##########
@@ -0,0 +1,283 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.codecs.lucene99;
+
+import static org.apache.lucene.codecs.hnsw.ScalarQuantizedVectorScorer.quantizeQuery;
+import static org.apache.lucene.util.VectorUtil.scaleMaxInnerProductScore;
+
+import java.io.IOException;
+import org.apache.lucene.codecs.hnsw.FlatVectorsScorer;
+import org.apache.lucene.index.VectorSimilarityFunction;
+import org.apache.lucene.util.VectorUtil;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
+import org.apache.lucene.util.hnsw.RandomVectorScorer;
+import org.apache.lucene.util.hnsw.RandomVectorScorerSupplier;
+import org.apache.lucene.util.quantization.RandomAccessQuantizedByteVectorValues;
+import org.apache.lucene.util.quantization.ScalarQuantizer;
+
+/**
+ * Optimized scalar quantized implementation of {@link FlatVectorsScorer} for quantized vectors
+ * stored in the Lucene99 format.
+ *
+ * @lucene.experimental
+ */
+public class Lucene99ScalarQuantizedVectorScorer implements FlatVectorsScorer {
Review Comment:
I have to write up some tests for this still.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2079695750
OK, I ran on Google's ARM machine (`Tau T2A machine series`) to make sure the ARM performance improvements still exist for int4 (and it wasn't some silly macos thing):
```
Benchmark (size) Mode Cnt Score Error Units
VectorUtilBenchmark.binaryDotProductScalar 1024 thrpt 15 2.850 ± 0.002 ops/us
VectorUtilBenchmark.binaryDotProductVector 1024 thrpt 15 2.771 ± 0.016 ops/us
VectorUtilBenchmark.binaryHalfByteScalar 1024 thrpt 15 2.845 ± 0.009 ops/us
VectorUtilBenchmark.binaryHalfByteScalarPacked 1024 thrpt 15 2.128 ± 0.003 ops/us
VectorUtilBenchmark.binaryHalfByteVector 1024 thrpt 15 7.667 ± 0.007 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 1024 thrpt 15 7.009 ± 0.025 ops/us
```
Something else funny is that this is almost at the same speed as `floatVector` on this hardware.
Micro-benchmarks are VERY close to float. This means the reduction in bytes read & parsing will make int4 much faster than float.
```
Benchmark (size) Mode Cnt Score Error Units
VectorUtilBenchmark.floatDotProductScalar 1024 thrpt 15 2.476 ± 0.028 ops/us
VectorUtilBenchmark.floatDotProductVector 1024 thrpt 75 8.703 ± 0.300 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] Improve int4 compressed comparisons performance [lucene]
Posted by "rmuir (via GitHub)" <gi...@apache.org>.
rmuir commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2078163094
panama logic looks good to me. Not for this PR, just a question, is it possible to use this same trick for 8 bit integer calculations too? I imagine this trick could probably help there as well, if it is safe.
> // iterate in chunks of 1024 items to ensure we don't overflow the short accumulator
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2079578770
> panama logic looks good to me. Not for this PR, just a question, is it possible to use this same trick for 8 bit integer calculations too? I imagine this trick could probably help there as well, if it is safe.
Some napkin math (this would need to be double checked...)
For `int4`, the max dot-product value is just `15*15=225`, which means we can fit 290 summations in a short (with saturation) and 145 without saturation (since 1024 is Lucene's max vector length, I went without saturation).
For `int8`, the max dot-product (since we are signed) is `-128*-128=16384`. Which saturates a `short` with 2 values, `16384 * 2 = 32768 = Short.MAX_VALUE + 1`. So, since its already saturating at 2 values, 3 values might as well be summed (4 "double saturates?" I don't know the correct term, but 4 loops over again and thus won't work).
128 bitwidth fits 8 shorts.
In `int4` this means it sum up 1160 dimensions (each lane only summing `1160/8=145` multiplications) without saturation. Well within the 1024 limit.
In `int8`, this is reduced significantly to 24 dimensions (each lane summing 3 multiplications with saturation). While this small, it could reduce the number of vector lane expansions due to type sizes and java type casting, but the overhead of accounting for the saturation of shorts when expanding to integers could slow things down.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2088378164
@uschindler I addressed your comments.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on code in PR #13321:
URL: https://github.com/apache/lucene/pull/13321#discussion_r1579422728
##########
lucene/core/src/java/org/apache/lucene/util/VectorUtil.java:
##########
@@ -179,7 +179,30 @@ public static int int4DotProduct(byte[] a, byte[] b) {
if (a.length != b.length) {
throw new IllegalArgumentException("vector dimensions differ: " + a.length + "!=" + b.length);
}
- return IMPL.int4DotProduct(a, b);
+ return IMPL.int4DotProduct(a, false, b, false);
+ }
+
+ /**
+ * Dot product computed over int4 (values between [0,15]) bytes. The second vector is considered
+ * "packed" (i.e. every two bytes represent a single value). The following packing is assumed:
Review Comment:
Yep.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on code in PR #13321:
URL: https://github.com/apache/lucene/pull/13321#discussion_r1582893750
##########
lucene/core/src/java21/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -390,22 +392,202 @@ private int dotProductBody128(byte[] a, byte[] b, int limit) {
}
@Override
- public int int4DotProduct(byte[] a, byte[] b) {
+ public int int4DotProduct(byte[] a, boolean apacked, byte[] b, boolean bpacked) {
+ assert (apacked && bpacked) == false;
int i = 0;
int res = 0;
- if (VECTOR_BITSIZE >= 512 || VECTOR_BITSIZE == 256) {
- return dotProduct(a, b);
- } else if (a.length >= 32 && HAS_FAST_INTEGER_VECTORS) {
- i += ByteVector.SPECIES_128.loopBound(a.length);
- res += int4DotProductBody128(a, b, i);
- }
- // scalar tail
- for (; i < a.length; i++) {
- res += b[i] * a[i];
+ if (apacked || bpacked) {
+ byte[] packed = apacked ? a : b;
+ byte[] unpacked = apacked ? b : a;
+ if (packed.length >= 32) {
+ if (VECTOR_BITSIZE >= 512) {
+ i += ByteVector.SPECIES_256.loopBound(packed.length);
+ res += dotProductBody512Int4Packed(unpacked, packed, i);
+ } else if (VECTOR_BITSIZE == 256) {
+ i += ByteVector.SPECIES_128.loopBound(packed.length);
+ res += dotProductBody256Int4Packed(unpacked, packed, i);
+ } else if (HAS_FAST_INTEGER_VECTORS) {
+ i += ByteVector.SPECIES_64.loopBound(packed.length);
+ res += dotProductBody128Int4Packed(unpacked, packed, i);
+ }
+ }
+ // scalar tail
+ for (; i < packed.length; i++) {
+ byte packedByte = packed[i];
+ byte unpacked1 = unpacked[i];
+ byte unpacked2 = unpacked[i + packed.length];
+ res += (packedByte & 0x0F) * unpacked2;
+ res += ((packedByte & 0xFF) >> 4) * unpacked1;
+ }
+ } else {
+ if (VECTOR_BITSIZE >= 512 || VECTOR_BITSIZE == 256) {
+ return dotProduct(a, b);
+ } else if (a.length >= 32 && HAS_FAST_INTEGER_VECTORS) {
+ i += ByteVector.SPECIES_128.loopBound(a.length);
+ res += int4DotProductBody128(a, b, i);
+ }
+ // scalar tail
+ for (; i < a.length; i++) {
+ res += b[i] * a[i];
+ }
}
+
return res;
}
+ private int dotProductBody512Int4Packed(byte[] unpacked, byte[] packed, int limit) {
+ int sum = 0;
+ // iterate in chunks of 1024 items to ensure we don't overflow the short accumulator
+ for (int i = 0; i < limit; i += 4096) {
+ ShortVector acc0 = ShortVector.zero(ShortVector.SPECIES_512);
+ ShortVector acc1 = ShortVector.zero(ShortVector.SPECIES_512);
+ int innerLimit = Math.min(limit - i, 4096);
+ for (int j = 0; j < innerLimit; j += ByteVector.SPECIES_256.length()) {
+ // packed
+ var vb8 = ByteVector.fromArray(ByteVector.SPECIES_256, packed, i + j);
+ // unpacked
+ var va8 = ByteVector.fromArray(ByteVector.SPECIES_256, unpacked, i + j + packed.length);
+
+ // upper
+ ByteVector prod8 = vb8.and((byte) 0x0F).mul(va8);
+ Vector<Short> prod16 = prod8.convertShape(ZERO_EXTEND_B2S, ShortVector.SPECIES_512, 0);
+ acc0 = acc0.add(prod16);
+
+ // lower
+ ByteVector vc8 = ByteVector.fromArray(ByteVector.SPECIES_256, unpacked, i + j);
+ ByteVector prod8a = vb8.lanewise(LSHR, 4).mul(vc8);
+ Vector<Short> prod16a = prod8a.convertShape(ZERO_EXTEND_B2S, ShortVector.SPECIES_512, 0);
+ acc1 = acc1.add(prod16a);
+ }
+ IntVector intAcc0 = acc0.convertShape(S2I, IntVector.SPECIES_512, 0).reinterpretAsInts();
+ IntVector intAcc1 = acc0.convertShape(S2I, IntVector.SPECIES_512, 1).reinterpretAsInts();
+ IntVector intAcc2 = acc1.convertShape(S2I, IntVector.SPECIES_512, 0).reinterpretAsInts();
+ IntVector intAcc3 = acc1.convertShape(S2I, IntVector.SPECIES_512, 1).reinterpretAsInts();
+ sum += intAcc0.add(intAcc1).add(intAcc2).add(intAcc3).reduceLanes(ADD);
+ }
+ return sum;
+ }
+
+ private int dotProductBody256Int4Packed(byte[] unpacked, byte[] packed, int limit) {
+ int sum = 0;
+ // iterate in chunks of 1024 items to ensure we don't overflow the short accumulator
+ for (int i = 0; i < limit; i += 2048) {
+ ShortVector acc0 = ShortVector.zero(ShortVector.SPECIES_256);
+ ShortVector acc1 = ShortVector.zero(ShortVector.SPECIES_256);
+ int innerLimit = Math.min(limit - i, 2048);
+ for (int j = 0; j < innerLimit; j += ByteVector.SPECIES_128.length()) {
+ // packed
+ var vb8 = ByteVector.fromArray(ByteVector.SPECIES_128, packed, i + j);
+ // unpacked
+ var va8 = ByteVector.fromArray(ByteVector.SPECIES_128, unpacked, i + j + packed.length);
+
+ // upper
+ ByteVector prod8 = vb8.and((byte) 0x0F).mul(va8);
+ Vector<Short> prod16 = prod8.convertShape(ZERO_EXTEND_B2S, ShortVector.SPECIES_256, 0);
+ acc0 = acc0.add(prod16);
+
+ // lower
+ ByteVector vc8 = ByteVector.fromArray(ByteVector.SPECIES_128, unpacked, i + j);
+ ByteVector prod8a = vb8.lanewise(LSHR, 4).mul(vc8);
+ Vector<Short> prod16a = prod8a.convertShape(ZERO_EXTEND_B2S, ShortVector.SPECIES_256, 0);
+ acc1 = acc1.add(prod16a);
+ }
+ IntVector intAcc0 = acc0.convertShape(S2I, IntVector.SPECIES_256, 0).reinterpretAsInts();
+ IntVector intAcc1 = acc0.convertShape(S2I, IntVector.SPECIES_256, 1).reinterpretAsInts();
+ IntVector intAcc2 = acc1.convertShape(S2I, IntVector.SPECIES_256, 0).reinterpretAsInts();
+ IntVector intAcc3 = acc1.convertShape(S2I, IntVector.SPECIES_256, 1).reinterpretAsInts();
+ sum += intAcc0.add(intAcc1).add(intAcc2).add(intAcc3).reduceLanes(ADD);
+ }
+ return sum;
+ }
+
+ /** vectorized dot product body (128 bit vectors) */
+ private int dotProductBody128Int4Packed(byte[] unpacked, byte[] packed, int limit) {
+ int sum = 0;
+ // iterate in chunks of 1024 items to ensure we don't overflow the short accumulator
+ for (int i = 0; i < limit; i += 1024) {
+ ShortVector acc0 = ShortVector.zero(ShortVector.SPECIES_128);
+ ShortVector acc1 = ShortVector.zero(ShortVector.SPECIES_128);
+ int innerLimit = Math.min(limit - i, 1024);
+ for (int j = 0; j < innerLimit; j += ByteVector.SPECIES_64.length()) {
+ // packed
+ ByteVector vb8 = ByteVector.fromArray(ByteVector.SPECIES_64, packed, i + j);
+ // unpacked
+ ByteVector va8 =
+ ByteVector.fromArray(ByteVector.SPECIES_64, unpacked, i + j + packed.length);
+
+ // upper
+ ByteVector prod8 = vb8.and((byte) 0x0F).mul(va8);
+ ShortVector prod16 =
+ prod8.convertShape(B2S, ShortVector.SPECIES_128, 0).reinterpretAsShorts();
+ acc0 = acc0.add(prod16.and((short) 0xFF));
+
+ // lower
+ va8 = ByteVector.fromArray(ByteVector.SPECIES_64, unpacked, i + j);
+ prod8 = vb8.lanewise(LSHR, 4).mul(va8);
+ prod16 = prod8.convertShape(B2S, ShortVector.SPECIES_128, 0).reinterpretAsShorts();
+ acc1 = acc1.add(prod16.and((short) 0xFF));
+ }
+ IntVector intAcc0 = acc0.convertShape(S2I, IntVector.SPECIES_128, 0).reinterpretAsInts();
+ IntVector intAcc1 = acc0.convertShape(S2I, IntVector.SPECIES_128, 1).reinterpretAsInts();
+ IntVector intAcc2 = acc1.convertShape(S2I, IntVector.SPECIES_128, 0).reinterpretAsInts();
+ IntVector intAcc3 = acc1.convertShape(S2I, IntVector.SPECIES_128, 1).reinterpretAsInts();
+ sum += intAcc0.add(intAcc1).add(intAcc2).add(intAcc3).reduceLanes(ADD);
+ }
+ return sum;
+ }
+
+ private int dotProductBody512Packed(byte[] unpacked, byte[] packed, int limit) {
+ IntVector acc = IntVector.zero(INT_SPECIES);
+ for (int i = 0; i < limit; i += BYTE_SPECIES.length()) {
+ ByteVector va8 = ByteVector.fromArray(BYTE_SPECIES, unpacked, i);
+ ByteVector vb8 = ByteVector.fromArray(BYTE_SPECIES, packed, i);
+
+ // 16-bit multiply: avoid AVX-512 heavy multiply on zmm
+ Vector<Short> va16 = va8.convertShape(B2S, SHORT_SPECIES, 0);
+ Vector<Short> vb16 = vb8.lanewise(LSHR, 4).convertShape(B2S, SHORT_SPECIES, 0);
+ Vector<Short> prod16 = va16.mul(vb16);
+
+ // 32-bit add
+ Vector<Integer> prod32 = prod16.convertShape(S2I, INT_SPECIES, 0);
+ acc = acc.add(prod32);
+
+ va8 = ByteVector.fromArray(BYTE_SPECIES, unpacked, i + packed.length);
+ va16 = va8.convertShape(B2S, SHORT_SPECIES, 0);
+ vb16 = vb8.and((byte) 0x0F).convertShape(B2S, SHORT_SPECIES, 0);
+ prod16 = va16.mul(vb16);
+ prod32 = prod16.convertShape(S2I, INT_SPECIES, 0);
+ acc = acc.add(prod32);
+ }
+ // reduce
+ return acc.reduceLanes(ADD);
+ }
+
+ private int dotProductBody256Packed(byte[] unpacked, byte[] packed, int limit) {
Review Comment:
Same as above, now unused.
##########
lucene/core/src/java21/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -390,22 +392,202 @@ private int dotProductBody128(byte[] a, byte[] b, int limit) {
}
@Override
- public int int4DotProduct(byte[] a, byte[] b) {
+ public int int4DotProduct(byte[] a, boolean apacked, byte[] b, boolean bpacked) {
+ assert (apacked && bpacked) == false;
int i = 0;
int res = 0;
- if (VECTOR_BITSIZE >= 512 || VECTOR_BITSIZE == 256) {
- return dotProduct(a, b);
- } else if (a.length >= 32 && HAS_FAST_INTEGER_VECTORS) {
- i += ByteVector.SPECIES_128.loopBound(a.length);
- res += int4DotProductBody128(a, b, i);
- }
- // scalar tail
- for (; i < a.length; i++) {
- res += b[i] * a[i];
+ if (apacked || bpacked) {
+ byte[] packed = apacked ? a : b;
+ byte[] unpacked = apacked ? b : a;
+ if (packed.length >= 32) {
+ if (VECTOR_BITSIZE >= 512) {
+ i += ByteVector.SPECIES_256.loopBound(packed.length);
+ res += dotProductBody512Int4Packed(unpacked, packed, i);
+ } else if (VECTOR_BITSIZE == 256) {
+ i += ByteVector.SPECIES_128.loopBound(packed.length);
+ res += dotProductBody256Int4Packed(unpacked, packed, i);
+ } else if (HAS_FAST_INTEGER_VECTORS) {
+ i += ByteVector.SPECIES_64.loopBound(packed.length);
+ res += dotProductBody128Int4Packed(unpacked, packed, i);
+ }
+ }
+ // scalar tail
+ for (; i < packed.length; i++) {
+ byte packedByte = packed[i];
+ byte unpacked1 = unpacked[i];
+ byte unpacked2 = unpacked[i + packed.length];
+ res += (packedByte & 0x0F) * unpacked2;
+ res += ((packedByte & 0xFF) >> 4) * unpacked1;
+ }
+ } else {
+ if (VECTOR_BITSIZE >= 512 || VECTOR_BITSIZE == 256) {
+ return dotProduct(a, b);
+ } else if (a.length >= 32 && HAS_FAST_INTEGER_VECTORS) {
+ i += ByteVector.SPECIES_128.loopBound(a.length);
+ res += int4DotProductBody128(a, b, i);
+ }
+ // scalar tail
+ for (; i < a.length; i++) {
+ res += b[i] * a[i];
+ }
}
+
return res;
}
+ private int dotProductBody512Int4Packed(byte[] unpacked, byte[] packed, int limit) {
+ int sum = 0;
+ // iterate in chunks of 1024 items to ensure we don't overflow the short accumulator
+ for (int i = 0; i < limit; i += 4096) {
+ ShortVector acc0 = ShortVector.zero(ShortVector.SPECIES_512);
+ ShortVector acc1 = ShortVector.zero(ShortVector.SPECIES_512);
+ int innerLimit = Math.min(limit - i, 4096);
+ for (int j = 0; j < innerLimit; j += ByteVector.SPECIES_256.length()) {
+ // packed
+ var vb8 = ByteVector.fromArray(ByteVector.SPECIES_256, packed, i + j);
+ // unpacked
+ var va8 = ByteVector.fromArray(ByteVector.SPECIES_256, unpacked, i + j + packed.length);
+
+ // upper
+ ByteVector prod8 = vb8.and((byte) 0x0F).mul(va8);
+ Vector<Short> prod16 = prod8.convertShape(ZERO_EXTEND_B2S, ShortVector.SPECIES_512, 0);
+ acc0 = acc0.add(prod16);
+
+ // lower
+ ByteVector vc8 = ByteVector.fromArray(ByteVector.SPECIES_256, unpacked, i + j);
+ ByteVector prod8a = vb8.lanewise(LSHR, 4).mul(vc8);
+ Vector<Short> prod16a = prod8a.convertShape(ZERO_EXTEND_B2S, ShortVector.SPECIES_512, 0);
+ acc1 = acc1.add(prod16a);
+ }
+ IntVector intAcc0 = acc0.convertShape(S2I, IntVector.SPECIES_512, 0).reinterpretAsInts();
+ IntVector intAcc1 = acc0.convertShape(S2I, IntVector.SPECIES_512, 1).reinterpretAsInts();
+ IntVector intAcc2 = acc1.convertShape(S2I, IntVector.SPECIES_512, 0).reinterpretAsInts();
+ IntVector intAcc3 = acc1.convertShape(S2I, IntVector.SPECIES_512, 1).reinterpretAsInts();
+ sum += intAcc0.add(intAcc1).add(intAcc2).add(intAcc3).reduceLanes(ADD);
+ }
+ return sum;
+ }
+
+ private int dotProductBody256Int4Packed(byte[] unpacked, byte[] packed, int limit) {
+ int sum = 0;
+ // iterate in chunks of 1024 items to ensure we don't overflow the short accumulator
+ for (int i = 0; i < limit; i += 2048) {
+ ShortVector acc0 = ShortVector.zero(ShortVector.SPECIES_256);
+ ShortVector acc1 = ShortVector.zero(ShortVector.SPECIES_256);
+ int innerLimit = Math.min(limit - i, 2048);
+ for (int j = 0; j < innerLimit; j += ByteVector.SPECIES_128.length()) {
+ // packed
+ var vb8 = ByteVector.fromArray(ByteVector.SPECIES_128, packed, i + j);
+ // unpacked
+ var va8 = ByteVector.fromArray(ByteVector.SPECIES_128, unpacked, i + j + packed.length);
+
+ // upper
+ ByteVector prod8 = vb8.and((byte) 0x0F).mul(va8);
+ Vector<Short> prod16 = prod8.convertShape(ZERO_EXTEND_B2S, ShortVector.SPECIES_256, 0);
+ acc0 = acc0.add(prod16);
+
+ // lower
+ ByteVector vc8 = ByteVector.fromArray(ByteVector.SPECIES_128, unpacked, i + j);
+ ByteVector prod8a = vb8.lanewise(LSHR, 4).mul(vc8);
+ Vector<Short> prod16a = prod8a.convertShape(ZERO_EXTEND_B2S, ShortVector.SPECIES_256, 0);
+ acc1 = acc1.add(prod16a);
+ }
+ IntVector intAcc0 = acc0.convertShape(S2I, IntVector.SPECIES_256, 0).reinterpretAsInts();
+ IntVector intAcc1 = acc0.convertShape(S2I, IntVector.SPECIES_256, 1).reinterpretAsInts();
+ IntVector intAcc2 = acc1.convertShape(S2I, IntVector.SPECIES_256, 0).reinterpretAsInts();
+ IntVector intAcc3 = acc1.convertShape(S2I, IntVector.SPECIES_256, 1).reinterpretAsInts();
+ sum += intAcc0.add(intAcc1).add(intAcc2).add(intAcc3).reduceLanes(ADD);
+ }
+ return sum;
+ }
+
+ /** vectorized dot product body (128 bit vectors) */
+ private int dotProductBody128Int4Packed(byte[] unpacked, byte[] packed, int limit) {
+ int sum = 0;
+ // iterate in chunks of 1024 items to ensure we don't overflow the short accumulator
+ for (int i = 0; i < limit; i += 1024) {
+ ShortVector acc0 = ShortVector.zero(ShortVector.SPECIES_128);
+ ShortVector acc1 = ShortVector.zero(ShortVector.SPECIES_128);
+ int innerLimit = Math.min(limit - i, 1024);
+ for (int j = 0; j < innerLimit; j += ByteVector.SPECIES_64.length()) {
+ // packed
+ ByteVector vb8 = ByteVector.fromArray(ByteVector.SPECIES_64, packed, i + j);
+ // unpacked
+ ByteVector va8 =
+ ByteVector.fromArray(ByteVector.SPECIES_64, unpacked, i + j + packed.length);
+
+ // upper
+ ByteVector prod8 = vb8.and((byte) 0x0F).mul(va8);
+ ShortVector prod16 =
+ prod8.convertShape(B2S, ShortVector.SPECIES_128, 0).reinterpretAsShorts();
+ acc0 = acc0.add(prod16.and((short) 0xFF));
+
+ // lower
+ va8 = ByteVector.fromArray(ByteVector.SPECIES_64, unpacked, i + j);
+ prod8 = vb8.lanewise(LSHR, 4).mul(va8);
+ prod16 = prod8.convertShape(B2S, ShortVector.SPECIES_128, 0).reinterpretAsShorts();
+ acc1 = acc1.add(prod16.and((short) 0xFF));
+ }
+ IntVector intAcc0 = acc0.convertShape(S2I, IntVector.SPECIES_128, 0).reinterpretAsInts();
+ IntVector intAcc1 = acc0.convertShape(S2I, IntVector.SPECIES_128, 1).reinterpretAsInts();
+ IntVector intAcc2 = acc1.convertShape(S2I, IntVector.SPECIES_128, 0).reinterpretAsInts();
+ IntVector intAcc3 = acc1.convertShape(S2I, IntVector.SPECIES_128, 1).reinterpretAsInts();
+ sum += intAcc0.add(intAcc1).add(intAcc2).add(intAcc3).reduceLanes(ADD);
+ }
+ return sum;
+ }
+
+ private int dotProductBody512Packed(byte[] unpacked, byte[] packed, int limit) {
Review Comment:
This is currently unused, I didn't remove it, in case @benwtrent wanted it for something else. If not, then it can be removed.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2088443326
To me changes look fine.
For discussion: In my opinion the conditional code falling back to defaults should possibly be moved to the VectorUtil class and i think them the booleans could be removed and we only have two variants directly called from VectorUtil.
Uwe
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on code in PR #13321:
URL: https://github.com/apache/lucene/pull/13321#discussion_r1581482527
##########
lucene/core/src/java21/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -390,22 +391,139 @@ private int dotProductBody128(byte[] a, byte[] b, int limit) {
}
@Override
- public int int4DotProduct(byte[] a, byte[] b) {
+ public int int4DotProduct(byte[] a, boolean apacked, byte[] b, boolean bpacked) {
+ if (apacked && bpacked) {
Review Comment:
AH! Good point @uschindler . I will adjust since these are internal.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2082304493
> In int8, this is reduced significantly to 24 dimensions (each lane summing 3 multiplications with saturation). While this small, it could reduce the number of vector lane expansions due to type sizes and java type casting, but the overhead of accounting for the saturation of shorts when expanding to integers could slow things down.
This is a great optimisation for int4, but won't work for int8.
We can get a bit more perf out of int4 on AVX 2 and AVX 512, by applying a similar same pattern.
AVX 256
A maximum of 2320 dimensions - each lane summing 2320/16=145 multiplications. Let's set an inner loop bound of 2048.
before
```
Benchmark (size) Mode Cnt Score Error Units
VectorUtilBenchmark.binaryHalfByteVectorPacked 1024 thrpt 15 9.715 ± 0.021 ops/us
```
after
```
Benchmark (size) Mode Cnt Score Error Units
VectorUtilBenchmark.binaryHalfByteVectorPacked 1024 thrpt 15 12.190 ± 0.029 ops/us
```
AVX 512
A maximum of 4640 dimensions - each lane summing 4640/32=145 multiplications. Let's set an inner loop bound of 4096.
before
```
Benchmark (size) Mode Cnt Score Error Units
VectorUtilBenchmark.binaryHalfByteVectorPacked 1024 thrpt 15 12.506 ± 0.064 ops/us
```
after
```
Benchmark (size) Mode Cnt Score Error Units
VectorUtilBenchmark.binaryHalfByteVectorPacked 1024 thrpt 15 14.235 ± 0.043 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] Improve int4 compressed comparisons performance [lucene]
Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2077675140
> Because this makes things measurably slower. ..
Ok. That's a very good reason! ;-)
> And I am not sure how it makes the comparisons easier. We then have to add LoC to decompress both and then compare both. The iteration code, etc. all remains the same.
Right. It's just that the masking and shifting would apply equally to each of the inputs. And we'd load less data - since the number of bytes in the query would be less. I'm perfectly ok with the code as it is, I was mainly ensuring that such was considered (which is was).
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on code in PR #13321:
URL: https://github.com/apache/lucene/pull/13321#discussion_r1577962121
##########
lucene/core/src/test/org/apache/lucene/codecs/lucene99/TestLucene99ScalarQuantizedVectorScorer.java:
##########
@@ -0,0 +1,145 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import org.apache.lucene.codecs.Codec;
+import org.apache.lucene.codecs.KnnVectorsFormat;
+import org.apache.lucene.codecs.KnnVectorsReader;
+import org.apache.lucene.codecs.hnsw.DefaultFlatVectorScorer;
+import org.apache.lucene.codecs.perfield.PerFieldKnnVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.VectorSimilarityFunction;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.util.VectorUtil;
+import org.apache.lucene.util.hnsw.RandomVectorScorer;
+
+public class TestLucene99ScalarQuantizedVectorScorer extends LuceneTestCase {
+
+ private static Codec getCodec(int bits, boolean compress) {
+ return new Lucene99Codec() {
+ @Override
+ public KnnVectorsFormat getKnnVectorsFormatForField(String field) {
+ return new Lucene99HnswScalarQuantizedVectorsFormat(
+ Lucene99HnswVectorsFormat.DEFAULT_MAX_CONN,
+ Lucene99HnswVectorsFormat.DEFAULT_BEAM_WIDTH,
+ 1,
+ bits,
+ compress,
+ null,
+ null);
+ }
+ };
+ }
+
+ public void testScoringCompressedInt4() throws Exception {
+ vectorScoringTest(4, true);
+ }
+
+ public void testScoringUncompressedInt4() throws Exception {
+ vectorScoringTest(4, false);
+ }
+
+ public void testScoringInt7() throws Exception {
+ vectorScoringTest(7, random().nextBoolean());
+ }
+
+ private void vectorScoringTest(int bits, boolean compress) throws IOException {
+ float[][] storedVectors = new float[10][];
+ int numVectors = 10;
+ for (int i = 0; i < numVectors; i++) {
+ float[] vector = new float[] {i, i + 1, i + 2, i + 3};
Review Comment:
Compression doesn't allow odd-sized vectors. It will throw on trying to index. But I can add odd-sized test for things that aren't compressed.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on code in PR #13321:
URL: https://github.com/apache/lucene/pull/13321#discussion_r1579117412
##########
lucene/core/src/java/org/apache/lucene/util/VectorUtil.java:
##########
@@ -179,7 +179,30 @@ public static int int4DotProduct(byte[] a, byte[] b) {
if (a.length != b.length) {
throw new IllegalArgumentException("vector dimensions differ: " + a.length + "!=" + b.length);
}
- return IMPL.int4DotProduct(a, b);
+ return IMPL.int4DotProduct(a, false, b, false);
+ }
+
+ /**
+ * Dot product computed over int4 (values between [0,15]) bytes. The second vector is considered
+ * "packed" (i.e. every two bytes represent a single value). The following packing is assumed:
Review Comment:
is this not "every byte represents two values" ?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene99/Lucene99ScalarQuantizedVectorScorer.java:
##########
@@ -0,0 +1,283 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.codecs.lucene99;
+
+import static org.apache.lucene.codecs.hnsw.ScalarQuantizedVectorScorer.quantizeQuery;
+import static org.apache.lucene.util.VectorUtil.scaleMaxInnerProductScore;
+
+import java.io.IOException;
+import org.apache.lucene.codecs.hnsw.FlatVectorsScorer;
+import org.apache.lucene.index.VectorSimilarityFunction;
+import org.apache.lucene.util.VectorUtil;
+import org.apache.lucene.util.hnsw.RandomAccessVectorValues;
+import org.apache.lucene.util.hnsw.RandomVectorScorer;
+import org.apache.lucene.util.hnsw.RandomVectorScorerSupplier;
+import org.apache.lucene.util.quantization.RandomAccessQuantizedByteVectorValues;
+import org.apache.lucene.util.quantization.ScalarQuantizer;
+
+/**
+ * Optimized scalar quantized implementation of {@link FlatVectorsScorer} for quantized vectors
+ * stored in the Lucene99 format.
+ *
+ * @lucene.experimental
+ */
+public class Lucene99ScalarQuantizedVectorScorer implements FlatVectorsScorer {
+
+ private final FlatVectorsScorer nonQuantizedDelegate;
+
+ public Lucene99ScalarQuantizedVectorScorer(FlatVectorsScorer flatVectorsScorer) {
+ nonQuantizedDelegate = flatVectorsScorer;
+ }
+
+ @Override
+ public RandomVectorScorerSupplier getRandomVectorScorerSupplier(
+ VectorSimilarityFunction similarityFunction, RandomAccessVectorValues vectorValues)
+ throws IOException {
+ if (vectorValues instanceof RandomAccessQuantizedByteVectorValues quantizedByteVectorValues) {
+ return new ScalarQuantizedRandomVectorScorerSupplier(
+ quantizedByteVectorValues, similarityFunction);
+ }
+ // It is possible to get to this branch during initial indexing and flush
+ return nonQuantizedDelegate.getRandomVectorScorerSupplier(similarityFunction, vectorValues);
+ }
+
+ @Override
+ public RandomVectorScorer getRandomVectorScorer(
+ VectorSimilarityFunction similarityFunction,
+ RandomAccessVectorValues vectorValues,
+ float[] target)
+ throws IOException {
+ if (vectorValues instanceof RandomAccessQuantizedByteVectorValues quantizedByteVectorValues) {
+ ScalarQuantizer scalarQuantizer = quantizedByteVectorValues.getScalarQuantizer();
+ byte[] targetBytes = new byte[target.length];
+ float offsetCorrection =
+ quantizeQuery(target, targetBytes, similarityFunction, scalarQuantizer);
+ return fromVectorSimilarity(
+ targetBytes,
+ offsetCorrection,
+ similarityFunction,
+ scalarQuantizer.getConstantMultiplier(),
+ quantizedByteVectorValues);
+ }
+ // It is possible to get to this branch during initial indexing and flush
+ return nonQuantizedDelegate.getRandomVectorScorer(similarityFunction, vectorValues, target);
+ }
+
+ @Override
+ public RandomVectorScorer getRandomVectorScorer(
+ VectorSimilarityFunction similarityFunction,
+ RandomAccessVectorValues vectorValues,
+ byte[] target)
+ throws IOException {
+ return nonQuantizedDelegate.getRandomVectorScorer(similarityFunction, vectorValues, target);
+ }
+
+ @Override
+ public String toString() {
+ return "ScalarQuantizedVectorScorer(" + "nonQuantizedDelegate=" + nonQuantizedDelegate + ')';
+ }
+
+ static RandomVectorScorer fromVectorSimilarity(
+ byte[] targetBytes,
+ float offsetCorrection,
+ VectorSimilarityFunction sim,
+ float constMultiplier,
+ RandomAccessQuantizedByteVectorValues values) {
+ return switch (sim) {
+ case EUCLIDEAN -> new Euclidean(values, constMultiplier, targetBytes);
+ case COSINE, DOT_PRODUCT -> new DotProduct(
+ values, constMultiplier, targetBytes, offsetCorrection);
+ case MAXIMUM_INNER_PRODUCT -> new MaximumInnerProduct(
+ values, constMultiplier, targetBytes, offsetCorrection);
+ };
+ }
+
+ private static class Euclidean extends RandomVectorScorer.AbstractRandomVectorScorer {
+ private final float constMultiplier;
+ private final byte[] targetBytes;
+ private final RandomAccessQuantizedByteVectorValues values;
+
+ private Euclidean(
+ RandomAccessQuantizedByteVectorValues values, float constMultiplier, byte[] targetBytes) {
+ super(values);
+ this.values = values;
+ this.constMultiplier = constMultiplier;
+ this.targetBytes = targetBytes;
+ }
+
+ @Override
+ public float score(int node) throws IOException {
+ byte[] nodeVector = values.vectorValue(node);
+ int squareDistance = VectorUtil.squareDistance(nodeVector, targetBytes);
+ float adjustedDistance = squareDistance * constMultiplier;
+ return 1 / (1f + adjustedDistance);
+ }
+ }
+
+ /** Calculates dot product on quantized vectors, applying the appropriate corrections */
+ private static class DotProduct extends RandomVectorScorer.AbstractRandomVectorScorer {
+ private final float constMultiplier;
+ private final RandomAccessQuantizedByteVectorValues values;
+ private final byte[] compressedVector;
+ private final byte[] targetBytes;
+ private final float offsetCorrection;
+
+ public DotProduct(
+ RandomAccessQuantizedByteVectorValues values,
+ float constMultiplier,
+ byte[] targetBytes,
+ float offsetCorrection) {
+ super(values);
+ this.constMultiplier = constMultiplier;
+ this.values = values;
+ if (values.getScalarQuantizer().getBits() <= 4
+ && values.getVectorByteLength() != values.dimension()
+ && values.getSlice() != null) {
+ this.compressedVector = new byte[values.getVectorByteLength()];
+ } else {
+ this.compressedVector = null;
+ }
+ this.targetBytes = targetBytes;
+ this.offsetCorrection = offsetCorrection;
+ }
+
+ @Override
+ public float score(int vectorOrdinal) throws IOException {
+ float adjustedDistance =
+ optimizedDotProduct(
+ targetBytes,
+ offsetCorrection,
+ vectorOrdinal,
+ values,
+ compressedVector,
+ constMultiplier);
+ return (1 + adjustedDistance) / 2;
+ }
+ }
+
+ /** Calculates max inner product on quantized vectors, applying the appropriate corrections */
+ private static class MaximumInnerProduct extends RandomVectorScorer.AbstractRandomVectorScorer {
+ private final float constMultiplier;
+ private final RandomAccessQuantizedByteVectorValues values;
+ private final byte[] compressedVector;
+ private final byte[] targetBytes;
+ private final float offsetCorrection;
+
+ public MaximumInnerProduct(
+ RandomAccessQuantizedByteVectorValues values,
+ float constMultiplier,
+ byte[] targetBytes,
+ float offsetCorrection) {
+ super(values);
+ this.constMultiplier = constMultiplier;
+ this.values = values;
+ if (values.getScalarQuantizer().getBits() <= 4
+ && values.getVectorByteLength() != values.dimension()
+ && values.getSlice() != null) {
+ this.compressedVector = new byte[values.getVectorByteLength()];
+ } else {
+ this.compressedVector = null;
+ }
+ this.targetBytes = targetBytes;
+ this.offsetCorrection = offsetCorrection;
+ }
+
+ @Override
+ public float score(int vectorOrdinal) throws IOException {
+ float adjustedDistance =
+ optimizedDotProduct(
+ targetBytes,
+ offsetCorrection,
+ vectorOrdinal,
+ values,
+ compressedVector,
+ constMultiplier);
+ return scaleMaxInnerProductScore(adjustedDistance);
+ }
+ }
+
+ private static float optimizedDotProduct(
+ byte[] queryVector,
+ float queryOffset,
+ int vectorOrdinal,
+ RandomAccessQuantizedByteVectorValues values,
+ byte[] compressedVector,
+ float constMultiplier)
+ throws IOException {
+ final int dotProduct;
+ final float vectorOffset;
+ if (values.getScalarQuantizer().getBits() <= 4) {
+ // This means we can use our optimized path for 4-bit quantization comparisons
+ if (values.getSlice() != null && compressedVector != null) {
Review Comment:
Is seems that some of these branches are known at construction time, so could be eliminated by separate implementation classes - rather than branching during scoring. Something that can be evaluated later.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2077121498
> in which case why not just pack the query vector, allowing to do the comparison more easily
Because this makes things measurably slower. Having to decompressing only one of the vectors, and not adding the cost of compressing the query vector is the reason why this is so fast.
And I am not sure how it makes the comparisons easier. We then have to add LoC to decompress both and then compare both. The iteration code, etc. all remains the same.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent merged PR #13321:
URL: https://github.com/apache/lucene/pull/13321
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "benwtrent (via GitHub)" <gi...@apache.org>.
benwtrent commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2082532411
I double checked @ChrisHegarty 's improvements on 512:
My previous numbers:
```
VectorUtilBenchmark.binaryHalfByteVectorPacked 1024 thrpt 15 8.638 ± 0.095 ops/us
```
Here are the new numbers (I include float32 and regular binaryVector for comparisons):
```
VectorUtilBenchmark.binaryDotProductVector 1024 thrpt 15 14.248 ± 0.044 ops/us
VectorUtilBenchmark.binaryHalfByteVectorPacked 1024 thrpt 15 10.157 ± 0.044 ops/us
VectorUtilBenchmark.floatDotProductVector 1024 thrpt 75 17.633 ± 0.330 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] Improve int4 compressed comparisons performance [lucene]
Posted by "uschindler (via GitHub)" <gi...@apache.org>.
uschindler commented on code in PR #13321:
URL: https://github.com/apache/lucene/pull/13321#discussion_r1581305081
##########
lucene/core/src/java21/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -390,22 +391,139 @@ private int dotProductBody128(byte[] a, byte[] b, int limit) {
}
@Override
- public int int4DotProduct(byte[] a, byte[] b) {
+ public int int4DotProduct(byte[] a, boolean apacked, byte[] b, boolean bpacked) {
+ if (apacked && bpacked) {
Review Comment:
Actually, those checks here are not needed at all, because this is not a public API. Checks like the vector length is identical is in VectorUtil. VectorUtil also never passes both true.
Maybe make an assertion of it. Same applies for the default impl.
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -152,7 +152,23 @@ public int dotProduct(byte[] a, byte[] b) {
}
@Override
- public int int4DotProduct(byte[] a, byte[] b) {
+ public int int4DotProduct(byte[] a, boolean apacked, byte[] b, boolean bpacked) {
+ if (apacked && bpacked) {
Review Comment:
see below!
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on PR #13321:
URL: https://github.com/apache/lucene/pull/13321#issuecomment-2079213000
I went over the Panama code again, and confused myself about the potential to overflow - there is no issue, but it was not obvious as one has to match the number of potential values (not bytes) to the number of lanes x accumulators. Anyway, I added a test for boundary conditions - which will help when we move to optimising wider bit-widths.
--
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] Improve int4 compressed comparisons performance [lucene]
Posted by "ChrisHegarty (via GitHub)" <gi...@apache.org>.
ChrisHegarty commented on code in PR #13321:
URL: https://github.com/apache/lucene/pull/13321#discussion_r1577918752
##########
lucene/core/src/java/org/apache/lucene/util/hnsw/RandomAccessVectorValues.java:
##########
@@ -72,6 +84,11 @@ interface Floats extends RandomAccessVectorValues {
* @param targetOrd a valid ordinal, ≥ 0 and < {@link #size()}.
*/
float[] vectorValue(int targetOrd) throws IOException;
+
+ @Override
+ default int getVectorByteLength() {
Review Comment:
Maybe add a trivial javadoc that says that the default is dimensions by bytes-per dimension - not compressed.
##########
lucene/core/src/test/org/apache/lucene/codecs/lucene99/TestLucene99ScalarQuantizedVectorScorer.java:
##########
@@ -0,0 +1,145 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.codecs.lucene99;
+
+import java.io.IOException;
+import org.apache.lucene.codecs.Codec;
+import org.apache.lucene.codecs.KnnVectorsFormat;
+import org.apache.lucene.codecs.KnnVectorsReader;
+import org.apache.lucene.codecs.hnsw.DefaultFlatVectorScorer;
+import org.apache.lucene.codecs.perfield.PerFieldKnnVectorsFormat;
+import org.apache.lucene.document.Document;
+import org.apache.lucene.document.KnnFloatVectorField;
+import org.apache.lucene.index.CodecReader;
+import org.apache.lucene.index.DirectoryReader;
+import org.apache.lucene.index.IndexWriter;
+import org.apache.lucene.index.IndexWriterConfig;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.VectorSimilarityFunction;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.util.VectorUtil;
+import org.apache.lucene.util.hnsw.RandomVectorScorer;
+
+public class TestLucene99ScalarQuantizedVectorScorer extends LuceneTestCase {
+
+ private static Codec getCodec(int bits, boolean compress) {
+ return new Lucene99Codec() {
+ @Override
+ public KnnVectorsFormat getKnnVectorsFormatForField(String field) {
+ return new Lucene99HnswScalarQuantizedVectorsFormat(
+ Lucene99HnswVectorsFormat.DEFAULT_MAX_CONN,
+ Lucene99HnswVectorsFormat.DEFAULT_BEAM_WIDTH,
+ 1,
+ bits,
+ compress,
+ null,
+ null);
+ }
+ };
+ }
+
+ public void testScoringCompressedInt4() throws Exception {
+ vectorScoringTest(4, true);
+ }
+
+ public void testScoringUncompressedInt4() throws Exception {
+ vectorScoringTest(4, false);
+ }
+
+ public void testScoringInt7() throws Exception {
+ vectorScoringTest(7, random().nextBoolean());
+ }
+
+ private void vectorScoringTest(int bits, boolean compress) throws IOException {
+ float[][] storedVectors = new float[10][];
+ int numVectors = 10;
+ for (int i = 0; i < numVectors; i++) {
+ float[] vector = new float[] {i, i + 1, i + 2, i + 3};
Review Comment:
can we test with an odd sized vector.
--
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