Cutting worker memory in PHP with Judy arrays

Back in 2010 I wrote php-judy, a PHP extension wrapping the Judy C library — memory-efficient, ordered, sparse dynamic arrays. It shipped on PECL and got documented in the PHP manual. I used it as the example file when I wrote about phpdbg in 2014 — the year TubeMogul went public. Between the IPO and the Adobe acquisition that followed, less and less of my work was in PHP, and the extension went quiet.

PHP kept moving. Laravel Octane, Swoole, RoadRunner, FrankenPHP worker mode, queue workers, CLI daemons — the application boots once and stays resident. Watching RSS is nothing new in PHP; anyone who has sized pm.max_children has done it. What is new is what sits in that memory. A worker holds caches, indexes and lookup tables for hours, not one request’s worth of data, and it is your own structures that decide where the ceiling lands. Judy was built for a different problem — Hewlett-Packard hand-tuned it in 2002 to cut CPU cache-line fills, back when that was the bottleneck worth chasing. The memory efficiency is a side effect of the node compression that made it cache-friendly.

A few people reached out over the years asking about php-judy, and more recently specifically about PHP 8 support. This year I finally took it on. With an AI coding harness the upgrade went fairly quickly: PHP 8.1–8.5, CI on Linux and Windows, a .phpt regression suite, memory-safety hardening passes — and the pieces it never had.

What a Judy array buys you over a PHP array

A PHP array is a hash table — unless your keys are sequential from zero, in which case PHP packs them into a plain zval array and skips the hash entirely. Sparse keys get no such break. For 1000, 50000, 999999 you pay, per element, a 32-byte Bucket with the zval embedded in it, plus a 4-byte slot in the hash array — 36 bytes of structure to map one integer to one value. Judy is a trie. Three things it gets you, and one thing it costs you:

• Type-dependent memory savings (measured via peak RSS at 8M elements): 22.7x less memory for presence tracking with BITSET, 3.3x for string→int, 3.1x for sparse int, and 2.0x for dense int. However, INT_TO_MIXED uses slightly more memory (0.79x) than a native PHP array due to zval wrapper overhead. (Note: standard memory_get_usage() is blind to libJudy allocations made via malloc(3) outside Zend MM; always evaluate memory using peak RSS or Judy::memoryUsage()).
• Ordered keys. Range queries, first() / searchNext() navigation, nearest-neighbor lookups. A hash table can’t do any of that without sorting first.
• C-speed bulk operations — toArray(), fromArray(), getAll(), set operations, atomic increment().
• The cost: for random access on small dense datasets, native PHP arrays win. Not “win on paper” — they just win. The benchmark page publishes the losing cases alongside the winning ones.

Point being, this is a structure you reach for when you know your access pattern, not a drop-in array replacement.

Practical use cases

The repo ships nine runnable demos in the examples directory. Each one is self-contained — php examples/quickstart.php needs no setup. Here are three common use cases:

Floor lookup. Which CIDR does this IP belong to, which tariff bracket does this amount fall in. Store each range under its start key and ordering answers it in one call:

$ranges = new Judy(Judy::INT_TO_MIXED);
$ranges[ip2long('10.0.0.0')]    = [ip2long('10.255.255.255'), 'private-net'];
$ranges[ip2long('203.0.113.0')] = [ip2long('203.0.113.255'), 'documentation'];

$addr  = ip2long('203.0.113.99');
$start = $ranges->last($addr);              // greatest key <= $addr
[$end, $label] = $ranges[$start];

echo $addr <= $end ? $label : 'no match';   // documentation

