Cutting worker memory in PHP with Judy arrays

Writing ·

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:

PHP hash table compared with a Judy trieStoring the sparse keys 1000, 1001 and 1002. The hash table scatters them into unrelated buckets; each element costs a 32-byte Bucket (an 8-byte hash, an 8-byte key pointer and an inline 16-byte zval that also carries the collision index) plus a 4-byte hash slot. The trie splits each key into bytes, so all three share the 0x03 byte and differ only in the final byte E8, E9 or EA, and the keys stay in sorted order.PHP ARRAY — HASH TABLE100010011002hash()h (hash/index) 8Bkey ptr 8Bzval (inline) 16B└ holds collision idxBucket, 32 B + 4 B hash slotEvery sparse key costs the same, however it hashes.Buckets keep insertion order — but not key order.JUDY — TRIE1000 = 0x03 E81001 = 0x03 E91002 = 0x03 EA03leading zero bytes compressed awayE8E9EAsorted order — a prefix is one contiguous walkNeighbouring keys share their prefix nodes,so clustered keys cost far less than scattered ones.
Three adjacent sparse keys. The hash table pays 36 bytes of structure per element and keeps them in insertion order, so finding a key range means scanning; the trie stores the shared 0x03 byte once and keeps keys in key order, which is what makes a prefix delete a single range walk.

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

Three packages: extension, polyfill, cache

1. The extension. pie install orieg/judy via PIE/Packagist, install-php-extensions judy in Docker, or PECL if that’s still your workflow.

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 249-check 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\JudyCache();

$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.');

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:

backendpeak RSSset kops/sget kops/sgroup-invalidate
plain PHP array (serialized values)495 MB447537280 ms (full scan)
Symfony ArrayAdapter921 MB1121881.08 s (full scan)
Symfony TagAwareAdapter1407 MB226510 µs (deferred)
APCu294 MB37845763 ms (regex scan)
judy-cache (trie)172 MB24928152 µs (range walk)

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.

Sharing it 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:

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, is being investigated. Two things make it plausible: libJudy’s allocator is a link-time hook, and FPM and Octane workers fork from a master, so a mapping made at extension init lands at the same address in every child — which dissolves the shared-pointer problem. If it passes, Judy becomes useful under classic FPM too. It is not a promise.

The 2013 API problem

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.

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

Sixteen years is a long time to leave something on the shelf. If you’re running 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.