[improve][broker] Optimize SegmentedLongArray with heap-backed long[][]

[nodece]

Motivation

SegmentedLongArray previously used Netty ByteBuf as its backing store. Every readLong/writeLong operation went through ByteBuf.getLong()/setLong(), adding extra indirection on the hot path of TripleLongPriorityQueue heap operations(siftUp/siftDown).

PR #26010 identified SegmentedLongArray as the remaining bottleneck after optimizing the heap algorithms, and suggested replacing the backing storage with primitive arrays.

This PR replaces the ByteBuf backing store with segmented heap-backed long[][] arrays while preserving the segmented architecture required to support capacities beyond Integer.MAX_VALUE elements (PR #16490).

Modifications

• SegmentedLongArray
  • Replace the ByteBuf backing store with segmented heap-backed long[][] arrays.
  • Use bit-shift/bit-mask for segment lookup instead of division/modulo.
  • Grow the outer segment array using an amortized expansion strategy to avoid copying on every new segment allocation.

Benchmark Results

JMH benchmarks from TripleLongPriorityQueueBenchmark(2 forks, 3 warmup iterations, 5 measurement iterations, JDK 21.0.5).

Before (ByteBuf)

Benchmark	Size	Score (us/op)	Error
recoveryBulkAddThenPop	500,000	454,423	±142,390
recoveryBulkAddThenPop	2,000,000	2,406,656	±680,108
interleavedAddPop	500,000	335,764	±461,320
interleavedAddPop	2,000,000	1,560,565	±403,289
steadyState	500,000	261,449	±11,931
steadyState	2,000,000	1,148,007	±699,420

After (heap-backed long[][])

Benchmark	Size	Score (us/op)	Error
recoveryBulkAddThenPop	500,000	337,634	±6,460
recoveryBulkAddThenPop	2,000,000	1,805,059	±99,786
interleavedAddPop	500,000	231,696	±1,425
interleavedAddPop	2,000,000	1,102,539	±89,740
steadyState	500,000	261,390	±7,856
steadyState	2,000,000	1,054,573	±58,502

Comparison (Size = 2,000,000)

Benchmark	Before (ms)	After (ms)	Improvement
recoveryBulkAddThenPop	2,407	1,805	+25%
interleavedAddPop	1,561	1,103	+29%
steadyState	1,148	1,055	+8%

Note: The baseline measurements showed relatively large variance in some
scenarios, while the new implementation produced noticeably more stable
results. The reported improvements should therefore be interpreted together
with the benchmark error margins.

[void-ptr974]

This looks like a capacity growth contract issue.

SegmentedLongArray uses fixed-size segment addressing:

segmentIndex = offset >>> SEGMENT_SHIFT;
indexInSegment = offset & SEGMENT_MASK;

With this addressing scheme, every segment before the last one must be fully allocated. Otherwise a logical offset can map into a partial middle segment.

For example, with an initial capacity of 3 * 1024 * 1024 longs:

segment[0] = 2M longs
segment[1] = 1M longs
capacity   = 3M longs

After increaseCapacity() appends a new full segment:

segment[0] = 2M longs
segment[1] = 1M longs
segment[2] = 2M longs
capacity   = 5M longs

Offsets in [3M, 4M) are now within the reported capacity, but still map to segment[1], whose physical length is only 1M. A valid write can therefore fail:

SegmentedLongArray a = new SegmentedLongArray(3 * 1024 * 1024);
a.increaseCapacity();

a.writeLong(3 * 1024 * 1024, 1L); // within capacity, but fails

There is also a related caller-side issue: TripleLongPriorityQueue.add() calls increaseCapacity() once and then writes 3 longs for one tuple. If increaseCapacity() only expands a partial last segment to SEGMENT_SIZE, it may still not provide enough room for the pending 3-long write when the capacity is just below a segment boundary.

It would be safer for the growth API to express the required target capacity, for example:

array.ensureCapacity(arrayIdx + ITEMS_COUNT);

and have SegmentedLongArray guarantee:

capacity >= requiredCapacity
all segments before the last segment are full-sized

Alternatively, the caller would need to keep growing in a loop until the pending write is guaranteed to fit.

[void-ptr974]

This is a good CPU-side improvement. One concern I have is the GC impact from moving the backing storage from Netty direct memory to Java heap.

The logical storage size is roughly the same, but large queues will now use heap long[] segments. This may add sizable long-lived heap allocations and, under G1, could also involve humongous allocations.

It would be good to have an estimate of the GC impact in realistic broker-side scenarios. It may also be worth evaluating whether the existing segment size is still appropriate when the backing storage is on-heap.

[nodece]

@void-ptr974

Thanks for your GC concern. I analyzed production metric CSV files under realistic broker load (50k msg/s, 30M ledger entries), with full charts attached:

1. Zero G1 humongous allocations, Eden usage fluctuates normally.
2. Massive heap reclamation (over 2GiB freed) after every seal shows temporary objects get cleaned up efficiently by GC; Survivor region recycling is healthy.
3. CPU drop post-seal comes from reduced allocation pressure instead of GC STW pauses, no abnormal GC stalls observed.
4. Primitive long[] adds negligible GC marking overhead without reference tracing cost.

Two seal events captured during a 16-minute window:

Event	Time	Heap	CPU User
seal-1	09:46:40	3.52 GiB → 1.42 GiB (−2.1 GiB / 16s)	22.9% → 14.6%
seal-2	09:56:00	3.62 GiB → 1.33 GiB (−2.29 GiB / 13s)	22.3% → 19.3%

CPU:

GC: