You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "gf2121 (via GitHub)" <gi...@apache.org> on 2025/07/11 10:19:46 UTC
[PR] Optimize bitset to array [lucene]
gf2121 opened a new pull request, #14935:
URL: https://github.com/apache/lucene/pull/14935
This comes from https://github.com/apache/lucene/pull/14910#issuecomment-3059176116.
JMH shows:
1. `whileLoop`, `forloop`, `forLoopManualUnrolling` are having even performance, `whileLoop` is even slightly better. So in #14910, the speed-up i see (when vector module disabled or at mac m2) may come from some where else, like the consumer abstraction? JMH results can sometimes be not consistent with luceneutil as well. So it is hard to say.
```
BitsetToArrayBenchmark.whileLoop 5 thrpt 5 29.180 ± 0.568 ops/us
BitsetToArrayBenchmark.whileLoop 10 thrpt 5 23.460 ± 0.120 ops/us
BitsetToArrayBenchmark.whileLoop 20 thrpt 5 16.722 ± 0.330 ops/us
BitsetToArrayBenchmark.whileLoop 30 thrpt 5 13.006 ± 0.292 ops/us
BitsetToArrayBenchmark.whileLoop 40 thrpt 5 10.678 ± 0.195 ops/us
BitsetToArrayBenchmark.whileLoop 50 thrpt 5 9.035 ± 0.179 ops/us
BitsetToArrayBenchmark.whileLoop 60 thrpt 5 7.834 ± 0.060 ops/us
BitsetToArrayBenchmark.forLoop 5 thrpt 5 26.207 ± 0.642 ops/us
BitsetToArrayBenchmark.forLoop 10 thrpt 5 21.541 ± 0.281 ops/us
BitsetToArrayBenchmark.forLoop 20 thrpt 5 15.884 ± 0.310 ops/us
BitsetToArrayBenchmark.forLoop 30 thrpt 5 12.666 ± 0.013 ops/us
BitsetToArrayBenchmark.forLoop 40 thrpt 5 10.412 ± 0.180 ops/us
BitsetToArrayBenchmark.forLoop 50 thrpt 5 8.881 ± 0.091 ops/us
BitsetToArrayBenchmark.forLoop 60 thrpt 5 7.709 ± 0.222 ops/us
BitsetToArrayBenchmark.forLoopManualUnrolling 5 thrpt 5 25.848 ± 0.492 ops/us
BitsetToArrayBenchmark.forLoopManualUnrolling 10 thrpt 5 21.263 ± 0.354 ops/us
BitsetToArrayBenchmark.forLoopManualUnrolling 20 thrpt 5 15.842 ± 0.315 ops/us
BitsetToArrayBenchmark.forLoopManualUnrolling 30 thrpt 5 12.641 ± 0.053 ops/us
BitsetToArrayBenchmark.forLoopManualUnrolling 40 thrpt 5 10.489 ± 0.073 ops/us
BitsetToArrayBenchmark.forLoopManualUnrolling 50 thrpt 5 8.930 ± 0.178 ops/us
BitsetToArrayBenchmark.forLoopManualUnrolling 60 thrpt 5 7.816 ± 0.018 ops/us
```
2.
> By the way, we may want to look into other approaches for the scalar case. Since we only use bit sets in postings when many bits would be set, a linear scan should perform quite efficiently?
Inspired by this comment, i tried some dense optimization ways, as you can see `denseXXX` in jmh. The fastest is `denseBranchlessUnrolling` but i liked `denseBranchlessVectorized` better since it has less code.
```
Benchmark (bitCount) Mode Cnt Score Error Units
BitsetToArrayBenchmark.dense 5 thrpt 5 9.668 ± 0.054 ops/us
BitsetToArrayBenchmark.dense 10 thrpt 5 6.949 ± 0.068 ops/us
BitsetToArrayBenchmark.dense 20 thrpt 5 4.607 ± 0.057 ops/us
BitsetToArrayBenchmark.dense 30 thrpt 5 3.432 ± 0.037 ops/us
BitsetToArrayBenchmark.dense 40 thrpt 5 3.759 ± 0.036 ops/us
BitsetToArrayBenchmark.dense 50 thrpt 5 5.310 ± 0.016 ops/us
BitsetToArrayBenchmark.dense 60 thrpt 5 9.039 ± 0.240 ops/us
BitsetToArrayBenchmark.denseBranchLess 5 thrpt 5 13.464 ± 0.446 ops/us
BitsetToArrayBenchmark.denseBranchLess 10 thrpt 5 13.547 ± 0.250 ops/us
BitsetToArrayBenchmark.denseBranchLess 20 thrpt 5 13.531 ± 0.209 ops/us
BitsetToArrayBenchmark.denseBranchLess 30 thrpt 5 13.534 ± 0.336 ops/us
BitsetToArrayBenchmark.denseBranchLess 40 thrpt 5 13.530 ± 0.319 ops/us
BitsetToArrayBenchmark.denseBranchLess 50 thrpt 5 13.515 ± 0.330 ops/us
BitsetToArrayBenchmark.denseBranchLess 60 thrpt 5 13.526 ± 0.067 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 5 thrpt 5 15.753 ± 0.262 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 10 thrpt 5 15.709 ± 0.214 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 20 thrpt 5 15.811 ± 0.334 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 30 thrpt 5 15.752 ± 0.444 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 40 thrpt 5 15.861 ± 0.074 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 50 thrpt 5 15.630 ± 0.052 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 60 thrpt 5 15.789 ± 0.682 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 5 thrpt 5 14.884 ± 0.212 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 10 thrpt 5 14.931 ± 0.328 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 20 thrpt 5 14.953 ± 0.050 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 30 thrpt 5 15.011 ± 0.328 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 40 thrpt 5 14.961 ± 0.394 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 50 thrpt 5 14.927 ± 0.323 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 60 thrpt 5 14.924 ± 0.286 ops/us
BitsetToArrayBenchmark.denseInvert 5 thrpt 5 22.539 ± 0.523 ops/us
BitsetToArrayBenchmark.denseInvert 10 thrpt 5 16.538 ± 0.298 ops/us
BitsetToArrayBenchmark.denseInvert 20 thrpt 5 12.110 ± 0.228 ops/us
BitsetToArrayBenchmark.denseInvert 30 thrpt 5 10.344 ± 0.195 ops/us
BitsetToArrayBenchmark.denseInvert 40 thrpt 5 9.934 ± 0.201 ops/us
BitsetToArrayBenchmark.denseInvert 50 thrpt 5 10.192 ± 0.309 ops/us
BitsetToArrayBenchmark.denseInvert 60 thrpt 5 11.114 ± 0.387 ops/us
BitsetToArrayBenchmark.hybrid 5 thrpt 5 25.812 ± 0.503 ops/us
BitsetToArrayBenchmark.hybrid 10 thrpt 5 21.618 ± 0.062 ops/us
BitsetToArrayBenchmark.hybrid 20 thrpt 5 15.988 ± 0.018 ops/us
BitsetToArrayBenchmark.hybrid 30 thrpt 5 12.660 ± 0.027 ops/us
BitsetToArrayBenchmark.hybrid 40 thrpt 5 14.960 ± 0.201 ops/us
BitsetToArrayBenchmark.hybrid 50 thrpt 5 14.907 ± 0.407 ops/us
BitsetToArrayBenchmark.hybrid 60 thrpt 5 14.933 ± 0.364 ops/us
```
Benefited from this dense optimization, the luceneutil result seems even better than the AVX512 patch, so we may not need that any more!
```
TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff p-value
TermTitleSort 56.43 (3.2%) 54.92 (3.3%) -2.7% ( -8% - 3%) 0.030
AndHighOrMedMed 21.09 (1.7%) 20.91 (1.3%) -0.9% ( -3% - 2%) 0.140
CountAndHighMed 63.47 (2.6%) 63.16 (3.5%) -0.5% ( -6% - 5%) 0.672
TermDayOfYearSort 302.92 (1.2%) 301.46 (4.3%) -0.5% ( -5% - 5%) 0.685
PKLookup 76.25 (2.4%) 76.01 (1.4%) -0.3% ( -3% - 3%) 0.671
Fuzzy1 32.73 (2.4%) 32.66 (3.3%) -0.2% ( -5% - 5%) 0.849
Fuzzy2 30.22 (1.7%) 30.20 (2.7%) -0.1% ( -4% - 4%) 0.929
CombinedTerm 16.35 (2.1%) 16.34 (1.3%) -0.0% ( -3% - 3%) 0.976
Respell 27.75 (1.9%) 27.77 (2.7%) 0.1% ( -4% - 4%) 0.947
FilteredTerm 64.97 (1.9%) 65.02 (2.5%) 0.1% ( -4% - 4%) 0.920
CountFilteredPhrase 11.49 (1.1%) 11.51 (1.2%) 0.1% ( -2% - 2%) 0.820
Wildcard 48.76 (3.1%) 48.81 (3.1%) 0.1% ( -5% - 6%) 0.923
CountFilteredOrHighHigh 25.92 (0.8%) 25.96 (1.1%) 0.1% ( -1% - 2%) 0.685
Term 396.14 (5.7%) 396.74 (5.4%) 0.2% ( -10% - 11%) 0.943
IntNRQ 55.37 (2.1%) 55.48 (2.4%) 0.2% ( -4% - 4%) 0.815
TermMonthSort 1158.39 (3.1%) 1160.79 (5.3%) 0.2% ( -7% - 8%) 0.899
CountAndHighHigh 54.59 (1.5%) 54.72 (1.9%) 0.2% ( -3% - 3%) 0.713
FilteredOrHighHigh 16.18 (1.8%) 16.23 (2.9%) 0.3% ( -4% - 5%) 0.735
IntSet 149.94 (4.3%) 150.42 (4.7%) 0.3% ( -8% - 9%) 0.851
CountFilteredOrHighMed 31.52 (0.9%) 31.62 (1.3%) 0.3% ( -1% - 2%) 0.462
FilteredAndStopWords 12.58 (1.9%) 12.62 (1.9%) 0.4% ( -3% - 4%) 0.602
FilteredIntNRQ 54.87 (1.1%) 55.09 (1.9%) 0.4% ( -2% - 3%) 0.503
CountFilteredIntNRQ 24.33 (1.2%) 24.44 (1.5%) 0.4% ( -2% - 3%) 0.403
FilteredAndHighHigh 14.57 (1.8%) 14.64 (2.0%) 0.5% ( -3% - 4%) 0.513
FilteredPhrase 11.89 (2.4%) 11.95 (3.0%) 0.5% ( -4% - 6%) 0.624
Prefix3 79.10 (3.9%) 79.51 (4.5%) 0.5% ( -7% - 9%) 0.743
FilteredOrHighMed 49.42 (1.8%) 49.69 (3.2%) 0.5% ( -4% - 5%) 0.586
CombinedAndHighMed 28.15 (1.8%) 28.31 (2.7%) 0.6% ( -3% - 5%) 0.514
FilteredOr2Terms2StopWords 57.94 (1.9%) 58.27 (2.8%) 0.6% ( -3% - 5%) 0.520
FilteredPrefix3 73.30 (4.3%) 73.76 (4.8%) 0.6% ( -8% - 10%) 0.720
Phrase 9.22 (2.2%) 9.28 (2.9%) 0.6% ( -4% - 5%) 0.517
CountOrHighMed 83.12 (2.1%) 83.68 (2.4%) 0.7% ( -3% - 5%) 0.431
CountOrHighHigh 55.51 (0.9%) 55.89 (1.7%) 0.7% ( -1% - 3%) 0.173
FilteredOrStopWords 11.10 (2.1%) 11.18 (2.7%) 0.7% ( -3% - 5%) 0.426
FilteredAnd3Terms 80.17 (1.4%) 80.77 (2.9%) 0.7% ( -3% - 5%) 0.383
AndMedOrHighHigh 19.29 (3.1%) 19.43 (3.5%) 0.8% ( -5% - 7%) 0.545
CountTerm 2854.29 (2.9%) 2876.79 (3.9%) 0.8% ( -5% - 7%) 0.545
DismaxTerm 321.50 (4.0%) 324.09 (3.6%) 0.8% ( -6% - 8%) 0.575
FilteredOr3Terms 50.89 (1.3%) 51.31 (2.9%) 0.8% ( -3% - 5%) 0.327
CombinedOrHighMed 27.67 (1.7%) 27.93 (2.4%) 0.9% ( -3% - 5%) 0.238
OrHighMed 78.17 (8.1%) 78.97 (8.1%) 1.0% ( -13% - 18%) 0.737
DismaxOrHighMed 52.90 (4.7%) 53.87 (5.0%) 1.8% ( -7% - 12%) 0.317
TermDTSort 184.12 (1.8%) 187.60 (4.0%) 1.9% ( -3% - 7%) 0.109
FilteredAndHighMed 42.42 (2.3%) 43.24 (3.4%) 1.9% ( -3% - 7%) 0.084
AndHighMed 59.49 (6.4%) 60.73 (8.2%) 2.1% ( -11% - 17%) 0.452
OrHighRare 113.84 (5.1%) 116.29 (5.9%) 2.1% ( -8% - 13%) 0.303
And2Terms2StopWords 60.52 (4.4%) 62.04 (4.9%) 2.5% ( -6% - 12%) 0.154
DismaxOrHighHigh 37.38 (5.3%) 38.37 (5.7%) 2.7% ( -7% - 14%) 0.201
FilteredAnd2Terms2StopWords 61.89 (2.5%) 63.59 (3.8%) 2.7% ( -3% - 9%) 0.025
CombinedAndHighHigh 7.77 (1.9%) 7.99 (2.0%) 2.8% ( -1% - 6%) 0.000
CombinedOrHighHigh 7.66 (1.9%) 7.90 (2.3%) 3.1% ( -1% - 7%) 0.000
Or2Terms2StopWords 62.35 (4.3%) 64.34 (5.4%) 3.2% ( -6% - 13%) 0.086
AndHighHigh 26.50 (9.3%) 28.10 (10.7%) 6.0% ( -12% - 28%) 0.112
OrHighHigh 26.64 (8.6%) 28.27 (10.4%) 6.1% ( -11% - 27%) 0.089
Or3Terms 64.65 (4.8%) 68.88 (6.5%) 6.5% ( -4% - 18%) 0.002
And3Terms 69.90 (4.6%) 74.59 (6.7%) 6.7% ( -4% - 18%) 0.002
AndStopWords 10.30 (5.8%) 11.89 (9.2%) 15.4% ( 0% - 32%) 0.000
OrStopWords 10.83 (7.6%) 12.57 (10.1%) 16.0% ( -1% - 36%) 0.000
```
Another thing makes me not happy is the duplicate word-level code with `FixedBitSet#forEach`, but i have not had a good idea to reuse it for now.
--
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] Optimize bitset to array [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14935:
URL: https://github.com/apache/lucene/pull/14935#issuecomment-3062244403
This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.
--
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] Optimize bitset to array [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14935:
URL: https://github.com/apache/lucene/pull/14935#issuecomment-3061678159
This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.
--
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] Optimize bitset to array [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on code in PR #14935:
URL: https://github.com/apache/lucene/pull/14935#discussion_r2200926950
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/BitsetToArrayBenchmark.java:
##########
@@ -0,0 +1,379 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.benchmark.jmh;
+
+import java.util.SplittableRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.IntStream;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MICROSECONDS)
+@State(Scope.Benchmark)
+@Warmup(iterations = 3, time = 1)
+@Measurement(iterations = 5, time = 1)
+@Fork(
+ value = 1,
+ jvmArgsAppend = {"-Xmx1g", "-Xms1g", "-XX:+AlwaysPreTouch"})
+public class BitsetToArrayBenchmark {
+
+ private final SplittableRandom R = new SplittableRandom(4314123142L);
+
+ @Param({"5", "10", "20", "30", "40", "50", "60"})
+ int bitCount;
+
+ private final int[] scratch = new int[64];
+ private long word;
+ private int[] resultArray;
+ private int base;
+ private int offset;
+
+ @Setup(Level.Trial)
+ public void setup() {
+ base = R.nextInt(1000);
+ resultArray = new int[bitCount + Long.SIZE];
+ }
+
+ @Setup(Level.Invocation)
+ public void setupInvocation() {
+ word = 0L;
+ while (Long.bitCount(word) < bitCount) {
+ word |= 1L << R.nextInt(64);
+ }
+ offset = R.nextInt(64);
+ }
+
+ @Benchmark
+ public int whileLoop() {
+ return _whileLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoop() {
+ return _forLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoopManualUnrolling() {
+ return _forLoopManualUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int dense() {
+ return _dense(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLess() {
+ return _denseBranchLess(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessUnrolling() {
+ return _denseBranchLessUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessVectorized() {
+ return _denseBranchLessVectorized(word, resultArray, offset, base, scratch);
+ }
+
+ @Benchmark
+ public int denseInvert() {
+ return _denseInvert(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int hybrid() {
+ return _hybrid(word, resultArray, offset, base, scratch);
+ }
+
+ private static int _whileLoop(long word, int[] resultArray, int offset, int base) {
+ while (word != 0) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[offset++] = base + bit;
+ word ^= 1L << bit;
+ }
+ return offset;
+ }
+
+ private static int _forLoop(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ for (int i = offset; i < to; i++) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + bit;
+ word ^= 1L << bit;
+ }
+ return to;
+ }
+
+ private static int _forLoopManualUnrolling(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ int i = offset;
+
+ for (; i < to - 3; i += 4) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ for (; i < to; i++) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ return to;
+ }
+
+ private static int _dense(long word, int[] resultArray, int offset, int base) {
+ for (int i = 0; i < Long.SIZE; i++) {
+ if ((word & (1L << i)) != 0) {
+ resultArray[offset++] = base + i;
+ }
+ }
+ return offset;
+ }
+
+ private static int _denseBranchLess(long word, int[] resultArray, int offset, int base) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+ for (int i = 0; i < Integer.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += lWord & 1;
+ lWord >>>= 1;
+ }
+ for (int i = Integer.SIZE; i < Long.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += hWord & 1;
+ hWord >>>= 1;
+ }
+ return offset;
Review Comment:
Here is the result: (i'll try to check if it is really compiled to COMV after setting up the env on this new machine)
```
Benchmark (bitCount) Mode Cnt Score Error Units
BitsetToArrayBenchmark.denseBranchLess 5 thrpt 5 13.582 ± 0.183 ops/us
BitsetToArrayBenchmark.denseBranchLess 10 thrpt 5 13.485 ± 0.290 ops/us
BitsetToArrayBenchmark.denseBranchLess 20 thrpt 5 13.575 ± 0.094 ops/us
BitsetToArrayBenchmark.denseBranchLess 30 thrpt 5 13.570 ± 0.233 ops/us
BitsetToArrayBenchmark.denseBranchLess 40 thrpt 5 13.478 ± 0.110 ops/us
BitsetToArrayBenchmark.denseBranchLess 50 thrpt 5 13.577 ± 0.075 ops/us
BitsetToArrayBenchmark.denseBranchLess 60 thrpt 5 13.558 ± 0.090 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 5 thrpt 5 8.501 ± 0.154 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 10 thrpt 5 6.373 ± 0.065 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 20 thrpt 5 11.544 ± 0.057 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 30 thrpt 5 11.538 ± 0.014 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 40 thrpt 5 11.475 ± 0.284 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 50 thrpt 5 11.546 ± 0.081 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 60 thrpt 5 9.061 ± 0.213 ops/us
BitsetToArrayBenchmark.denseBranchLessNoIdentityArray 5 thrpt 5 15.190 ± 0.505 ops/us
BitsetToArrayBenchmark.denseBranchLessNoIdentityArray 10 thrpt 5 15.236 ± 0.358 ops/us
BitsetToArrayBenchmark.denseBranchLessNoIdentityArray 20 thrpt 5 15.217 ± 0.324 ops/us
BitsetToArrayBenchmark.denseBranchLessNoIdentityArray 30 thrpt 5 15.271 ± 0.217 ops/us
BitsetToArrayBenchmark.denseBranchLessNoIdentityArray 40 thrpt 5 15.267 ± 0.406 ops/us
BitsetToArrayBenchmark.denseBranchLessNoIdentityArray 50 thrpt 5 15.212 ± 0.345 ops/us
BitsetToArrayBenchmark.denseBranchLessNoIdentityArray 60 thrpt 5 15.242 ± 0.308 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 5 thrpt 5 15.702 ± 0.483 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 10 thrpt 5 15.778 ± 0.275 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 20 thrpt 5 15.730 ± 0.468 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 30 thrpt 5 15.730 ± 1.251 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 40 thrpt 5 15.748 ± 0.429 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 50 thrpt 5 15.842 ± 0.213 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 60 thrpt 5 15.817 ± 0.396 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 5 thrpt 5 14.905 ± 0.129 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 10 thrpt 5 14.922 ± 0.322 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 20 thrpt 5 14.828 ± 0.516 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 30 thrpt 5 14.686 ± 0.133 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 40 thrpt 5 14.881 ± 0.239 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 50 thrpt 5 14.978 ± 0.233 ops/us
BitsetToArrayBenchmark.denseBranchLessVectorized 60 thrpt 5 14.991 ± 0.338 ops/us
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Optimize bitset to array [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #14935:
URL: https://github.com/apache/lucene/pull/14935#discussion_r2201711227
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/BitsetToArrayBenchmark.java:
##########
@@ -0,0 +1,379 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.benchmark.jmh;
+
+import java.util.SplittableRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.IntStream;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MICROSECONDS)
+@State(Scope.Benchmark)
+@Warmup(iterations = 3, time = 1)
+@Measurement(iterations = 5, time = 1)
+@Fork(
+ value = 1,
+ jvmArgsAppend = {"-Xmx1g", "-Xms1g", "-XX:+AlwaysPreTouch"})
+public class BitsetToArrayBenchmark {
+
+ private final SplittableRandom R = new SplittableRandom(4314123142L);
+
+ @Param({"5", "10", "20", "30", "40", "50", "60"})
+ int bitCount;
+
+ private final int[] scratch = new int[64];
+ private long word;
+ private int[] resultArray;
+ private int base;
+ private int offset;
+
+ @Setup(Level.Trial)
+ public void setup() {
+ base = R.nextInt(1000);
+ resultArray = new int[bitCount + Long.SIZE];
+ }
+
+ @Setup(Level.Invocation)
+ public void setupInvocation() {
+ word = 0L;
+ while (Long.bitCount(word) < bitCount) {
+ word |= 1L << R.nextInt(64);
+ }
+ offset = R.nextInt(64);
+ }
+
+ @Benchmark
+ public int whileLoop() {
+ return _whileLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoop() {
+ return _forLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoopManualUnrolling() {
+ return _forLoopManualUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int dense() {
+ return _dense(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLess() {
+ return _denseBranchLess(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessUnrolling() {
+ return _denseBranchLessUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessVectorized() {
+ return _denseBranchLessVectorized(word, resultArray, offset, base, scratch);
+ }
+
+ @Benchmark
+ public int denseInvert() {
+ return _denseInvert(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int hybrid() {
+ return _hybrid(word, resultArray, offset, base, scratch);
+ }
+
+ private static int _whileLoop(long word, int[] resultArray, int offset, int base) {
+ while (word != 0) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[offset++] = base + bit;
+ word ^= 1L << bit;
+ }
+ return offset;
+ }
+
+ private static int _forLoop(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ for (int i = offset; i < to; i++) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + bit;
+ word ^= 1L << bit;
+ }
+ return to;
+ }
+
+ private static int _forLoopManualUnrolling(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ int i = offset;
+
+ for (; i < to - 3; i += 4) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ for (; i < to; i++) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ return to;
+ }
+
+ private static int _dense(long word, int[] resultArray, int offset, int base) {
+ for (int i = 0; i < Long.SIZE; i++) {
+ if ((word & (1L << i)) != 0) {
+ resultArray[offset++] = base + i;
+ }
+ }
+ return offset;
+ }
+
+ private static int _denseBranchLess(long word, int[] resultArray, int offset, int base) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+ for (int i = 0; i < Integer.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += lWord & 1;
+ lWord >>>= 1;
+ }
+ for (int i = Integer.SIZE; i < Long.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += hWord & 1;
+ hWord >>>= 1;
+ }
+ return offset;
Review Comment:
Thank you!
--
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] Optimize bitset to array [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14935:
URL: https://github.com/apache/lucene/pull/14935#issuecomment-3064579312
This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.
--
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] Optimize bitset to array [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14935:
URL: https://github.com/apache/lucene/pull/14935#issuecomment-3062971915
This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.
--
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] Optimize bitset to array [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on PR #14935:
URL: https://github.com/apache/lucene/pull/14935#issuecomment-3062225468
FWIW jmh result of the vectorized version (code in #14910)
```
Benchmark (bitCount) Mode Cnt Score Error Units
BitsetToArrayBenchmark.vectorize 5 thrpt 5 30.268 ? 0.096 ops/us
BitsetToArrayBenchmark.vectorize 10 thrpt 5 30.018 ? 1.609 ops/us
BitsetToArrayBenchmark.vectorize 20 thrpt 5 26.962 ? 1.625 ops/us
BitsetToArrayBenchmark.vectorize 30 thrpt 5 27.274 ? 0.078 ops/us
BitsetToArrayBenchmark.vectorize 40 thrpt 5 26.078 ? 2.184 ops/us
BitsetToArrayBenchmark.vectorize 50 thrpt 5 25.444 ? 0.964 ops/us
BitsetToArrayBenchmark.vectorize 60 thrpt 5 23.364 ? 0.062 ops/us
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Optimize bitset to array [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #14935:
URL: https://github.com/apache/lucene/pull/14935#discussion_r2202357715
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/BitSetUtil.java:
##########
@@ -0,0 +1,90 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene103;
+
+import java.util.Objects;
+import org.apache.lucene.util.FixedBitSet;
+
+class BitSetUtil {
+
+ final int denseBitsetToArray(FixedBitSet bitSet, int from, int to, int base, int[] array) {
Review Comment:
I believe that javadocs should say something about `array`'s size. It should hava a capacity of at least the number of bits in the range *plus one*, right? (since it always sets a value at `hOffset`, and then returns hOffset, without always incrementing it). Do we also need to change call sites to make sure that this array has enough capacity?
--
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] Optimize bitset to array [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 merged PR #14935:
URL: https://github.com/apache/lucene/pull/14935
--
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] Optimize bitset to array [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #14935:
URL: https://github.com/apache/lucene/pull/14935#discussion_r2202551786
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/BitSetUtil.java:
##########
@@ -0,0 +1,90 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene103;
+
+import java.util.Objects;
+import org.apache.lucene.util.FixedBitSet;
+
+class BitSetUtil {
+
+ final int denseBitsetToArray(FixedBitSet bitSet, int from, int to, int base, int[] array) {
Review Comment:
Let's add unit tests?
--
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] Optimize bitset to array [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on PR #14935:
URL: https://github.com/apache/lucene/pull/14935#issuecomment-3072341580
Nightly benchmarks caught up with the change. No slowdowns and a few good speedups! https://benchmarks.mikemccandless.com/OrStopWords.html I'll add an annotation.
--
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] Optimize bitset to array [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on code in PR #14935:
URL: https://github.com/apache/lucene/pull/14935#discussion_r2202681751
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/BitSetUtil.java:
##########
@@ -0,0 +1,90 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene103;
+
+import java.util.Objects;
+import org.apache.lucene.util.FixedBitSet;
+
+class BitSetUtil {
+
+ final int denseBitsetToArray(FixedBitSet bitSet, int from, int to, int base, int[] array) {
Review Comment:
Excellent catch! I fixed it and added a test.
--
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] Optimize bitset to array [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on code in PR #14935:
URL: https://github.com/apache/lucene/pull/14935#discussion_r2200932004
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/BitsetToArrayBenchmark.java:
##########
@@ -0,0 +1,379 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.benchmark.jmh;
+
+import java.util.SplittableRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.IntStream;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MICROSECONDS)
+@State(Scope.Benchmark)
+@Warmup(iterations = 3, time = 1)
+@Measurement(iterations = 5, time = 1)
+@Fork(
+ value = 1,
+ jvmArgsAppend = {"-Xmx1g", "-Xms1g", "-XX:+AlwaysPreTouch"})
+public class BitsetToArrayBenchmark {
+
+ private final SplittableRandom R = new SplittableRandom(4314123142L);
+
+ @Param({"5", "10", "20", "30", "40", "50", "60"})
+ int bitCount;
+
+ private final int[] scratch = new int[64];
+ private long word;
+ private int[] resultArray;
+ private int base;
+ private int offset;
+
+ @Setup(Level.Trial)
+ public void setup() {
+ base = R.nextInt(1000);
+ resultArray = new int[bitCount + Long.SIZE];
+ }
+
+ @Setup(Level.Invocation)
+ public void setupInvocation() {
+ word = 0L;
+ while (Long.bitCount(word) < bitCount) {
+ word |= 1L << R.nextInt(64);
+ }
+ offset = R.nextInt(64);
+ }
+
+ @Benchmark
+ public int whileLoop() {
+ return _whileLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoop() {
+ return _forLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoopManualUnrolling() {
+ return _forLoopManualUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int dense() {
+ return _dense(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLess() {
+ return _denseBranchLess(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessUnrolling() {
+ return _denseBranchLessUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessVectorized() {
+ return _denseBranchLessVectorized(word, resultArray, offset, base, scratch);
+ }
+
+ @Benchmark
+ public int denseInvert() {
+ return _denseInvert(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int hybrid() {
+ return _hybrid(word, resultArray, offset, base, scratch);
+ }
+
+ private static int _whileLoop(long word, int[] resultArray, int offset, int base) {
+ while (word != 0) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[offset++] = base + bit;
+ word ^= 1L << bit;
+ }
+ return offset;
+ }
+
+ private static int _forLoop(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ for (int i = offset; i < to; i++) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + bit;
+ word ^= 1L << bit;
+ }
+ return to;
+ }
+
+ private static int _forLoopManualUnrolling(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ int i = offset;
+
+ for (; i < to - 3; i += 4) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ for (; i < to; i++) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ return to;
+ }
+
+ private static int _dense(long word, int[] resultArray, int offset, int base) {
+ for (int i = 0; i < Long.SIZE; i++) {
+ if ((word & (1L << i)) != 0) {
+ resultArray[offset++] = base + i;
+ }
+ }
+ return offset;
+ }
+
+ private static int _denseBranchLess(long word, int[] resultArray, int offset, int base) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+ for (int i = 0; i < Integer.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += lWord & 1;
+ lWord >>>= 1;
+ }
+ for (int i = Integer.SIZE; i < Long.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += hWord & 1;
+ hWord >>>= 1;
+ }
+ return offset;
+ }
+
+ private static int _denseBranchLessUnrolling(long word, int[] resultArray, int offset, int base) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+
+ resultArray[offset] = base + 0;
+ offset += (lWord >>> 0) & 1;
+ resultArray[offset] = base + 1;
+ offset += (lWord >>> 1) & 1;
+ resultArray[offset] = base + 2;
+ offset += (lWord >>> 2) & 1;
+ resultArray[offset] = base + 3;
+ offset += (lWord >>> 3) & 1;
+ resultArray[offset] = base + 4;
+ offset += (lWord >>> 4) & 1;
+ resultArray[offset] = base + 5;
+ offset += (lWord >>> 5) & 1;
+ resultArray[offset] = base + 6;
+ offset += (lWord >>> 6) & 1;
+ resultArray[offset] = base + 7;
+ offset += (lWord >>> 7) & 1;
+ resultArray[offset] = base + 8;
+ offset += (lWord >>> 8) & 1;
+ resultArray[offset] = base + 9;
+ offset += (lWord >>> 9) & 1;
+ resultArray[offset] = base + 10;
+ offset += (lWord >>> 10) & 1;
+ resultArray[offset] = base + 11;
+ offset += (lWord >>> 11) & 1;
+ resultArray[offset] = base + 12;
+ offset += (lWord >>> 12) & 1;
+ resultArray[offset] = base + 13;
+ offset += (lWord >>> 13) & 1;
+ resultArray[offset] = base + 14;
+ offset += (lWord >>> 14) & 1;
+ resultArray[offset] = base + 15;
+ offset += (lWord >>> 15) & 1;
+ resultArray[offset] = base + 16;
+ offset += (lWord >>> 16) & 1;
+ resultArray[offset] = base + 17;
+ offset += (lWord >>> 17) & 1;
+ resultArray[offset] = base + 18;
+ offset += (lWord >>> 18) & 1;
+ resultArray[offset] = base + 19;
+ offset += (lWord >>> 19) & 1;
+ resultArray[offset] = base + 20;
+ offset += (lWord >>> 20) & 1;
+ resultArray[offset] = base + 21;
+ offset += (lWord >>> 21) & 1;
+ resultArray[offset] = base + 22;
+ offset += (lWord >>> 22) & 1;
+ resultArray[offset] = base + 23;
+ offset += (lWord >>> 23) & 1;
+ resultArray[offset] = base + 24;
+ offset += (lWord >>> 24) & 1;
+ resultArray[offset] = base + 25;
+ offset += (lWord >>> 25) & 1;
+ resultArray[offset] = base + 26;
+ offset += (lWord >>> 26) & 1;
+ resultArray[offset] = base + 27;
+ offset += (lWord >>> 27) & 1;
+ resultArray[offset] = base + 28;
+ offset += (lWord >>> 28) & 1;
+ resultArray[offset] = base + 29;
+ offset += (lWord >>> 29) & 1;
+ resultArray[offset] = base + 30;
+ offset += (lWord >>> 30) & 1;
+ resultArray[offset] = base + 31;
+ offset += (lWord >>> 31) & 1;
+
+ resultArray[offset] = base + 32;
+ offset += (hWord >>> 0) & 1;
+ resultArray[offset] = base + 33;
+ offset += (hWord >>> 1) & 1;
+ resultArray[offset] = base + 34;
+ offset += (hWord >>> 2) & 1;
+ resultArray[offset] = base + 35;
+ offset += (hWord >>> 3) & 1;
+ resultArray[offset] = base + 36;
+ offset += (hWord >>> 4) & 1;
+ resultArray[offset] = base + 37;
+ offset += (hWord >>> 5) & 1;
+ resultArray[offset] = base + 38;
+ offset += (hWord >>> 6) & 1;
+ resultArray[offset] = base + 39;
+ offset += (hWord >>> 7) & 1;
+ resultArray[offset] = base + 40;
+ offset += (hWord >>> 8) & 1;
+ resultArray[offset] = base + 41;
+ offset += (hWord >>> 9) & 1;
+ resultArray[offset] = base + 42;
+ offset += (hWord >>> 10) & 1;
+ resultArray[offset] = base + 43;
+ offset += (hWord >>> 11) & 1;
+ resultArray[offset] = base + 44;
+ offset += (hWord >>> 12) & 1;
+ resultArray[offset] = base + 45;
+ offset += (hWord >>> 13) & 1;
+ resultArray[offset] = base + 46;
+ offset += (hWord >>> 14) & 1;
+ resultArray[offset] = base + 47;
+ offset += (hWord >>> 15) & 1;
+ resultArray[offset] = base + 48;
+ offset += (hWord >>> 16) & 1;
+ resultArray[offset] = base + 49;
+ offset += (hWord >>> 17) & 1;
+ resultArray[offset] = base + 50;
+ offset += (hWord >>> 18) & 1;
+ resultArray[offset] = base + 51;
+ offset += (hWord >>> 19) & 1;
+ resultArray[offset] = base + 52;
+ offset += (hWord >>> 20) & 1;
+ resultArray[offset] = base + 53;
+ offset += (hWord >>> 21) & 1;
+ resultArray[offset] = base + 54;
+ offset += (hWord >>> 22) & 1;
+ resultArray[offset] = base + 55;
+ offset += (hWord >>> 23) & 1;
+ resultArray[offset] = base + 56;
+ offset += (hWord >>> 24) & 1;
+ resultArray[offset] = base + 57;
+ offset += (hWord >>> 25) & 1;
+ resultArray[offset] = base + 58;
+ offset += (hWord >>> 26) & 1;
+ resultArray[offset] = base + 59;
+ offset += (hWord >>> 27) & 1;
+ resultArray[offset] = base + 60;
+ offset += (hWord >>> 28) & 1;
+ resultArray[offset] = base + 61;
+ offset += (hWord >>> 29) & 1;
+ resultArray[offset] = base + 62;
+ offset += (hWord >>> 30) & 1;
+ resultArray[offset] = base + 63;
+ offset += (hWord >>> 31) & 1;
+
+ return offset;
+ }
+
+ static int[] IDENTITY = IntStream.range(0, 32).toArray();
+
+ private static int _denseBranchLessVectorized(
+ long word, int[] resultArray, int offset, int base, int[] scratch) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+
+ // vectorized loop
+ for (int i = 0; i < 32; i++) {
+ scratch[i] = (lWord >>> IDENTITY[i]) & 1;
+ scratch[i + 32] = (hWord >>> IDENTITY[i]) & 1;
Review Comment:
I remembered met performance issue when using `i` but as another comment `denseBranchLessNoIdentityArray` showing, it was my illusion. i'll rollback to `i`.
--
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] Optimize bitset to array [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on code in PR #14935:
URL: https://github.com/apache/lucene/pull/14935#discussion_r2201126320
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/BitsetToArrayBenchmark.java:
##########
@@ -0,0 +1,379 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.benchmark.jmh;
+
+import java.util.SplittableRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.IntStream;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MICROSECONDS)
+@State(Scope.Benchmark)
+@Warmup(iterations = 3, time = 1)
+@Measurement(iterations = 5, time = 1)
+@Fork(
+ value = 1,
+ jvmArgsAppend = {"-Xmx1g", "-Xms1g", "-XX:+AlwaysPreTouch"})
+public class BitsetToArrayBenchmark {
+
+ private final SplittableRandom R = new SplittableRandom(4314123142L);
+
+ @Param({"5", "10", "20", "30", "40", "50", "60"})
+ int bitCount;
+
+ private final int[] scratch = new int[64];
+ private long word;
+ private int[] resultArray;
+ private int base;
+ private int offset;
+
+ @Setup(Level.Trial)
+ public void setup() {
+ base = R.nextInt(1000);
+ resultArray = new int[bitCount + Long.SIZE];
+ }
+
+ @Setup(Level.Invocation)
+ public void setupInvocation() {
+ word = 0L;
+ while (Long.bitCount(word) < bitCount) {
+ word |= 1L << R.nextInt(64);
+ }
+ offset = R.nextInt(64);
+ }
+
+ @Benchmark
+ public int whileLoop() {
+ return _whileLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoop() {
+ return _forLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoopManualUnrolling() {
+ return _forLoopManualUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int dense() {
+ return _dense(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLess() {
+ return _denseBranchLess(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessUnrolling() {
+ return _denseBranchLessUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessVectorized() {
+ return _denseBranchLessVectorized(word, resultArray, offset, base, scratch);
+ }
+
+ @Benchmark
+ public int denseInvert() {
+ return _denseInvert(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int hybrid() {
+ return _hybrid(word, resultArray, offset, base, scratch);
+ }
+
+ private static int _whileLoop(long word, int[] resultArray, int offset, int base) {
+ while (word != 0) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[offset++] = base + bit;
+ word ^= 1L << bit;
+ }
+ return offset;
+ }
+
+ private static int _forLoop(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ for (int i = offset; i < to; i++) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + bit;
+ word ^= 1L << bit;
+ }
+ return to;
+ }
+
+ private static int _forLoopManualUnrolling(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ int i = offset;
+
+ for (; i < to - 3; i += 4) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ for (; i < to; i++) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ return to;
+ }
+
+ private static int _dense(long word, int[] resultArray, int offset, int base) {
+ for (int i = 0; i < Long.SIZE; i++) {
+ if ((word & (1L << i)) != 0) {
+ resultArray[offset++] = base + i;
+ }
+ }
+ return offset;
+ }
+
+ private static int _denseBranchLess(long word, int[] resultArray, int offset, int base) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+ for (int i = 0; i < Integer.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += lWord & 1;
+ lWord >>>= 1;
+ }
+ for (int i = Integer.SIZE; i < Long.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += hWord & 1;
+ hWord >>>= 1;
+ }
+ return offset;
Review Comment:
I find that it can be complied to `cmovne` when bitCount=20/30/40/50, but can not when bitCount=5/10/60.
--
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] Optimize bitset to array [lucene]
Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #14935:
URL: https://github.com/apache/lucene/pull/14935#discussion_r2200809196
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/BitsetToArrayBenchmark.java:
##########
@@ -0,0 +1,379 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.benchmark.jmh;
+
+import java.util.SplittableRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.IntStream;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MICROSECONDS)
+@State(Scope.Benchmark)
+@Warmup(iterations = 3, time = 1)
+@Measurement(iterations = 5, time = 1)
+@Fork(
+ value = 1,
+ jvmArgsAppend = {"-Xmx1g", "-Xms1g", "-XX:+AlwaysPreTouch"})
+public class BitsetToArrayBenchmark {
+
+ private final SplittableRandom R = new SplittableRandom(4314123142L);
+
+ @Param({"5", "10", "20", "30", "40", "50", "60"})
+ int bitCount;
+
+ private final int[] scratch = new int[64];
+ private long word;
+ private int[] resultArray;
+ private int base;
+ private int offset;
+
+ @Setup(Level.Trial)
+ public void setup() {
+ base = R.nextInt(1000);
+ resultArray = new int[bitCount + Long.SIZE];
+ }
+
+ @Setup(Level.Invocation)
+ public void setupInvocation() {
+ word = 0L;
+ while (Long.bitCount(word) < bitCount) {
+ word |= 1L << R.nextInt(64);
+ }
+ offset = R.nextInt(64);
+ }
+
+ @Benchmark
+ public int whileLoop() {
+ return _whileLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoop() {
+ return _forLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoopManualUnrolling() {
+ return _forLoopManualUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int dense() {
+ return _dense(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLess() {
+ return _denseBranchLess(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessUnrolling() {
+ return _denseBranchLessUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessVectorized() {
+ return _denseBranchLessVectorized(word, resultArray, offset, base, scratch);
+ }
+
+ @Benchmark
+ public int denseInvert() {
+ return _denseInvert(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int hybrid() {
+ return _hybrid(word, resultArray, offset, base, scratch);
+ }
+
+ private static int _whileLoop(long word, int[] resultArray, int offset, int base) {
+ while (word != 0) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[offset++] = base + bit;
+ word ^= 1L << bit;
+ }
+ return offset;
+ }
+
+ private static int _forLoop(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ for (int i = offset; i < to; i++) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + bit;
+ word ^= 1L << bit;
+ }
+ return to;
+ }
+
+ private static int _forLoopManualUnrolling(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ int i = offset;
+
+ for (; i < to - 3; i += 4) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ for (; i < to; i++) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ return to;
+ }
+
+ private static int _dense(long word, int[] resultArray, int offset, int base) {
+ for (int i = 0; i < Long.SIZE; i++) {
+ if ((word & (1L << i)) != 0) {
+ resultArray[offset++] = base + i;
+ }
+ }
+ return offset;
+ }
+
+ private static int _denseBranchLess(long word, int[] resultArray, int offset, int base) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+ for (int i = 0; i < Integer.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += lWord & 1;
+ lWord >>>= 1;
+ }
+ for (int i = Integer.SIZE; i < Long.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += hWord & 1;
+ hWord >>>= 1;
+ }
+ return offset;
+ }
+
+ private static int _denseBranchLessUnrolling(long word, int[] resultArray, int offset, int base) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+
+ resultArray[offset] = base + 0;
+ offset += (lWord >>> 0) & 1;
+ resultArray[offset] = base + 1;
+ offset += (lWord >>> 1) & 1;
+ resultArray[offset] = base + 2;
+ offset += (lWord >>> 2) & 1;
+ resultArray[offset] = base + 3;
+ offset += (lWord >>> 3) & 1;
+ resultArray[offset] = base + 4;
+ offset += (lWord >>> 4) & 1;
+ resultArray[offset] = base + 5;
+ offset += (lWord >>> 5) & 1;
+ resultArray[offset] = base + 6;
+ offset += (lWord >>> 6) & 1;
+ resultArray[offset] = base + 7;
+ offset += (lWord >>> 7) & 1;
+ resultArray[offset] = base + 8;
+ offset += (lWord >>> 8) & 1;
+ resultArray[offset] = base + 9;
+ offset += (lWord >>> 9) & 1;
+ resultArray[offset] = base + 10;
+ offset += (lWord >>> 10) & 1;
+ resultArray[offset] = base + 11;
+ offset += (lWord >>> 11) & 1;
+ resultArray[offset] = base + 12;
+ offset += (lWord >>> 12) & 1;
+ resultArray[offset] = base + 13;
+ offset += (lWord >>> 13) & 1;
+ resultArray[offset] = base + 14;
+ offset += (lWord >>> 14) & 1;
+ resultArray[offset] = base + 15;
+ offset += (lWord >>> 15) & 1;
+ resultArray[offset] = base + 16;
+ offset += (lWord >>> 16) & 1;
+ resultArray[offset] = base + 17;
+ offset += (lWord >>> 17) & 1;
+ resultArray[offset] = base + 18;
+ offset += (lWord >>> 18) & 1;
+ resultArray[offset] = base + 19;
+ offset += (lWord >>> 19) & 1;
+ resultArray[offset] = base + 20;
+ offset += (lWord >>> 20) & 1;
+ resultArray[offset] = base + 21;
+ offset += (lWord >>> 21) & 1;
+ resultArray[offset] = base + 22;
+ offset += (lWord >>> 22) & 1;
+ resultArray[offset] = base + 23;
+ offset += (lWord >>> 23) & 1;
+ resultArray[offset] = base + 24;
+ offset += (lWord >>> 24) & 1;
+ resultArray[offset] = base + 25;
+ offset += (lWord >>> 25) & 1;
+ resultArray[offset] = base + 26;
+ offset += (lWord >>> 26) & 1;
+ resultArray[offset] = base + 27;
+ offset += (lWord >>> 27) & 1;
+ resultArray[offset] = base + 28;
+ offset += (lWord >>> 28) & 1;
+ resultArray[offset] = base + 29;
+ offset += (lWord >>> 29) & 1;
+ resultArray[offset] = base + 30;
+ offset += (lWord >>> 30) & 1;
+ resultArray[offset] = base + 31;
+ offset += (lWord >>> 31) & 1;
+
+ resultArray[offset] = base + 32;
+ offset += (hWord >>> 0) & 1;
+ resultArray[offset] = base + 33;
+ offset += (hWord >>> 1) & 1;
+ resultArray[offset] = base + 34;
+ offset += (hWord >>> 2) & 1;
+ resultArray[offset] = base + 35;
+ offset += (hWord >>> 3) & 1;
+ resultArray[offset] = base + 36;
+ offset += (hWord >>> 4) & 1;
+ resultArray[offset] = base + 37;
+ offset += (hWord >>> 5) & 1;
+ resultArray[offset] = base + 38;
+ offset += (hWord >>> 6) & 1;
+ resultArray[offset] = base + 39;
+ offset += (hWord >>> 7) & 1;
+ resultArray[offset] = base + 40;
+ offset += (hWord >>> 8) & 1;
+ resultArray[offset] = base + 41;
+ offset += (hWord >>> 9) & 1;
+ resultArray[offset] = base + 42;
+ offset += (hWord >>> 10) & 1;
+ resultArray[offset] = base + 43;
+ offset += (hWord >>> 11) & 1;
+ resultArray[offset] = base + 44;
+ offset += (hWord >>> 12) & 1;
+ resultArray[offset] = base + 45;
+ offset += (hWord >>> 13) & 1;
+ resultArray[offset] = base + 46;
+ offset += (hWord >>> 14) & 1;
+ resultArray[offset] = base + 47;
+ offset += (hWord >>> 15) & 1;
+ resultArray[offset] = base + 48;
+ offset += (hWord >>> 16) & 1;
+ resultArray[offset] = base + 49;
+ offset += (hWord >>> 17) & 1;
+ resultArray[offset] = base + 50;
+ offset += (hWord >>> 18) & 1;
+ resultArray[offset] = base + 51;
+ offset += (hWord >>> 19) & 1;
+ resultArray[offset] = base + 52;
+ offset += (hWord >>> 20) & 1;
+ resultArray[offset] = base + 53;
+ offset += (hWord >>> 21) & 1;
+ resultArray[offset] = base + 54;
+ offset += (hWord >>> 22) & 1;
+ resultArray[offset] = base + 55;
+ offset += (hWord >>> 23) & 1;
+ resultArray[offset] = base + 56;
+ offset += (hWord >>> 24) & 1;
+ resultArray[offset] = base + 57;
+ offset += (hWord >>> 25) & 1;
+ resultArray[offset] = base + 58;
+ offset += (hWord >>> 26) & 1;
+ resultArray[offset] = base + 59;
+ offset += (hWord >>> 27) & 1;
+ resultArray[offset] = base + 60;
+ offset += (hWord >>> 28) & 1;
+ resultArray[offset] = base + 61;
+ offset += (hWord >>> 29) & 1;
+ resultArray[offset] = base + 62;
+ offset += (hWord >>> 30) & 1;
+ resultArray[offset] = base + 63;
+ offset += (hWord >>> 31) & 1;
+
+ return offset;
+ }
+
+ static int[] IDENTITY = IntStream.range(0, 32).toArray();
+
+ private static int _denseBranchLessVectorized(
+ long word, int[] resultArray, int offset, int base, int[] scratch) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+
+ // vectorized loop
+ for (int i = 0; i < 32; i++) {
+ scratch[i] = (lWord >>> IDENTITY[i]) & 1;
+ scratch[i + 32] = (hWord >>> IDENTITY[i]) & 1;
Review Comment:
Did it perform better with `IDENTITY[i]` than just `i`?
##########
lucene/benchmark-jmh/src/java/org/apache/lucene/benchmark/jmh/BitsetToArrayBenchmark.java:
##########
@@ -0,0 +1,379 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.benchmark.jmh;
+
+import java.util.SplittableRandom;
+import java.util.concurrent.TimeUnit;
+import java.util.stream.IntStream;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Warmup;
+
+@BenchmarkMode(Mode.Throughput)
+@OutputTimeUnit(TimeUnit.MICROSECONDS)
+@State(Scope.Benchmark)
+@Warmup(iterations = 3, time = 1)
+@Measurement(iterations = 5, time = 1)
+@Fork(
+ value = 1,
+ jvmArgsAppend = {"-Xmx1g", "-Xms1g", "-XX:+AlwaysPreTouch"})
+public class BitsetToArrayBenchmark {
+
+ private final SplittableRandom R = new SplittableRandom(4314123142L);
+
+ @Param({"5", "10", "20", "30", "40", "50", "60"})
+ int bitCount;
+
+ private final int[] scratch = new int[64];
+ private long word;
+ private int[] resultArray;
+ private int base;
+ private int offset;
+
+ @Setup(Level.Trial)
+ public void setup() {
+ base = R.nextInt(1000);
+ resultArray = new int[bitCount + Long.SIZE];
+ }
+
+ @Setup(Level.Invocation)
+ public void setupInvocation() {
+ word = 0L;
+ while (Long.bitCount(word) < bitCount) {
+ word |= 1L << R.nextInt(64);
+ }
+ offset = R.nextInt(64);
+ }
+
+ @Benchmark
+ public int whileLoop() {
+ return _whileLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoop() {
+ return _forLoop(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int forLoopManualUnrolling() {
+ return _forLoopManualUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int dense() {
+ return _dense(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLess() {
+ return _denseBranchLess(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessUnrolling() {
+ return _denseBranchLessUnrolling(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int denseBranchLessVectorized() {
+ return _denseBranchLessVectorized(word, resultArray, offset, base, scratch);
+ }
+
+ @Benchmark
+ public int denseInvert() {
+ return _denseInvert(word, resultArray, offset, base);
+ }
+
+ @Benchmark
+ public int hybrid() {
+ return _hybrid(word, resultArray, offset, base, scratch);
+ }
+
+ private static int _whileLoop(long word, int[] resultArray, int offset, int base) {
+ while (word != 0) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[offset++] = base + bit;
+ word ^= 1L << bit;
+ }
+ return offset;
+ }
+
+ private static int _forLoop(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ for (int i = offset; i < to; i++) {
+ int bit = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + bit;
+ word ^= 1L << bit;
+ }
+ return to;
+ }
+
+ private static int _forLoopManualUnrolling(long word, int[] resultArray, int offset, int base) {
+ int to = offset + Long.bitCount(word);
+ int i = offset;
+
+ for (; i < to - 3; i += 4) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ for (; i < to; i++) {
+ int ntz = Long.numberOfTrailingZeros(word);
+ resultArray[i] = base + ntz;
+ word ^= 1L << ntz;
+ }
+
+ return to;
+ }
+
+ private static int _dense(long word, int[] resultArray, int offset, int base) {
+ for (int i = 0; i < Long.SIZE; i++) {
+ if ((word & (1L << i)) != 0) {
+ resultArray[offset++] = base + i;
+ }
+ }
+ return offset;
+ }
+
+ private static int _denseBranchLess(long word, int[] resultArray, int offset, int base) {
+ int lWord = (int) word;
+ int hWord = (int) (word >>> 32);
+ for (int i = 0; i < Integer.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += lWord & 1;
+ lWord >>>= 1;
+ }
+ for (int i = Integer.SIZE; i < Long.SIZE; i++) {
+ resultArray[offset] = base + i;
+ offset += hWord & 1;
+ hWord >>>= 1;
+ }
+ return offset;
Review Comment:
Another way to make it branchless may be to try to get the compiler to use a cmov, e.g. I'm curious how something like this would perform:
```java
for (int j = 0; j < Long.SIZE; ++j) {
resultArray[offset] = base + j;
if ((word & (1L << j)) != 0L) { // hopefully compiles as cmov?
offset++;
}
}
```
--
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] Optimize bitset to array [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on PR #14935:
URL: https://github.com/apache/lucene/pull/14935#issuecomment-3064581110
I did some iteration locally and find out a way providing similar performance without `scratch` array (new code in `denseBranchLessParallel`).
```
Benchmark (bitCount) Mode Cnt Score Error Units
BitsetToArrayBenchmark.denseBranchLess 5 thrpt 5 13.582 ± 0.179 ops/us
BitsetToArrayBenchmark.denseBranchLess 10 thrpt 5 13.574 ± 0.034 ops/us
BitsetToArrayBenchmark.denseBranchLess 20 thrpt 5 13.543 ± 0.244 ops/us
BitsetToArrayBenchmark.denseBranchLess 30 thrpt 5 13.398 ± 0.249 ops/us
BitsetToArrayBenchmark.denseBranchLess 40 thrpt 5 13.524 ± 0.409 ops/us
BitsetToArrayBenchmark.denseBranchLess 50 thrpt 5 13.522 ± 0.434 ops/us
BitsetToArrayBenchmark.denseBranchLess 60 thrpt 5 13.575 ± 0.025 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 5 thrpt 5 8.508 ± 0.124 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 10 thrpt 5 6.374 ± 0.066 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 20 thrpt 5 11.519 ± 0.182 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 30 thrpt 5 11.496 ± 0.246 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 40 thrpt 5 11.521 ± 0.256 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 50 thrpt 5 11.501 ± 0.285 ops/us
BitsetToArrayBenchmark.denseBranchLessCmov 60 thrpt 5 9.102 ± 0.026 ops/us
BitsetToArrayBenchmark.denseBranchLessParallel 5 thrpt 5 15.238 ± 0.312 ops/us
BitsetToArrayBenchmark.denseBranchLessParallel 10 thrpt 5 15.268 ± 0.112 ops/us
BitsetToArrayBenchmark.denseBranchLessParallel 20 thrpt 5 15.278 ± 0.199 ops/us
BitsetToArrayBenchmark.denseBranchLessParallel 30 thrpt 5 15.269 ± 0.348 ops/us
BitsetToArrayBenchmark.denseBranchLessParallel 40 thrpt 5 15.182 ± 0.458 ops/us
BitsetToArrayBenchmark.denseBranchLessParallel 50 thrpt 5 15.287 ± 0.105 ops/us
BitsetToArrayBenchmark.denseBranchLessParallel 60 thrpt 5 15.312 ± 0.158 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 5 thrpt 5 15.727 ± 0.294 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 10 thrpt 5 15.852 ± 0.256 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 20 thrpt 5 15.815 ± 0.258 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 30 thrpt 5 15.738 ± 0.620 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 40 thrpt 5 15.821 ± 0.435 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 50 thrpt 5 15.806 ± 0.202 ops/us
BitsetToArrayBenchmark.denseBranchLessUnrolling 60 thrpt 5 15.483 ± 2.151 ops/us
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
Re: [PR] Optimize bitset to array [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #14935:
URL: https://github.com/apache/lucene/pull/14935#issuecomment-3063052843
This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.
--
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] Optimize bitset to array [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on code in PR #14935:
URL: https://github.com/apache/lucene/pull/14935#discussion_r2202681751
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene103/BitSetUtil.java:
##########
@@ -0,0 +1,90 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.codecs.lucene103;
+
+import java.util.Objects;
+import org.apache.lucene.util.FixedBitSet;
+
+class BitSetUtil {
+
+ final int denseBitsetToArray(FixedBitSet bitSet, int from, int to, int base, int[] array) {
Review Comment:
Excellent catch! I fixed it and added a test that can catch this.
--
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] Optimize bitset to array [lucene]
Posted by "gf2121 (via GitHub)" <gi...@apache.org>.
gf2121 commented on PR #14935:
URL: https://github.com/apache/lucene/pull/14935#issuecomment-3065989475
The luceneutil result sounds too good to be true for me, so i rechecked and found that this new branch contains https://github.com/apache/lucene/pull/14906 while baseline not, so the previous compare is unfair. Here is the correct one, sorry for the noise!
```
TaskQPS baseline StdDevQPS my_modified_version StdDev Pct diff p-value
CountFilteredPhrase 12.56 (1.1%) 12.57 (1.3%) 0.1% ( -2% - 2%) 0.833
Fuzzy1 35.40 (2.0%) 35.44 (2.4%) 0.1% ( -4% - 4%) 0.886
IntSet 159.97 (5.4%) 160.21 (5.4%) 0.2% ( -10% - 11%) 0.929
FilteredOrStopWords 12.18 (2.2%) 12.20 (1.7%) 0.2% ( -3% - 4%) 0.798
Fuzzy2 32.34 (2.0%) 32.40 (2.3%) 0.2% ( -4% - 4%) 0.798
FilteredAndStopWords 14.12 (1.8%) 14.15 (1.9%) 0.2% ( -3% - 3%) 0.692
CountFilteredOrHighMed 33.44 (0.8%) 33.53 (0.7%) 0.3% ( -1% - 1%) 0.249
CountOrHighHigh 65.91 (1.0%) 66.11 (1.3%) 0.3% ( -2% - 2%) 0.416
CountFilteredIntNRQ 25.03 (1.0%) 25.11 (1.0%) 0.3% ( -1% - 2%) 0.334
FilteredOrHighHigh 18.82 (1.7%) 18.89 (1.8%) 0.4% ( -3% - 3%) 0.511
CountFilteredOrHighHigh 28.01 (0.8%) 28.12 (0.7%) 0.4% ( -1% - 1%) 0.076
Phrase 10.22 (2.4%) 10.27 (2.5%) 0.5% ( -4% - 5%) 0.538
CountAndHighHigh 65.46 (1.2%) 65.78 (1.4%) 0.5% ( -2% - 3%) 0.227
FilteredPhrase 13.49 (2.1%) 13.55 (2.0%) 0.5% ( -3% - 4%) 0.458
CombinedTerm 17.05 (2.5%) 17.14 (2.6%) 0.5% ( -4% - 5%) 0.513
FilteredAndHighHigh 17.35 (1.4%) 17.44 (1.6%) 0.5% ( -2% - 3%) 0.261
CountAndHighMed 92.88 (1.3%) 93.43 (1.4%) 0.6% ( -2% - 3%) 0.173
FilteredOrHighMed 52.86 (2.4%) 53.17 (2.2%) 0.6% ( -3% - 5%) 0.409
FilteredAnd3Terms 110.52 (2.0%) 111.18 (2.1%) 0.6% ( -3% - 4%) 0.353
IntNRQ 57.31 (1.4%) 57.66 (1.6%) 0.6% ( -2% - 3%) 0.209
CountOrHighMed 97.32 (1.3%) 97.94 (1.5%) 0.6% ( -2% - 3%) 0.142
FilteredIntNRQ 56.84 (1.5%) 57.22 (1.6%) 0.7% ( -2% - 3%) 0.170
CombinedAndHighHigh 8.38 (2.1%) 8.45 (2.1%) 0.8% ( -3% - 5%) 0.254
FilteredAnd2Terms2StopWords 74.22 (3.3%) 74.79 (2.4%) 0.8% ( -4% - 6%) 0.408
FilteredOr3Terms 55.26 (2.2%) 55.72 (1.6%) 0.8% ( -2% - 4%) 0.173
Respell 28.72 (2.1%) 28.97 (2.1%) 0.9% ( -3% - 5%) 0.195
AndHighOrMedMed 21.84 (2.4%) 22.04 (2.2%) 0.9% ( -3% - 5%) 0.227
OrHighRare 121.45 (4.8%) 122.58 (5.1%) 0.9% ( -8% - 11%) 0.555
FilteredTerm 70.79 (1.9%) 71.46 (2.6%) 0.9% ( -3% - 5%) 0.187
And2Terms2StopWords 71.18 (4.5%) 71.85 (3.3%) 0.9% ( -6% - 9%) 0.447
CombinedOrHighHigh 8.22 (3.4%) 8.30 (3.2%) 1.0% ( -5% - 7%) 0.351
AndMedOrHighHigh 23.64 (3.0%) 23.87 (2.0%) 1.0% ( -3% - 6%) 0.216
FilteredAndHighMed 49.01 (2.4%) 49.50 (1.7%) 1.0% ( -3% - 5%) 0.129
FilteredOr2Terms2StopWords 61.95 (2.2%) 62.62 (1.8%) 1.1% ( -2% - 5%) 0.091
Or2Terms2StopWords 73.44 (4.6%) 74.31 (3.0%) 1.2% ( -6% - 9%) 0.331
CombinedAndHighMed 30.40 (2.6%) 30.77 (2.9%) 1.2% ( -4% - 6%) 0.166
FilteredPrefix3 80.79 (3.2%) 81.78 (4.0%) 1.2% ( -5% - 8%) 0.286
TermTitleSort 62.42 (2.5%) 63.18 (3.8%) 1.2% ( -4% - 7%) 0.229
DismaxOrHighMed 60.65 (3.9%) 61.40 (3.4%) 1.2% ( -5% - 8%) 0.286
CombinedOrHighMed 29.75 (3.5%) 30.14 (3.0%) 1.3% ( -4% - 7%) 0.203
TermDayOfYearSort 351.91 (2.8%) 356.71 (3.4%) 1.4% ( -4% - 7%) 0.165
CountTerm 3725.09 (4.9%) 3783.50 (5.3%) 1.6% ( -8% - 12%) 0.330
DismaxTerm 369.05 (3.9%) 374.93 (4.1%) 1.6% ( -6% - 10%) 0.210
Prefix3 86.00 (3.6%) 87.41 (4.5%) 1.6% ( -6% - 10%) 0.201
TermDTSort 208.45 (4.2%) 211.88 (4.6%) 1.6% ( -6% - 10%) 0.240
DismaxOrHighHigh 41.61 (5.3%) 42.32 (3.1%) 1.7% ( -6% - 10%) 0.210
And3Terms 94.46 (5.6%) 96.13 (3.4%) 1.8% ( -6% - 11%) 0.234
TermMonthSort 1553.66 (5.3%) 1581.95 (5.2%) 1.8% ( -8% - 13%) 0.277
Wildcard 51.46 (3.0%) 52.52 (2.9%) 2.1% ( -3% - 8%) 0.027
Or3Terms 84.97 (5.8%) 86.75 (3.4%) 2.1% ( -6% - 12%) 0.164
OrHighMed 91.63 (6.7%) 93.76 (3.0%) 2.3% ( -6% - 12%) 0.159
AndHighMed 76.48 (7.1%) 78.29 (2.9%) 2.4% ( -7% - 13%) 0.165
Term 448.90 (5.1%) 459.66 (4.6%) 2.4% ( -6% - 12%) 0.118
OrHighHigh 31.64 (8.9%) 32.63 (3.2%) 3.1% ( -8% - 16%) 0.135
AndHighHigh 31.54 (9.4%) 33.20 (2.9%) 5.3% ( -6% - 19%) 0.017
AndStopWords 11.89 (7.8%) 12.76 (4.0%) 7.3% ( -4% - 20%) 0.000
OrStopWords 12.40 (8.8%) 13.74 (3.6%) 10.8% ( -1% - 25%) 0.000
```
--
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