Judy Array Architecture and Compressed Bit Structures

This article provides an overview of how Judy arrays achieve near-optimal memory scaling and high computational performance in binary mapping. By dynamically switching between compressed and uncompressed bit structures across a hierarchical digital tree (trie), the Judy array architecture minimizes CPU cache misses, avoids dynamic memory allocation overhead for sparse domains, and delivers fast associative array operations for integer keys.

The Foundation: 256-Way Digital Trees

At its core, a Judy array is a highly optimized, 256-ary digital tree (trie). Keys, typically 32-bit or 64-bit unsigned integers, are partitioned into consecutive bytes (8-bit chunks). Each level of the tree resolves one byte of the key, spanning values from 0x00 to 0xFF.

Standard 256-way tries suffer from massive memory waste because allocating 256 pointers per node for sparsely populated data consumes excessive memory. Judy arrays solve this by refusing to use a uniform node representation. Instead, each node dynamically adapts its internal memory layout based on the number of keys it currently holds.

Adaptive Node Types: Compressed vs. Uncompressed

A Judy array transitions through several internal node structures as the population of a byte branch grows:

1. Linear and Indirect Nodes (Sparse Key Densities): When a node contains only a few keys (e.g., fewer than 32 entries), it stores keys in a tightly packed linear array. Lookups use linear or binary search directly over CPU registers. No full 256-entry pointer table is allocated, maximizing data density within a single CPU cache line.

2. Bitmap and Compressed Bit Nodes (Moderate Densities): As the number of keys grows, the node transitions to a bitmap structure. A 256-bit vector (typically four 64-bit words) represents the presence or absence of sub-branches. Rather than allocating 256 full pointers, the node maintains a compressed pointer array matching only the set bits in the bitmask. To find the location of a child pointer:

   • The system checks if the bit corresponding to the key byte is set.
   • If set, it calculates the bit’s population count (popcount) prior to that position to compute the direct index into the compressed child pointer array. This compressed structure avoids the memory overhead of null pointers while retaining deterministic \(O(1)\) indexing.

3. Uncompressed Direct Nodes (Full Densities): When a node is densely populated (approaching 256 entries), the overhead of bit-counting and indirect indexing outweighs direct memory addressing. The node automatically expands into a direct, uncompressed 256-element array of pointers. In this state, the byte value directly indexes into the array, offering maximum lookup speed at the cost of a fixed memory footprint.

Judy1 vs. JudyL in the Binary Number System

The architecture applies these bit structures to two primary array types:

• Judy1 (Bit Arrays): Acts as an expandable bitset where the existence of an integer key represents a boolean state (true). Judy1 eliminates leaf pointer allocations entirely; terminal nodes pack remaining key bytes directly as bit structures, allowing dense clusters of integers to be represented with minimal memory.
• JudyL (Key-to-Value Maps): Maps an integer key to a word-sized value (such as a pointer or another integer). Terminal leaves store paired key-remainder and value arrays, utilizing the same compressed bitmask strategies to omit unassigned keys.

CPU Cache Alignment and High Performance

The performance of Judy arrays in binary systems is directly tied to modern hardware design. Dynamic transitions between compressed and uncompressed bit formats ensure that most node operations fit entirely within a single L1 or L2 CPU cache line (64 bytes). By minimizing memory bandwidth consumption and utilizing fast native bitwise instructions (such as population count and bit scans), the architecture reduces pointer chasing and keeps execution pipelines saturated.