DEV Community

Vladislav Malikov
Vladislav Malikov

Posted on

LRU Cache in PHP 8.5 for Identity Map: 13+ Million Ops/Sec

#laravel #php #webdev

An LRU cache in PHP is one of those problems everyone and their dog has already solved a dozen times over.

The classic approach — O(1) key lookup plus a doubly linked list for access order — works, reads well, and everyone's happy with it. But once you start benchmarking, you find that most implementations top out at 2–5 million ops/sec. For typical web workloads that's fine. For highload, it isn't. Especially when the LRU isn't "somewhere in Redis" but the foundation of an Identity Map sitting directly in the hot path of every request.

I'm building my own persistence layer on top of Eloquent — with an Identity Map, Unit of Work, and optimistic locking. For that architecture, the LRU is a foundational layer. If its latency drops below 2–3 million ops/sec, the cache overhead starts measuring in hundreds of nanoseconds per request. That's comparable to the cost of a full network round-trip to the database. At that point the Identity Map stops paying for itself: instead of saving queries, you get pure latency degradation on every hit.

The task seemed simple: take the canonical implementation (HashMap + doubly linked list), swap objects for arrays, account for JIT quirks. In reality it took 10 iterations, each one benchmarked. Somewhere I lost 50% of throughput to property hooks; somewhere else, splitting the class into four gave me +25%.

Final number: 13.1 million ops/sec on touch of an existing key (best run — 15.4M), and that's on a weak laptop, inside Docker with a bunch of neighboring containers. Haven't tested in prod yet, admittedly.

The Interface 

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @phpstan-extends \IteratorAggregate<int, non-empty-string>
 */
interface LruCacheInterface extends \Countable, \IteratorAggregate
{
    /**
     * @phpstan-param non-empty-string $key
     * @phpstan-return non-empty-string|null
     */
    public function touch(string $key): ?string;

    /**
     * @phpstan-param iterable<non-empty-string> $keys
     * @phpstan-return list<non-empty-string>
     */
    public function touchMany(iterable $keys): array;

    /**
     * @phpstan-return non-empty-string|null
     * @throws \AssertionError
     */
    public function evict(): ?string;

    /**
     * @phpstan-param string $key
     * @phpstan-return void
     */
    public function remove(string $key): void;

    /**
     * @phpstan-return void
     */
    public function clear(): void;
}
Enter fullscreen mode Exit fullscreen mode

Key points:

  • touch() — adds a key or refreshes its position. Returns the evicted key (if any).
  • touchMany() — bulk insert. Returns the list of evicted keys.
  • evict() — force-evicts the oldest key.
  • remove() — removes a specific key.
  • clear() — wipes all structures.

The Main Implementation 

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @implements LruCacheInterface
 */
final class LruCache implements LruCacheInterface
{
    /**
     * @phpstan-var array<non-empty-string, int<0, max>>
     */
    private array $nodes = [];

    /**
     * @phpstan-var int<0, max>
     */
    private int $size = 0;

    /**
     * @phpstan-var LruNodePool
     */
    private readonly LruNodePool $pool;

    /**
     * @phpstan-var LruNodeKeys
     */
    private readonly LruNodeKeys $keys;

    /**
     * @phpstan-var LruNodeLinks
     */
    private readonly LruNodeLinks $links;

    /**
     * @phpstan-param int<1, max> $capacity
     * @throws \InvalidArgumentException
     */
    public function __construct(
        private readonly int $capacity
    ) {
        if ($capacity < 1) {
            throw new \InvalidArgumentException(
                message: 'Capacity must be at least 1.'
            );
        }

        $this->pool = new LruNodePool(
            capacity: $capacity
        );

        $this->keys = new LruNodeKeys();
        $this->links = new LruNodeLinks();
    }

    /**
     * @phpstan-param non-empty-string $key
     * @phpstan-return non-empty-string|null
     */
    #[\NoDiscard]
    public function touch(string $key): ?string
    {
        $node = $this->nodes[$key] ?? null;

        if ($node !== null) {
            if ($node !== $this->links->tail) {
                $this->links->touch(node: $node);
            }

            return null;
        }

        $evicted = $this->size >= $this->capacity
            ? $this->evict()
            : null;

        $node = $this->pool->allocate();

        $this->keys->set(node: $node, key: $key);
        $this->nodes[$key] = $node;
        $this->links->push(node: $node);

        $this->size++;

        return $evicted;
    }

    /**
     * @phpstan-param iterable<non-empty-string> $keys
     * @phpstan-return list<non-empty-string>
     */
    #[\NoDiscard]
    public function touchMany(iterable $keys): array
    {
        $evicted = [];

        foreach ($keys as $key) {
            $result = $this->touch(key: $key);

            if ($result !== null) {
                $evicted[] = $result;
            }
        }

        return $evicted;
    }

