ART Prefix Trees: Memory and Cache Optimization

Optimizing Prefix Trees: From 825 MB to 18 MB for Autocomplete

A trie for searching 50,000 commands consumed 825 MB of memory and ran 8 times slower than a hash table (4.8M cycles vs. 600K). Each node was 2,064 bytes with a 256-pointer array, causing frequent cache misses during lookups.

The perf stat benchmark revealed 125K cache misses versus just 18K for the hash table. Searching a 5-character string triggered 5 cache misses because each node didn’t fit in a single cache line.

Node Structure and Memory Usage

Standard node implementation:

typedef struct trie_node {
    struct trie_node *children[256];  // 2048 bytes
    void *value;                      // 8 bytes
    bool is_end;                      // 1 byte
    // Total: 2064 bytes
} trie_node_t;

For a dataset of 50K commands (average length 8 characters), ~400K nodes were needed—825 MB compared to just 1.2 MB for a hash table, a 687× difference.

Compact Tries: Chain Compression

Solution: Compact tries (Patricia tries), where chains of single-child nodes are compressed into prefixes. Nodes store prefix strings instead of individual characters.

typedef struct radix_node {
    char *prefix;
    int prefix_len;
    struct radix_node *children[256];
    void *value;
} radix_node_t;

Search algorithm:

void* radix_search(radix_node_t *node, const char *key) {
    while (node) {
        int i = 0;
        while (i < node->prefix_len && key[i] == node->prefix[i]) {
            i++;
        }
        if (i < node->prefix_len) return NULL;
        if (key[i] == '\0') return node->value;
        node = node->children[(unsigned char)key[i]];
        key += i + 1;
    }
    return NULL;
}

Result: Memory dropped to 330 MB, cycles to 2.4M, and cache misses to 6.8—a 2× speedup.

Adaptive Radix Trees (ART)

Problem remained: 98% of the 256-pointer arrays were empty. Solution: adaptive nodes based on child count.

• Node4 (1–4 children): 40 bytes
• Node16 (5–16 children): 152 bytes
• Node48 (17–48 children): 640 bytes
• Node256 (49+ children): 2048 bytes

Growth strategy: Node4 → Node16 → Node48 → Node256 when limits are exceeded.

Average node size: 40–152 bytes vs. 2048—memory savings of 10–50×.

Benchmark Results

Comparison across 1M searches over 50K commands:

| Structure | Memory | Cycles | Cache Misses | Speedup |

|-----------|--------|--------|--------------|---------|

| Trie | 825 MB | 4,800 | 12.5 | 1× |

| Radix | 330 MB | 2,400 | 6.8 | 2× |

| ART | 18 MB | 1,200 | 3.2 | 4× |

| Hash | 1.2 MB | 600 | 1.8 | 8× |

ART is 45× more compact than standard trie; Node4/Node16 nodes fit in 1–2 cache lines.

Use Cases for Prefix Trees

Use ART when you need prefix operations:

• Autocomplete: Traverse subtree in O(k + m), where m is matches. Hash tables require full scan.
• IP Routing: Longest prefix matching by address bits.
• Spell Checking: Search via edit distance using prefixes.
• Sparse Arrays: As used in the Linux kernel (page cache, IDR, XArray).

Avoid for exact lookups, small datasets (<1,000 items), or strings with no shared prefixes.

Compact Tries in the Linux Kernel

The kernel uses radix_tree_node with 64 slots (6 bits per level). For a 32-bit index, that’s 6 levels—~6 cache misses vs. 32 for BST.

Advantages:

• Range operations support
• Predictable O(log₆₄ n) complexity
• Efficient for sparse data

Key Takeaways

• Standard tries use 687× more memory due to 256-pointer arrays
• ART reduces memory to 18 MB and cache misses to 3.2 via adaptive nodes
• Use for prefix queries; hash tables win at exact lookup
• Compact tries compress chains, delivering 2× speedup
• Linux kernel uses them for sparse arrays and ID allocation

— Editorial Team