Memoization in PHP: Automatically Caching Pure Functions

1. What memoization is and why it requires pure functions

Memoization is an optimization technique where the result of a function call is computed the first time and stored in a cache together with the arguments used. On every further call with the same arguments, the memoized function returns the stored result directly, without running the actual computation again. The name derives from the Latin word for memory and describes exactly this behavior: the function remembers results it has already computed.

This technique only works correctly when the function being memoized is a pure function, meaning it is guaranteed to always return the same result for the same arguments and does not query external state. If a function were memoized that reads, say, the current time or the contents of a changing database table, the cache would eventually return stale, wrong values, because the underlying requirement of memoization, same input equals same output, would be violated.

In PHP, memoization can be implemented directly with closures and arrays, without any framework or external dependency. This article shows what a generic memoize function for any number of parameters looks like, how to generate cache keys for objects and arrays, and where the practical limits of this technique lie.

2. A minimal memoize() function for a single parameter

The simplest form of memoization takes a closure and returns a new closure that checks, before every call, whether the argument is already present in an internal cache array. If it is present, the stored value is returned without running the original function again. If it is not present, the original function is called, the result is stored in the cache, and then returned.

Crucial for this implementation is using use (&$cache) by reference, because the cache must persist across multiple calls to the returned closure. Without the reference, a fresh copy of the cache array would be used on every call, rendering memoization useless, since no call could ever find a cache hit.

<?php

declare(strict_types=1);

/**
 * Memoize a single-argument pure function.
 *
 * @return Closure(int): int
 */
function memoize(Closure $fn): Closure
{
    $cache = [];

    return function (int $arg) use ($fn, &$cache): int {
        if (!array_key_exists($arg, $cache)) {
            $cache[$arg] = $fn($arg);
        }

        return $cache[$arg];
    };
}

$callCount = 0;

$expensiveSquare = function (int $n) use (&$callCount): int {
    $callCount++;
    usleep(50_000); // simulate an expensive computation
    return $n * $n;
};

$memoizedSquare = memoize($expensiveSquare);

echo $memoizedSquare(12); // computed, callCount becomes 1
echo $memoizedSquare(12); // returned from cache, callCount stays 1
echo $memoizedSquare(7);  // computed, callCount becomes 2

echo "Total calculations: {$callCount}"; // 2, not 3

3. Generating cache keys for multiple arguments

Once a function accepts more than one argument, a simple array key like in the previous example is no longer enough, because PHP arrays only support scalar or string keys. The practical solution is to combine all arguments into a unique string, for example with serialize() or with json_encode(), and use that string as the cache key. Important here: the serialization must be deterministic, so the same argument combination always produces the same key.

A common mistake with multiple arguments is simply concatenating them with a separator such as a comma, without accounting for type. The string "1,2" could then arise from either the arguments (1, 2) or from ("1", 2), causing two actually different calls to share the same cache entry. serialize() retains type information and reliably avoids this collision.

<?php

declare(strict_types=1);

/**
 * Memoize a function accepting any number of scalar arguments.
 *
 * @return Closure(mixed ...$args): mixed
 */
function memoizeVariadic(Closure $fn): Closure
{
    $cache = [];

    return function (mixed ...$args) use ($fn, &$cache): mixed {
        // serialize() keeps type information, avoiding key collisions
        $key = serialize($args);

        if (!array_key_exists($key, $cache)) {
            $cache[$key] = $fn(...$args);
        }

        return $cache[$key];
    };
}

$calculateShipping = function (float $weight, string $country, bool $express): float {
    $base = $weight * 2.5;
    $countryFactor = $country === 'DE' ? 1.0 : 1.4;
    $expressFactor = $express ? 1.8 : 1.0;

    return round($base * $countryFactor * $expressFactor, 2);
};

$memoizedShipping = memoizeVariadic($calculateShipping);

echo $memoizedShipping(3.5, 'DE', false); // computed once
echo $memoizedShipping(3.5, 'DE', false); // cache hit, identical arguments
echo $memoizedShipping(3.5, 'DE', true);  // computed, different arguments

4. Memoization with objects and arrays as arguments

Objects as arguments introduce an additional difficulty: serialize() does work with objects, but only produces the same key for two objects with identical state if both objects actually carry the same property values. This is usually uncritical for simple, immutable value objects, but becomes problematic as soon as an object carries private, irrelevant internal state that unnecessarily alters the serialized string without affecting the actual result of the function.

A more robust alternative for objects is to explicitly build the cache key from the relevant properties themselves, instead of relying on automatic serialization of the entire object. This explicit key construction makes visible which object properties actually influence the result, and prevents irrelevant internal details from generating unnecessarily many cache entries.

<?php

declare(strict_types=1);

final class TaxContext
{
    public function __construct(
        public readonly string $countryCode,
        public readonly string $vatClass,
    ) {
    }
}

/**
 * Memoize using an explicit key builder instead of raw serialization.
 *
 * @return Closure(float, TaxContext): float
 */
function memoizeWithKeyBuilder(Closure $fn, Closure $keyBuilder): Closure
{
    $cache = [];

    return function (float $amount, TaxContext $context) use ($fn, $keyBuilder, &$cache): float {
        $key = $keyBuilder($amount, $context);

        if (!array_key_exists($key, $cache)) {
            $cache[$key] = $fn($amount, $context);
        }

        return $cache[$key];
    };
}

$calculateTax = function (float $amount, TaxContext $context): float {
    $rate = match ($context->vatClass) {
        'standard' => 0.19,
        'reduced' => 0.07,
        default => 0.0,
    };

    return round($amount * $rate, 2);
};

