You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "slow-J (via GitHub)" <gi...@apache.org> on 2026/10/07 14:01:34 UTC
[PR] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
slow-J opened a new pull request, #16790:
URL: https://github.com/apache/lucene/pull/16790
Starting as a draft, as I want to make sure this approach is valid first.
I was looking into more opportunities for vectorization after we shipped https://github.com/apache/lucene/pull/16631 .
`OptimizedScalarQuantizer.scalarQuantize` centers the vector, then runs a coordinate descent to pick the quantization interval. Each descent iteration walks the whole vector twice, once for the loss and once for the next step, one scalar double at a time. Then it rounds each component to its quantized value.
I am moving those loops into three `VectorUtilSupport` methods:
- `osqCenter`: centering, plus the centroid dot product, min, max and sums
- `osqGridStats`: one descent iteration's loss and step sums, in one pass
- `osqAssign`: rounding to the final quantized values
The Panama versions keep a float running sum per lane, with FMA, and add the lanes in lane order at the end (`reduceLanes(ADD)` adds in a different order before and after C2 compiles it, which made the output depend on JIT warm-up). The scalar versions in `DefaultVectorUtilSupport` do the same work in one pass, summing in float for `osqCenter` and in double for `osqGridStats`.
The variance, loss and descent sums are now reordered and partly computed in float, so they are less precise. The output is not identical to before: a slightly different sum can end the descent on a different interval, or move a component on a rounding boundary to the next level. Per-doc OSQ loss gets worse about as often as it gets better.
On the first 20K Cohere v3 1024d docs:
| bits | docs with any value changed | components changed | max change (levels) | OSQ loss vs before (per doc, >0.1%) |
|---:|---:|---:|---:|---|
| 1 | 2 (0.010%) | 0.0001% | 1 | 0 worse, 0 better |
| 2 | 10 (0.050%) | 0.0004% | 1 | 8 worse, 3 better |
| 4 | 49 (0.245%) | 0.0048% | 1 | 27 worse, 27 better |
| 7 | 327 (1.635%) | 0.0258% | 3 | 129 worse, 134 better |
| 8 | 640 (3.200%) | 0.0371% | 4 | 208 worse, 193 better |
Recall is unchanged in the luceneutil runs below.
### Benchmarked via JMH
Added a `scalarQuantize` pair to `VectorUtilBenchmark` (4 bits, rotating through 64 random vectors) and ran
```
java --module-path lucene/benchmark-jmh/build/benchmarks \
--module org.apache.lucene.benchmark.jmh \
'VectorUtilBenchmark.scalarQuantize.*' -p size=384,768,1024,4096 -tu ms
```
Hardware:
- EC2 Host: m6g.16xlarge
- AWS Graviton2 (Neoverse N1), aarch64, no SVE, preferredBitSize=128; FMA enabled, JDK 25.0.2
`scalarQuantizeVector`: ops/ms, main 3bb5f43990 -> this PR
| size | main | this PR | ratio |
|---:|---:|---:|---:|
| 384 | 40.845 ± 1.306 | 348.335 ± 8.971 | 8.53x |
| 768 | 18.729 ± 0.625 | 172.376 ± 5.507 | 9.20x |
| 1024 | 14.008 ± 0.908 | 126.265 ± 4.294 | 9.01x |
| 4096 | 3.111 ± 0.183 | 30.205 ± 1.167 | 9.71x |
`scalarQuantizeScalar` (no `--add-modules jdk.incubator.vector`): ops/ms
| size | main | this PR | ratio |
|---:|---:|---:|---:|
| 384 | 41.614 ± 2.166 | 70.515 ± 3.753 | 1.69x |
| 768 | 19.235 ± 0.829 | 33.504 ± 1.473 | 1.74x |
| 1024 | 14.245 ± 0.700 | 24.396 ± 1.009 | 1.71x |
| 4096 | 3.133 ± 0.115 | 5.571 ± 0.156 | 1.78x |
### Benchmarked via luceneutil
`knnPerfTest.py` set up like #16631: Cohere v3 Wikipedia 1024d, `ndoc=1_000_000`, `maxConn=64`,
`beamWidthIndex=250`, `quantizeBits=4`, `forceMerge`, rerank off + at 32/8/4 bits,
`numIndexThreads=8`, `numMergeThread=8`, `numMergeWorker=24`. First with search and stats (topK 100,
fanout 100, overSample 1/2/5, 10K queries), then index only. 3 reps each of baseline + candidate.
Build seconds (index + merge wait + force merge), mean of 3 reps, main 3bb5f43990 -> this PR
| rerank | search + stats: total | Δ total | Δ index phase | index-only: total | Δ total | Δ index phase |
|---|---:|---:|---:|---:|---:|---:|
| 32 bits | 1891.0 -> 1764.7 | -6.7% | -3.4% | 1896.4 -> 1777.6 | -6.2% | -4.3% |
| 8 bits | 963.1 -> 742.0 | -22.8% | -11.2% | 925.9 -> 765.8 | -17.3% | -9.4% |
| 4 bits | 963.1 -> 752.3 | -21.4% | -11.2% | 954.1 -> 797.4 | -16.3% | -10.8% |
| no | 870.0 -> 798.5 | -8.1% | -5.8% | 855.3 -> 767.8 | -9.6% | -5.5% |
| **12 builds** | | **-14.7%** (t -5.2) | **-7.9%** (t -7.2) | | **-12.4%** (t -5.4) | **-7.5%** (t -8.8) |
The index phase is faster in all 24 pairs. The totals swing more between reps (-6% to -18% per rep)
because faster indexing changes which merges TieredMergePolicy picks, which moves time between merge
wait and force merge.
Recall and latency, mean of 3 reps, main -> this PR
| rerank | overSample | recall (same) | latency main (ms) | latency this PR (ms) |
|---|---|---|---:|---:|
| 32 bits | 1/2/5 | 0.914/0.995/0.999 | 3.85/6.41/12.27 | 3.81/6.35/12.21 |
| 8 bits | 1/2/5 | 0.914/0.981/0.984 | 3.93/6.59/12.43 | 3.83/6.56/12.25 |
| 4 bits | 1/2/5 | 0.914/0.918/0.920 | 3.87/6.52/12.11 | 3.74/6.26/11.82 |
| no | 1/2/5 | 0.914/0.918/0.920 | 3.73/6.35/11.74 | 3.69/6.17/11.69 |
Latency is 1.7% lower over the 36 paired runs (t -5.2).
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4426153892
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
+
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ FloatVector accDot = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accMin = FloatVector.broadcast(FLOAT_SPECIES, Float.MAX_VALUE);
+ FloatVector accMax = FloatVector.broadcast(FLOAT_SPECIES, -Float.MAX_VALUE);
+ FloatVector accSq = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accSum = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector v = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ FloatVector c = FloatVector.fromArray(FLOAT_SPECIES, centroid, i);
+ accDot = fma(v, c, accDot);
+ FloatVector x = v.sub(c);
+ x.intoArray(vector, i);
+ accMin = accMin.min(x);
+ accMax = accMax.max(x);
+ accSq = fma(x, x, accSq);
+ accSum = accSum.add(x);
+ }
+ // scalar tail
+ float dot = 0;
+ float min = accMin.reduceLanes(VectorOperators.MIN);
+ float max = accMax.reduceLanes(VectorOperators.MAX);
+ float sumSq = 0;
+ float sum = 0;
+ for (; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot + sumLanes(accDot);
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq + sumLanes(accSq);
+ stats[4] = sum + sumLanes(accSum);
+ }
+
+ // k * k is at most 255^2, so an int lane can sum about 33K of them before it overflows. Below
+ // 2^16 dims, no lane gets that many.
+ private static final int OSQ_GRID_STATS_MAX_DIMS = 1 << 16;
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ if (vector.length >= OSQ_GRID_STATS_MAX_DIMS) {
+ DefaultVectorUtilSupport.osqGridStatsImpl(vector, lower, upper, points, stats);
+ return;
+ }
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ IntVector accK = IntVector.zero(INT_SPECIES);
+ IntVector accKK = IntVector.zero(INT_SPECIES);
+ FloatVector accXK = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accXD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accDD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accX = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector x = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ // Not fma, so k matches the scalar version.
+ FloatVector t = x.max(lower).min(upper).sub(lower).mul(stepInv).add(0.5f);
+ IntVector k = (IntVector) t.convert(VectorOperators.F2I, 0);
+ FloatVector kf = (FloatVector) k.convert(VectorOperators.I2F, 0);
+ FloatVector d = x.sub(kf.mul(step).add(lower));
+ accK = accK.add(k);
+ accKK = accKK.add(k.mul(k));
+ accXK = fma(x, kf, accXK);
+ accXD = fma(x, d, accXD);
+ accDD = fma(d, d, accDD);
+ accX = accX.add(x);
+ }
+ long sumK = accK.reduceLanesToLong(ADD);
+ long sumKK = accKK.reduceLanesToLong(ADD);
+ double sumXK = sumLanes(accXK);
+ double sumXD = sumLanes(accXD);
+ double sumDD = sumLanes(accDD);
+ double sumX = sumLanes(accX);
+ // scalar tail
+ for (; i < vector.length; i++) {
+ float x = vector[i];
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
+ stats[0] = sumK;
+ stats[1] = sumKK;
+ stats[2] = sumXK;
+ stats[3] = sumXD;
+ stats[4] = sumDD;
+ stats[5] = sumX;
+ }
+
+ @Override
+ public int osqAssign(float[] vector, float lower, float upper, float step, byte[] dest) {
+ // The vector loop converts levels with F2I, so it needs every level in [0, 2^31).
+ float maxLevel = (upper - lower) / step;
+ if ((maxLevel > 0 && maxLevel < 0x1p31f) == false) {
+ return DefaultVectorUtilSupport.osqAssignImpl(vector, 0, lower, upper, step, dest);
+ }
+ IntVector sums = IntVector.zero(INT_SPECIES);
+ final int lanes = FLOAT_SPECIES.length();
+ // Four int vectors of levels fill one byte vector.
+ final int bound = BYTE_SPECIES_FULL.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += BYTE_SPECIES_FULL.length()) {
+ ByteVector out = ByteVector.zero(BYTE_SPECIES_FULL);
+ for (int part = 0; part < 4; part++) {
Review Comment:
We can look this as a follow up if thats ok.
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/VectorUtilBenchmark.java:
##########
@@ -118,6 +126,21 @@ public void init() {
floatsB[i] = random.nextFloat();
shortsB[i] = Float.floatToFloat16(floatsB[i]);
}
+ // Rotate through 64 vectors, as the number of descent steps depends on the vector. They are
+ // centered here and the centroid is zero, so scalarQuantize leaves them as they are and every
+ // call can be checked against the first.
+ quantizeVectors = new float[64][size];
+ expectedQuantizeResults = new OptimizedScalarQuantizer.QuantizationResult[64];
+ quantizeCentroid = new float[size];
+ quantizeDest = new byte[size];
+ quantizer = new OptimizedScalarQuantizer(VectorSimilarityFunction.DOT_PRODUCT);
+ for (int j = 0; j < 64; j++) {
+ for (int i = 0; i < size; ++i) {
+ quantizeVectors[j][i] = random.nextFloat() - floatsB[i];
+ }
+ expectedQuantizeResults[j] =
+ quantizer.scalarQuantize(quantizeVectors[j], quantizeDest, (byte) 4, quantizeCentroid);
Review Comment:
Makes sense, I'll remove.
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/VectorUtilBenchmark.java:
##########
@@ -118,6 +126,21 @@ public void init() {
floatsB[i] = random.nextFloat();
shortsB[i] = Float.floatToFloat16(floatsB[i]);
}
+ // Rotate through 64 vectors, as the number of descent steps depends on the vector. They are
+ // centered here and the centroid is zero, so scalarQuantize leaves them as they are and every
+ // call can be checked against the first.
+ quantizeVectors = new float[64][size];
+ expectedQuantizeResults = new OptimizedScalarQuantizer.QuantizationResult[64];
+ quantizeCentroid = new float[size];
Review Comment:
Currently, setup subtracts a random centroid from each vector, and scalarQuantize subtracts the centroid in place, so a random one here would change the vectors on every call and we'd need to copy. Should we still do it?
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/NativeVectorUtilSupport.java:
##########
@@ -571,6 +571,21 @@ public float recalculateScalarQuantizationOffset(
vector.length);
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ delegateVectorUtilSupport.osqCenter(vector, centroid, stats);
Review Comment:
Sure, I'll add the three to `dotProduct.h` and call them through `invokeOrDelegate`.
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -459,6 +459,87 @@ private float quantizeFloat(float v, byte[] dest, int destIndex) {
}
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ osqCenterImpl(vector, centroid, 0, stats);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static void osqCenterImpl(float[] vector, float[] centroid, int start, float[] stats) {
+ float dot = 0;
+ float min = Float.MAX_VALUE;
+ float max = -Float.MAX_VALUE;
+ float sumSq = 0;
+ float sum = 0;
+ for (int i = start; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot;
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq;
+ stats[4] = sum;
+ }
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ osqGridStatsImpl(vector, 0, lower, upper, points, stats);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static void osqGridStatsImpl(
+ float[] vector, int start, float lower, float upper, int points, double[] stats) {
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ long sumK = 0;
+ long sumKK = 0;
+ double sumXK = 0;
+ double sumXD = 0;
+ double sumDD = 0;
+ double sumX = 0;
Review Comment:
Good idea, I'll do that in the next commit.
##########
lucene/core/src/java/org/apache/lucene/util/VectorUtil.java:
##########
@@ -598,6 +598,52 @@ public static float recalculateOffset(
vector, oldAlpha, oldMinQuantile, scale, alpha, minQuantile, maxQuantile);
}
+ /**
+ * Subtracts {@code centroid} from {@code vector} in place, for the optimized scalar quantizer,
+ * and writes into {@code stats} the dot product of the original vector with {@code centroid},
+ * then the min, max, sum of squares and sum of the result.
+ */
+ public static void osqCenter(float[] vector, float[] centroid, float[] stats) {
Review Comment:
Thanks, I'll make them experimental in the next commit.
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -459,6 +459,87 @@ private float quantizeFloat(float v, byte[] dest, int destIndex) {
}
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ osqCenterImpl(vector, centroid, 0, stats);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static void osqCenterImpl(float[] vector, float[] centroid, int start, float[] stats) {
+ float dot = 0;
+ float min = Float.MAX_VALUE;
+ float max = -Float.MAX_VALUE;
+ float sumSq = 0;
+ float sum = 0;
+ for (int i = start; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot;
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq;
+ stats[4] = sum;
+ }
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ osqGridStatsImpl(vector, 0, lower, upper, points, stats);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static void osqGridStatsImpl(
+ float[] vector, int start, float lower, float upper, int points, double[] stats) {
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ long sumK = 0;
+ long sumKK = 0;
+ double sumXK = 0;
Review Comment:
Very true, I'll make the scalar sums float.
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "kaivalnp (via GitHub) via issues" <is...@lucene.apache.org>.
kaivalnp commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4516973200
##########
lucene/core/src/java/org/apache/lucene/util/VectorUtil.java:
##########
@@ -598,6 +598,62 @@ public static float recalculateOffset(
vector, oldAlpha, oldMinQuantile, scale, alpha, minQuantile, maxQuantile);
}
+ /**
+ * Subtracts {@code centroid} from {@code vector} in place, for the optimized scalar quantizer,
+ * and writes into {@code stats} the dot product of the original vector with {@code centroid},
+ * then the min, max, sum of squares and sum of the result, and the sum of its squared differences
+ * from its mean.
+ *
+ * @lucene.experimental
+ */
+ public static void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ if (vector.length != centroid.length) {
+ throw new IllegalArgumentException(
+ "vector dimensions differ: " + vector.length + "!=" + centroid.length);
+ }
+ if (stats.length != 6) {
+ throw new IllegalArgumentException("stats must have 6 entries: " + stats.length);
+ }
+ IMPL.osqCenter(vector, centroid, stats);
+ }
+
+ /**
+ * Computes the sums that the optimized scalar quantizer's interval search needs for one interval.
+ * Each value {@code x} of {@code vector}, limited to {@code [lower, upper]}, is rounded half up
+ * to one of {@code points} levels {@code k}, which dequantizes to {@code x'}. Writes the sums of
+ * k, k * k, x * k, x * (x - x') and (x - x') * (x - x') into {@code stats}.
+ *
+ * @lucene.experimental
+ */
+ public static void osqGridStats(
+ float[] vector, float lower, float upper, int points, double[] stats) {
+ if (points < 2 || points > 256) {
+ throw new IllegalArgumentException("points must be in [2, 256]: " + points);
+ }
+ if (stats.length != 5) {
+ throw new IllegalArgumentException("stats must have 5 entries: " + stats.length);
+ }
+ assert lower <= upper : lower + " > " + upper;
Review Comment:
I asked an AI for an example of when the quantize function can trip this assertion:
```java
float[] v = {0.1f, 0.1f, 0.10000001f, 0.10000001f}; // two values 1 ulp apart
new OptimizedScalarQuantizer(VectorSimilarityFunction.EUCLIDEAN)
.scalarQuantize(v, new byte[4], (byte) 2, new float[4]);
```
Unfortunately looks like this can be common, should we remove the assertion?
Sorry for the churn :(
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
Review Comment:
Based on [existing usage](https://github.com/apache/lucene/blob/e0a3a951e7ef2e7b4e04b6b9966468099e642056/lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java#L237-L239), this personally feels ok to use.
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "kaivalnp (via GitHub) via issues" <is...@lucene.apache.org>.
kaivalnp commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4446889958
##########
lucene/core/src/java/org/apache/lucene/util/quantization/OptimizedScalarQuantizer.java:
##########
@@ -192,25 +176,15 @@ public QuantizationResult scalarQuantize(
assert bits > 0 && bits <= 8;
float[] intervalScratch = new float[2];
int points = 1 << bits;
- double vecMean = 0;
- double vecVar = 0;
- float norm2 = 0;
- float centroidDot = 0;
- float min = Float.MAX_VALUE;
- float max = -Float.MAX_VALUE;
- for (int i = 0; i < vector.length; ++i) {
- if (similarityFunction != EUCLIDEAN) {
- centroidDot += vector[i] * centroid[i];
- }
- vector[i] = vector[i] - centroid[i];
- min = Math.min(min, vector[i]);
- max = Math.max(max, vector[i]);
- norm2 += (vector[i] * vector[i]);
- double delta = vector[i] - vecMean;
- vecMean += delta / (i + 1);
- vecVar += delta * (vector[i] - vecMean);
- }
- vecVar /= vector.length;
+ float[] centerStats = new float[5];
+ VectorUtil.osqCenter(vector, centroid, centerStats);
+ float centroidDot = centerStats[0];
+ float min = centerStats[1];
+ float max = centerStats[2];
+ float norm2 = centerStats[3];
+ double vecMean = centerStats[4] / (double) vector.length;
+ // Rounding can push the mean of squares minus the squared mean just below zero.
+ double vecVar = Math.max(0, norm2 / (double) vector.length - vecMean * vecMean);
Review Comment:
The Cohere dataset may be unit-norm / centered, so the simple method works well.
Other datasets might have larger norms (i.e. using `MAXIMUM_INNER_PRODUCT`) and / or off-center vectors (e.g. a data-blind assumption), which might cause issues?
I feel like the 6-8% performance drop is worth the broader correctness support (on par with `main`).
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "slow-J (via GitHub) via issues" <is...@lucene.apache.org>.
slow-J commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4524997923
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
Review Comment:
Sure, I'll use reduceLanes then!
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "slow-J (via GitHub) via issues" <is...@lucene.apache.org>.
slow-J commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4454189430
##########
lucene/core/src/java/org/apache/lucene/util/quantization/OptimizedScalarQuantizer.java:
##########
@@ -192,25 +176,15 @@ public QuantizationResult scalarQuantize(
assert bits > 0 && bits <= 8;
float[] intervalScratch = new float[2];
int points = 1 << bits;
- double vecMean = 0;
- double vecVar = 0;
- float norm2 = 0;
- float centroidDot = 0;
- float min = Float.MAX_VALUE;
- float max = -Float.MAX_VALUE;
- for (int i = 0; i < vector.length; ++i) {
- if (similarityFunction != EUCLIDEAN) {
- centroidDot += vector[i] * centroid[i];
- }
- vector[i] = vector[i] - centroid[i];
- min = Math.min(min, vector[i]);
- max = Math.max(max, vector[i]);
- norm2 += (vector[i] * vector[i]);
- double delta = vector[i] - vecMean;
- vecMean += delta / (i + 1);
- vecVar += delta * (vector[i] - vecMean);
- }
- vecVar /= vector.length;
+ float[] centerStats = new float[5];
+ VectorUtil.osqCenter(vector, centroid, centerStats);
+ float centroidDot = centerStats[0];
+ float min = centerStats[1];
+ float max = centerStats[2];
+ float norm2 = centerStats[3];
+ double vecMean = centerStats[4] / (double) vector.length;
+ // Rounding can push the mean of squares minus the squared mean just below zero.
+ double vecVar = Math.max(0, norm2 / (double) vector.length - vecMean * vecMean);
Review Comment:
Thanks for validating and sorry for the churn here, I will bring back the Welford in next commit!
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "slow-J (via GitHub) via issues" <is...@lucene.apache.org>.
slow-J commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4454189430
##########
lucene/core/src/java/org/apache/lucene/util/quantization/OptimizedScalarQuantizer.java:
##########
@@ -192,25 +176,15 @@ public QuantizationResult scalarQuantize(
assert bits > 0 && bits <= 8;
float[] intervalScratch = new float[2];
int points = 1 << bits;
- double vecMean = 0;
- double vecVar = 0;
- float norm2 = 0;
- float centroidDot = 0;
- float min = Float.MAX_VALUE;
- float max = -Float.MAX_VALUE;
- for (int i = 0; i < vector.length; ++i) {
- if (similarityFunction != EUCLIDEAN) {
- centroidDot += vector[i] * centroid[i];
- }
- vector[i] = vector[i] - centroid[i];
- min = Math.min(min, vector[i]);
- max = Math.max(max, vector[i]);
- norm2 += (vector[i] * vector[i]);
- double delta = vector[i] - vecMean;
- vecMean += delta / (i + 1);
- vecVar += delta * (vector[i] - vecMean);
- }
- vecVar /= vector.length;
+ float[] centerStats = new float[5];
+ VectorUtil.osqCenter(vector, centroid, centerStats);
+ float centroidDot = centerStats[0];
+ float min = centerStats[1];
+ float max = centerStats[2];
+ float norm2 = centerStats[3];
+ double vecMean = centerStats[4] / (double) vector.length;
+ // Rounding can push the mean of squares minus the squared mean just below zero.
+ double vecVar = Math.max(0, norm2 / (double) vector.length - vecMean * vecMean);
Review Comment:
Thanks for validating and sorry for the churn here, I will bring back the Welford's algorithm in next commit!
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4424696499
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -459,6 +459,87 @@ private float quantizeFloat(float v, byte[] dest, int destIndex) {
}
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ osqCenterImpl(vector, centroid, 0, stats);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static void osqCenterImpl(float[] vector, float[] centroid, int start, float[] stats) {
+ float dot = 0;
+ float min = Float.MAX_VALUE;
+ float max = -Float.MAX_VALUE;
+ float sumSq = 0;
+ float sum = 0;
+ for (int i = start; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot;
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq;
+ stats[4] = sum;
+ }
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ osqGridStatsImpl(vector, 0, lower, upper, points, stats);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static void osqGridStatsImpl(
+ float[] vector, int start, float lower, float upper, int points, double[] stats) {
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ long sumK = 0;
+ long sumKK = 0;
+ double sumXK = 0;
Review Comment:
This is a difference in precision b/w the default and SIMD version (`double` v/s `float`); I feel that they should be consistent (apart from the documented / accepted variation with order of float operations).
Perhaps relaxing these to `float` is fine too, but a second opinion would be appreciated.
##########
lucene/core/src/java/org/apache/lucene/util/VectorUtil.java:
##########
@@ -598,6 +598,52 @@ public static float recalculateOffset(
vector, oldAlpha, oldMinQuantile, scale, alpha, minQuantile, maxQuantile);
}
+ /**
+ * Subtracts {@code centroid} from {@code vector} in place, for the optimized scalar quantizer,
+ * and writes into {@code stats} the dot product of the original vector with {@code centroid},
+ * then the min, max, sum of squares and sum of the result.
+ */
+ public static void osqCenter(float[] vector, float[] centroid, float[] stats) {
Review Comment:
`OptimizedScalarQuantizer` is marked [experimental](https://github.com/apache/lucene/blob/46432a3f0db981f8d1ef5e6bdc142f0704b7c321/lucene/core/src/java/org/apache/lucene/util/quantization/OptimizedScalarQuantizer.java#L40) and this opens up its internals -- I think we should mark these functions similarly.
I was initially concerned about exposing quantization in `VectorUtil`, but I see there is some precedent in #13922 and #14304.
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
+
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ FloatVector accDot = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accMin = FloatVector.broadcast(FLOAT_SPECIES, Float.MAX_VALUE);
+ FloatVector accMax = FloatVector.broadcast(FLOAT_SPECIES, -Float.MAX_VALUE);
+ FloatVector accSq = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accSum = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector v = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ FloatVector c = FloatVector.fromArray(FLOAT_SPECIES, centroid, i);
+ accDot = fma(v, c, accDot);
+ FloatVector x = v.sub(c);
+ x.intoArray(vector, i);
+ accMin = accMin.min(x);
+ accMax = accMax.max(x);
+ accSq = fma(x, x, accSq);
+ accSum = accSum.add(x);
+ }
+ // scalar tail
+ float dot = 0;
+ float min = accMin.reduceLanes(VectorOperators.MIN);
+ float max = accMax.reduceLanes(VectorOperators.MAX);
+ float sumSq = 0;
+ float sum = 0;
+ for (; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot + sumLanes(accDot);
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq + sumLanes(accSq);
+ stats[4] = sum + sumLanes(accSum);
+ }
+
+ // k * k is at most 255^2, so an int lane can sum about 33K of them before it overflows. Below
+ // 2^16 dims, no lane gets that many.
+ private static final int OSQ_GRID_STATS_MAX_DIMS = 1 << 16;
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ if (vector.length >= OSQ_GRID_STATS_MAX_DIMS) {
+ DefaultVectorUtilSupport.osqGridStatsImpl(vector, lower, upper, points, stats);
+ return;
+ }
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ IntVector accK = IntVector.zero(INT_SPECIES);
+ IntVector accKK = IntVector.zero(INT_SPECIES);
+ FloatVector accXK = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accXD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accDD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accX = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector x = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ // Not fma, so k matches the scalar version.
+ FloatVector t = x.max(lower).min(upper).sub(lower).mul(stepInv).add(0.5f);
+ IntVector k = (IntVector) t.convert(VectorOperators.F2I, 0);
+ FloatVector kf = (FloatVector) k.convert(VectorOperators.I2F, 0);
+ FloatVector d = x.sub(kf.mul(step).add(lower));
+ accK = accK.add(k);
+ accKK = accKK.add(k.mul(k));
+ accXK = fma(x, kf, accXK);
+ accXD = fma(x, d, accXD);
+ accDD = fma(d, d, accDD);
+ accX = accX.add(x);
+ }
+ long sumK = accK.reduceLanesToLong(ADD);
+ long sumKK = accKK.reduceLanesToLong(ADD);
+ double sumXK = sumLanes(accXK);
+ double sumXD = sumLanes(accXD);
+ double sumDD = sumLanes(accDD);
+ double sumX = sumLanes(accX);
+ // scalar tail
+ for (; i < vector.length; i++) {
+ float x = vector[i];
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
+ stats[0] = sumK;
+ stats[1] = sumKK;
+ stats[2] = sumXK;
+ stats[3] = sumXD;
+ stats[4] = sumDD;
+ stats[5] = sumX;
+ }
+
+ @Override
+ public int osqAssign(float[] vector, float lower, float upper, float step, byte[] dest) {
+ // The vector loop converts levels with F2I, so it needs every level in [0, 2^31).
+ float maxLevel = (upper - lower) / step;
+ if ((maxLevel > 0 && maxLevel < 0x1p31f) == false) {
+ return DefaultVectorUtilSupport.osqAssignImpl(vector, 0, lower, upper, step, dest);
+ }
+ IntVector sums = IntVector.zero(INT_SPECIES);
+ final int lanes = FLOAT_SPECIES.length();
+ // Four int vectors of levels fill one byte vector.
+ final int bound = BYTE_SPECIES_FULL.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += BYTE_SPECIES_FULL.length()) {
+ ByteVector out = ByteVector.zero(BYTE_SPECIES_FULL);
+ for (int part = 0; part < 4; part++) {
Review Comment:
I wonder if for some bit widths: it becomes faster to write to the array without accumulating 4x into a single SIMD register first. We can defer this for later though.
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/NativeVectorUtilSupport.java:
##########
@@ -571,6 +571,21 @@ public float recalculateScalarQuantizationOffset(
vector.length);
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ delegateVectorUtilSupport.osqCenter(vector, centroid, stats);
Review Comment:
I was hoping to add a function to the header file [like this](https://github.com/apache/lucene/blob/208608f75307ccc19f0fb99dc8ddcce817240f66/lucene/misc/src/c/dotProduct.h#L59-L64) and wiring up the native provider, so that implementers can override _if needed_ (we don't need to write the entire C implementation, I see many functions are missing from https://github.com/apache/lucene/blob/main/lucene/misc/src/c/dotProduct.c).
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -459,6 +459,87 @@ private float quantizeFloat(float v, byte[] dest, int destIndex) {
}
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ osqCenterImpl(vector, centroid, 0, stats);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static void osqCenterImpl(float[] vector, float[] centroid, int start, float[] stats) {
+ float dot = 0;
+ float min = Float.MAX_VALUE;
+ float max = -Float.MAX_VALUE;
+ float sumSq = 0;
+ float sum = 0;
+ for (int i = start; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot;
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq;
+ stats[4] = sum;
+ }
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ osqGridStatsImpl(vector, 0, lower, upper, points, stats);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static void osqGridStatsImpl(
+ float[] vector, int start, float lower, float upper, int points, double[] stats) {
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ long sumK = 0;
+ long sumKK = 0;
+ double sumXK = 0;
+ double sumXD = 0;
+ double sumDD = 0;
+ double sumX = 0;
Review Comment:
`osqCenter` computes `sumX` internally, I wonder if it can be passed on (and avoid recomputing here)?
Though if this is small, it might be worth keeping as-is for code clarity.
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/VectorUtilBenchmark.java:
##########
@@ -118,6 +126,21 @@ public void init() {
floatsB[i] = random.nextFloat();
shortsB[i] = Float.floatToFloat16(floatsB[i]);
}
+ // Rotate through 64 vectors, as the number of descent steps depends on the vector. They are
+ // centered here and the centroid is zero, so scalarQuantize leaves them as they are and every
+ // call can be checked against the first.
+ quantizeVectors = new float[64][size];
+ expectedQuantizeResults = new OptimizedScalarQuantizer.QuantizationResult[64];
+ quantizeCentroid = new float[size];
+ quantizeDest = new byte[size];
+ quantizer = new OptimizedScalarQuantizer(VectorSimilarityFunction.DOT_PRODUCT);
+ for (int j = 0; j < 64; j++) {
+ for (int i = 0; i < size; ++i) {
+ quantizeVectors[j][i] = random.nextFloat() - floatsB[i];
+ }
+ expectedQuantizeResults[j] =
+ quantizer.scalarQuantize(quantizeVectors[j], quantizeDest, (byte) 4, quantizeCentroid);
Review Comment:
This sets "expected" using the same function that is being measured, so correctness issues may not result in exceptions being thrown?
Sorry, I realize that redoing the "quantize" function is a hassle here, perhaps it is ok to remove the check entirely (but any future changes to the function will need to be accompanied by end-to-end checks like you did here).
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/VectorUtilBenchmark.java:
##########
@@ -118,6 +126,21 @@ public void init() {
floatsB[i] = random.nextFloat();
shortsB[i] = Float.floatToFloat16(floatsB[i]);
}
+ // Rotate through 64 vectors, as the number of descent steps depends on the vector. They are
+ // centered here and the centroid is zero, so scalarQuantize leaves them as they are and every
+ // call can be checked against the first.
+ quantizeVectors = new float[64][size];
+ expectedQuantizeResults = new OptimizedScalarQuantizer.QuantizationResult[64];
+ quantizeCentroid = new float[size];
Review Comment:
Can this be a random vector too, just to exercise more randomness?
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "slow-J (via GitHub) via issues" <is...@lucene.apache.org>.
slow-J commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4445874681
##########
lucene/core/src/java/org/apache/lucene/util/quantization/OptimizedScalarQuantizer.java:
##########
@@ -192,25 +176,15 @@ public QuantizationResult scalarQuantize(
assert bits > 0 && bits <= 8;
float[] intervalScratch = new float[2];
int points = 1 << bits;
- double vecMean = 0;
- double vecVar = 0;
- float norm2 = 0;
- float centroidDot = 0;
- float min = Float.MAX_VALUE;
- float max = -Float.MAX_VALUE;
- for (int i = 0; i < vector.length; ++i) {
- if (similarityFunction != EUCLIDEAN) {
- centroidDot += vector[i] * centroid[i];
- }
- vector[i] = vector[i] - centroid[i];
- min = Math.min(min, vector[i]);
- max = Math.max(max, vector[i]);
- norm2 += (vector[i] * vector[i]);
- double delta = vector[i] - vecMean;
- vecMean += delta / (i + 1);
- vecVar += delta * (vector[i] - vecMean);
- }
- vecVar /= vector.length;
+ float[] centerStats = new float[5];
+ VectorUtil.osqCenter(vector, centroid, centerStats);
+ float centroidDot = centerStats[0];
+ float min = centerStats[1];
+ float max = centerStats[2];
+ float norm2 = centerStats[3];
+ double vecMean = centerStats[4] / (double) vector.length;
+ // Rounding can push the mean of squares minus the squared mean just below zero.
+ double vecVar = Math.max(0, norm2 / (double) vector.length - vecMean * vecMean);
Review Comment:
Tried to hack something up to measure this with results as follows:
A SIMD Welford (per lane, merged at the end) makes `scalarQuantizeVector` 6-8% slower at 384-4096 dims.
On the first 20K Cohere docs, the variance is off by at most 5e-7 both with or without it. The simple version goes wrong when a vector's mean after centering is ~1000x its std.
I would like to keep the simple one, WDYT?
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/VectorUtilBenchmark.java:
##########
@@ -118,6 +126,21 @@ public void init() {
floatsB[i] = random.nextFloat();
shortsB[i] = Float.floatToFloat16(floatsB[i]);
}
+ // Rotate through 64 vectors, as the number of descent steps depends on the vector. They are
+ // centered here and the centroid is zero, so scalarQuantize leaves them as they are and every
+ // call can be checked against the first.
+ quantizeVectors = new float[64][size];
+ expectedQuantizeResults = new OptimizedScalarQuantizer.QuantizationResult[64];
+ quantizeCentroid = new float[size];
Review Comment:
Will do in latest commit. The centroid is now random and each call copies the next vector into a scratch array first. The copy is ~1-2% of `scalarQuantizeVector` at 384-4096 dims, so I left it in the benchmark.
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -459,6 +459,80 @@ private float quantizeFloat(float v, byte[] dest, int destIndex) {
}
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ float dot = 0;
+ float min = Float.MAX_VALUE;
+ float max = -Float.MAX_VALUE;
+ float sumSq = 0;
+ float sum = 0;
+ for (int i = 0; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot;
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq;
+ stats[4] = sum;
+ }
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ osqGridStatsImpl(vector, lower, upper, points, stats);
+ }
+
+ static void osqGridStatsImpl(
+ float[] vector, float lower, float upper, int points, double[] stats) {
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ long sumK = 0;
+ long sumKK = 0;
+ double sumXK = 0;
+ double sumXD = 0;
+ double sumDD = 0;
+ double sumX = 0;
+ for (float x : vector) {
+ // Adds 0.5 and truncates, as Math.round is costly to match in the Panama version.
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
+ stats[0] = sumK;
+ stats[1] = sumKK;
+ stats[2] = sumXK;
+ stats[3] = sumXD;
+ stats[4] = sumDD;
+ stats[5] = sumX;
+ }
+
+ @Override
+ public int osqAssign(float[] vector, float lower, float upper, float step, byte[] dest) {
+ return osqAssignImpl(vector, 0, lower, upper, step, dest);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static int osqAssignImpl(
+ float[] vector, int start, float lower, float upper, float step, byte[] dest) {
+ int sum = 0;
+ for (int i = start; i < vector.length; i++) {
+ int k = Math.round((Math.min(Math.max(vector[i], lower), upper) - lower) / step);
Review Comment:
Couldn't find existing assertions, I added some in next commit. With asserts on, the first 20K Cohere docs at 1, 2, 4, 7 and 8 bits never hit lower > upper or step < 0, Panama or scalar. Forgot to say earlier that the Panama code has `x.max(lower).min(upper)` and changing the scalar one would add a difference since there are some behaviour changes like a 0.0 vs -0.0 edge case that would throw with `Math.clamp`. WDYT?
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4427524385
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/VectorUtilBenchmark.java:
##########
@@ -118,6 +126,21 @@ public void init() {
floatsB[i] = random.nextFloat();
shortsB[i] = Float.floatToFloat16(floatsB[i]);
}
+ // Rotate through 64 vectors, as the number of descent steps depends on the vector. They are
+ // centered here and the centroid is zero, so scalarQuantize leaves them as they are and every
+ // call can be checked against the first.
+ quantizeVectors = new float[64][size];
+ expectedQuantizeResults = new OptimizedScalarQuantizer.QuantizationResult[64];
+ quantizeCentroid = new float[size];
Review Comment:
Yes, I think we should do it -- perhaps we can continue with the same "copy to scratch" proposal you had earlier..
If the copy overhead is large compared to the function being benchmarked, perhaps we can put it in a "setup" function with `Level.Invocation`? (which may not be needed if the overhead is small enough)
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4424253337
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -459,6 +459,80 @@ private float quantizeFloat(float v, byte[] dest, int destIndex) {
}
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ float dot = 0;
+ float min = Float.MAX_VALUE;
+ float max = -Float.MAX_VALUE;
+ float sumSq = 0;
+ float sum = 0;
+ for (int i = 0; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot;
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq;
+ stats[4] = sum;
+ }
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ osqGridStatsImpl(vector, lower, upper, points, stats);
+ }
+
+ static void osqGridStatsImpl(
+ float[] vector, float lower, float upper, int points, double[] stats) {
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ long sumK = 0;
+ long sumKK = 0;
+ double sumXK = 0;
+ double sumXD = 0;
+ double sumDD = 0;
+ double sumX = 0;
+ for (float x : vector) {
+ // Adds 0.5 and truncates, as Math.round is costly to match in the Panama version.
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
+ stats[0] = sumK;
+ stats[1] = sumKK;
+ stats[2] = sumXK;
+ stats[3] = sumXD;
+ stats[4] = sumDD;
+ stats[5] = sumX;
+ }
+
+ @Override
+ public int osqAssign(float[] vector, float lower, float upper, float step, byte[] dest) {
+ return osqAssignImpl(vector, 0, lower, upper, step, dest);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static int osqAssignImpl(
+ float[] vector, int start, float lower, float upper, float step, byte[] dest) {
+ int sum = 0;
+ for (int i = start; i < vector.length; i++) {
+ int k = Math.round((Math.min(Math.max(vector[i], lower), upper) - lower) / step);
Review Comment:
I used `min(max(...))` because `Math.clamp` throws when lower > upper. I don't think anything asserts that the interval is ordered.
There is an existing
```
private static double clamp(double x, double a, double b) {
return Math.min(Math.max(x, a), b);
}
```
used in OptimizedScalarQuantizer, maybe we could use a similar helper method here?
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
+
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ FloatVector accDot = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accMin = FloatVector.broadcast(FLOAT_SPECIES, Float.MAX_VALUE);
+ FloatVector accMax = FloatVector.broadcast(FLOAT_SPECIES, -Float.MAX_VALUE);
+ FloatVector accSq = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accSum = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector v = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ FloatVector c = FloatVector.fromArray(FLOAT_SPECIES, centroid, i);
+ accDot = fma(v, c, accDot);
+ FloatVector x = v.sub(c);
+ x.intoArray(vector, i);
+ accMin = accMin.min(x);
+ accMax = accMax.max(x);
+ accSq = fma(x, x, accSq);
+ accSum = accSum.add(x);
+ }
+ // scalar tail
+ float dot = 0;
+ float min = accMin.reduceLanes(VectorOperators.MIN);
+ float max = accMax.reduceLanes(VectorOperators.MAX);
+ float sumSq = 0;
+ float sum = 0;
+ for (; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot + sumLanes(accDot);
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq + sumLanes(accSq);
+ stats[4] = sum + sumLanes(accSum);
+ }
+
+ // k * k is at most 255^2, so an int lane can sum about 33K of them before it overflows. Below
+ // 2^16 dims, no lane gets that many.
+ private static final int OSQ_GRID_STATS_MAX_DIMS = 1 << 16;
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ if (vector.length >= OSQ_GRID_STATS_MAX_DIMS) {
+ DefaultVectorUtilSupport.osqGridStatsImpl(vector, lower, upper, points, stats);
+ return;
+ }
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ IntVector accK = IntVector.zero(INT_SPECIES);
+ IntVector accKK = IntVector.zero(INT_SPECIES);
+ FloatVector accXK = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accXD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accDD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accX = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector x = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ // Not fma, so k matches the scalar version.
+ FloatVector t = x.max(lower).min(upper).sub(lower).mul(stepInv).add(0.5f);
+ IntVector k = (IntVector) t.convert(VectorOperators.F2I, 0);
+ FloatVector kf = (FloatVector) k.convert(VectorOperators.I2F, 0);
+ FloatVector d = x.sub(kf.mul(step).add(lower));
+ accK = accK.add(k);
+ accKK = accKK.add(k.mul(k));
+ accXK = fma(x, kf, accXK);
+ accXD = fma(x, d, accXD);
+ accDD = fma(d, d, accDD);
+ accX = accX.add(x);
+ }
+ long sumK = accK.reduceLanesToLong(ADD);
+ long sumKK = accKK.reduceLanesToLong(ADD);
+ double sumXK = sumLanes(accXK);
+ double sumXD = sumLanes(accXD);
+ double sumDD = sumLanes(accDD);
+ double sumX = sumLanes(accX);
+ // scalar tail
+ for (; i < vector.length; i++) {
+ float x = vector[i];
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
+ stats[0] = sumK;
+ stats[1] = sumKK;
+ stats[2] = sumXK;
+ stats[3] = sumXD;
+ stats[4] = sumDD;
+ stats[5] = sumX;
+ }
+
+ @Override
+ public int osqAssign(float[] vector, float lower, float upper, float step, byte[] dest) {
+ // The vector loop converts levels with F2I, so it needs every level in [0, 2^31).
+ float maxLevel = (upper - lower) / step;
+ if ((maxLevel > 0 && maxLevel < 0x1p31f) == false) {
+ return DefaultVectorUtilSupport.osqAssignImpl(vector, 0, lower, upper, step, dest);
+ }
+ IntVector sums = IntVector.zero(INT_SPECIES);
+ final int lanes = FLOAT_SPECIES.length();
+ // Four int vectors of levels fill one byte vector.
+ final int bound = BYTE_SPECIES_FULL.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += BYTE_SPECIES_FULL.length()) {
+ ByteVector out = ByteVector.zero(BYTE_SPECIES_FULL);
+ for (int part = 0; part < 4; part++) {
+ FloatVector x = FloatVector.fromArray(FLOAT_SPECIES, vector, i + part * lanes);
+ FloatVector t = x.max(lower).min(upper).sub(lower).div(step);
+ // Same as Math.round(t): truncate, then add 1 when twice the fraction truncates to 1. NaN
+ // converts to 0, as in Math.round.
+ IntVector k = (IntVector) t.convert(VectorOperators.F2I, 0);
+ FloatVector frac = t.sub((FloatVector) k.convert(VectorOperators.I2F, 0));
+ k = k.add((IntVector) frac.add(frac).convert(VectorOperators.F2I, 0));
Review Comment:
Good idea, will do this in latest commit!
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/NativeVectorUtilSupport.java:
##########
@@ -571,6 +571,21 @@ public float recalculateScalarQuantizationOffset(
vector.length);
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ delegateVectorUtilSupport.osqCenter(vector, centroid, stats);
Review Comment:
`invokeOrDelegate` looks like it tries to invoke a C version of the function, calling it if it exists, else falling back to the Java delegate.
There's no C version of these, so I think we should call the delegate directly? Unless you think we should add C code here?
`invokeOrDelegate` also has a TODO saying it's slow, but I didn't look into why.
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
+
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ FloatVector accDot = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accMin = FloatVector.broadcast(FLOAT_SPECIES, Float.MAX_VALUE);
+ FloatVector accMax = FloatVector.broadcast(FLOAT_SPECIES, -Float.MAX_VALUE);
+ FloatVector accSq = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accSum = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector v = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ FloatVector c = FloatVector.fromArray(FLOAT_SPECIES, centroid, i);
+ accDot = fma(v, c, accDot);
+ FloatVector x = v.sub(c);
+ x.intoArray(vector, i);
+ accMin = accMin.min(x);
+ accMax = accMax.max(x);
+ accSq = fma(x, x, accSq);
+ accSum = accSum.add(x);
+ }
+ // scalar tail
+ float dot = 0;
+ float min = accMin.reduceLanes(VectorOperators.MIN);
+ float max = accMax.reduceLanes(VectorOperators.MAX);
+ float sumSq = 0;
+ float sum = 0;
+ for (; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot + sumLanes(accDot);
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq + sumLanes(accSq);
+ stats[4] = sum + sumLanes(accSum);
+ }
+
+ // k * k is at most 255^2, so an int lane can sum about 33K of them before it overflows. Below
+ // 2^16 dims, no lane gets that many.
+ private static final int OSQ_GRID_STATS_MAX_DIMS = 1 << 16;
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ if (vector.length >= OSQ_GRID_STATS_MAX_DIMS) {
+ DefaultVectorUtilSupport.osqGridStatsImpl(vector, lower, upper, points, stats);
+ return;
+ }
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ IntVector accK = IntVector.zero(INT_SPECIES);
+ IntVector accKK = IntVector.zero(INT_SPECIES);
+ FloatVector accXK = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accXD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accDD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accX = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector x = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ // Not fma, so k matches the scalar version.
+ FloatVector t = x.max(lower).min(upper).sub(lower).mul(stepInv).add(0.5f);
+ IntVector k = (IntVector) t.convert(VectorOperators.F2I, 0);
+ FloatVector kf = (FloatVector) k.convert(VectorOperators.I2F, 0);
+ FloatVector d = x.sub(kf.mul(step).add(lower));
+ accK = accK.add(k);
+ accKK = accKK.add(k.mul(k));
+ accXK = fma(x, kf, accXK);
+ accXD = fma(x, d, accXD);
+ accDD = fma(d, d, accDD);
+ accX = accX.add(x);
+ }
+ long sumK = accK.reduceLanesToLong(ADD);
+ long sumKK = accKK.reduceLanesToLong(ADD);
+ double sumXK = sumLanes(accXK);
+ double sumXD = sumLanes(accXD);
+ double sumDD = sumLanes(accDD);
+ double sumX = sumLanes(accX);
+ // scalar tail
+ for (; i < vector.length; i++) {
+ float x = vector[i];
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
Review Comment:
Good idea, will do in next commit!
##########
lucene/core/src/java/org/apache/lucene/util/VectorUtil.java:
##########
@@ -598,6 +598,52 @@ public static float recalculateOffset(
vector, oldAlpha, oldMinQuantile, scale, alpha, minQuantile, maxQuantile);
}
+ /**
+ * Subtracts {@code centroid} from {@code vector} in place, for the optimized scalar quantizer,
+ * and writes into {@code stats} the dot product of the original vector with {@code centroid},
+ * then the min, max, sum of squares and sum of the result.
+ */
+ public static void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ if (vector.length != centroid.length) {
+ throw new IllegalArgumentException(
+ "vector dimensions differ: " + vector.length + "!=" + centroid.length);
+ }
+ if (stats.length < 5) {
Review Comment:
Will do in next commit!
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
Review Comment:
Not my area of expertise, so if you think it's valid I can change it. Let me know what you think.
I actually ran JMH against this before the PR was finished.
`reduceLanes(ADD)` adds the lanes in a different order before and after C2 compiles the method, so the same vector can get different quantized values depending on JIT warm-up: 5 force merges of the same 1-bit index wrote 3 different `.veq` files.
| scalarQuantizeVector ops/ms, 2 runs | reduceLanes(ADD) | sumLanes |
|---|---:|---:|
| 1024d | 129.6 / 130.2 | 129.2 / 130.4 |
| 4096d | 30.9 / 31.2 | 30.9 / 30.8 |
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/VectorUtilBenchmark.java:
##########
@@ -304,6 +321,20 @@ public byte[] binaryHalfByteUnpackVector() {
return halfBytesUnpackDest;
}
+ // scalarQuantize centers its input in place, so each call copies the next vector first.
+ @Benchmark
+ public OptimizedScalarQuantizer.QuantizationResult scalarQuantizeScalar() {
+ System.arraycopy(quantizeVectors[quantizeNext++ & 63], 0, quantizeScratch, 0, size);
+ return quantizer.scalarQuantize(quantizeScratch, quantizeDest, (byte) 4, floatsB);
Review Comment:
Done in the next commit. Vectors are centered in setup with a zero centroid, so there's no copy, and each call is checked against the setup result for that 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
Re: [PR] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "slow-J (via GitHub) via issues" <is...@lucene.apache.org>.
slow-J commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4525008951
##########
lucene/core/src/java/org/apache/lucene/util/VectorUtil.java:
##########
@@ -598,6 +598,62 @@ public static float recalculateOffset(
vector, oldAlpha, oldMinQuantile, scale, alpha, minQuantile, maxQuantile);
}
+ /**
+ * Subtracts {@code centroid} from {@code vector} in place, for the optimized scalar quantizer,
+ * and writes into {@code stats} the dot product of the original vector with {@code centroid},
+ * then the min, max, sum of squares and sum of the result, and the sum of its squared differences
+ * from its mean.
+ *
+ * @lucene.experimental
+ */
+ public static void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ if (vector.length != centroid.length) {
+ throw new IllegalArgumentException(
+ "vector dimensions differ: " + vector.length + "!=" + centroid.length);
+ }
+ if (stats.length != 6) {
+ throw new IllegalArgumentException("stats must have 6 entries: " + stats.length);
+ }
+ IMPL.osqCenter(vector, centroid, stats);
+ }
+
+ /**
+ * Computes the sums that the optimized scalar quantizer's interval search needs for one interval.
+ * Each value {@code x} of {@code vector}, limited to {@code [lower, upper]}, is rounded half up
+ * to one of {@code points} levels {@code k}, which dequantizes to {@code x'}. Writes the sums of
+ * k, k * k, x * k, x * (x - x') and (x - x') * (x - x') into {@code stats}.
+ *
+ * @lucene.experimental
+ */
+ public static void osqGridStats(
+ float[] vector, float lower, float upper, int points, double[] stats) {
+ if (points < 2 || points > 256) {
+ throw new IllegalArgumentException("points must be in [2, 256]: " + points);
+ }
+ if (stats.length != 5) {
+ throw new IllegalArgumentException("stats must have 5 entries: " + stats.length);
+ }
+ assert lower <= upper : lower + " > " + upper;
Review Comment:
Good catch, I'll remove it!
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "kaivalnp (via GitHub) via issues" <is...@lucene.apache.org>.
kaivalnp commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4447066163
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -459,6 +459,80 @@ private float quantizeFloat(float v, byte[] dest, int destIndex) {
}
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ float dot = 0;
+ float min = Float.MAX_VALUE;
+ float max = -Float.MAX_VALUE;
+ float sumSq = 0;
+ float sum = 0;
+ for (int i = 0; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot;
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq;
+ stats[4] = sum;
+ }
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ osqGridStatsImpl(vector, lower, upper, points, stats);
+ }
+
+ static void osqGridStatsImpl(
+ float[] vector, float lower, float upper, int points, double[] stats) {
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ long sumK = 0;
+ long sumKK = 0;
+ double sumXK = 0;
+ double sumXD = 0;
+ double sumDD = 0;
+ double sumX = 0;
+ for (float x : vector) {
+ // Adds 0.5 and truncates, as Math.round is costly to match in the Panama version.
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
+ stats[0] = sumK;
+ stats[1] = sumKK;
+ stats[2] = sumXK;
+ stats[3] = sumXD;
+ stats[4] = sumDD;
+ stats[5] = sumX;
+ }
+
+ @Override
+ public int osqAssign(float[] vector, float lower, float upper, float step, byte[] dest) {
+ return osqAssignImpl(vector, 0, lower, upper, step, dest);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static int osqAssignImpl(
+ float[] vector, int start, float lower, float upper, float step, byte[] dest) {
+ int sum = 0;
+ for (int i = start; i < vector.length; i++) {
+ int k = Math.round((Math.min(Math.max(vector[i], lower), upper) - lower) / step);
Review Comment:
Ah nice catch! So if `lower = +0f` and `upper = -0f`, the assertions won't be triggered, but `Math.clamp` will throw -- in that case keeping it as `min(max(...))` looks okay to me.
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4415952295
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -459,6 +459,80 @@ private float quantizeFloat(float v, byte[] dest, int destIndex) {
}
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ float dot = 0;
+ float min = Float.MAX_VALUE;
+ float max = -Float.MAX_VALUE;
+ float sumSq = 0;
+ float sum = 0;
+ for (int i = 0; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot;
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq;
+ stats[4] = sum;
+ }
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ osqGridStatsImpl(vector, lower, upper, points, stats);
+ }
+
+ static void osqGridStatsImpl(
+ float[] vector, float lower, float upper, int points, double[] stats) {
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ long sumK = 0;
+ long sumKK = 0;
+ double sumXK = 0;
+ double sumXD = 0;
+ double sumDD = 0;
+ double sumX = 0;
+ for (float x : vector) {
+ // Adds 0.5 and truncates, as Math.round is costly to match in the Panama version.
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
+ stats[0] = sumK;
+ stats[1] = sumKK;
+ stats[2] = sumXK;
+ stats[3] = sumXD;
+ stats[4] = sumDD;
+ stats[5] = sumX;
+ }
+
+ @Override
+ public int osqAssign(float[] vector, float lower, float upper, float step, byte[] dest) {
+ return osqAssignImpl(vector, 0, lower, upper, step, dest);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static int osqAssignImpl(
+ float[] vector, int start, float lower, float upper, float step, byte[] dest) {
+ int sum = 0;
+ for (int i = start; i < vector.length; i++) {
+ int k = Math.round((Math.min(Math.max(vector[i], lower), upper) - lower) / step);
Review Comment:
Can we use `Math.clamp` instead of `Math.min(Math.max(...`?
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
Review Comment:
IMO we can accept the arbitrary order of floating point additions here, and use the more performant `reduceLanes(ADD)`.
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
+
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ FloatVector accDot = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accMin = FloatVector.broadcast(FLOAT_SPECIES, Float.MAX_VALUE);
+ FloatVector accMax = FloatVector.broadcast(FLOAT_SPECIES, -Float.MAX_VALUE);
+ FloatVector accSq = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accSum = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector v = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ FloatVector c = FloatVector.fromArray(FLOAT_SPECIES, centroid, i);
+ accDot = fma(v, c, accDot);
+ FloatVector x = v.sub(c);
+ x.intoArray(vector, i);
+ accMin = accMin.min(x);
+ accMax = accMax.max(x);
+ accSq = fma(x, x, accSq);
+ accSum = accSum.add(x);
+ }
+ // scalar tail
+ float dot = 0;
+ float min = accMin.reduceLanes(VectorOperators.MIN);
+ float max = accMax.reduceLanes(VectorOperators.MAX);
+ float sumSq = 0;
+ float sum = 0;
+ for (; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot + sumLanes(accDot);
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq + sumLanes(accSq);
+ stats[4] = sum + sumLanes(accSum);
+ }
+
+ // k * k is at most 255^2, so an int lane can sum about 33K of them before it overflows. Below
+ // 2^16 dims, no lane gets that many.
+ private static final int OSQ_GRID_STATS_MAX_DIMS = 1 << 16;
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ if (vector.length >= OSQ_GRID_STATS_MAX_DIMS) {
+ DefaultVectorUtilSupport.osqGridStatsImpl(vector, lower, upper, points, stats);
+ return;
+ }
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ IntVector accK = IntVector.zero(INT_SPECIES);
+ IntVector accKK = IntVector.zero(INT_SPECIES);
+ FloatVector accXK = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accXD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accDD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accX = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector x = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ // Not fma, so k matches the scalar version.
+ FloatVector t = x.max(lower).min(upper).sub(lower).mul(stepInv).add(0.5f);
+ IntVector k = (IntVector) t.convert(VectorOperators.F2I, 0);
+ FloatVector kf = (FloatVector) k.convert(VectorOperators.I2F, 0);
+ FloatVector d = x.sub(kf.mul(step).add(lower));
+ accK = accK.add(k);
+ accKK = accKK.add(k.mul(k));
+ accXK = fma(x, kf, accXK);
+ accXD = fma(x, d, accXD);
+ accDD = fma(d, d, accDD);
+ accX = accX.add(x);
+ }
+ long sumK = accK.reduceLanesToLong(ADD);
+ long sumKK = accKK.reduceLanesToLong(ADD);
+ double sumXK = sumLanes(accXK);
+ double sumXD = sumLanes(accXD);
+ double sumDD = sumLanes(accDD);
+ double sumX = sumLanes(accX);
+ // scalar tail
+ for (; i < vector.length; i++) {
+ float x = vector[i];
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
+ stats[0] = sumK;
+ stats[1] = sumKK;
+ stats[2] = sumXK;
+ stats[3] = sumXD;
+ stats[4] = sumDD;
+ stats[5] = sumX;
+ }
+
+ @Override
+ public int osqAssign(float[] vector, float lower, float upper, float step, byte[] dest) {
+ // The vector loop converts levels with F2I, so it needs every level in [0, 2^31).
+ float maxLevel = (upper - lower) / step;
+ if ((maxLevel > 0 && maxLevel < 0x1p31f) == false) {
+ return DefaultVectorUtilSupport.osqAssignImpl(vector, 0, lower, upper, step, dest);
+ }
+ IntVector sums = IntVector.zero(INT_SPECIES);
+ final int lanes = FLOAT_SPECIES.length();
+ // Four int vectors of levels fill one byte vector.
+ final int bound = BYTE_SPECIES_FULL.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += BYTE_SPECIES_FULL.length()) {
+ ByteVector out = ByteVector.zero(BYTE_SPECIES_FULL);
+ for (int part = 0; part < 4; part++) {
+ FloatVector x = FloatVector.fromArray(FLOAT_SPECIES, vector, i + part * lanes);
+ FloatVector t = x.max(lower).min(upper).sub(lower).div(step);
+ // Same as Math.round(t): truncate, then add 1 when twice the fraction truncates to 1. NaN
+ // converts to 0, as in Math.round.
+ IntVector k = (IntVector) t.convert(VectorOperators.F2I, 0);
+ FloatVector frac = t.sub((FloatVector) k.convert(VectorOperators.I2F, 0));
+ k = k.add((IntVector) frac.add(frac).convert(VectorOperators.F2I, 0));
Review Comment:
If we're looking for `k = Math.round(t)` where `t` is non-negative, I wonder if we can simplify this to `k = t.add(0.5f).convert(VectorOperators.F2I, 0)`?
I see `osqGridStats` already does this..
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/NativeVectorUtilSupport.java:
##########
@@ -571,6 +571,21 @@ public float recalculateScalarQuantizationOffset(
vector.length);
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ delegateVectorUtilSupport.osqCenter(vector, centroid, stats);
Review Comment:
Should we have the same `invokeOrDelegate` pattern here?
##########
lucene/core/src/java/org/apache/lucene/util/quantization/OptimizedScalarQuantizer.java:
##########
@@ -192,25 +176,15 @@ public QuantizationResult scalarQuantize(
assert bits > 0 && bits <= 8;
float[] intervalScratch = new float[2];
int points = 1 << bits;
- double vecMean = 0;
- double vecVar = 0;
- float norm2 = 0;
- float centroidDot = 0;
- float min = Float.MAX_VALUE;
- float max = -Float.MAX_VALUE;
- for (int i = 0; i < vector.length; ++i) {
- if (similarityFunction != EUCLIDEAN) {
- centroidDot += vector[i] * centroid[i];
- }
- vector[i] = vector[i] - centroid[i];
- min = Math.min(min, vector[i]);
- max = Math.max(max, vector[i]);
- norm2 += (vector[i] * vector[i]);
- double delta = vector[i] - vecMean;
- vecMean += delta / (i + 1);
- vecVar += delta * (vector[i] - vecMean);
- }
- vecVar /= vector.length;
+ float[] centerStats = new float[5];
+ VectorUtil.osqCenter(vector, centroid, centerStats);
+ float centroidDot = centerStats[0];
+ float min = centerStats[1];
+ float max = centerStats[2];
+ float norm2 = centerStats[3];
+ double vecMean = centerStats[4] / (double) vector.length;
+ // Rounding can push the mean of squares minus the squared mean just below zero.
+ double vecVar = Math.max(0, norm2 / (double) vector.length - vecMean * vecMean);
Review Comment:
Earlier, `vecVar` was computed using Welford's algorithm -- I wonder if this simpler version can degrade for some datasets?
I don't have a concrete example here, but should we measure a SIMD version of the original algorithm too? (and keep using that if not too costly)
##########
lucene/core/src/java25/org/apache/lucene/internal/vectorization/PanamaVectorUtilSupport.java:
##########
@@ -1584,6 +1584,151 @@ public float recalculateScalarQuantizationOffset(
return correction;
}
+ // reduceLanes(ADD) leaves the order of the additions open, and it adds in a different order
+ // before C2 compiles it than after, so the codes would depend on JIT state.
+ // Adding the lanes in order keeps them the same.
+ private static float sumLanes(FloatVector v) {
+ float sum = 0;
+ for (int i = 0; i < v.length(); i++) {
+ sum += v.lane(i);
+ }
+ return sum;
+ }
+
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ FloatVector accDot = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accMin = FloatVector.broadcast(FLOAT_SPECIES, Float.MAX_VALUE);
+ FloatVector accMax = FloatVector.broadcast(FLOAT_SPECIES, -Float.MAX_VALUE);
+ FloatVector accSq = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accSum = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector v = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ FloatVector c = FloatVector.fromArray(FLOAT_SPECIES, centroid, i);
+ accDot = fma(v, c, accDot);
+ FloatVector x = v.sub(c);
+ x.intoArray(vector, i);
+ accMin = accMin.min(x);
+ accMax = accMax.max(x);
+ accSq = fma(x, x, accSq);
+ accSum = accSum.add(x);
+ }
+ // scalar tail
+ float dot = 0;
+ float min = accMin.reduceLanes(VectorOperators.MIN);
+ float max = accMax.reduceLanes(VectorOperators.MAX);
+ float sumSq = 0;
+ float sum = 0;
+ for (; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot + sumLanes(accDot);
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq + sumLanes(accSq);
+ stats[4] = sum + sumLanes(accSum);
+ }
+
+ // k * k is at most 255^2, so an int lane can sum about 33K of them before it overflows. Below
+ // 2^16 dims, no lane gets that many.
+ private static final int OSQ_GRID_STATS_MAX_DIMS = 1 << 16;
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ if (vector.length >= OSQ_GRID_STATS_MAX_DIMS) {
+ DefaultVectorUtilSupport.osqGridStatsImpl(vector, lower, upper, points, stats);
+ return;
+ }
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ IntVector accK = IntVector.zero(INT_SPECIES);
+ IntVector accKK = IntVector.zero(INT_SPECIES);
+ FloatVector accXK = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accXD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accDD = FloatVector.zero(FLOAT_SPECIES);
+ FloatVector accX = FloatVector.zero(FLOAT_SPECIES);
+ final int bound = FLOAT_SPECIES.loopBound(vector.length);
+ int i = 0;
+ for (; i < bound; i += FLOAT_SPECIES.length()) {
+ FloatVector x = FloatVector.fromArray(FLOAT_SPECIES, vector, i);
+ // Not fma, so k matches the scalar version.
+ FloatVector t = x.max(lower).min(upper).sub(lower).mul(stepInv).add(0.5f);
+ IntVector k = (IntVector) t.convert(VectorOperators.F2I, 0);
+ FloatVector kf = (FloatVector) k.convert(VectorOperators.I2F, 0);
+ FloatVector d = x.sub(kf.mul(step).add(lower));
+ accK = accK.add(k);
+ accKK = accKK.add(k.mul(k));
+ accXK = fma(x, kf, accXK);
+ accXD = fma(x, d, accXD);
+ accDD = fma(d, d, accDD);
+ accX = accX.add(x);
+ }
+ long sumK = accK.reduceLanesToLong(ADD);
+ long sumKK = accKK.reduceLanesToLong(ADD);
+ double sumXK = sumLanes(accXK);
+ double sumXD = sumLanes(accXD);
+ double sumDD = sumLanes(accDD);
+ double sumX = sumLanes(accX);
+ // scalar tail
+ for (; i < vector.length; i++) {
+ float x = vector[i];
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
Review Comment:
This appears to be a duplicate of the non-SIMD version, should we refactor into a reusable static method? (same for `osqCenter`)
##########
lucene/core/src/java/org/apache/lucene/util/VectorUtil.java:
##########
@@ -598,6 +598,52 @@ public static float recalculateOffset(
vector, oldAlpha, oldMinQuantile, scale, alpha, minQuantile, maxQuantile);
}
+ /**
+ * Subtracts {@code centroid} from {@code vector} in place, for the optimized scalar quantizer,
+ * and writes into {@code stats} the dot product of the original vector with {@code centroid},
+ * then the min, max, sum of squares and sum of the result.
+ */
+ public static void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ if (vector.length != centroid.length) {
+ throw new IllegalArgumentException(
+ "vector dimensions differ: " + vector.length + "!=" + centroid.length);
+ }
+ if (stats.length < 5) {
Review Comment:
Can we make these checks stricter? (i.e. `== 5`)
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/VectorUtilBenchmark.java:
##########
@@ -304,6 +321,20 @@ public byte[] binaryHalfByteUnpackVector() {
return halfBytesUnpackDest;
}
+ // scalarQuantize centers its input in place, so each call copies the next vector first.
+ @Benchmark
+ public OptimizedScalarQuantizer.QuantizationResult scalarQuantizeScalar() {
+ System.arraycopy(quantizeVectors[quantizeNext++ & 63], 0, quantizeScratch, 0, size);
+ return quantizer.scalarQuantize(quantizeScratch, quantizeDest, (byte) 4, floatsB);
Review Comment:
Can we add some kind of check to ensure that the value produced is correct? I realize this is costlier to do than other functions like `binaryHalfByteDotProductSinglePackedScalar`, but might be helpful to catch errors early while tweaking the function.
Also, should the `arraycopy` be done outside the measurement?
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "kaivalnp (via GitHub)" <gi...@apache.org>.
kaivalnp commented on code in PR #16790:
URL: https://github.com/apache/lucene/pull/16790#discussion_r4426512903
##########
lucene/core/src/java/org/apache/lucene/internal/vectorization/DefaultVectorUtilSupport.java:
##########
@@ -459,6 +459,80 @@ private float quantizeFloat(float v, byte[] dest, int destIndex) {
}
}
+ @Override
+ public void osqCenter(float[] vector, float[] centroid, float[] stats) {
+ float dot = 0;
+ float min = Float.MAX_VALUE;
+ float max = -Float.MAX_VALUE;
+ float sumSq = 0;
+ float sum = 0;
+ for (int i = 0; i < vector.length; i++) {
+ dot += vector[i] * centroid[i];
+ float x = vector[i] - centroid[i];
+ vector[i] = x;
+ min = Math.min(min, x);
+ max = Math.max(max, x);
+ sumSq += x * x;
+ sum += x;
+ }
+ stats[0] = dot;
+ stats[1] = min;
+ stats[2] = max;
+ stats[3] = sumSq;
+ stats[4] = sum;
+ }
+
+ @Override
+ public void osqGridStats(float[] vector, float lower, float upper, int points, double[] stats) {
+ osqGridStatsImpl(vector, lower, upper, points, stats);
+ }
+
+ static void osqGridStatsImpl(
+ float[] vector, float lower, float upper, int points, double[] stats) {
+ float stepInv = (points - 1f) / (upper - lower);
+ float step = (upper - lower) / (points - 1f);
+ long sumK = 0;
+ long sumKK = 0;
+ double sumXK = 0;
+ double sumXD = 0;
+ double sumDD = 0;
+ double sumX = 0;
+ for (float x : vector) {
+ // Adds 0.5 and truncates, as Math.round is costly to match in the Panama version.
+ int k = (int) ((Math.min(Math.max(x, lower), upper) - lower) * stepInv + 0.5f);
+ float d = x - (lower + k * step);
+ sumK += k;
+ sumKK += (long) k * k;
+ sumXK += x * k;
+ sumXD += x * d;
+ sumDD += d * d;
+ sumX += x;
+ }
+ stats[0] = sumK;
+ stats[1] = sumKK;
+ stats[2] = sumXK;
+ stats[3] = sumXD;
+ stats[4] = sumDD;
+ stats[5] = sumX;
+ }
+
+ @Override
+ public int osqAssign(float[] vector, float lower, float upper, float step, byte[] dest) {
+ return osqAssignImpl(vector, 0, lower, upper, step, dest);
+ }
+
+ // The Panama version calls this for its tail, with start where its vector loop stopped.
+ static int osqAssignImpl(
+ float[] vector, int start, float lower, float upper, float step, byte[] dest) {
+ int sum = 0;
+ for (int i = start; i < vector.length; i++) {
+ int k = Math.round((Math.min(Math.max(vector[i], lower), upper) - lower) / step);
Review Comment:
I feel like we should be asserting on `lower <= upper` and `step >= 0`, is there a possible counter case?
--
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] Vectorize 3 loops in OptimizedScalarQuantizer [lucene]
Posted by "slow-J (via GitHub)" <gi...@apache.org>.
slow-J commented on PR #16790:
URL: https://github.com/apache/lucene/pull/16790#issuecomment-6524921967
Thanks for the review @kaivalnp ! Publishing a new commit shortly addressing most comments, will come back to the Welford's algorithm one.
Re-ran JMH too and it looks more performant with your input.
`scalarQuantizeVector`: ops/ms, main f7bcc0abd8 -> this PR
| size | main | this PR | ratio |
|---:|---:|---:|---:|
| 384 | 41.126 ± 1.232 | 375.719 ± 8.801 | 9.14x |
| 768 | 19.121 ± 0.617 | 185.526 ± 3.898 | 9.70x |
| 1024 | 13.892 ± 0.402 | 137.864 ± 3.340 | 9.92x |
| 4096 | 3.144 ± 0.091 | 33.293 ± 0.624 | 10.59x |
--
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