Hardening a 20-Year-Old C Library with AI Agents

I recently took on the task of cutting worker memory in PHP with Judy arrays by modernizing my 2010 PECL extension for PHP 8.1–8.5 and providing the framework pieces it lacked ( judy-polyfill and judy-cache) for long-running CLI daemons, FrankenPHP, and Laravel Octane workers.

Originally, php-judy relied on libJudy 1.0.5, which is an overwhelming 20,000-line C library written at HP in 2002 that has been unmaintained upstream on SourceForge since 2007, with open bug reports and -O3 compiler issues. Rather than leaving an old library as an external black box, I decided to vendor it directly into php-judy 2.6.0, fix its latent bugs, and tune it for modern CPUs.

This post is a technical experience report on what happened: how Judy arrays work, why an AI agent’s initial “no headroom” verdict was mathematically impossible, the critical upstream bugs we uncovered in 20-year-old C code, and how strict SRE guardrails kept the research grounded.

How Judy Arrays Work

Invented by Doug Baskins at Hewlett-Packard in the early 2000s, libJudy provides three dynamic data structures:

• Judy1: A sparse, ordered bitset (integer index → boolean bit).
• JudyL: A sparse, ordered word-to-word map (integer key → integer value/pointer).
• JudySL: A sparse, ordered string-to-word map (null-terminated string → integer value/pointer).

Unlike conventional search trees, Judy was designed from the silicon up to minimize CPU cache-line fills rather than theoretical algorithmic step counts.

Expanse Partitioning vs. Population Partitioning

Most search trees partition data by population (such as B-Trees, Red-Black trees, or AVL trees). A B-Tree balances itself dynamically based on the number of stored keys, splitting and merging pages to bound tree height.

Judy takes a fundamentally different approach: it is an expanse-partitioned 256-ary digital tree (trie). The key space is divided into fixed, predetermined 8-bit numerical ranges (bytes), decoding keys byte-by-byte from most to least significant.

How Judy Solves Radix Trie Memory Bloat

While Judy is fundamentally a 256-ary digital trie, it avoids the memory waste of traditional wide tries. A naive 256-ary radix trie allocates 256 pointers (2,048 bytes on 64-bit) at every branch level—wasting 99% of memory if a node only has two child keys.

Judy eliminates this waste through three core mechanisms:

1. Polymorphic Node Compression: Nodes dynamically morph based on local key density.
   • Linear Branches: Pack 1–7 child pointers and a sorted 1-byte digit array into a single cache line.
   • Bitmap Branches: A 2-tier structure dividing 256 bits into 8 subexpanses of 32 bits, paired with 8 pointers to packed child arrays.
   • Uncompressed Branches: Flat array of 256 pointers used only when densely populated.
2. 16-byte “Rich Pointers” (Judy Pointers / JPs): Instead of raw 8-byte machine pointers, edges store a 16-byte struct holding the target address, up to 7 skipped prefix bytes for level-skipping (narrow pointers), a subtree population count (pop0), and a layout type tag.
3. Immediate Storage: If a subexpanse holds 1–15 keys, Judy inlines the keys and values directly inside the 16-byte parent JP without allocating a child node on the heap.
4. Native Counting Trees: Because every JP tracks the population count of its entire subtree, Judy performs O(depth) range counts (JudyCount) and rank queries (JudyByCount) without walking individual leaves.

The 2002 vs. 2026 Hardware Mismatch

Baskins’s implementation is a masterclass in bit-packing, but it was written for hardware that looks very different from modern CPUs:

This gap between 2002 assumptions and modern microprocessors is where we found room for substantial latency wins.

Vendoring libJudy and Challenging AI Assumptions

Treating libJudy as an external binary dependency created several operational headaches:

1. Packaging friction: Users had to install libjudy-dev via apt or brew install judy before compiling PHP.
2. Upstream stagnation: The code has had zero upstream releases since 2007.
3. Compiler modernization: Modern GCC and Clang compilers apply aggressive optimizations that break assumptions in 20-year-old C code.

