Explore opportunities for Vector/SIMD performance improvements
- Dominant language
- C#
- Stars
- 2.4k
- Forks
- 658
- Avg merge
- 3d 5h
- Merged PRs (30d)
- 9
Description
### Is there an existing issue for this?
- [x] I have searched the existing issues
### Is your feature request related to a problem? Please describe the problem.
.NET supports [`Vector`](https://learn.microsoft.com/en-us/dotnet/api/system.numerics.vector-1?view=net-10.0) (including back to `net462` via the [System.Numerics.Vectors NuGet package](https://www.nuget.org/packages/System.Numerics.Vectors#readme-body-tab)) and [SIMD intrinsics](https://learn.microsoft.com/en-us/dotnet/api/system.runtime.intrinsics?view=net-10.0) that have the potential to improve performance in some areas of Lucene.NET.
### Describe the solution you'd like
An initial analysis by Claude Code found the following areas as potentially being able to take advantage of Vector/SIMD.
## Tier 1: Actually worth doing
### `FixedBitSet` / `OpenBitSet` / `Int64BitSet` bulk bitwise ops
`Or`, `Xor`, `And`, and `AndNot` are textbook SIMD. `Vector` handles 4 longs/iteration on AVX2, 8 on AVX-512. These run in the hot path of conjunction/disjunction query execution when filters get materialized as bitsets, so it's not micro-benchmark theater. The scalar tail loop pattern is well-understood and low-risk.
### Cardinality / popcount (`BitUtil.Pop_Intersect`, `Pop_Union`, `Pop_AndNot`, `Pop_Xor`)
These already lean on `.PopCount()` (a JIT intrinsic), but the surrounding loop still walks `long[]` one word at a time computing `a[i] & b[i]` then popcounting. Vector256 AND/OR + a vectorized popcount (or AVX-512 VPOPCNTQ via Avx512.PopCount) is a well-trodden path. Directly speeds up faceting and `intersectionCount`-style filter selectivity checks.
## Tier 2: Plausible but with caveats
### Delta / prefix-sum decode (`BlockPackedReaderIterator.cs`, similarity norm decode)
The simple `values[i] += minValue` broadcast-add is trivially vectorizable. But the genuinely hot one, the running prefix sum for doc-ID deltas (`values[i] += values[i-1]`), has a serial dependency and needs the shift-and-add SIMD prefix-sum trick to beat scalar. Doable, more code, smaller/less certain win. I'd only touch it with a benchmark in hand.
### BytesRef comparison (`StringHelper.BytesDifference`, `Utf8SortedAsUnicodeComparer`)
`Vector` mismatch-find is a real win for long terms, but terms are often short (< 16 bytes), where SIMD setup cost dominates. Note .NET already gives you `MemoryExtensions.SequenceCompareTo` / `CommonPrefixLength`, which are SIMD-accelerated internally, so the right move here is delegate to the BCL, not hand-roll intrinsics.
## Tier 3: Don't bother
Packed-int bit unpacking (`BulkOperationPacked1-24`), MurmurHash, and UTF-8 encode all have irregular bit boundaries, state dependencies, or heavy branching. The Java-faithful scalar code is fine there.
### Additional context
The operations that can use `Vector` can support older targets like `net462` via the NuGet package. This will be JIT-optimized on those platforms but not intrinsic-ified like modern .NET. It still might result in a speed-up, but at least should be as good as the existing code. If benchmarks prove otherwise, we might need to conditionally compile based on a feature flag.
Anything that needs to use the SIMD intrinsics directly will need conditional compilation as that is not available prior to our .NET 8 target.
All of these changes should only be done if benchmarks prove beneficial. Otherwise, it's not worth the increased code complexity.
This is low priority for the 4.8.0 final release, and should not change the API surface.
Contributor guide
Research direction
Start by benchmarking the named FixedBitSet, OpenBitSet, Int64BitSet, and BitUtil.Pop_* operations, then review BlockPackedReaderIterator.cs and the BytesRef comparison areas. Focus on one measured SIMD candidate at a time, preserving net462 compatibility for Vector and using conditional compilation for .NET 8 intrinsics. Done means benchmarks show a benefit, the implementation avoids API changes, and no unprofitable optimization is added.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- csharp
- Domain
- performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100