You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pulsar.apache.org by lh...@apache.org on 2026/09/08 14:55:39 UTC
(pulsar) branch master updated: [improve][ml] Back LongBitmap with the on-heap RoaringBitmap to fix ack allocation hotspot (#26500)
This is an automated email from the ASF dual-hosted git repository.
lhotari pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/pulsar.git
The following commit(s) were added to refs/heads/master by this push:
new 00d475f65f50 [improve][ml] Back LongBitmap with the on-heap RoaringBitmap to fix ack allocation hotspot (#26500)
00d475f65f50 is described below
commit 00d475f65f5010700c8172918e105d0c471f4c5b
Author: Lari Hotari <lh...@users.noreply.github.com>
AuthorDate: Tue Sep 8 17:55:31 2026 +0300
[improve][ml] Back LongBitmap with the on-heap RoaringBitmap to fix ack allocation hotspot (#26500)
---
.../mledger/impl/PositionRangeSetBenchmark.java | 5 +
.../util/collections/LongBitmapBenchmark.java | 11 ++
.../util/collections/ConcurrentRoaringBitmap.java | 124 +++++++++++++-----
.../common/util/collections/LongBitmaps.java | 4 +-
.../collections/LongBitmapCompatibilityTest.java | 70 +++++++++-
.../common/util/collections/LongBitmapTest.java | 143 +++++++++++++++++++--
6 files changed, 310 insertions(+), 47 deletions(-)
diff --git a/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/PositionRangeSetBenchmark.java b/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/PositionRangeSetBenchmark.java
index 1e920ef62a4d..a8961901f79a 100644
--- a/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/PositionRangeSetBenchmark.java
+++ b/microbench/src/main/java/org/apache/bookkeeper/mledger/impl/PositionRangeSetBenchmark.java
@@ -47,6 +47,11 @@ import org.openjdk.jmh.infra.Blackhole;
* <pre>{@code
* ./gradlew :microbench:shadowJar
* java -jar microbench/build/libs/microbench-*-benchmarks.jar PositionRangeSetBenchmark
+ *
+ * # Allocation profile of the individual-ack path (addOpenClosedSameLedger issues a
+ * # one-wide range add per ack, the shape that dominates cursor allocation):
+ * java -jar microbench/build/libs/microbench-*-benchmarks.jar \
+ * PositionRangeSetBenchmark.addOpenClosedSameLedger -prof gc
* }</pre>
*/
@BenchmarkMode(Mode.Throughput)
diff --git a/microbench/src/main/java/org/apache/pulsar/common/util/collections/LongBitmapBenchmark.java b/microbench/src/main/java/org/apache/pulsar/common/util/collections/LongBitmapBenchmark.java
index 9fa3c464d732..2ac388d9f3f1 100644
--- a/microbench/src/main/java/org/apache/pulsar/common/util/collections/LongBitmapBenchmark.java
+++ b/microbench/src/main/java/org/apache/pulsar/common/util/collections/LongBitmapBenchmark.java
@@ -89,6 +89,17 @@ public class LongBitmapBenchmark {
return longBitmap.checkedAdd(v);
}
+ @Benchmark
+ @Threads(1)
+ public void longBitmapAddSingleValueRangeSingleThread() {
+ // The shape PositionRangeSet.addOpenClosed issues for an individually acked message:
+ // a one-wide range, not a point add. Every other benchmark here uses checkedAdd, which
+ // was already on the amortized growth path, so none of them could observe the
+ // container-growth regression this benchmark exists to guard.
+ long v = nextValue.getAndIncrement();
+ longBitmap.add(v, v + 1);
+ }
+
@Benchmark
@Threads(1)
public boolean roaringBitmapAddSingleThread() {
diff --git a/pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentRoaringBitmap.java b/pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentRoaringBitmap.java
index 96ed33c2f804..8f29c763530c 100644
--- a/pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentRoaringBitmap.java
+++ b/pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/ConcurrentRoaringBitmap.java
@@ -27,25 +27,45 @@ import java.util.function.LongConsumer;
import org.roaringbitmap.BitSetUtil;
import org.roaringbitmap.PeekableIntIterator;
import org.roaringbitmap.RoaringBitmap;
-import org.roaringbitmap.buffer.MutableRoaringBitmap;
/**
- * {@link LongBitmap} implementation backed by {@link MutableRoaringBitmap} and guarded
- * by a {@link StampedLock}.
+ * {@link LongBitmap} implementation backed by {@link RoaringBitmap} and guarded by a
+ * {@link StampedLock}.
+ *
+ * <p><b>Why the on-heap variant.</b> {@link RoaringBitmap} stores each container in a plain
+ * {@code char[]}/{@code long[]}. Its {@code org.roaringbitmap.buffer.MutableRoaringBitmap}
+ * counterpart stores them in NIO buffers, which exists so that a bitmap can be read straight out
+ * of a memory-mapped {@link ByteBuffer}. Pulsar never memory-maps a bitmap and never hands one out
+ * as a zero-copy read-only view, so it paid the indirection for nothing: the buffer variant's
+ * {@code MappeableArrayContainer.iadd} reallocates its container to exactly the new cardinality
+ * with no growth headroom, so appending one value at a time through {@link #add(long, long)} — the
+ * shape an individual message acknowledgement produces — reallocated on every single call, while
+ * {@code ArrayContainer.iadd} grows geometrically. Both variants share the portable serialization
+ * format, so persisted cursor state and delayed-delivery snapshots round-trip across this choice in
+ * both directions.
*
* <p><b>Thread-safety basis.</b> RoaringBitmap is not thread-safe by default
- * (see <a href="https://github.com/apache/pulsar/issues/25991">pulsar#25991</a>). This
- * wrapper relies on the documented contract that {@link MutableRoaringBitmap}'s read
- * methods — the {@code ImmutableBitmapDataProvider} surface inherited from
- * {@code ImmutableRoaringBitmap} — do not mutate internal state, while methods added by
- * {@code BitmapDataProvider} and other {@code MutableRoaringBitmap} mutators
- * ({@code andNot}, {@code or}, {@code checkedRemove}, {@code runOptimize}, {@code clone},
- * ...) do. Read methods run under the read lock; mutators under the write lock.
- * {@code clone()} is used under the read lock in {@link #forEachLong} and {@link #serialize};
- * its source has been audited to be read-only on the live bitmap. <b>Before upgrading
- * the RoaringBitmap dependency or changing the lock split</b>, re-audit these methods
- * and run the concurrency regression tests ({@code testConcurrentForEachLongAndMutate},
- * {@code testOrDoesNotMutateInput}).
+ * (see <a href="https://github.com/apache/pulsar/issues/25991">pulsar#25991</a>).
+ * {@link RoaringBitmap} is a single class implementing both {@code ImmutableBitmapDataProvider} and
+ * {@code BitmapDataProvider}, so the type system does not separate readers from mutators here — the
+ * split below is maintained by audit rather than by the compiler. Under the READ lock this class
+ * calls only {@code contains(int)}, {@code contains(long, long)}, {@code getLongCardinality()},
+ * {@code isEmpty()}, {@code rank(int)}, {@code nextValue(int)}, {@code previousValue(int)},
+ * {@code nextAbsentValue(int)}, {@code previousAbsentValue(int)}, {@code serializedSizeInBytes()},
+ * {@code clone()} and {@link BitSetUtil#toLongArray(RoaringBitmap)}; each was verified to read
+ * {@code highLowContainer} and its containers without writing to either. Everything that mutates —
+ * {@code add}, {@code checkedAdd}, {@code checkedRemove}, {@code remove}, {@code clear},
+ * {@code or}, {@code andNot}, {@code runOptimize}, {@code trim}, {@code getIntIterator} (used by
+ * {@link #drainTo} alongside the removal it feeds) and {@code deserialize} — runs under the WRITE
+ * lock. {@code clone()} is used under the read lock in {@link #forEachLong} and {@link #serialize};
+ * {@code runOptimize()} and {@code serialize(ByteBuffer)} then run on that clone with no lock held.
+ * <b>Before upgrading the RoaringBitmap dependency or changing the lock split</b>, re-audit that
+ * list and run the concurrency regression tests ({@code testConcurrentForEachLongAndMutate},
+ * {@code testOrDoesNotMutateInput}, {@code testConcurrentSerializeToLongArray}).
+ *
+ * <p>The instance must be a plain {@link RoaringBitmap}, never {@code FastRankRoaringBitmap}: the
+ * latter memoizes cardinalities inside {@code rank}/{@code select}, which would turn a read-lock
+ * call into a data race.
*
* <p><b>Critical sections.</b> Single-value reads take the read lock; mutations take the
* write lock. Bulk mutations that touch two bitmaps ({@link #or}) acquire this bitmap's
@@ -54,9 +74,9 @@ import org.roaringbitmap.buffer.MutableRoaringBitmap;
* ({@link #serialize}, {@link #forEachLong}) clones under a brief read lock and finishes
* without holding it, so optimize/iterate/runOptimize don't block writers.
*
- * <p><b>Memory.</b> {@link MutableRoaringBitmap#trim()} fires when removals since the
- * last trim reach {@link #TRIM_AFTER_REMOVES}, or whenever the bitmap becomes empty.
- * {@link #serialize} runs {@code runOptimize()} on the clone so persisted bytes are compact.
+ * <p><b>Memory.</b> {@link RoaringBitmap#trim()} fires when removals since the last trim reach
+ * {@link #TRIM_AFTER_REMOVES}, or whenever the bitmap becomes empty. {@link #serialize} runs
+ * {@code runOptimize()} on the clone so persisted bytes are compact.
*/
class ConcurrentRoaringBitmap implements LongBitmap {
@@ -64,20 +84,36 @@ class ConcurrentRoaringBitmap implements LongBitmap {
private static final long UINT32_SIZE = 1L << 32;
private static final long MAX_UINT32 = UINT32_SIZE - 1;
- private final MutableRoaringBitmap bitmap;
+ private final RoaringBitmap bitmap;
private final StampedLock lock;
private long removesSinceTrim;
ConcurrentRoaringBitmap() {
- this.bitmap = new MutableRoaringBitmap();
- this.lock = new StampedLock();
+ this(new RoaringBitmap());
}
- private ConcurrentRoaringBitmap(MutableRoaringBitmap bitmap) {
+ private ConcurrentRoaringBitmap(RoaringBitmap bitmap) {
this.bitmap = bitmap;
this.lock = new StampedLock();
}
+ /**
+ * Creates a bitmap holding the values encoded in {@code data}, in the
+ * {@link java.util.BitSet#toLongArray()} format produced by {@link #serializeToLongArray()}.
+ *
+ * <p>{@link BitSetUtil#bitmapOf(long[])} already builds every container at its exact block
+ * cardinality, so adopting its result avoids the empty-bitmap plus {@code clear()} plus
+ * {@code or()} round trip that the instance method {@link #deserializeFromLongArray(long[])}
+ * cannot avoid — {@link #bitmap} is {@code final}, because {@link #or} reads its identity
+ * without holding a lock to order the two locks it acquires.
+ *
+ * @param data long array in BitSet format
+ * @return a new bitmap containing exactly the values encoded in {@code data}
+ */
+ static ConcurrentRoaringBitmap fromLongArray(long[] data) {
+ return new ConcurrentRoaringBitmap(BitSetUtil.bitmapOf(data));
+ }
+
@Override
public void add(long value) {
validateRange(value);
@@ -109,7 +145,19 @@ class ConcurrentRoaringBitmap implements LongBitmap {
validateRange(to - 1);
long stamp = lock.writeLock();
try {
- bitmap.add(from, to);
+ if (to - from == 1) {
+ // Single-value ranges dominate the acknowledgement path: PositionRangeSet
+ // .addOpenClosed issues add(entryId, entryId + 1) for every individually acked
+ // message. add(int) seeds a brand-new container at ArrayContainer's default
+ // capacity, while add(long, long) seeds it through Container.rangeOfOnes at
+ // exactly 1 and then has to grow on the next value. The two are equivalent for a
+ // one-wide range: rangeOfOnes returns an ArrayContainer for cardinality <= 2, the
+ // same class add(int) creates, and both convert to a bitmap container at
+ // cardinality 4096. Must stay inside the lock and after both validateRange calls.
+ bitmap.add((int) from);
+ } else {
+ bitmap.add(from, to);
+ }
} finally {
lock.unlockWrite(stamp);
}
@@ -339,13 +387,18 @@ class ConcurrentRoaringBitmap implements LongBitmap {
@Override
public void forEachLong(LongConsumer action) {
- MutableRoaringBitmap snapshot;
+ RoaringBitmap snapshot;
long stamp = lock.readLock();
try {
+ if (bitmap.isEmpty()) {
+ return;
+ }
snapshot = bitmap.clone();
} finally {
lock.unlockRead(stamp);
}
+ // The cast is load-bearing: RoaringBitmap also implements Iterable<Integer>, so an
+ // uncast lambda binds to Iterable.forEach(Consumer<? super Integer>) and boxes every value.
snapshot.forEach((org.roaringbitmap.IntConsumer) v ->
action.accept(Integer.toUnsignedLong(v)));
}
@@ -355,7 +408,7 @@ class ConcurrentRoaringBitmap implements LongBitmap {
if (limit <= 0) {
return 0;
}
- MutableRoaringBitmap toRemove = new MutableRoaringBitmap();
+ RoaringBitmap toRemove = new RoaringBitmap();
long collected;
long writeStamp = lock.writeLock();
try {
@@ -392,7 +445,7 @@ class ConcurrentRoaringBitmap implements LongBitmap {
@Override
public byte[] serialize() {
- MutableRoaringBitmap copy;
+ RoaringBitmap copy;
long stamp = lock.readLock();
try {
copy = bitmap.clone();
@@ -409,8 +462,12 @@ class ConcurrentRoaringBitmap implements LongBitmap {
public long[] serializeToLongArray() {
long stamp = lock.readLock();
try {
- RoaringBitmap immutable = bitmap.toRoaringBitmap();
- return BitSetUtil.toLongArray(immutable);
+ // BitSetUtil.toLongArray only reads the bitmap (isEmpty / last / getContainerPointer /
+ // Container.copyBitmapTo, all of which write solely into the returned array), so it is
+ // correct against the live instance under the read lock. Do not reintroduce a
+ // defensive copy: MutableRoaringBitmap.toRoaringBitmap(), which this replaced,
+ // advanced the live containers' buffer positions and so mutated under the read lock.
+ return BitSetUtil.toLongArray(bitmap);
} finally {
lock.unlockRead(stamp);
}
@@ -418,11 +475,13 @@ class ConcurrentRoaringBitmap implements LongBitmap {
@Override
public void deserializeFromLongArray(long[] data) {
+ // Built outside the lock: BitSetUtil.bitmapOf reads only the caller-owned long[] and the
+ // result is thread-confined until it is merged in below.
+ RoaringBitmap replacement = BitSetUtil.bitmapOf(data);
long stamp = lock.writeLock();
try {
bitmap.clear();
- RoaringBitmap rb = BitSetUtil.bitmapOf(data);
- bitmap.or(rb.toMutableRoaringBitmap());
+ bitmap.or(replacement);
removesSinceTrim = 0;
} finally {
lock.unlockWrite(stamp);
@@ -433,7 +492,10 @@ class ConcurrentRoaringBitmap implements LongBitmap {
try {
ByteBuffer nioBuffer = buf.nioBuffer(buf.readerIndex(), buf.readableBytes());
int startPosition = nioBuffer.position();
- MutableRoaringBitmap bitmap = new MutableRoaringBitmap();
+ RoaringBitmap bitmap = new RoaringBitmap();
+ // Deliberately the DataInput overload: RoaringBitmap.deserialize(ByteBuffer) slices its
+ // argument and leaves the caller's position untouched, which would break the
+ // skipBytes accounting below.
bitmap.deserialize(new ByteBufferDataInput(nioBuffer));
buf.skipBytes(nioBuffer.position() - startPosition);
return new ConcurrentRoaringBitmap(bitmap);
diff --git a/pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/LongBitmaps.java b/pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/LongBitmaps.java
index ac7b4fadbedd..27abd7898461 100644
--- a/pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/LongBitmaps.java
+++ b/pulsar-common/src/main/java/org/apache/pulsar/common/util/collections/LongBitmaps.java
@@ -70,8 +70,6 @@ public final class LongBitmaps {
* @return a new LongBitmap containing the deserialized values
*/
public static LongBitmap deserializeFromLongArray(long[] data) {
- LongBitmap bitmap = create();
- bitmap.deserializeFromLongArray(data);
- return bitmap;
+ return ConcurrentRoaringBitmap.fromLongArray(data);
}
}
diff --git a/pulsar-common/src/test/java/org/apache/pulsar/common/util/collections/LongBitmapCompatibilityTest.java b/pulsar-common/src/test/java/org/apache/pulsar/common/util/collections/LongBitmapCompatibilityTest.java
index 6c9081db44f5..4d05011b2453 100644
--- a/pulsar-common/src/test/java/org/apache/pulsar/common/util/collections/LongBitmapCompatibilityTest.java
+++ b/pulsar-common/src/test/java/org/apache/pulsar/common/util/collections/LongBitmapCompatibilityTest.java
@@ -84,6 +84,72 @@ public class LongBitmapCompatibilityTest {
"LongBitmap buffer must be byte-identical to standard 32-bit RoaringBitmap buffer");
}
+ /**
+ * Golden on-disk bytes, captured from the implementation before it moved to the on-heap
+ * {@code org.roaringbitmap.RoaringBitmap}. {@link #testLongBitmapBufferEqualsStandardRoaringBitmap}
+ * compares {@link LongBitmap} against {@code org.roaringbitmap.RoaringBitmap}, so once
+ * {@code ConcurrentRoaringBitmap} is itself backed by that class the comparison no longer pins
+ * the format against an independent reference. These literals do, and they must not change:
+ * the cursor's individually-deleted ranges and the delayed-delivery bucket snapshots are
+ * persisted in exactly this format.
+ */
+ private static final byte[] GOLDEN_POINTS = {
+ (byte) 0x3A, (byte) 0x30, (byte) 0x00, (byte) 0x00, (byte) 0x03, (byte) 0x00,
+ (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x01, (byte) 0x00,
+ (byte) 0x10, (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0xFF, (byte) 0xFF,
+ (byte) 0x00, (byte) 0x00, (byte) 0x20, (byte) 0x00, (byte) 0x00, (byte) 0x00,
+ (byte) 0x24, (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x26, (byte) 0x00,
+ (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x00, (byte) 0x64, (byte) 0x00,
+ (byte) 0x00, (byte) 0x00, (byte) 0xFF, (byte) 0xFF,
+ };
+
+ private static final byte[] GOLDEN_RUN = {
+ (byte) 0x3B, (byte) 0x30, (byte) 0x00, (byte) 0x00, (byte) 0x01, (byte) 0x00,
+ (byte) 0x00, (byte) 0x87, (byte) 0x13, (byte) 0x01, (byte) 0x00, (byte) 0x00,
+ (byte) 0x00, (byte) 0x87, (byte) 0x13,
+ };
+
+ /**
+ * Pins the persisted format against literals rather than against another RoaringBitmap
+ * instance, so it keeps its meaning across a change of backing implementation.
+ */
+ @Test
+ public void testSerializedFormatMatchesGoldenBytes() {
+ LongBitmap points = LongBitmaps.create();
+ points.add(0);
+ points.add(100);
+ points.add(1L << 20);
+ points.add(0xFFFFFFFFL);
+ assertEquals(points.serialize(), GOLDEN_POINTS,
+ "persisted format changed for sparse points");
+
+ // A contiguous run exercises runOptimize(), which serialize() applies to its clone —
+ // the one place a container-representation change would surface in persisted bytes.
+ LongBitmap run = LongBitmaps.create();
+ for (int i = 0; i < 5000; i++) {
+ run.add(i);
+ }
+ assertEquals(run.serialize(), GOLDEN_RUN, "persisted format changed for a contiguous run");
+ }
+
+ /**
+ * The golden bytes must also read back. Guards the deserialize side of the format, including
+ * that {@code readerIndex} advances by exactly the payload length.
+ */
+ @Test
+ public void testGoldenBytesRoundTrip() {
+ for (byte[] golden : new byte[][]{GOLDEN_POINTS, GOLDEN_RUN}) {
+ ByteBuf buf = Unpooled.wrappedBuffer(golden);
+ try {
+ LongBitmap restored = LongBitmaps.deserialize(buf);
+ assertEquals(restored.serialize(), golden);
+ assertEquals(buf.readableBytes(), 0, "readerIndex must advance by the payload");
+ } finally {
+ buf.release();
+ }
+ }
+ }
+
/**
* Round-trip: 32-bit RoaringBitmap buffer -> LongBitmap. Confirms that
* persisted data written by the old code path can be read by LongBitmap.
@@ -140,7 +206,7 @@ public class LongBitmapCompatibilityTest {
/**
* Roaring64Bitmap buffer cannot be deserialized as a LongBitmap.
* Roaring64Bitmap's serialized format starts with a bucket count, not the
- * 32-bit cookie (12346), so {@code MutableRoaringBitmap.deserialize} throws.
+ * 32-bit cookie (12346), so {@code RoaringBitmap.deserialize} throws.
*/
@Test
public void testRoaring64BufferNotReadableAsLongBitmap() throws Exception {
@@ -153,7 +219,7 @@ public class LongBitmapCompatibilityTest {
ByteBuf buf = Unpooled.wrappedBuffer(roaring64Bytes);
try {
- // MutableRoaringBitmap wraps IOException as RuntimeException.
+ // RoaringBitmap wraps IOException as RuntimeException.
assertThrows(Exception.class, () -> LongBitmaps.deserialize(buf));
} finally {
buf.release();
diff --git a/pulsar-common/src/test/java/org/apache/pulsar/common/util/collections/LongBitmapTest.java b/pulsar-common/src/test/java/org/apache/pulsar/common/util/collections/LongBitmapTest.java
index 333dda0b24e4..5f195f243275 100644
--- a/pulsar-common/src/test/java/org/apache/pulsar/common/util/collections/LongBitmapTest.java
+++ b/pulsar-common/src/test/java/org/apache/pulsar/common/util/collections/LongBitmapTest.java
@@ -25,6 +25,7 @@ import static org.testng.Assert.assertTrue;
import io.netty.buffer.ByteBuf;
import io.netty.buffer.Unpooled;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.CountDownLatch;
@@ -488,21 +489,141 @@ public class LongBitmapTest {
@Test
public void testRangeVsSingleValueEquivalence() {
- // For any v, add(v, v+1) / contains(v, v+1) / remove(v, v+1) ≡ add(v) / contains(v) / remove(v).
+ // For any v, add(v, v+1) / remove(v, v+1) is equivalent to add(v) / remove(v).
long[] values = {0, 1, 100, 65535, 65536, 1L << 30, 0xFFFFFFFFL};
for (long v : values) {
- LongBitmap bitmap = LongBitmaps.create();
- bitmap.add(v);
- assertTrue(bitmap.contains(v));
- assertEquals(bitmap.cardinality(), 1);
+ LongBitmap viaRange = LongBitmaps.create();
+ LongBitmap viaPoint = LongBitmaps.create();
+
+ viaRange.add(v, v + 1);
+ viaPoint.add(v);
+ assertTrue(viaRange.contains(v));
+ assertEquals(viaRange.cardinality(), 1);
+ assertEquals(viaRange.serialize(), viaPoint.serialize());
+
+ viaRange.add(v, v + 1); // idempotent
+ viaPoint.add(v);
+ assertEquals(viaRange.cardinality(), 1);
+ assertEquals(viaPoint.cardinality(), 1);
+
+ assertTrue(viaRange.remove(v, v + 1));
+ assertTrue(viaPoint.remove(v));
+ assertFalse(viaRange.contains(v));
+ assertEquals(viaRange.cardinality(), 0);
+ assertEquals(viaRange.serialize(), viaPoint.serialize());
+ }
+ // Note: contains(v, v + 1) is deliberately not asserted here — see
+ // testUint32BoundaryRange for the documented false-negative at the uint32 boundary.
+ }
+
+ @Test
+ public void testSingleValueRangeAddMatchesPointAdd() {
+ // add(v, v + 1) must be indistinguishable from add(v) through the whole LongBitmap
+ // surface, including persisted bytes. Each seed crosses the 4096 array-to-bitmap
+ // container conversion, and the last one reaches the uint32 boundary where
+ // (int) from == -1.
+ long[] seeds = {0, 1, 4090, 65530, 1L << 20, 0x7FFFF000L, 0xFFFFFFFFL - 8200};
+ for (long seed : seeds) {
+ LongBitmap viaRange = LongBitmaps.create();
+ LongBitmap viaPoint = LongBitmaps.create();
+ for (int i = 0; i < 8300; i++) {
+ long v = seed + i;
+ if (v > 0xFFFFFFFFL) {
+ break;
+ }
+ viaRange.add(v, v + 1);
+ viaPoint.add(v);
+ assertEquals(viaRange.cardinality(), viaPoint.cardinality(),
+ "seed " + seed + " i " + i);
+ }
+ assertEquals(viaRange.serialize(), viaPoint.serialize(), "seed " + seed);
+ assertEquals(viaRange.serializedSize(), viaPoint.serializedSize());
+ assertEquals(viaRange.lastPresentValue(), viaPoint.lastPresentValue());
+ for (int i = 0; i < 8300; i += 97) {
+ long v = seed + i;
+ if (v > 0xFFFFFFFFL) {
+ break;
+ }
+ assertEquals(viaRange.rank(v + 1), viaPoint.rank(v + 1));
+ assertEquals(viaRange.nextAbsentValue(v), viaPoint.nextAbsentValue(v));
+ assertEquals(viaRange.nextPresentValue(v), viaPoint.nextPresentValue(v));
+ }
+ }
+ }
- bitmap.add(v); // idempotent
- assertEquals(bitmap.cardinality(), 1);
+ @Test
+ public void testCapacitySlackIsNotObservable() {
+ // The backing container is grown geometrically and shrunk on removal, so its capacity
+ // can exceed its cardinality. Nothing observable through LongBitmap may depend on that:
+ // serialization writes exactly `cardinality` values.
+ LongBitmap withSlack = LongBitmaps.create();
+ for (int i = 0; i < 3000; i++) {
+ withSlack.add(i * 2L);
+ }
+ for (int i = 0; i < 1500; i++) {
+ withSlack.remove(i * 2L);
+ }
+ LongBitmap fresh = LongBitmaps.create();
+ for (int i = 1500; i < 3000; i++) {
+ fresh.add(i * 2L);
+ }
+ assertEquals(withSlack.cardinality(), fresh.cardinality());
+ assertEquals(withSlack.serializedSize(), fresh.serializedSize());
+ assertEquals(withSlack.serialize(), fresh.serialize());
+ assertEquals(withSlack.serializeToLongArray(), fresh.serializeToLongArray());
- bitmap.remove(v);
- assertFalse(bitmap.contains(v));
- assertEquals(bitmap.cardinality(), 0);
+ LongBitmap grown = LongBitmaps.create();
+ for (int i = 0; i < 5000; i++) {
+ grown.add(i, i + 1L);
+ }
+ LongBitmap pointBuilt = LongBitmaps.create();
+ for (int i = 0; i < 5000; i++) {
+ pointBuilt.add(i);
+ }
+ assertEquals(grown.serialize(), pointBuilt.serialize());
+ assertEquals(grown.serializeToLongArray(), pointBuilt.serializeToLongArray());
+ }
+
+ @Test
+ public void testConcurrentSerializeToLongArray() throws Exception {
+ // serializeToLongArray() runs under the READ lock, so concurrent callers must not
+ // interfere. This fails if the implementation ever reintroduces a conversion that
+ // mutates the live bitmap (the previous MutableRoaringBitmap.toRoaringBitmap() advanced
+ // each container's NIO buffer position and produced BufferUnderflowException here).
+ LongBitmap bitmap = LongBitmaps.create();
+ for (int i = 0; i < 60000; i += 2) {
+ bitmap.add(i);
+ }
+ long[] expected = bitmap.serializeToLongArray();
+
+ int threads = 8;
+ int iterations = 4000;
+ ExecutorService executor = Executors.newFixedThreadPool(threads);
+ AtomicInteger errors = new AtomicInteger();
+ AtomicInteger mismatches = new AtomicInteger();
+ CountDownLatch latch = new CountDownLatch(threads);
+ try {
+ for (int t = 0; t < threads; t++) {
+ executor.submit(() -> {
+ try {
+ for (int i = 0; i < iterations; i++) {
+ if (!Arrays.equals(bitmap.serializeToLongArray(), expected)) {
+ mismatches.incrementAndGet();
+ }
+ }
+ } catch (Throwable e) {
+ errors.incrementAndGet();
+ } finally {
+ latch.countDown();
+ }
+ });
+ }
+ assertTrue(latch.await(60, TimeUnit.SECONDS));
+ } finally {
+ executor.shutdownNow();
}
+ assertEquals(errors.get(), 0, "serializeToLongArray threw under concurrent readers");
+ assertEquals(mismatches.get(), 0, "serializeToLongArray returned a corrupt array");
}
@Test
@@ -698,7 +819,7 @@ public class LongBitmapTest {
public void testUint32BoundaryRange() {
// Verify range APIs handle the uint32 upper boundary correctly.
// add(MAX_UINT32, MAX_UINT32+1) should add exactly one value: MAX_UINT32.
- // Note: MutableRoaringBitmap.contains(long, long) has a known issue at this
+ // Note: RoaringBitmap.contains(long, long) has a known issue at this
// boundary where it returns false even when the value is present, so we only
// test contains(long) single-value form and cardinality.
LongBitmap bitmap = LongBitmaps.create();