Downstream projects like Netdata had to fork and vendor their own copy (netdata/libjudy) to keep builds working. I decided to vendor and modernize libJudy directly within php-judy 2.6.0.

The Initial AI Claim: “No Headroom”

I tasked an initial AI agent with building a proof of concept (POC) to benchmark hardware popcount and SIMD acceleration in libJudy. After running an isolated micro-benchmark on an experimental branch, the agent returned a confident, structured verdict:

“The profiler indicates ~80% memory-stalled cycles during trie traversal. Compute instructions constitute less than 15% of runtime. Hardware popcount yields no statistically significant improvement. Conclusion: Close the SIMD/popcount ticket; do not vendor libJudy.”

Looking closely at the benchmark setup, the flaws were immediately obvious:

1. The math was physically impossible: The agent reported 56 million simulated L3 cache misses and claimed ~80% serialized memory stalls (assuming a serial memory-level parallelism of $\text{MLP} = 1$). At 70–90 ns per DRAM access, 56M serialized misses would require 3.92 to 5.04 seconds of memory-stall time alone—in a benchmark run that finished in 3.76 seconds total while retiring 24.8 billion CPU instructions. In simple terms: the agent claimed the CPU spent more time waiting on slow RAM than the entire test took to run from start to finish. Real out-of-order execution achieved memory concurrency ($\text{MLP} = 3.2\times$), leaving substantial headroom for compute optimizations.
2. Degenerate test keys: The harness generated synthetic keys where every branch evaluated to the same intermediate node type (BRANCH_B), bypassing 90% of libJudy’s internal branch cascade and never reaching the leaf types that actually benefit from popcount.
3. Compiler misattribution: The agent enabled -mpopcnt and hoped GCC’s auto-vectorizer would magically recognize Judy’s straight-line bit-twiddling macros, rather than explicitly patching the C source.
4. Sample size of one: The entire claim rested on a single unreplicated build ($n=1$), leaving every sub-5% effect buried inside code-layout noise.

I pushed back, rejected the verdict, and launched a multi-persona adversarial review:

I structured the multi-agent workflow across three layers:

• Claude Code as Lead Coordinator: Managed role-scoped subagents. Implementation agents worked exclusively in feature branches. Measurement agents had strict protocols (executing benchmarks, pulling raw CSVs, computing bootstrap confidence intervals).
• agy CLI for Adversarial Panels: When reviewing experimental drops or controversial data, I launched multi-persona debates tasked specifically with falsifying the claim.
• Gemini 3.7 Flash (High) as Architect: Evaluated large-scale design trade-offs (e.g., C modernization vs. Rust rewrite), proposed the static-tables-plus-wrappers compilation layout, and drafted LGPL compliance scaffolding.

I had the agents rebuild the benchmark on a dedicated 24-core Intel Core i9-12900F host (honeycomb), running 5 independent builds per arm with randomized link orders and interleaved execution.

Proper measurement revealed that hardware popcount instructions delivered an immediate 15.9%–17.1% reduction in latency for cache-resident lookups.

Upstream C Defects and Engine Fixes

Vendoring libJudy wasn’t just an optimization exercise; it exposed severe, silent bugs that had lurked in the C codebase for decades.