    /**
     * @phpstan-return non-empty-string|null
     * @throws \AssertionError
     */
    #[\NoDiscard]
    public function evict(): ?string
    {
        if ($this->links->head === LruNodePool::NIL) {
            return null;
        }

        /** @phpstan-var int<0, max> $node */
        $node = $this->links->head;
        $key = $this->keys->get(node: $node);

        if ($key === null) {
            throw new \AssertionError(
                message: 'LRU head has null key.'
            );
        }

        $this->links->detach(node: $node);

        unset($this->nodes[$key]);

        $this->pool->release(node: $node);
        $this->size--;

        return $key;
    }

    /**
     * @phpstan-return \Generator<int, non-empty-string>
     * @throws \AssertionError
     */
    public function getIterator(): \Generator
    {
        $node = $this->links->head;

        while ($node !== LruNodePool::NIL) {
            /** @phpstan-var int<0, max> $node */
            $key = $this->keys->get(node: $node);

            if ($key === null) {
                throw new \AssertionError(
                    message: 'LRU list node has null key.'
                );
            }

            $next = $this->links->next[$node]
                ?? LruNodePool::NIL;

            yield $key;

            $node = $next;
        }
    }

    /**
     * @phpstan-return int<0, max>
     */
    public function count(): int
    {
        return $this->size;
    }

    /**
     * @phpstan-param string $key
     * @phpstan-return void
     */
    public function remove(string $key): void
    {
        $node = $this->nodes[$key] ?? null;

        if ($node === null) {
            return;
        }

        $this->links->detach(node: $node);

        unset($this->nodes[$key]);

        $this->pool->release(node: $node);
        $this->size--;
    }

    /**
     * @phpstan-return void
     */
    public function clear(): void
    {
        $this->links->clear();
        $this->pool->clear();
        $this->keys->clear();

        $this->nodes = [];
        $this->size = 0;
    }
}
Enter fullscreen mode Exit fullscreen mode

Architectural decisions:

  • Separation of concerns: LruNodePool, LruNodeKeys, LruNodeLinks — each class owns its own flat data structure. This isn't "more classes = slower"; it's faster thanks to JIT inlining. A small final method gets inlined wholesale by JIT, while a big method with complex logic takes much longer to trace.

  • Flat indexed arrays (integer ID maps): $nodes maps a string key to an integer node ID ($keyString => $nodeId) instead of objects. Fewer GC allocations, better data locality for the CPU cache.

  • Object pooling: LruNodePool hands out IDs from a pool of released indices rather than creating new structures. Result: zero allocations after the initial population.

  • Readonly properties: $pool, $keys, $links, $capacity are declared readonly. The JIT optimizer performs devirtualization more aggressively because it knows for certain the field won't change after the constructor.

  • Final class: forbids inheritance, eliminating vtable checks. This lets the JIT compiler fully inline the hot paths ($this->links->touch(…)).

Helper Classes

LruNodeKeys

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @internal
 */