// Key only depends on the fields that actually influence the result
$keyBuilder = fn (float $amount, TaxContext $ctx): string =>
    sprintf('%.2f|%s|%s', $amount, $ctx->countryCode, $ctx->vatClass);

$memoizedTax = memoizeWithKeyBuilder($calculateTax, $keyBuilder);

echo $memoizedTax(100.0, new TaxContext('DE', 'standard')); // 19.0

5. Bounding memory use: LRU and cache size

A naive memoization implementation grows without bound, because every new argument creates a new cache entry that is never removed. For functions with few possible argument combinations, this is uncritical, but for functions with very many or even unbounded possible inputs, it leads to steadily growing memory use, especially in long-running PHP processes such as Swoole workers or CLI daemons.

The common solution is a least-recently-used strategy, LRU for short: the cache gets a fixed maximum size, and once that limit is reached, the entry that has not been used for the longest time is removed before a new one is added. PHP arrays preserve insertion order, which can be exploited for a simple LRU implementation: the oldest key sits at the beginning of the array and can be found and removed with array_key_first().

<?php

declare(strict_types=1);

/**
 * Memoize with a bounded cache using a simple LRU eviction strategy.
 *
 * @return Closure(int): int
 */
function memoizeWithLimit(Closure $fn, int $maxEntries = 100): Closure
{
    $cache = [];

    return function (int $arg) use ($fn, &$cache, $maxEntries): int {
        if (array_key_exists($arg, $cache)) {
            // Move to the end to mark as recently used
            $value = $cache[$arg];
            unset($cache[$arg]);
            $cache[$arg] = $value;

            return $value;
        }

        if (count($cache) >= $maxEntries) {
            $oldestKey = array_key_first($cache);
            unset($cache[$oldestKey]);
        }

        $cache[$arg] = $fn($arg);

        return $cache[$arg];
    };
}

$memoizedFactorial = memoizeWithLimit(
    fn (int $n): int => array_product(range(1, max($n, 1))),
    maxEntries: 50,
);

6. Memoization for recursive functions: Fibonacci as the classic

The classic textbook example for memoization is the naive recursive Fibonacci function, whose runtime without a cache grows exponentially with input size, because the same subresults are recomputed over and over again. With memoization, each subresult is computed only once, dropping the runtime from exponential to linear, a difference that, for larger inputs, is the difference between milliseconds and practically infinite runtime.

With recursive functions, one special aspect must be considered: the closure needs to be able to reference itself in order to use the cache within the recursion too. In PHP this is solved either through a named function with a static cache, or through a closure that captures itself by reference, so recursive calls also benefit from the cache, not just the outermost call.

<?php

declare(strict_types=1);

function fibonacciMemoized(int $n): int
{
    static $cache = [];

    if ($n <= 1) {
        return $n;
    }

    if (array_key_exists($n, $cache)) {
        return $cache[$n];
    }

    // Recursive calls also hit the same static cache
    $result = fibonacciMemoized($n - 1) + fibonacciMemoized($n - 2);
    $cache[$n] = $result;

    return $result;
}

echo fibonacciMemoized(40); // fast, linear time instead of exponential

7. Cache lifetime: request, process, or Redis

A memoized cache in an array or a static variable only lives as long as the current PHP request, because PHP releases all memory after every request under classic PHP-FPM operation. For computations called multiple times within a single request with the same arguments, this short-lived cache is entirely sufficient and is the simplest form of memoization.

If a cache is meant to persist across multiple requests, a persistence layer outside the PHP process is needed, such as Redis or an OPcache-based shared memory approach. In long-running processes such as Swoole workers or ReactPHP applications, a memoized cache instead lives across many requests in the same process memory, which noticeably amplifies the effect of memoization but also makes a size limit more important.

8. Limits: when memoization becomes dangerous instead of useful

Memoizing an impure function is the classic mistake that leads to hard-to-find bugs: if a function is memoized that depends on external, mutable state, such as an exchange rate from a database, the cache will permanently return the original, by now stale value after the first computation, even if the exchange rate has since changed. The bug often only shows up days later and is then hard to trace back to its actual cause.

A second edge case concerns functions whose computation is faster than the cache lookup itself. For very simple arithmetic operations, the overhead of cache management, serializing the key and array access, can be larger than the actual computation, making memoization worsen performance instead of improving it. A benchmark before introducing memoization is therefore indispensable in unclear cases.

9. Memoization strategies compared

Depending on the use case, a different variant of memoization fits best. The following table classifies the most important strategies.

The rule of thumb: memoization pays off whenever a pure function is called with recurring, manageably many argument combinations and the computation itself is noticeably more expensive than an array access. When the purity of the function is unclear or there are unbounded possible arguments, extra caution with a size limit and an invalidation strategy is warranted.

10. Summary

Memoization stores the result of a function on its first call and returns it directly from cache for identical arguments, without running the computation again. This technique is only guaranteed correct for pure functions, because it assumes that identical inputs always produce identical outputs. A minimal memoize() function can be built with a closure and a cache array, and for multiple arguments serialize() provides unique, type-safe cache keys.

For recursive functions like Fibonacci, memoization drops the runtime from exponential to linear. For unbounded possible inputs, an LRU strategy with a size limit is needed to control memory use. The biggest danger remains memoizing impure functions whose result depends on external, mutable state, because the cache then returns stale values without an error becoming immediately visible.

11. FAQ: Memoization in PHP