You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucenenet.apache.org by pa...@apache.org on 2026/10/21 18:04:57 UTC
(lucenenet) branch master updated: Vectorize bulk bitset word loops, #1423 (#1500)
This is an automated email from the ASF dual-hosted git repository.
paulirwin pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/lucenenet.git
The following commit(s) were added to refs/heads/master by this push:
new b8998d900 Vectorize bulk bitset word loops, #1423 (#1500)
b8998d900 is described below
commit b8998d9007c69462f00cfe436d949dc7fa829c10
Author: Paul Irwin <pa...@gmail.com>
AuthorDate: Wed Oct 21 12:04:52 2026 -0600
Vectorize bulk bitset word loops, #1423 (#1500)
Co-authored-by: Claude Fable 5.1 <no...@anthropic.com>
---
.../Support/Util/TestBitArrayOperations.cs | 192 +++++++++++++++++++++
src/Lucene.Net/Support/Util/BitArrayOperations.cs | 134 ++++++++++++++
src/Lucene.Net/Util/FixedBitSet.cs | 20 +--
src/Lucene.Net/Util/LongBitSet.cs | 20 +--
src/Lucene.Net/Util/OpenBitSet.cs | 21 +--
5 files changed, 338 insertions(+), 49 deletions(-)
diff --git a/src/Lucene.Net.Tests/Support/Util/TestBitArrayOperations.cs b/src/Lucene.Net.Tests/Support/Util/TestBitArrayOperations.cs
new file mode 100644
index 000000000..13ab35e66
--- /dev/null
+++ b/src/Lucene.Net.Tests/Support/Util/TestBitArrayOperations.cs
@@ -0,0 +1,192 @@
+using Lucene.Net.Attributes;
+using NUnit.Framework;
+using RandomizedTesting.Generators;
+using System;
+using System.Collections.Generic;
+using System.Numerics;
+using Assert = Lucene.Net.TestFramework.Assert;
+
+namespace Lucene.Net.Util
+{
+ /*
+ * 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.
+ */
+
+ /// <summary>
+ /// LUCENENET specific: pins the vectorized word-loop helper behind
+ /// <see cref="FixedBitSet"/>, <see cref="OpenBitSet"/> and <see cref="Int64BitSet"/>
+ /// to the original scalar semantics at every vector-width boundary.
+ /// </summary>
+ [TestFixture]
+ public class TestBitArrayOperations : LuceneTestCase
+ {
+ private delegate void BulkOp(long[] dst, long[] src, int numWords);
+
+ private static readonly (string name, BulkOp op, Func<long, long, long> scalar)[] Ops =
+ {
+ ("Or", BitArrayOperations.Or, (a, b) => a | b),
+ ("And", BitArrayOperations.And, (a, b) => a & b),
+ ("AndNot", BitArrayOperations.AndNot, (a, b) => a & ~b),
+ ("Xor", BitArrayOperations.Xor, (a, b) => a ^ b),
+ };
+
+ /// <summary>
+ /// Word counts straddling the SIMD width so that the all-vector, vector-plus-tail,
+ /// tail-only and empty paths are each exercised regardless of hardware.
+ /// </summary>
+ private static IEnumerable<int> BoundaryWordCounts()
+ {
+ int count = Vector<long>.Count;
+ yield return 0;
+ yield return 1;
+ yield return count - 1;
+ yield return count;
+ yield return count + 1;
+ yield return 2 * count;
+ yield return 2 * count + 1;
+ yield return 1000;
+ }
+
+ private long[] RandomWords(int length)
+ {
+ long[] words = new long[length];
+ for (int i = 0; i < length; i++)
+ {
+ words[i] = Random.NextInt64();
+ }
+ return words;
+ }
+
+ [Test, LuceneNetSpecific]
+ public void BulkOps_MatchScalarReference_AtEveryVectorBoundary()
+ {
+ foreach (int numWords in BoundaryWordCounts())
+ {
+ foreach (var (name, op, scalar) in Ops)
+ {
+ long[] dst = RandomWords(numWords);
+ long[] src = RandomWords(numWords);
+ long[] expected = new long[numWords];
+ for (int i = 0; i < numWords; i++)
+ {
+ expected[i] = scalar(dst[i], src[i]);
+ }
+
+ op(dst, src, numWords);
+
+ Assert.AreEqual(expected, dst, "{0} with numWords={1}", name, numWords);
+ }
+ }
+ }
+
+ /// <summary>
+ /// All zeros, all ones and both alternating-bit patterns.
+ /// </summary>
+ private static readonly long[] Patterns =
+ {
+ 0L,
+ -1L,
+ 0x5555555555555555L,
+ unchecked((long)0xAAAAAAAAAAAAAAAAUL),
+ };
+
+ [Test, LuceneNetSpecific]
+ public void BulkOps_MatchScalarReference_ForDeterministicPatterns()
+ {
+ foreach (int numWords in BoundaryWordCounts())
+ {
+ foreach (var (name, op, scalar) in Ops)
+ {
+ foreach (long dstPattern in Patterns)
+ {
+ foreach (long srcPattern in Patterns)
+ {
+ long[] dst = new long[numWords];
+ long[] src = new long[numWords];
+ dst.AsSpan().Fill(dstPattern);
+ src.AsSpan().Fill(srcPattern);
+ long[] expected = new long[numWords];
+ expected.AsSpan().Fill(scalar(dstPattern, srcPattern));
+
+ op(dst, src, numWords);
+
+ Assert.AreEqual(expected, dst, "{0} with numWords={1}, dst=0x{2:X16}, src=0x{3:X16}", name, numWords, dstPattern, srcPattern);
+ }
+ }
+ }
+ }
+ }
+
+ [Test, LuceneNetSpecific]
+ public void BulkOps_MatchScalarReference_WhenDstIsSrc()
+ {
+ foreach (int numWords in BoundaryWordCounts())
+ {
+ foreach (var (name, op, scalar) in Ops)
+ {
+ long[] words = RandomWords(numWords);
+ long[] expected = new long[numWords];
+ for (int i = 0; i < numWords; i++)
+ {
+ expected[i] = scalar(words[i], words[i]);
+ }
+
+ op(words, words, numWords);
+
+ Assert.AreEqual(expected, words, "{0} with numWords={1}", name, numWords);
+ }
+ }
+ }
+
+ [Test, LuceneNetSpecific]
+ public void BulkOps_LeaveWordsPastNumWordsUntouched()
+ {
+ foreach (int numWords in BoundaryWordCounts())
+ {
+ foreach (var (name, op, scalar) in Ops)
+ {
+ const int slack = 7;
+ long[] dst = RandomWords(numWords + slack);
+ long[] src = RandomWords(numWords + slack);
+ long[] dstCopy = (long[])dst.Clone();
+ long[] srcCopy = (long[])src.Clone();
+
+ op(dst, src, numWords);
+
+ for (int i = 0; i < numWords; i++)
+ {
+ Assert.AreEqual(scalar(dstCopy[i], srcCopy[i]), dst[i], "{0} word {1} of numWords={2}", name, i, numWords);
+ }
+ for (int i = numWords; i < dst.Length; i++)
+ {
+ Assert.AreEqual(dstCopy[i], dst[i], "{0} modified dst[{1}] past numWords={2}", name, i, numWords);
+ }
+ Assert.AreEqual(srcCopy, src, "{0} modified src with numWords={1}", name, numWords);
+ }
+ }
+ }
+
+ [Test, LuceneNetSpecific]
+ public void BulkOps_ThrowWhenNumWordsExceedsEitherArray()
+ {
+ foreach (var (name, op, _) in Ops)
+ {
+ Assert.Throws<ArgumentOutOfRangeException>(() => op(new long[4], new long[8], 5), "{0} dst too short", name);
+ Assert.Throws<ArgumentOutOfRangeException>(() => op(new long[8], new long[4], 5), "{0} src too short", name);
+ }
+ }
+ }
+}
diff --git a/src/Lucene.Net/Support/Util/BitArrayOperations.cs b/src/Lucene.Net/Support/Util/BitArrayOperations.cs
new file mode 100644
index 000000000..0781c2ca3
--- /dev/null
+++ b/src/Lucene.Net/Support/Util/BitArrayOperations.cs
@@ -0,0 +1,134 @@
+using System;
+using System.Numerics;
+using System.Runtime.InteropServices;
+
+namespace Lucene.Net.Util
+{
+ /*
+ * 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.
+ */
+
+ /// <summary>
+ /// LUCENENET specific: in-place bulk bitwise operations over <see cref="long"/> word arrays,
+ /// shared by <see cref="FixedBitSet"/>, <see cref="OpenBitSet"/> and <see cref="Int64BitSet"/>.
+ /// <para/>
+ /// The Java JIT auto-vectorizes the simple word loops in these classes, but the .NET JIT does not,
+ /// so these helpers use <see cref="Vector{T}"/> explicitly when the hardware supports it and fall
+ /// back to the original scalar loop otherwise (for example, on 32-bit .NET Framework).
+ /// <para/>
+ /// Each method processes exactly the first <c>numWords</c> words of both arrays and leaves the
+ /// rest of <c>dst</c> untouched. Callers are responsible for bounds (as in the original loops,
+ /// an out-of-range <c>numWords</c> throws).
+ /// </summary>
+ internal static class BitArrayOperations
+ {
+ /// <summary>
+ /// <c>dst[i] |= src[i]</c> for <c>i</c> in <c>[0, numWords)</c>.
+ /// </summary>
+ public static void Or(long[] dst, long[] src, int numWords)
+ {
+ Span<long> d = dst.AsSpan(0, numWords);
+ ReadOnlySpan<long> s = src.AsSpan(0, numWords);
+ int i = 0;
+ if (Vector.IsHardwareAccelerated && numWords >= Vector<long>.Count)
+ {
+ Span<Vector<long>> vd = MemoryMarshal.Cast<long, Vector<long>>(d);
+ ReadOnlySpan<Vector<long>> vs = MemoryMarshal.Cast<long, Vector<long>>(s);
+ for (int v = 0; v < vd.Length; v++)
+ {
+ vd[v] |= vs[v];
+ }
+ i = vd.Length * Vector<long>.Count;
+ }
+ for (; i < d.Length; i++)
+ {
+ d[i] |= s[i];
+ }
+ }
+
+ /// <summary>
+ /// <c>dst[i] &= src[i]</c> for <c>i</c> in <c>[0, numWords)</c>.
+ /// </summary>
+ public static void And(long[] dst, long[] src, int numWords)
+ {
+ Span<long> d = dst.AsSpan(0, numWords);
+ ReadOnlySpan<long> s = src.AsSpan(0, numWords);
+ int i = 0;
+ if (Vector.IsHardwareAccelerated && numWords >= Vector<long>.Count)
+ {
+ Span<Vector<long>> vd = MemoryMarshal.Cast<long, Vector<long>>(d);
+ ReadOnlySpan<Vector<long>> vs = MemoryMarshal.Cast<long, Vector<long>>(s);
+ for (int v = 0; v < vd.Length; v++)
+ {
+ vd[v] &= vs[v];
+ }
+ i = vd.Length * Vector<long>.Count;
+ }
+ for (; i < d.Length; i++)
+ {
+ d[i] &= s[i];
+ }
+ }
+
+ /// <summary>
+ /// <c>dst[i] &= ~src[i]</c> for <c>i</c> in <c>[0, numWords)</c>.
+ /// </summary>
+ public static void AndNot(long[] dst, long[] src, int numWords)
+ {
+ Span<long> d = dst.AsSpan(0, numWords);
+ ReadOnlySpan<long> s = src.AsSpan(0, numWords);
+ int i = 0;
+ if (Vector.IsHardwareAccelerated && numWords >= Vector<long>.Count)
+ {
+ Span<Vector<long>> vd = MemoryMarshal.Cast<long, Vector<long>>(d);
+ ReadOnlySpan<Vector<long>> vs = MemoryMarshal.Cast<long, Vector<long>>(s);
+ for (int v = 0; v < vd.Length; v++)
+ {
+ vd[v] = Vector.AndNot(vd[v], vs[v]);
+ }
+ i = vd.Length * Vector<long>.Count;
+ }
+ for (; i < d.Length; i++)
+ {
+ d[i] &= ~s[i];
+ }
+ }
+
+ /// <summary>
+ /// <c>dst[i] ^= src[i]</c> for <c>i</c> in <c>[0, numWords)</c>.
+ /// </summary>
+ public static void Xor(long[] dst, long[] src, int numWords)
+ {
+ Span<long> d = dst.AsSpan(0, numWords);
+ ReadOnlySpan<long> s = src.AsSpan(0, numWords);
+ int i = 0;
+ if (Vector.IsHardwareAccelerated && numWords >= Vector<long>.Count)
+ {
+ Span<Vector<long>> vd = MemoryMarshal.Cast<long, Vector<long>>(d);
+ ReadOnlySpan<Vector<long>> vs = MemoryMarshal.Cast<long, Vector<long>>(s);
+ for (int v = 0; v < vd.Length; v++)
+ {
+ vd[v] ^= vs[v];
+ }
+ i = vd.Length * Vector<long>.Count;
+ }
+ for (; i < d.Length; i++)
+ {
+ d[i] ^= s[i];
+ }
+ }
+ }
+}
diff --git a/src/Lucene.Net/Util/FixedBitSet.cs b/src/Lucene.Net/Util/FixedBitSet.cs
index f1a9e25da..d89fb7003 100644
--- a/src/Lucene.Net/Util/FixedBitSet.cs
+++ b/src/Lucene.Net/Util/FixedBitSet.cs
@@ -412,10 +412,7 @@ private void Or(long[] otherArr, int otherNumWords)
if (Debugging.AssertsEnabled) Debugging.Assert(otherNumWords <= numWords, "numWords={0}, otherNumWords={1}", numWords, otherNumWords);
long[] thisArr = this.bits;
int pos = Math.Min(numWords, otherNumWords);
- while (--pos >= 0)
- {
- thisArr[pos] |= otherArr[pos];
- }
+ BitArrayOperations.Or(thisArr, otherArr, pos); // LUCENENET specific: vectorized word loop
}
/// <summary>
@@ -426,10 +423,7 @@ public void Xor(FixedBitSet other)
long[] thisBits = this.bits;
long[] otherBits = other.bits;
int pos = Math.Min(numWords, other.numWords);
- while (--pos >= 0)
- {
- thisBits[pos] ^= otherBits[pos];
- }
+ BitArrayOperations.Xor(thisBits, otherBits, pos); // LUCENENET specific: vectorized word loop
}
/// <summary>
@@ -510,10 +504,7 @@ private void And(long[] otherArr, int otherNumWords)
{
long[] thisArr = this.bits;
int pos = Math.Min(this.numWords, otherNumWords);
- while (--pos >= 0)
- {
- thisArr[pos] &= otherArr[pos];
- }
+ BitArrayOperations.And(thisArr, otherArr, pos); // LUCENENET specific: vectorized word loop
if (this.numWords > otherNumWords)
{
Arrays.Fill(thisArr, otherNumWords, this.numWords, 0L);
@@ -562,10 +553,7 @@ private void AndNot(long[] otherArr, int otherNumWords)
{
long[] thisArr = this.bits;
int pos = Math.Min(this.numWords, otherNumWords);
- while (--pos >= 0)
- {
- thisArr[pos] &= ~otherArr[pos];
- }
+ BitArrayOperations.AndNot(thisArr, otherArr, pos); // LUCENENET specific: vectorized word loop
}
// NOTE: no .isEmpty() here because that's trappy (ie,
diff --git a/src/Lucene.Net/Util/LongBitSet.cs b/src/Lucene.Net/Util/LongBitSet.cs
index 3bc788f01..f77acfa1d 100644
--- a/src/Lucene.Net/Util/LongBitSet.cs
+++ b/src/Lucene.Net/Util/LongBitSet.cs
@@ -236,10 +236,7 @@ public void Or(Int64BitSet other)
{
if (Debugging.AssertsEnabled) Debugging.Assert(other.numWords <= numWords, "numWords={0}, other.numWords={1}", numWords, other.numWords);
int pos = Math.Min(numWords, other.numWords);
- while (--pos >= 0)
- {
- bits[pos] |= other.bits[pos];
- }
+ BitArrayOperations.Or(bits, other.bits, pos); // LUCENENET specific: vectorized word loop
}
/// <summary>
@@ -248,10 +245,7 @@ public void Xor(Int64BitSet other)
{
if (Debugging.AssertsEnabled) Debugging.Assert(other.numWords <= numWords, "numWords={0}, other.numWords={1}", numWords, other.numWords);
int pos = Math.Min(numWords, other.numWords);
- while (--pos >= 0)
- {
- bits[pos] ^= other.bits[pos];
- }
+ BitArrayOperations.Xor(bits, other.bits, pos); // LUCENENET specific: vectorized word loop
}
/// <summary>
@@ -274,10 +268,7 @@ public bool Intersects(Int64BitSet other)
public void And(Int64BitSet other)
{
int pos = Math.Min(numWords, other.numWords);
- while (--pos >= 0)
- {
- bits[pos] &= other.bits[pos];
- }
+ BitArrayOperations.And(bits, other.bits, pos); // LUCENENET specific: vectorized word loop
if (numWords > other.numWords)
{
Arrays.Fill(bits, other.numWords, numWords, 0L);
@@ -289,10 +280,7 @@ public void And(Int64BitSet other)
public void AndNot(Int64BitSet other)
{
int pos = Math.Min(numWords, other.bits.Length);
- while (--pos >= 0)
- {
- bits[pos] &= ~other.bits[pos];
- }
+ BitArrayOperations.AndNot(bits, other.bits, pos); // LUCENENET specific: vectorized word loop
}
// NOTE: no .isEmpty() here because that's trappy (ie,
diff --git a/src/Lucene.Net/Util/OpenBitSet.cs b/src/Lucene.Net/Util/OpenBitSet.cs
index 5b6eafb16..43a96079a 100644
--- a/src/Lucene.Net/Util/OpenBitSet.cs
+++ b/src/Lucene.Net/Util/OpenBitSet.cs
@@ -893,11 +893,7 @@ public virtual void Intersect(OpenBitSet other)
long[] thisArr = this.m_bits;
long[] otherArr = other.m_bits;
// testing against zero can be more efficient
- int pos = newLen;
- while (--pos >= 0)
- {
- thisArr[pos] &= otherArr[pos];
- }
+ BitArrayOperations.And(thisArr, otherArr, newLen); // LUCENENET specific: vectorized word loop
if (this.m_wlen > newLen)
{
// fill zeros from the new shorter length to the old length
@@ -923,10 +919,7 @@ public virtual void Union(OpenBitSet other)
long[] thisArr = this.m_bits;
long[] otherArr = other.m_bits;
int pos = Math.Min(oldLen, other.m_wlen);
- while (--pos >= 0)
- {
- thisArr[pos] |= otherArr[pos];
- }
+ BitArrayOperations.Or(thisArr, otherArr, pos); // LUCENENET specific: vectorized word loop
if (oldLen < newLen)
{
Arrays.Copy(otherArr, oldLen, thisArr, oldLen, newLen - oldLen);
@@ -940,10 +933,7 @@ public virtual void Remove(OpenBitSet other)
int idx = Math.Min(m_wlen, other.m_wlen);
long[] thisArr = this.m_bits;
long[] otherArr = other.m_bits;
- while (--idx >= 0)
- {
- thisArr[idx] &= ~otherArr[idx];
- }
+ BitArrayOperations.AndNot(thisArr, otherArr, idx); // LUCENENET specific: vectorized word loop
}
/// <summary>
@@ -963,10 +953,7 @@ public virtual void Xor(OpenBitSet other)
long[] thisArr = this.m_bits;
long[] otherArr = other.m_bits;
int pos = Math.Min(oldLen, other.m_wlen);
- while (--pos >= 0)
- {
- thisArr[pos] ^= otherArr[pos];
- }
+ BitArrayOperations.Xor(thisArr, otherArr, pos); // LUCENENET specific: vectorized word loop
if (oldLen < newLen)
{
Arrays.Copy(otherArr, oldLen, thisArr, oldLen, newLen - oldLen);