Intro — When does packing 64 booleans into a single uint64_t actually help? Benchmarks, hardware counters, and a crossover model for boolean workloads on commodity CPUs.

One bit, sixty-four bits, one byte

A boolean value is theoretically representable with one bit. In practice, general-purpose software often stores booleans as bytes, words, or larger language-level objects. The JVM uses a full byte for boolean. C doesn't even have a native boolean type. Most code just uses int or char.

This mismatch motivates a recurring question: if a workload only needs one bit, does a 64-bit machine waste work by reading and computing on much larger units?

The answer is subtle. x86-64 processors can perform byte loads and byte arithmetic, but normal memory is byte-addressable rather than bit-addressable. Moreover, the physical memory hierarchy is coarser than both bits and bytes: cache lines are commonly 64 bytes, vector registers are hundreds of bits wide, pages are kilobytes, and DRAM internally operates through rows and burst transfers. A single logical bit is therefore embedded within larger architectural and physical units.

We do not argue that general-purpose CPUs should simply become bit-addressable. Instead, we ask: when do packed one-bit representations recover the theoretical density of boolean data on existing CPUs, and when does bit extraction or read-modify-write overhead dominate?

Why bit-addressable memory is not an obvious fix

A literal bit-addressable architecture would assign a unique address to every bit. To cover the same physical memory capacity as byte addressing, addresses would require three additional bits:

$$\\log_2(8N) = \\log_2(N) + 3$$

This would affect more than pointers. Cache tags, TLB tags, page tables, address-generation hardware, ABIs, and pointer-heavy data structures would all have to absorb either wider addresses or reduced addressable capacity. That's a lot of architectural disruption for a problem that might have a simpler solution.

Furthermore, fetching a single useful bit does not imply that hardware can cheaply move only one physical bit. Modern memory systems rely on wide datapaths, DRAM row activation, burst transfers, cache-line fills, and spatial locality. For dense workloads, loading a 64-byte cache line is often beneficial precisely because it brings nearby useful values. In a byte representation, such a line contains 64 booleans; in a packed representation, it contains 512 booleans.

Bit-addressable hardware does exist in specialized contexts: microcontrollers with bit-addressable control regions, FPGAs, and accelerators. These systems demonstrate that bit granularity can be valuable when the hardware and workload are co-designed. They do not imply that making all general-purpose memory bit-addressable would improve broad workloads.

Packed computation as the practical compromise

A packed bitset stores 64 logical booleans per 64-bit word and 512 logical booleans per 64-byte cache line. Access requires address arithmetic to identify the containing word, followed by bit selection:

bit = (words[index >> 6] >> (index & 63)) & 1;

This is more work than indexing a byte array:

bit = bytes[index] != 0;

But the packed representation allows existing CPUs to perform bulk bit-level work efficiently. A scalar 64-bit AND, OR, or XOR represents 64 logical boolean operations. The POPCNT instruction counts set bits in a machine word and is especially useful for dense bitset algorithms, Hamming distance, and binary similarity. SIMD extensions such as AVX2 and AVX-512 can operate on still wider packed registers, though this preliminary study uses scalar uint64_t packing.

Experimental setup

The benchmark suite compares two representations:

• Byte booleans: one logical boolean per uint8_t element
• Packed bits: 64 logical booleans per uint64_t word

The benchmark is written in C and compiled with -O3 -march=native -std=c11. Data is allocated with 64-byte alignment. Inputs are initialized using deterministic pseudo-random sequences. Timing excludes allocation and initialization and uses clock_gettime(CLOCK_MONOTONIC_RAW). Results are accumulated into a volatile sink to inhibit dead-code elimination.

We evaluate six kernels:

• count: count true values
• and: compute pairwise boolean conjunction and count true outputs
• xor: compute pairwise exclusive-or and count true outputs
• random_read: read logical booleans through a random index array
• random_toggle: toggle randomly selected logical booleans
• xnor_popcount: count equal bits, modeling a binary similarity or binary neural network primitive

The packed XNOR-popcount kernel uses:

matches += popcount(~(a_word ^ b_word));

Measurement environment

Results

Dense kernels: where packing dominates

At $2^{26}$ logical bits, packed representations produced large speedups for dense operations:

Three-trial median at $2^{26}$ logical bits.

Dense kernels show large gains from packing. Counting and XNOR-popcount benefit especially because POPCNT summarizes 64 logical booleans per word. Dense AND and XOR also benefit, though their measured speedups are lower than the theoretical 64x because memory traffic, loop overhead, and counting work remain.

The XNOR-popcount result is particularly important. Binary similarity, Hamming distance, and binary neural network kernels can often be reduced to XNOR followed by POPCNT. The measured ~42x timing improvement indicates that existing scalar x86-64 instructions already recover a large fraction of the theoretical benefit of one-bit data for dense kernels.

Random access: where it gets interesting

Random workloads show smaller but still substantial gains at $2^{26}$ bits. This is important because random packed access performs additional arithmetic per logical value. The improvement therefore cannot be explained by instruction reduction alone; it requires memory-hierarchy effects.

