Engineering Practical Succinct Bit Vectors: A Space-Time Pareto Analysis on Apple Silicon ARM64 Cores

Ishant Garg

arxiv: 2605.25528 · v1 · pith:EQFFPGMEnew · submitted 2026-05-25 · 💻 cs.DS

Engineering Practical Succinct Bit Vectors: A Space-Time Pareto Analysis on Apple Silicon ARM64 Cores

Ishant Garg This is my paper

Pith reviewed 2026-06-29 19:58 UTC · model grok-4.3

classification 💻 cs.DS

keywords succinct bit vectorsrank queriesselect queriesRRR codingARM64block indexingperformance measurementspace-time tradeoffs

0 comments

The pith

Asymmetric 4096/256-bit blocks deliver 1.4x faster rank queries on Apple Silicon with 7.8% overhead.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper evaluates three bit vector designs for rank and select: a standard two-level block layout, an asymmetric superblock variant, and an entropy-compressed RRR version. It reports concrete speedups on Apple M-series ARM64 processors from tuned block sizes and a superblock sampling index that keeps scans inside L1 cache. These measurements matter because many applications store large bitmaps in compressed form and need fast direct queries without full decompression. The work also documents a density-dependent latency pattern in the RRR design and confirms all code against a large assertion fuzzer.

Core claim

Asymmetric block boundaries of 4096 and 256 bits yield a 1.4 times speedup for rank queries at 7.8 percent rank index overhead on Apple Silicon ARM64 cores. RRRBitVec reaches 4.9 times faster select than binary-search baselines, finishing in 33.7 nanoseconds at uniform density by restricting sequential work to L1-cache superblock samples. Rank latency in RRRBitVec follows a symmetric bell curve that improves up to 39 percent at extreme densities because boundary-class offsets disappear.

What carries the argument

Asymmetric superblock and block boundaries together with superblock-level sampling indexes inside the RRR coding scheme

Load-bearing premise

The speedups measured on Apple M-series cores will appear under representative real-world query workloads and data distributions.

What would settle it

Re-running the same three implementations on a non-Apple ARM64 core or on x86-64 with production bit-vector workloads and checking whether the reported 1.4x rank and 4.9x select speedups remain.

read the original abstract

Succinct data structures use space close to the information-theoretic minimum while answering queries directly on the compressed representation. In this paper, we present a practical engineering study of rank and select queries on bit vectors. We evaluate a classic two-level block baseline (BlockBitVec), an asymmetric superblock implementation (FastBitVec), and an entropy-compressed representation (RRRBitVec) based on the Raman, Raman, and Rao (RRR) coding scheme. On Apple Silicon (M-series ARM architecture), we demonstrate a 1.4x speedup in rank queries through asymmetric 4096/256-bit block boundaries, with a rank index overhead of 7.8%. We investigate the empirical behavior of RRRBitVec and observe a symmetric density-dependent bell-curve for rank latency -- where queries at extreme densities (1% and 99%) run up to 39% faster due to offset elimination at boundary classes. We further show that RRRBitVec achieves a 4.9x speedup over classic binary-search select baselines, running in 33.7 ns at uniform density by using a superblock-level sampling index that restricts sequential scans to L1-cache lookups. All implementations are validated against a correctness fuzzer executing over 78 million assertions with no failures. Source code and test harnesses are publicly available.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

Solid measured speedups and public artifacts for bit vectors on Apple M-series, but incremental engineering tuning with no new primitives.

read the letter

This paper reports concrete performance numbers for rank and select on three bit vector implementations tuned for Apple Silicon ARM64. The main results are the 1.4x rank improvement from asymmetric 4096/256-bit blocks at 7.8% overhead and the 4.9x select speedup for RRRBitVec to 33.7 ns via superblock sampling.

The work does the engineering basics well. It ships public code, runs a 78-million-assertion fuzzer with zero failures, and directly measures the target hardware. The density-dependent latency curves for RRR rank, where extremes run faster due to offset elimination, are a clear empirical finding backed by the data. These details matter for anyone who needs to pick block sizes or sampling rates on M-series cores.

Nothing here introduces new algorithmic ideas. The two-level blocking and RRR coding are established techniques; the paper applies them with hardware-specific parameter choices and reports the resulting timings. The central claims rest entirely on those measurements rather than derivations or predictions.

The soft spots are the usual ones for this style of study. Speedups are shown on synthetic densities and access patterns, so how well they translate to real workloads like database bitmaps remains an assumption. Results are tied to Apple Silicon, with no data on other ARM cores or x86. These limits are minor for an engineering report but worth noting for readers outside the tested setup.

This is useful for practitioners who implement succinct structures on modern ARM hardware and want configuration guidance plus working code. A reading group focused on systems or practical data structures might cover it. It deserves peer review in a venue that accepts engineering evaluations, because the artifacts and validation are strong enough to support useful referee feedback.

Referee Report

0 major / 3 minor

