Sum up bit count with vector API
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
### Description
I played with vector API to sum up bit count. This pattern can be used in [bitset cardinality](https://github.com/apache/lucene/blob/dfff1e635805ffc61dd6029a8060e2635bfcbdb9/lucene/core/src/java/org/apache/lucene/util/FixedBitSet.java#L188C1-L200C4), [disjunction count](https://github.com/apache/lucene/blob/dfff1e635805ffc61dd6029a8060e2635bfcbdb9/lucene/core/src/java/org/apache/lucene/search/BooleanScorer.java#L187C1-L191C20), [IndexedDISI](https://github.com/apache/lucene/blob/dfff1e635805ffc61dd6029a8060e2635bfcbdb9/lucene/core/src/java/org/apache/lucene/codecs/lucene90/IndexedDISI.java#L605) etc.. Maybe worth implementing?
### Benchmark Result
> jdk 20.0.2
> AVX-512
```
Benchmark (size) Mode Cnt Score Error Units
BitcountBenchmark.bitCountNew 1024 thrpt 5 4.062 ± 0.004 ops/us
BitcountBenchmark.bitCountOld 1024 thrpt 5 1.195 ± 0.001 ops/us
```
### Code
```
@Benchmark
public int bitCountOld() {
int sum = 0;
for (int i = 0; i < size; i++) {
sum += Long.bitCount(longs[i]);
}
return sum;
}
@Benchmark
public int bitCountNew() {
int i = 0;
int res = 0;
int upperBound = PREFERRED_LONG_SPECIES.loopBound(longs.length);
LongVector acc = LongVector.zero(PREFERRED_LONG_SPECIES);
for (; i < upperBound; i += PREFERRED_LONG_SPECIES.length()) {
LongVector longVector = LongVector.fromArray(PREFERRED_LONG_SPECIES, longs, i);
LongVector bitCount = longVector.lanewise(VectorOperators.BIT_COUNT);
acc = acc.add(bitCount);
}
res += (int) acc.reduceLanes(VectorOperators.ADD);
for (; i < longs.length; i++) {
res += Long.bitCount(longs[i]);
}
return res;
}
```
Contributor guide
Research direction
Start by reading the cited bit-counting paths in FixedBitSet.java, BooleanScorer.java, and IndexedDISI.java, then compare them with the supplied vector benchmark. Determine which call sites can use the vector API and how the existing behavior should be validated. Done means an agreed implementation scope with performance evidence for the affected paths.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 32/100