Classes
class	SuccinctIncreasingStack
	Construction-only stack for monotonically increasing integer keys. More...

Detailed Description

Monotone-stack construction experiment, 2026-06-13.

SIMD investigation: for the RMQ benchmark's uniform-random value arrays, the Cartesian construction pop-run distribution is short: roughly 50% of iterations pop 0 entries, 25% pop 1, 12.5% pop 2, and only about 6.25% pop 4 or more. A SIMD path that gathers several stack-top values would therefore pay gather/setup overhead on mostly short runs. The retained improvement is bit-parallel rather than SIMD: 64-bit key blocks plus compact non-empty block summaries replace the old 63-bit data/pointer-word layout.

Command shape: taskset -c 0 ./build/benchmark-all-backends/rmq_benchmarks –benchmark_filter='^rmq_build_(cartesian_rmm|cartesian_hybrid_btree|sdsl_sct)/(4194304|67108864)$' –benchmark_repetitions=5

CPU mean, milliseconds.

N	row	before	after
2^22	CartesianRmM	44.731	40.274
2^22	CartesianHybridBTree	47.943	45.019
2^22	SdslSct control	39.911	39.628
-—	---------------------—	---—	----—
2^26	CartesianRmM	750.316	678.925
2^26	CartesianHybridBTree	772.157	732.582
2^26	SdslSct control	642.540	644.627

Classes

Detailed Description