Memoization in PHP: Reine Funktionen automatisch cachen

1. Was Memoization ist und warum sie reine Funktionen voraussetzt

Memoization ist eine Optimierungstechnik, bei der das Ergebnis eines Funktionsaufrufs beim ersten Mal berechnet und zusammen mit den verwendeten Argumenten in einem Cache abgelegt wird. Bei jedem weiteren Aufruf mit denselben Argumenten liefert die memoisierte Funktion das gespeicherte Ergebnis direkt zurück, ohne die eigentliche Berechnung erneut auszuführen. Der Name leitet sich vom lateinischen Wort für Gedächtnis ab und beschreibt genau dieses Verhalten: die Funktion erinnert sich an bereits berechnete Ergebnisse.

Diese Technik funktioniert nur korrekt, wenn die zu memoisierende Funktion eine Pure Function ist, also bei gleichen Argumenten garantiert immer dasselbe Ergebnis liefert und keine externen Zustände abfragt. Würde man eine Funktion memoisieren, die etwa die aktuelle Uhrzeit oder den Inhalt einer sich ändernden Datenbanktabelle abfragt, würde der Cache irgendwann veraltete, falsche Werte zurückgeben, weil die zugrunde liegende Voraussetzung von Memoization, gleiche Eingabe gleich gleiche Ausgabe, verletzt wäre.

In PHP lässt sich Memoization ohne Framework und ohne externe Abhängigkeit direkt mit Closures und Arrays umsetzen. Dieser Artikel zeigt, wie eine generische memoize-Funktion für beliebige Parameteranzahlen aussieht, wie man Cache-Keys für Objekte und Arrays erzeugt, und wo die praktischen Grenzen dieser Technik liegen.

2. Eine minimale memoize()-Funktion für einen Parameter

Die einfachste Form von Memoization nimmt eine Closure entgegen und gibt eine neue Closure zurück, die vor jedem Aufruf prüft, ob das Argument bereits im internen Cache-Array vorhanden ist. Ist es vorhanden, wird der gespeicherte Wert zurückgegeben, ohne die ursprüngliche Funktion erneut auszuführen. Ist es nicht vorhanden, wird die ursprüngliche Funktion aufgerufen, das Ergebnis im Cache abgelegt und anschließend zurückgegeben.

Entscheidend für diese Implementierung ist die Verwendung von use (&$cache) mit Referenz, weil der Cache über mehrere Aufrufe der zurückgegebenen Closure hinweg erhalten bleiben muss. Ohne die Referenz würde bei jedem Aufruf eine frische Kopie des Cache-Arrays verwendet, wodurch Memoization wirkungslos bliebe, weil kein Aufruf je einen Cache-Treffer finden könnte.

<?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. Cache-Keys für mehrere Argumente erzeugen

Sobald eine Funktion mehr als ein Argument entgegennimmt, reicht ein einfacher Array-Schlüssel wie im vorherigen Beispiel nicht mehr aus, weil PHP-Arrays nur skalare oder String-Schlüssel unterstützen. Die praktische Lösung besteht darin, alle Argumente zu einem eindeutigen String zusammenzufassen, etwa mit serialize() oder mit json_encode(), und diesen String als Cache-Key zu verwenden. Wichtig dabei: die Serialisierung muss deterministisch sein, damit dieselbe Argumentkombination immer denselben Schlüssel erzeugt.

Ein häufiger Fehler bei mehreren Argumenten ist, sie einfach mit einem Trennzeichen wie einem Komma zu verketten, ohne den Typ zu berücksichtigen. Der String "1,2" könnte dann sowohl aus den Argumenten (1, 2) als auch aus ("1", 2) entstehen, wodurch zwei eigentlich unterschiedliche Aufrufe denselben Cache-Eintrag teilen würden. serialize() behält Typinformationen bei und vermeidet diese Kollision zuverlässig.

<?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 mit Objekten und Arrays als Argumenten

Objekte als Argumente bringen eine zusätzliche Schwierigkeit mit sich: serialize() funktioniert zwar auch mit Objekten, erzeugt aber bei zwei Objekten mit identischem Zustand nur dann denselben Schlüssel, wenn beide Objekte tatsächlich dieselben Eigenschaftswerte tragen. Das ist bei einfachen, unveränderlichen Value Objects meist unkritisch, wird aber problematisch, sobald ein Objekt private, nicht relevante interne Zustände mitschleppt, die den serialisierten String unnötig verändern, ohne das eigentliche Ergebnis der Funktion zu beeinflussen.

Eine robustere Alternative für Objekte ist, den Cache-Key explizit aus den relevanten Eigenschaften selbst zu bilden, statt sich auf die automatische Serialisierung des gesamten Objekts zu verlassen. Diese explizite Schlüsselbildung macht sichtbar, welche Objekteigenschaften tatsächlich das Ergebnis beeinflussen, und verhindert, dass irrelevante interne Details unnötig viele Cache-Einträge erzeugen.

<?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. Speicherverbrauch begrenzen: LRU und Cache-Größe

Eine naive Memoization-Implementierung wächst unbegrenzt, weil jedes neue Argument einen neuen Cache-Eintrag erzeugt, der nie wieder entfernt wird. Bei Funktionen mit wenigen möglichen Argumentkombinationen ist das unkritisch, bei Funktionen mit sehr vielen oder gar unbegrenzt vielen möglichen Eingaben führt es aber zu stetig wachsendem Speicherverbrauch, besonders in langlaufenden PHP-Prozessen wie Swoole-Workern oder CLI-Daemons.