final class LruNodeKeys
{
    /**
     * @phpstan-var array<int<0, max>, non-empty-string|null>
     */
    private array $keys = [];

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-param non-empty-string $key
     *
     * @phpstan-return void
     */
    final public function set(int $node, string $key): void
    {
        $this->keys[$node] = $key;
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return non-empty-string|null
     */
    final public function get(int $node): ?string
    {
        return $this->keys[$node] ?? null;
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function reset(int $node): void
    {
        $this->keys[$node] = null;
    }

    /**
     * @phpstan-return void
     */
    final public function clear(): void
    {
        $this->keys = [];
    }
}
Enter fullscreen mode Exit fullscreen mode

A dedicated class for the node_id → key mapping. A tiny final class means JIT inlines the call down to a single MOV instruction on array access. If this code lived inside the main LruCache, JIT would have to trace the entire parent class just for one line — extra branches, extra type checks.

LruNodeLinks

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @internal
 */
final class LruNodeLinks
{
    /**
     * @phpstan-var int<0, max>|int<-1, -1>
     */
    public int $head = LruNodePool::NIL;

    /**
     * @phpstan-var int<0, max>|int<-1, -1>
     */
    public int $tail = LruNodePool::NIL;

    /**
     * @phpstan-var array<int<0, max>, int<0, max>|int<-1, -1>>
     */
    private array $prev = [];

    /**
     * @phpstan-var array<int<0, max>, int<0, max>|int<-1, -1>>
     */
    private array $next = [];

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function touch(int $node): void
    {
        if ($node === $this->tail) {
            return;
        }

        $prev = $this->prev[$node] ?? LruNodePool::NIL;
        $next = $this->next[$node] ?? LruNodePool::NIL;

        if ($prev !== LruNodePool::NIL) {
            $this->next[$prev] = $next;
        } else {
            $this->head = $next;
        }

        if ($next !== LruNodePool::NIL) {
            $this->prev[$next] = $prev;
        } else {
            $this->tail = $prev;
        }

        $this->prev[$node] = $this->tail;
        $this->next[$node] = LruNodePool::NIL;

        if ($this->tail !== LruNodePool::NIL) {
            $this->next[$this->tail] = $node;
        } else {
            $this->head = $node;
        }

        $this->tail = $node;
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function detach(int $node): void
    {
        $prev = $this->prev[$node] ?? LruNodePool::NIL;
        $next = $this->next[$node] ?? LruNodePool::NIL;

        if ($prev !== LruNodePool::NIL) {
            $this->next[$prev] = $next;
        } else {
            $this->head = $next;
        }

        if ($next !== LruNodePool::NIL) {
            $this->prev[$next] = $prev;
        } else {
            $this->tail = $prev;
        }
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function push(int $node): void
    {
        $this->prev[$node] = $this->tail;
        $this->next[$node] = LruNodePool::NIL;

        if ($this->tail !== LruNodePool::NIL) {
            $this->next[$this->tail] = $node;
        } else {
            $this->head = $node;
        }

        $this->tail = $node;
    }

    /**
     * @phpstan-return void
     */
    final public function reset(): void
    {
        $this->head = LruNodePool::NIL;
        $this->tail = LruNodePool::NIL;
    }

    /**
     * @phpstan-return void
     */
    final public function clear(): void
    {
        $this->head = LruNodePool::NIL;
        $this->tail = LruNodePool::NIL;

        $this->prev = [];
        $this->next = [];
    }
}
Enter fullscreen mode Exit fullscreen mode

A doubly linked list on arrays ($prev, $next). No objects, only integer IDs. This is the key decision of the entire architecture: objects in PHP are an expensive allocation and an indirect pointer access, whereas $this->prev[$node] gets turned into a direct offset memory access by JIT.

LruNodePool

<?php declare(strict_types=1);

namespace App\Orm\IdentityMap\Lru;

/**
 * @internal
 */
final class LruNodePool
{
    /**
     * @phpstan-var int<-1, -1>
     */
    public const int NIL = -1;

    /**
     * @phpstan-var list<int<0, max>>
     */
    private array $releasedIds = [];

    /**
     * @phpstan-var int<0, max>
     */
    private int $nextNewId = 0;

    /**
     * @phpstan-param int<1, max> $capacity
     * @throws \InvalidArgumentException
     */
    public function __construct(
        private readonly int $capacity
    ) {
        if ($capacity < 1) {
            throw new \InvalidArgumentException(
                message: 'Capacity must be at least 1.'
            );
        }
    }

    /**
     * @phpstan-return int<0, max>
     * @throws \RuntimeException
     */
    final public function allocate(): int
    {
        return match (true) {
            $this->releasedIds !== []
                => array_pop(array: $this->releasedIds),

            $this->nextNewId < $this->capacity
                => $this->nextNewId++,

            default => throw new \RuntimeException(
                message: sprintf(
                    'LruNodePool exhausted: capacity %d.',
                    $this->capacity
                )
            ),
        };
    }

    /**
     * @phpstan-param int<0, max> $node
     * @phpstan-return void
     */
    final public function release(int $node): void
    {
        $this->releasedIds[] = $node;
    }

    /**
     * @phpstan-return void
     */
    final public function clear(): void
    {
        $this->releasedIds = [];
        $this->nextNewId = 0;
    }
}
Enter fullscreen mode Exit fullscreen mode

An ID pool for nodes. It first hands out released IDs from the $releasedIds stack, then allocates fresh ones via $nextNewId. When capacity is exhausted — exception. The key optimization: zero allocations once the pool is populated. array_pop() and appending to the end of an array [] both run in O(1) without creating any entities. Using match(true) instead of an if/elseif/else chain gives the same speed (JIT compiles them identically) but makes the ID issuance rules visually obvious.

Benchmarks

Environment:

  • A modest laptop (nothing special).
  • Docker + highload (a bunch of neighboring containers).
  • PHP 8.5-FPM + JIT 1255 + 64M buffer.
  • Measurements via Pest benchmark.

Results:

Test ops/sec ns/op Allocations
Warm touch (100% hits) 13.1M 76 ns 0 B
Cold insert + eviction 7.89M 126 ns +2.00 MB allocated
Random access (100% hits) 9.92M 100 ns 0 B
Hot-set access (100% hits) 11.66M 85 ns 0 B

Takeaways

The LRU turned out not as "yet another implementation", but as exactly what it should be in an Identity Map — a load-bearing layer that holds the whole structure together while costing essentially nothing.

On an ordinary laptop, inside Docker with a bunch of neighboring containers, warm touch lands at 76 nanoseconds, and in the best runs — at 63. That's not "good for PHP" — that's the level where the cache stops being something you think about at all in the hot path. On bare metal it'll be faster, but that's a projection, not a measurement, and I wouldn't build architectural decisions on it. The reproducible baseline is enough: 13+ million ops/sec on a laptop, zero allocations in the hot path, predictable behavior across all scenarios.

What really matters here isn't a single number — it's that the structure behaves consistently across the entire load range. Warm touch, cold insert, random access, hot-set — all within the same order of magnitude, no cliffs, no surprises. In the hot path, predictability is what decides: an Identity Map shouldn't make you wonder whether it'll pay off on this particular request. And that's exactly what came out — the LRU works precisely where it should, and stays out of the way where it shouldn't.

Top comments (0)