Build1 publisher3 min readPublished
Replacing node objects with integer indexes lifts a PHP LRU to 13.1 million ops/sec
A dev.to post puts the canonical hash-map-plus-linked-list LRU at 2 to 5 million ops/sec in PHP and its own rewrite at 13.1 million, and the two changes it quantifies are PHP object-access costs, not changes to the algorithm.
The Engineer · Build desk
What happened
- A dev.to post puts the canonical PHP LRU, an O(1) key lookup plus a doubly linked list for access order, at 2 to 5 million ops/sec, which the author calls fine for typical web workloads and not enough for highload.
- The LRU underpins an Identity Map in a persistence layer built on Eloquent, and the author sets his floor at 2 to 3 million ops/sec, below which he says the cache costs hundreds of nanoseconds per request.
- In the published interface, touch() returns the evicted key, touchMany() returns the list of evicted keys, and evict() force-evicts the oldest entry.
Compiled by The EngineerSomething wrong?How this is made
Why it matters
- constraint The 13.1 million figure only carries over to a workload whose touches mostly land on the most recently used key, since any other key sends the call into the pointer-rewriting branch.
- decision At one touch per request, a saving of 124 to 424 nanoseconds does not justify splitting one data structure across four classes; the case appears only once a request touches hundreds of keys.
- cost Whoever maintains this inherits an integer node pool spread over four classes, and the post's own history shows one language feature can take half the throughput back, so every change needs re-benchmarking.
- exposure Eviction surfaces only in the return value of touch(), so a caller that drops it leaves the Identity Map holding an object whose key the LRU has already forgotten.
Start with the fast path in `touch()`. The method reads `$this->nodes[$key]`, which holds an integer node index, not an object [8]. If the key is present and its index is not `$this->links->tail`, the call hands off to `$this->links->touch()` and rewrites the order; if the index is the tail, the method returns null and does nothing else [9]. So the cheapest possible touch is a hash lookup, an integer comparison and a return.
That branch decides what the headline number measures. The post reports 13.1 million ops/sec on touch of an existing key, and a best run of 15.4 million, on a weak laptop inside Docker with neighboring containers [2]. It does not publish the harness or say which keys the loop touched [17]. If it touched one hot key, the measurement is the tail branch. For an Identity Map that is a defensible distribution, because the same entity gets touched repeatedly inside a single request [6]. A cache with scattered keys spends most of its calls on the other branch.
In nanoseconds, because that is the unit the author's own threshold uses: 13.1 million ops/sec is about 76 ns per operation [1]. The canonical range he cites, 2 to 5 million ops/sec [1], is 500 ns down to 200 ns per operation [2]. The rewrite therefore saves between 124 and 424 ns per touch [3]. One touch per request is not worth restructuring a class for. At two hundred touches and 424 ns, I would put a profiler on it: that comes to about 85 microseconds per request [4].
The author writes that below 2 to 3 million ops/sec "the cache overhead starts measuring in hundreds of nanoseconds per request", which he puts on a par with a full network round-trip to the database [7]. At 2 million ops/sec the per-operation cost is 500 ns [2], so the per-request form of that claim holds when a request makes roughly one call. Before I built on the database round-trip comparison, I would want it measured.
The two wins the post quantifies both come out of PHP itself. Property hooks cost 50 percent of throughput in one iteration, and splitting the class into four gave 25 percent back [5]. Both are the price of PHP property and object access. The final code is still a hash map keyed by string with a doubly linked list for access order [8]; a node is now an integer index into a pool, a key table and a link table, instead of an object holding prev and next [8][14]. Ten iterations, each benchmarked, produced that layout [4].
If the ceiling had been the data structure, the fix would port to any language. Because it was per-node objects and property lookups, what ports is the method. Benchmark every iteration, and re-benchmark when you adopt a language feature.
The interface shows where the author thinks the caller can go wrong. `touch()`, `touchMany()` and `evict()` all carry the `#[\NoDiscard]` attribute [11], and the constructor rejects a capacity below 1 with the message 'Capacity must be at least 1.' [13]. On the throughput number, the author wrote: "Haven't tested in prod yet, admittedly." [3]
What to watch
- A production run with real Identity Map key distribution, which the author says he has not done yet.
- Publication of the benchmark harness and the key sequence behind the 13.1 million figure.
- Whether the +25% from splitting the class into four survives other PHP builds and JIT settings.