Die gängige Lösung ist eine Least-Recently-Used-Strategie, kurz LRU: der Cache erhält eine feste Maximalgröße, und sobald diese Grenze erreicht ist, wird der am längsten nicht mehr verwendete Eintrag entfernt, bevor ein neuer hinzukommt. PHP-Arrays behalten die Einfügereihenfolge bei, was sich für eine einfache LRU-Implementierung ausnutzen lässt: der älteste Schlüssel steht am Anfang des Arrays und kann mit array_key_first() gefunden und entfernt werden.

<?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 bei rekursiven Funktionen: Fibonacci als Klassiker

Das klassische Lehrbeispiel für Memoization ist die naive rekursive Fibonacci-Funktion, deren Laufzeit ohne Cache exponentiell mit der Eingabegröße wächst, weil dieselben Teilergebnisse immer wieder neu berechnet werden. Mit Memoization wird jedes Teilergebnis nur einmal berechnet, wodurch die Laufzeit von exponentiell auf linear sinkt, ein Unterschied, der bei größeren Eingaben den Unterschied zwischen Millisekunden und praktisch unendlicher Laufzeit ausmacht.

Bei rekursiven Funktionen ist eine Besonderheit zu beachten: die Closure muss sich selbst referenzieren können, um den Cache auch innerhalb der Rekursion zu nutzen. In PHP löst man das entweder über eine benannte Funktion mit statischem Cache oder über eine Closure, die sich selbst per Referenz erfasst, damit auch die rekursiven Aufrufe durch den Cache profitieren, statt nur der äußerste Aufruf.

<?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. Lebensdauer des Caches: Request, Prozess oder Redis

Ein memoisierter Cache in einem Array oder einer statischen Variable lebt nur solange wie der aktuelle PHP-Request, weil PHP nach jedem Request unter klassischem PHP-FPM-Betrieb den kompletten Speicher freigibt. Für Berechnungen, die innerhalb eines einzelnen Requests mehrfach mit denselben Argumenten aufgerufen werden, reicht dieser kurzlebige Cache völlig aus und ist die einfachste Form von Memoization.

Soll ein Cache über mehrere Requests hinweg bestehen bleiben, braucht es eine Persistenzschicht außerhalb des PHP-Prozesses, etwa Redis oder ein OPcache-basierter Shared-Memory-Ansatz. In langlaufenden Prozessen wie Swoole-Workern oder ReactPHP-Anwendungen lebt ein memoisierter Cache dagegen über viele Requests hinweg im selben Prozessspeicher, was die Wirkung von Memoization deutlich verstärkt, aber auch die Notwendigkeit einer Größenbegrenzung wichtiger macht.

8. Grenzen: wann Memoization gefährlich statt nützlich wird

Memoization einer unpure Funktion ist der klassische Fehler, der zu schwer auffindbaren Bugs führt: wird eine Funktion memoisiert, die von externem, veränderlichem Zustand abhängt, etwa einem Wechselkurs aus einer Datenbank, liefert der Cache nach der ersten Berechnung dauerhaft den ursprünglichen, mittlerweile veralteten Wert zurück, selbst wenn sich der Wechselkurs zwischenzeitlich geändert hat. Der Fehler zeigt sich oft erst Tage später und ist dann schwer auf die eigentliche Ursache zurückzuführen.

Ein zweiter Grenzfall betrifft Funktionen, deren Berechnung schneller ist als das Nachschlagen im Cache selbst. Bei sehr einfachen arithmetischen Operationen kann der Overhead der Cache-Verwaltung, Serialisierung des Schlüssels und Array-Zugriff, größer sein als die eigentliche Berechnung, wodurch Memoization die Performance sogar verschlechtert statt verbessert. Ein Benchmark vor der Einführung von Memoization ist deshalb bei unklaren Fällen unverzichtbar.

9. Memoization-Strategien im Vergleich

Je nach Anwendungsfall eignet sich eine andere Variante von Memoization. Die folgende Tabelle ordnet die wichtigsten Strategien ein.

Die Grundregel: Memoization lohnt sich immer dann, wenn eine Pure Function mit wiederkehrenden, überschaubar vielen Argumentkombinationen aufgerufen wird und die Berechnung selbst spürbar teurer ist als ein Array-Zugriff. Bei unklarer Reinheit der Funktion oder unbegrenzt vielen möglichen Argumenten ist besondere Vorsicht mit Größenlimit und Invalidierungsstrategie geboten.

10. Zusammenfassung

Memoization speichert das Ergebnis einer Funktion beim ersten Aufruf und liefert es bei gleichen Argumenten sofort aus dem Cache zurück, ohne die Berechnung erneut auszuführen. Diese Technik ist nur bei Pure Functions garantiert korrekt, weil sie voraussetzt, dass gleiche Eingaben immer gleiche Ausgaben liefern. Eine minimale memoize()-Funktion lässt sich mit einer Closure und einem Cache-Array umsetzen, für mehrere Argumente sorgt serialize() für eindeutige, typsichere Cache-Keys.

Bei rekursiven Funktionen wie Fibonacci senkt Memoization die Laufzeit von exponentiell auf linear. Für unbegrenzt viele mögliche Eingaben ist eine LRU-Strategie mit Größenlimit nötig, um den Speicherverbrauch zu kontrollieren. Die größte Gefahr bleibt die Memoization unpurer Funktionen, deren Ergebnis von externem, veränderlichem Zustand abhängt, weil der Cache dann veraltete Werte liefert, ohne dass ein Fehler sofort sichtbar wird.

11. FAQ: Memoization in PHP