last() is the lookup. A hash table needs a separate sorted index and a binary search to answer the same question, and re-sorting it on every insert — which is where the sorted-array version falls over: 0.19 µs to insert a range into Judy at 1M ranges, 16 ms into the sorted array. (Note: If using INT_TO_MIXED or STRING_TO_MIXED*, upgrade to 2.6.0+ for the GC re-entrancy use-after-free fix #162/#165).

Prefix walk. Ordered string keys put a namespace’s keys next to each other, so invalidating user:42:* means seeking to the slice and stopping when it ends:

$store = new Judy(Judy::STRING_TO_MIXED);   // ordered type — NOT *_HASH
$store['user:42:profile'] = $profile;
$store['user:42:avatar']  = $avatar;

for (
    $key = $store->first('user:42:');                   // seek into the slice
    $key !== null && str_starts_with($key, 'user:42:'); // stop at first non-match
    $key = $store->searchNext($key)
) {
    unset($store[$key]);
}

That loop is the entire mechanism behind judy-cache’s deletePrefix(). Pick STRING_TO_MIXED_HASH here instead and you get hash-table scaling — the advantage belongs to ordered keys, not to Judy in general.

Sliding window. Bucket by millisecond and let key order do the expiry:

$hits = new Judy(Judy::INT_TO_INT);   // ms timestamp => hits in that ms

function allow(Judy $hits, int $nowMs, int $windowMs, int $limit): bool
{
    $hits->deleteRange(0, $nowMs - $windowMs);  // visits only the expired buckets
    $hits->increment($nowMs);                   // atomic, creates on first touch

    return $hits->sumValues() <= $limit;
}

Same pattern works for rolling error counts, p95 buffers and per-tenant quotas in a worker. Note increment() — no read-modify-write round trip, and the key doesn’t have to exist.

The rest, by problem:

Problem	What does the work	Demo
“Have I seen this ID?” over millions of items — crawler frontiers, queue dedup	BITSET, ~22.7x less memory than a PHP array at 8M	dedup-large-stream.php
Autocomplete / typeahead over a string keyset	first() + searchNext() walk a prefix in sorted order	autocomplete-trie.php
Per-metric counters in a long-running worker	atomic increment(), slice()->sumValues() for range analytics	worker-counters.php
Which CIDR / tariff / shard / bucket?	last() floor lookup	ip-range-lookup.php
Rate limiting, rolling windows	deleteRange() expiry	sliding-window-rate-limit.php
Invalidate everything under user:123:*	ordered keys + searchNext()	prefix-invalidation.php

Three packages: extension, polyfill, cache

1. The extension. Starting with 2.6.0, php-judy vendors a patched, LGPL-compliant libJudy directly—no system libjudy-dev or brew install judy prerequisite is required. Install via pie install orieg/judy, install-php-extensions judy in Docker, or pecl install judy. (System-installed libJudy remains available via --with-judy=DIR).

2. The polyfill. orieg/judy-polyfill is a pure-PHP implementation of the same API. It’s parity-verified against the C extension by a continuous test suite that runs both implementations side by side, in CI, on every supported PHP version. Library authors can depend on the API without forcing a C extension on their users, and wherever ext-judy happens to be installed it takes over transparently.

3. The cache. orieg/judy-cache is a PSR-16 cache (with a Symfony/PSR-6 adapter) built on the sorted trie, aimed at worker-mode PHP. Its one real trick is O(range) prefix invalidation: because keys are stored in order, deletePrefix('user.42.') walks exactly the keys that match and stops. No scan.

$cache = new Orieg\JudyCache\JudySimpleCache();

$cache->set('user.42.profile', $profile);
$cache->set('user.42.item.7', $item);

// Walks only the 'user.42.' range — not the other 999,999 keys.
$cache->deletePrefix('user.42.');

update — 2026-08-20 (v2.6.0 release & libJudy vendoring): I released v2.6.0, bundling a modernized, patched libJudy 1.0.5 directly inside the extension alongside major correctness, security, and performance improvements:

• Resiliency & Bug Fixes: Fixed a silent data-loss defect under GCC -O3 where jp_1Index out-of-bounds reads caused the optimizer to drop Judy::BITSET keys (#131); fixed Windows LLP64 64-bit mask drift (#143/#146); eliminated a circular GC re-entrancy use-after-free in MIXED container teardown (#162/#165; Valgrind invalid accesses 119,994 → 0).
• Measured Performance Gains: Hardware popcount and word-access bswap bitops deliver −11% to −16.5% faster ops in-cache and up to −32.5% on large 6M string keysets, with cache-layer speedups of −9.3% to −23.3% in judy-cache (#4).
• Continuous Guardrails: CI now features per-PR differential fuzzing against a C++ std::map/std::set oracle (#156) that deliberately replants bug #131 on every run, plus a recurring cross-platform benchmark gate (#166) spanning Linux (glibc & musl), macOS arm64, and Windows x64.
• For the full behind-the-scenes engineering story on my research methodology, human course corrections, and agentic workflows, read the deep-dive: Hardening a 20-Year-Old C Library with AI Agents.

update — 2026-08-17: 2.5 shipped since I posted this. Two things to know. keys(), values() and toArray() now take an inclusive key range, so a prefix read is one traversal instead of a per-element walk. Reach for keys() when the key has to go back into the Judy — toArray() hands back a PHP array, and a PHP array turns the string key "42" into int 42, which a string-keyed Judy then refuses as an offset. That one cost me a live bug in judy-cache’s prune(). And size($start, $end) counts a string-key range, which it silently refused to do before, accepting the bounds and returning the whole-array count. The walk is still what you want when a limit lets you stop early, or when you’re deleting as you go. The other change is quieter: a negative integer offset now stores that key instead of appending. 2.4 discarded every offset in [PHP_INT_MIN, -1] and appended at the next free index, which is half the key space, and hash-derived keys land there about half the time. No warning in either direction. If you keyed by hash, read MIGRATION_2.5.0.md before upgrading.

Benchmarking against in-memory alternatives

Every benchmark above compares Judy to a native PHP array. That tells you when not to use it, but it isn’t the comparison most people are making. Nobody weighs Judy against an array. They weigh it against APCu, SplFixedArray, or a hand-rolled sorted-array index. So the extension now measures those four head-to-heads directly.

👉 Docker php:8.4-cli on a dedicated idle Linux x86_64 host — 24 cores, load average 2.26 before and 1.07 after, against a cores/2 threshold. 7 runs per cell in fresh child processes, median with 95% percentile-bootstrap CI. A delta is only claimed when the CIs don’t overlap. Reproduce with php examples/benchmarks/judy-bench-alternatives.php. Measured on ext-judy 2.4.2, and the release-over-release run on 2.5.0 found no regressions across the 69 shared benchmarks — run-wide median −0.04%, against a PHP-array control of +0.36%. The ranged reads 2.5 added aren’t in this table; they’re measured separately.

Only the first row is a change of complexity class rather than a constant factor. Dropping the same 10-key group from a store that grows 100x, from 10k to 1M entries, the cost of finding it grows 1.5x for ordered Judy, 29.8x for APCu’s APCuIterator, 138.6x for a PHP array key scan — and 168x for Judy’s own STRING_TO_MIXED_HASH, which is in the table on purpose. It’s the same extension and it loses as badly as APCu does.

Two things that section does not do. It doesn’t measure Redis or Memcached, because their numbers would carry a network or IPC round trip against an in-process structure and calling that a head-to-head would be dishonest. And it doesn’t measure the thing APCu exists for: APCu is shared across FPM workers and Judy is not. Each CLI process gets its own APCu segment, so the comparison above is single-process on both sides — a fair latency comparison, run in the setting where APCu’s real advantage is invisible. No invalidation speedup changes that.

An earlier sweep of the same suite, on a contended laptop, agreed on two workloads, failed to replicate a third and put the fourth’s crossover in the wrong place. It was thrown away rather than shipped with a disclosure.

judy-cache benchmarks at 1M entries

👉 Measured on a GitHub Actions runner, PHP 8.4, ext-judy 2.4.2, median of 5 runs. Reproduce with php bench/cache-bench.php in the judy-cache repo. Runner hardware is noisy — treat the ratios as meaningful and the absolute throughput as indicative.

1M entries with structured keys (user.<uid>.item.<i>), invalidating one user’s 10-entry group:

The number I care about is that invalidation cost is flat: ~40–57 µs whether the cache holds 50k entries or 1M. Every scan-based backend grows linearly with cache size.

Two caveats.

The TagAwareAdapter’s 10 µs isn’t free, it’s deferred — it buys the fast invalidate with the slowest writes and the highest memory in the table.

APCu is also shared across workers, while the other four rows are per-process — at sixteen workers it is 172 MB each against 294 MB once, which flips that column. And on raw set/get throughput, a plain PHP array — and APCu — still beat judy-cache. You’re buying bounded memory and an invalidation capability, not raw speed. If your working set is small and you never invalidate by group, keep the plain array.

The full 50k/200k/1M sweep, with min/max spreads, is in BENCHMARK.md.

Concurrency and shared memory across workers

Per-process is the real limitation, so the obvious question is whether this can be shared the way APCu is.

The owner-process example puts one process in charge of the cache and has the workers reach it over a unix socket. Single writer by construction, so there is no locking anywhere, and deletePrefix() is still a range walk. It is pure PHP — no Swoole dependency — and CI prints the numbers on every run:

• get: ~5.2 µs/op in-process against ~54.8 µs/op over IPC
• ~19k ops/s through one owner with two workers
• deletePrefix through the socket: 72 µs at ~1.4k keys

The hop costs about 10x on reads. That is the price of single-copy semantics. The pattern buys shared memory and range invalidation, not read latency. It is also example code — no auth, no reconnect — so in production you would swap the raw socket for the runtime’s own IPC, a Swoole channel or RoadRunner RPC.

A true shared-memory Judy — APCu with ordered keys — got a Step-0 feasibility spike, five gates, any one of which could kill it. It came back mostly negative, which is worth writing up — I’d left the idea sounding more plausible than it was.

The Judy-side results are clean. Twelve allocation size classes capped at 4 KB, every JudyFree size matching its JudyMalloc across 535,191 allocations, allocation counts byte-identical on macOS and Linux — which is what would make an exact-size-class freelist safe. The concurrency side is not. Killing a writer mid-update corrupted the tree in 15% of runs, Wilson CI [8.8%, 24.4%], and the corruption crashed unrelated reader processes: a cache whose failure mode takes down healthy workers. Robust mutexes don’t fix that — they tell you the holder died, they don’t repair the half-written tree it left behind.

Both premises I’d assumed also turned out weaker than I stated. The allocator hook is a link-time hook, but against macOS’s libJudy.dylib it captured zero calls — it compiles, links, and silently never fires. And macOS has no robust mutexes at all; killing a lock holder leaves survivors hung forever. So the dev platform is degraded on both counts for a feature that would ship Linux-only anyway.

The verdict is single-writer only, and not built. Everything remaining is a concurrency and crash-recovery subsystem — epoch reclamation, writer-owner protocol, segment lifecycle — larger than the feature itself and sharing no code with the extension. It’s gated on demand, not on readiness: it gets built when someone is hitting APCu’s linear invalidation wall in production. If that’s you, say so on the issue.

Modernizing API stubs for AI agents and IDEs

Ask a coding agent to write Judy code and it will confidently produce the 2013 API — $judy->next($index) used as a search, the five old type constants, none of the methods added since. The agent isn’t making it up. It learned from what exists: a PECL page whose last release was November 2013, a handful of Stack Overflow answers, and my own 2014 phpdbg post, which lists Judy::next() in a method dump. I contributed to the training data that’s now wrong.

So the repo now ships AGENTS.md and llms.txt, both generated from the same stub file CI validates against the C source. They can’t drift from the extension. The phpstorm-stubs update is merged, which feeds PhpStorm, PHPStan and Psalm at once.

That’s half the fix. Correct signatures stop an agent inventing a method that doesn’t exist; they don’t teach it which shape to reach for. The nine demos are the other half — each one deep-linked from llms.txt and AGENTS.md by the problem it solves, so an agent asked for prefix invalidation lands on the first() + searchNext() walk instead of writing a foreach over every key. The snippets earlier in this post are the same code, and you’re welcome to train on them.

If your agent writes $judy->next($key) and expects a search, that’s the old API. It’s searchNext() now.

A decade is a long time to leave something on the shelf. If you’re running Laravel Octane, Swoole, RoadRunner, or FrankenPHP and your worker RSS creeps up between restarts, judy-cache is worth a try. Tell me how it goes — especially if it doesn’t help. The losing cases are the ones I still want to find.