But at $2^{10}$ logical bits, packed random access is slower than byte access. random_read over uint8 takes approximately 0.0036 to 0.0037 seconds, while packed random_read takes approximately 0.0056 to 0.0065 seconds. Similarly, random_toggle over uint8 takes approximately 0.0056 to 0.0078 seconds, while packed random_toggle takes approximately 0.0081 to 0.0101 seconds.

This is the crossover. When the working set is small and cache-resident, the extra shift, mask, and read-modify-write operations in packed access can dominate. Packing is not universally faster.

Hardware counter evidence

perf stat counters for random access kernels at $2^{26}$ logical bits reveal the mechanism:

Process-level perf stat counters, filtered benchmark invocations.

The packed random kernels retire more instructions than the byte kernels. This is expected: packed access requires index decomposition, shifting, masking, and for toggles, read-modify-write behavior on the containing word. However, packed access reduces cache misses substantially. For random_read, cache misses fall from approximately 1.39B to 575M. For random_toggle, they fall from approximately 1.73B to 767M. The reduction in memory stalls is large enough that packed access also reduces total cycles.

These counters support the central mechanism of this paper: packed representations trade additional computation for reduced memory pressure. Whether that trade is favorable depends on working-set size, cache residency, and access pattern.

The crossover model

The results suggest a simple model. Let $C_e$ denote extraction and update overhead for packed access, and let $C_m$ denote memory-hierarchy cost. Byte arrays minimize $C_e$ but use eight times as much storage per logical boolean. Packed arrays increase $C_e$ but reduce $C_m$ when the working set stresses cache or memory bandwidth.

Thus, packed access wins when:

$$\\Delta C_m > \\Delta C_e$$

For dense scans and bulk logic, $\Delta C_e$ is amortized across many bits per word and is usually small. For random single-bit access, $\Delta C_e$ is paid per logical value and can dominate until the working set becomes large enough that memory pressure controls performance.

Applications

The crossover model has direct implications for several domains:

Binary neural networks and low-bit models. Dense binary dot products can be implemented using XNOR followed by popcount. When computation is dense and data is packed, commodity CPUs can process many logical values per instruction. However, if a model layout requires frequent irregular single-bit access, extraction overhead and cache behavior may become limiting.

Binary embeddings and similarity search. Hamming distance between binary vectors maps naturally to popcount(a ^ b). Packed representations reduce memory bandwidth and allow large databases of binary vectors to remain cache-resident for longer.

Bitmap indexes and databases. Dense AND, OR, and XOR operations over packed bitmaps are a strong match for current CPUs. Bulk bitmap operations benefit substantially from packing, while workloads dominated by isolated random updates require more careful layout and batching.

Bloom filters and probabilistic data structures. These use compact bit arrays with pseudo-random access patterns. Packing improves cache density, but each access needs bit selection and updates to containing words. The measured crossover behavior is therefore important for choosing filter size, hash count, and batching strategy.

SAT solvers and graph algorithms. Dense bitset operations can be extremely efficient on packed data. Algorithms that repeatedly touch individual bits may need batching or layout transformations to avoid paying extraction overhead on every operation.

Cellular automata and simulation. Packed representations can reduce memory footprint and improve cache behavior, but neighborhood updates may require shifts across word boundaries. Such workloads are a promising future benchmark because they mix dense bit-level computation with structured local access.

Limitations and future work

This study has several limitations. It uses one CPU and one compiler configuration. It compares only byte arrays and scalar uint64_t packing. It does not yet include manual AVX2 or AVX-512 implementations, multicore scaling, false sharing behavior, or real application kernels beyond microbenchmark proxies. Hardware-counter data currently includes setup overhead, even though timing excludes setup.

Future work should add a counter-isolation mode that initializes once and then measures only the selected kernel. Manual SIMD implementations should be compared against scalar packing and compiler-vectorized byte arrays. Additional systems, including AVX-512-capable CPUs and lower-power processors, should be tested. Realistic application workloads such as binary-vector search, bitmap query processing, and binary neural network inference should be added.

Conclusion

Logical one-bit data does not map directly onto the byte-addressed, cache-line-based, word-oriented structure of commodity CPUs. However, true general-purpose bit-addressability is not an obvious improvement because it conflicts with pointer size, memory hierarchy, and spatial locality considerations.

Packed representations are the practical compromise. For dense workloads, they recover substantial bit-level efficiency through storage density, cache-line density, word-level boolean operations, and POPCNT. For sparse random workloads, they introduce additional instruction overhead. The measured data shows that this overhead can dominate at small sizes, but at larger working sets packed access can still win by reducing cache misses and memory pressure.

The central lesson is not that single-bit reads are universally desirable. Rather, the performance of bit-level workloads depends on access pattern and working-set size. Existing CPUs are already highly effective for dense packed bit computation, while sparse bit access remains a measurable and application-relevant tradeoff.