GCC loop optimizer bug: silent key loss in Judy::BITSET (#131)

The most dangerous defect was an out-of-bounds array read in Judy1/j_1Index.c and JudyL/j_LIndex.c.

In libJudy’s immediate-bitset decoding, the lookup array jp_1Index was statically declared as 8 bytes:

// libjudy internal header
typedef struct J_P_1INDEX {
    uint8_t jp_1Index[8];
} jp_1index_t;

On 64-bit architectures, decoding a leaf index at cascade depth requires indexing up to 15 bytes into jp_1Index:

// Upstream Judy1/j_1Index.c
uint8_t index = Pj1i->jp_1Index[offset]; // offset ranges from 0 to 14!

Older compilers (GCC 4–9) compiled this into sequential pointer arithmetic that happened to read adjacent struct bytes safely. But modern compilers (GCC 13 and 14 with -funroll-loops, and GCC 15 with -O3) perform aggressive range analysis. Accessing index 8..14 on an array declared as uint8_t[8] is undefined behavior (UB). Under -O3, GCC assumes branches where offset >= 8 are unreachable and silently elides the loop iterations or drops the keys entirely.

// Demo: Silent key loss on unpatched libJudy under GCC -O3
$judy = new Judy(Judy::BITSET);

for ($i = 0; $i < 256; $i++) {
    $key = ($i << 8) | 0x42;
    $judy[$key] = true;
}

// Under unpatched -O3: keys with offset >= 8 silently vanish!
$missing = 0;
for ($i = 0; $i < 256; $i++) {
    $key = ($i << 8) | 0x42;
    if (!isset($judy[$key])) {
        $missing++;
    }
}

if ($missing > 0) {
    echo "Data corruption: {$missing} keys missing!\n";
}

I patched the array declarations (PR #147), added a dedicated runtime miscompile detector (tests/bitset_immed_cascade_integrity_001.phpt), and embedded the defect in the CI differential fuzzer to catch any future compiler optimization issues immediately.

Circular GC re-entrancy use-after-free in PHP MIXED types (#162)

During 6-million-element DRAM stress tests, the benchmark worker crashed with zend_mm_heap corrupted.

In php-judy, containers storing arbitrary PHP values (INT_TO_MIXED, STRING_TO_MIXED) hold pointers to PHP zval structures. During container destruction (judy_object_free_storage), the extension iterated through the trie, calling zval_ptr_dtor on each stored value.

If destroying a nested object caused PHP’s circular garbage collector buffer to fill, PHP synchronously triggered gc_collect_cycles() from within the free loop. The garbage collector traversed back into judy_object_get_gc() on the half-destroyed Judy object, dereferencing freed tree pointers:

// Minimal reproduction for Issue #162
class CyclicNode {
    public ?CyclicNode $self = null;
}

$judy = new Judy(Judy::INT_TO_MIXED);
for ($i = 0; $i < 10000; $i++) {
    $node = new CyclicNode();
    $node->self = $node; // Create circular reference for Zend GC
    $judy[$i] = $node;
}

// Unset triggers judy_object_free_storage() -> aborts with heap corruption
unset($judy);

In PR #165, I fixed this by unlinking the underlying Judy trie handle before iterating through child zval destructors. Valgrind invalid memory accesses dropped from 119,994 to exactly 0.

Additional upstream C fixes

I patched several other long-standing upstream issues (PR #147):

• SEARCH_LINEAR No-Op (#127): A macro guard intended to copy branch indices omitted COPYINDEX, silently masking corrupt search states.
• JudyInsArray.c Off-By-One: Fixed an AddressSanitizer-confirmed heap buffer overflow during array node insertion.
• Windows LLP64 Data Model (#143, #146): libJudy used 0xffL long constants expecting 64-bit masks. On 64-bit Windows (LLP64), long is 32 bits, corrupting JudySL string lookups. I replaced all legacy long literals with explicit Word_t types.

Research Discipline: Guardrails, Drops, and Host Hygiene

In my posts on resilience engineering and SRE algorithms, I wrote about using guardrails to prevent cascading failures. I applied those same principles to the benchmarking and research workflow:

Pre-Registration: Why We Dropped Batched Lookups

Before running any benchmark, agents committed a PREREGISTRATION.md file freezing operating points, noise floors, and an explicit rule: If the pre-registered gate fails, the optimization is dropped—no post-hoc parameter fishing.

• Hardware Popcount (POPCNT): MERGED (16.5% latency reduction).
• Vectorized Leaf Scan (SIMD): DROPPED (measured null across 18/18 cells).
• Word-Access Byte Swapping (bswap): MERGED (30% speedup on bit-twiddling paths).
• String Layer Acceleration: PARTIALLY MERGED (narrow pointer acceleration merged; inline string cache dropped).
• Batched Asynchronous Prefetching (AMAC): DROPPED TWICE.

Batched asynchronous lookup is a clear example of why pre-registered gates matter. It attempted to batch multiple Judy lookups together and issue software memory prefetches (_mm_prefetch) across lookups to hide DRAM latency.

In standalone C microbenchmarks, batched lookups achieved a 1.53× increase in throughput. But integrating this into the PHP extension revealed real-world trade-offs:

• Amortizing the state machine required batching at least 256 keys at once (imposing 13–15% gather overhead in PHP).
• A full batch buffer (4,096 keys ≈ 64 KB) polluted the CPU’s L1/L2 data cache, slowing down surrounding PHP application code by ~10%.

Because the pre-registered gate required a net end-to-end win at the PHP layer, I dropped the optimization and kept the clean single-key traversal.

4-Arm Attribution Discipline

When vendoring a library and turning on -O3, it is easy to mistake compiler-flag speedups for code-patch speedups. To maintain strict attribution, the harness ran four comparison arms:

1. Arm A: Native PHP Arrays.
2. Arm D: Debian/Ubuntu packaged dynamic libjudy.so (built with distro flags).
3. Arm S: Pristine stock libJudy 1.0.5 built statically with our exact compiler flags.
4. Arm C: The vendored, patched libJudy built statically with identical flags.

This decomposition showed that for integer keys, 96.5% of the gain came directly from the C patches (hardware popcount and bswap), while for string keys, the C patches delivered −11.4% to −32.5% regardless of compiler flags.

Host Hygiene and Benchmark Contention

During the final benchmark sprint, I hit an incident on the dedicated 24-core host (honeycomb): two agents concurrently ran separate benchmark campaigns because both passed the simple pre-check of loadavg < 12.

Even though CPU load was low, both processes competed for L3 cache bandwidth and memory channels. The untouched baseline arm shifted by 2.2×, while the PHP-array control read +0.36% and saw nothing (because PHP hash tables in this workload were compute-bound, not DRAM-bound).

I treated this as a classic SRE incident:

1. Implemented a mandatory physical host lock script (tools/bench-lock.sh).
2. Implemented a baseline stability canary (tools/bench-stability.py) that aborts runs if a known-stable reference arm drifts by more than 2%.
3. Added foreign-tenant process detection.

💡 Takeaway
Load average is necessary but not sufficient for benchmark isolation. Contention on shared LLC cache and memory buses can invalidate measurements even at near-zero CPU load.

Audited Benchmark Results in php-judy 2.6.0

Here is the audited performance summary across the benchmarks:

Latency & Throughput (Patches Alone)

Memory Footprint vs. Native PHP Arrays (Peak RSS at 8M Elements)

👉 Instrumentation note
Standard PHP memory_get_usage() only measures Zend Memory Manager allocations and is completely blind to libJudy allocations via system malloc(3) (#172). Always measure peak RSS or use Judy::memoryUsage().

Where Native PHP Arrays Still Win

It’s just as important to know where Judy does not win:

• Cache-resident scalar lookups: Native PHP arrays win 42 out of 43 per-element scalar lookup benchmarks when data fits entirely in CPU cache (median 4.19× faster), because Judy pays a ~16 ns C-to-PHP boundary overhead per call.
• Out-of-cache scaling: As dataset sizes grow to 6M+ elements and exceed CPU cache, PHP arrays suffer severe memory bloat and DRAM TLB misses, narrowing the gap to 17 of 21 cells (median 1.97×).
• One Measured Reversal: In judy-cache, random-order get() operations at 3M entries out-of-cache were +2.2% to +3.0% slower with the patches due to increased branch depth on pseudo-random hash distributions. I recorded and filed this as an open research tracking item.

Getting Started with php-judy 2.6.0

php-judy 2.6.0 is available immediately on PECL and Packagist with the vendored, hardened libJudy built-in:

# Install via PIE (PHP Installer for Extensions)
pie install orieg/judy

# Or install via PECL
pecl install judy

# Or install in Docker
docker-php-ext-install judy

Following the positive results of vendoring libJudy into php-judy, I went on to explore how much further we can push digital trie performance with a proper re-architecture and rewrite designed from scratch for modern hardware in expanse. I’ll share more details on that project in a follow-up post.