Summary. The paper presents an empirical engineering study of three succinct bit-vector implementations for rank and select queries on Apple Silicon ARM64: a classic two-level BlockBitVec, an asymmetric FastBitVec with 4096/256-bit superblock/block boundaries, and an RRRBitVec using Raman-Raman-Rao coding. It reports concrete performance numbers including a 1.4x rank speedup at 7.8% index overhead for the asymmetric design, density-dependent rank latency in RRRBitVec (up to 39% faster at 1%/99% densities), and a 4.9x select speedup to 33.7 ns via superblock sampling that limits scans to L1 cache. All implementations are validated by a public 78-million-assertion fuzzer with zero failures, and source code is released.

Significance. If the measurements are representative, the work supplies architecture-specific, reproducible timing data and implementation techniques (asymmetric boundaries, superblock sampling) that practitioners can directly apply when deploying succinct structures on M-series cores. The combination of public code, extensive fuzzing, and Pareto-style space-time reporting on a concrete platform strengthens its utility for the succinct-data-structures community.

minor comments (3)

[§3.2] §3.2 and Figure 4: the description of the 'symmetric density-dependent bell-curve' for RRR rank latency would benefit from an explicit statement of how many independent runs and which density points were averaged to produce each plotted point.
[Table 2] Table 2: the reported 33.7 ns select time for RRRBitVec at uniform density should include the corresponding space overhead percentage so readers can directly compare the space-time trade-off with the binary-search baseline.
[§4] The abstract and §4 claim '78 million assertions' but the fuzzer description does not state the exact distribution of test vectors (e.g., fraction at extreme densities or with adversarial block alignments).

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive review and recommendation to accept. We appreciate the recognition of the empirical results, public code, and fuzzing validation on Apple Silicon ARM64.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper is an empirical engineering study consisting of concrete implementations (BlockBitVec, FastBitVec, RRRBitVec), direct timing measurements on Apple M-series ARM64 hardware, and validation via a 78-million-assertion fuzzer. No derivation chain, equations, fitted parameters presented as predictions, or load-bearing self-citations exist. All reported speedups (1.4x rank, 4.9x select) and overheads are measured quantities on specific hardware and data distributions, with public code provided. The analysis is fully self-contained against external benchmarks and contains no self-definitional, fitted-input, or uniqueness-imported steps.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The work rests on standard assumptions about bit-vector semantics and cache behavior on ARM64; the only engineering parameters are the chosen block sizes and sampling densities, which are presented as design choices rather than fitted constants.

free parameters (2)

block boundary sizes
4096-bit and 256-bit boundaries selected for L1-cache fit on Apple Silicon; these are explicit engineering parameters that determine the reported 1.4x speedup.
superblock sampling interval
Sampling density chosen to restrict sequential scans to L1-cache lookups; directly affects the 4.9x select speedup claim.

axioms (2)

domain assumption Rank and select operations on the compressed representation produce identical results to the uncompressed bit vector.
Invoked implicitly when claiming correctness via the fuzzer; standard for succinct data structures.
domain assumption Hardware performance counters and timing measurements on Apple M-series cores reflect stable, representative behavior.
Required for the reported nanosecond latencies and speedups to be meaningful.

pith-pipeline@v0.9.1-grok · 5766 in / 1501 out tokens · 24062 ms · 2026-06-29T19:58:58.066889+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

3 extracted references · 2 canonical work pages

[1]

Space-efficient static trees and graphs

5 Guy Jacobson. Space-efficient static trees and graphs. InProceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 549–554. IEEE, 1989.doi: 10.1109/SFCS.1989.63533. 6 Gonzalo Navarro.Compact Data Structures: A Practical Approach. Cambridge University Press, Cambridge, UK,

work page doi:10.1109/sfcs.1989.63533 1989
[2]

Practical entropy-compressed rank/select dic- tionary

7 Daisuke Okanohara and Kunihiko Sadakane. Practical entropy-compressed rank/select dic- tionary. InProceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 60–70. SIAM, 2007.doi:10.1137/1.9781611972870.6. 8 Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct indexable dictionaries with applications to representat...

work page doi:10.1137/1.9781611972870.6 2007
[3]

Andersen, and Michael Kaminsky

10 Dong Zhou, David G. Andersen, and Michael Kaminsky. Space-efficient, fast rank and select structure. InProceedings of the 2013 IEEE International Conference on Data Engineering (ICDE), pages 1141–1152. IEEE, 2013

2013

[1] [1]

Space-efficient static trees and graphs

5 Guy Jacobson. Space-efficient static trees and graphs. InProceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS), pages 549–554. IEEE, 1989.doi: 10.1109/SFCS.1989.63533. 6 Gonzalo Navarro.Compact Data Structures: A Practical Approach. Cambridge University Press, Cambridge, UK,

work page doi:10.1109/sfcs.1989.63533 1989

[2] [2]

Practical entropy-compressed rank/select dic- tionary

7 Daisuke Okanohara and Kunihiko Sadakane. Practical entropy-compressed rank/select dic- tionary. InProceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 60–70. SIAM, 2007.doi:10.1137/1.9781611972870.6. 8 Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao. Succinct indexable dictionaries with applications to representat...

work page doi:10.1137/1.9781611972870.6 2007

[3] [3]

Andersen, and Michael Kaminsky

10 Dong Zhou, David G. Andersen, and Michael Kaminsky. Space-efficient, fast rank and select structure. InProceedings of the 2013 IEEE International Conference on Data Engineering (ICDE), pages 1141–1152. IEEE, 2013

2013