Engineering Practical Succinct Bit Vectors: A Space-Time Pareto Analysis on Apple Silicon ARM64 Cores
Ishant Garg · 2026
Read Engineering Practical Succinct Bit Vectors: A Space-Time Pareto Analysis on Apple Silicon ARM64 Cores by Ishant Garg (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-25528.txt.
Introduction
Ishant Garg engineers practical succinct bit vectors, compressed structures answering rank and select queries near the information-theoretic minimum. He evaluates a classic two-level block baseline, an asymmetric superblock design, and an entropy-compressed RRR design on Apple Silicon ARM64 cores. Asymmetric 4096/256-bit block boundaries speed rank queries 1.4 times, at a rank index overhead near eight percent. The RRR design runs select queries 4.9 times faster than binary-search baselines, near 34 nanoseconds at uniform density, and all implementations pass a fuzzer over 78 million assertions.
Catalog record
| CREATOR | Ishant Garg |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 36984 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.25528
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Engineering Practical Succinct Bit Vectors: A Space-Time Pareto Analysis on Apple Silicon ARM64 Cores Ishant Garg 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 ( B l o c k B i t V e c BlockBitVec ), an asymmetric superblock implementation ( F a s t B i t V e c FastBitVec ), and an entropy-compressed representation ( R R R B i t V e c RRRBitVec ) based on the Raman, Raman, and Rao (RRR) coding scheme. On Apple Silicon (M-series ARM architecture), we demonstrate a 1.4 × 1.4\times speedup in rank queries through asymmetric 4096/256-bit block boundaries, with a rank index overhead of 7.8 % 7.8\% . We investigate the empirical behavior of R R R B i t V e c RRRBitVec and observe a symmetric density-dependent bell-curve for rank latency—where queries at extreme densities (1% and 99%) run up to 39 % 39\% faster due to offset elimination at boundary classes. We further show that R R R B i t V e c RRRBitVec achieves a 4.9 × 4.9\times speedup over classic binary-search select baselines, running in 33.7 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 78 million assertions with no failures. Source code and test harnesses are publicly available. Independent Researcher, [email protected]://orcid.org/0009-0005-7281-5421 ccs Theory of computation Succinct data structures ccs Theory of computation Design and analysis of algorithms keywords Succinct Data Structures, Rank and Select, RRR Coding, Algorithm Engineering, Micro-architectural Optimization, Apple Silicon † † runningtitle: Engineering Practical Succinct Bit Vectors † † runningauthor: I. Garg † † copyright: Ishant Garg † † supplement: Source code and correctness fuzzers are publicly available at https://github.com/ishantgarg2332/succinct-bitvec-cpp . 1 Introduction Since Jacobson’s seminal work [ 5 ] introducing succinct data structures, rank and select queries have been the foundational building blocks of modern succinct designs, including Wavelet Trees, Succinct Trees, and FM-Indices. Given a bit vector B[0\dots N-1] : • \text{rank}_{1}(B,i) returns the number of 1 -bits in the prefix B[0\dots i] . • \text{select}_{1}(B,j) returns the index of the (j+1) -th set bit in B . While theoretical succinct structures guarantee o(N) bits of space overhead and O(1) query times, the constant factors in practice depend heavily on the memory hierarchy, cache miss rates, instruction-level parallelism (ILP), and the cost of bitwise operations such as popcount. Practical, standard implementations of these theoretical designs are available in the Succinct Data Structure Library (SDSL) [ 3 ] , and are summarized in textbooks such as Navarro’s comprehensive reference [ 6 ] .In this work, we present an engineering study of rank and select structures. We examine the space-time Pareto frontier (visualized in Figure 1 ) by benchmarking three implementations 1 1 1 To support open science and reproducible research, our source code and correctness fuzzers are publicly available at https://github.com/ishantgarg2332/succinct-bitvec-cpp . : 1. BlockBitVec : A standard two-level index structure with 2048 -bit superblocks and 512 -bit blocks, yielding an index overhead of \approx 6.25\% . 2. FastBitVec : An engineered variant featuring asymmetric block sizing ( 4096 -bit superblocks and 256 -bit blocks) to saturate instruction pipelining, paired with a coarse-grained select sampling index to replace global binary search. 3. RRRBitVec : A practical implementation of the Raman, Raman, and Rao compressed representation with block size b=15 . This structure compresses the underlying bit string approaching its zeroth-order empirical entropy H_{0} while supporting direct rank and select queries. In this work, we demonstrate that by tuning the block boundaries asymmetrically to 4096/256 bits, we can engineer a structure ( FastBitVec ) that achieves an average rank latency of 1.65 ns on wide-issue ARM64 cores at only 7.8% index space overhead—strictly dominating the industry-standard SDSL rank support (2.25 ns at 25% overhead). Moreover, we leverage a superblock-level sampling index for RRRBitVec to reduce DRAM latency overhead, restricting sequential decompression scans to L1 data caches and accelerating select queries to 33.7 ns. 2 Related Work The practical implementation of succinct rank and select structures has been an active area of algorithm engineering. The most widely used baseline is the Succinct Data Structure Library (SDSL) [ 3 ] , which provides standard plug-and-play implementations such as sdsl::rank_support_v and sdsl::select_support_mcl . SDSL’s rank directory uses a standard two-level superblock/block layout requiring 25% space overhead (with 512-bit superblocks and 64-bit blocks) to achieve fast query execution. To reduce this space overhead, several advanced indexing directories have been proposed. Vigna’s rank9 layout [ 9 ] utilizes broadword programming techniques to pack a 64-bit superblock along with nine 32-bit relative offsets into a single 512-bit word. This achieves a flat 25% space overhead and delivers high performance on 64-bit systems by minimizing cache line fetches. Another landmark structure is Poppy by Zhou et al. [ 10 ] , which introduces a multi-level directory structure using 32-bit offsets to reduce the index space to just 3–4% of the bit vector size while remaining competitive in time. For select queries, Clark and Munro [ 1 , 2 ] established foundational theoretical frameworks supporting constant-time select queries. In practice, building a separate select index consumes substantial space, leading to extensive research into compact indexing directories. However, prior evaluations of these structures have predominantly focused on x86 architectures, where word sizes and instruction-level parallelism (ILP) characteristics differ from modern out-of-order ARM64 pipelines. Furthermore, the practical integration of the Raman, Raman, and Rao (RRR) compressed scheme [ 8 ] has historically been regarded as slow due to the decompression overhead of block classes and offsets. Key steps toward practical RRR implementations include the work of González et al. [ 4 ] , who explored look-up table architectures, and Okanohara and Sadakane [ 7 ] , who proposed alternative entropy-compressed structures such as d-arrays. 3 Algorithmic and System Design 3.1 Baseline Block Layout ( BlockBitVec ) The classic two-level rank index divides a bit vector of length N into superblocks of size S=2048 bits, and blocks of size B=512 bits. The superblock array stores the cumulative rank from the beginning of the vector using a 64-bit counter ( uint64_t ). The block array stores the relative rank from the start of the enclosing superblock. Since relative ranks within 2048 bits cannot exceed 2048 , they are compactly represented using 16-bit integers ( uint16_t ). The index overhead is computed as: \text{Overhead}=\frac{64}{2048}+\frac{16}{512}=0.03125+0.03125=0.0625\text{ bits per element (bp)}\quad(6.25\%) (1) 3.2 Asymmetric Superblocking and Popcount Pipelining ( FastBitVec ) To optimize rank latency, we introduce FastBitVec , which restructures the block boundaries asymmetrically: • Superblock size S=4096 bits (64-bit integer index). • Block size B=256 bits (16-bit integer index). This layout changes the index overhead slightly: \text{Overhead}=\frac{64}{4096}+\frac{16}{256}=0.015625+0.0625=0.078125\text{ bits per element}\quad(7.81\%) (2) The