Memoization in JavaScript – jenseits von useMemo

#javascript#performance

Memoization cacht das Ergebnis eines Funktionsaufrufs anhand seiner Argumente, sodass ein erneuter Aufruf mit denselben Argumenten den gecachten Wert zurückgibt, statt die Arbeit noch einmal zu machen. Die meisten JavaScript-Entwickler begegnen ihr über Reacts useMemo, aber das ist nur eine enge Anwendung einer allgemeinen Technik, die ebenso nützlich ist in einfachen Funktionen, rekursiven Algorithmen und serverseitigem Code, der nichts mit Rendering zu tun hat.

Das Kernmuster

Memoization braucht drei Dinge: einen Weg, aus den Argumenten einen Cache-Schlüssel abzuleiten, einen Speicher für gecachte Ergebnisse und einen Wrapper, der den Speicher prüft, bevor er die eigentliche Funktion aufruft.

function memoize(fn, keyFn = (...args) => JSON.stringify(args)) {
  const cache = new Map();

  return function memoized(...args) {
    const key = keyFn(...args);
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result = fn.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

function expensiveCalculation(n) {
  console.log(`Computing for ${n}...`);
  let total = 0;
  for (let i = 0; i < n * 1e7; i++) total += i;
  return total;
}

const memoized = memoize(expensiveCalculation);

memoized(5); // Computing for 5... (slow)
memoized(5); // instant, no log line — served from cache
memoized(6); // Computing for 6... (slow, different key)

Die Standard-Schlüsselfunktion JSON.stringify funktioniert für primitive und einfache Objektargumente, versagt aber bei Funktionen, Map-/Set-Argumenten oder Objekten, bei denen die Schlüsselreihenfolge nicht stabil garantiert ist – übergib eine eigene keyFn, wenn der Standard nicht reicht.

Warum das über React hinaus wichtig ist

useMemo existiert, um zu vermeiden, dass ein Wert bei jedem Rendern einer Komponente neu berechnet wird. Das ist ein echter Anwendungsfall, aber Memoization ist ebenso wertvoll überall dort, wo eine Funktion:

rein ist (gleiche Eingabe liefert immer dieselbe Ausgabe), und
teuer im Verhältnis zu einem Cache-Lookup ist (eine Datenbankabfrage, ein regulärer Ausdruck gegen einen riesigen String, eine rekursive Berechnung).

Nichts davon erfordert React. Ein Node.js-API-Handler, der denselben aggregierten Bericht für jede Anfrage in einem Schwall neu berechnet, ein CLI-Tool, das dieselbe Konfigurationsdatei bei jedem Aufruf innerhalb eines Batches neu parst, oder ein rekursiver Algorithmus, der dasselbe Teilproblem wiederholt neu berechnet, sind allesamt gute Kandidaten.

Der klassische Fall: rekursives Fibonacci

Naives rekursives Fibonacci ist das Lehrbuchbeispiel, weil der Performance-Unterschied dramatisch und leicht zu sehen ist.

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

fib(35) macht etwa 30 Millionen Aufrufe, die meisten davon berechnen dieselben Werte neu – fib(10) wird als Teilproblem von fib(35) tausendfach berechnet. Memoization reduziert das auf einen Aufruf pro unterschiedlichem n:

function memoizedFib() {
  const cache = new Map([[0, 0], [1, 1]]);

  function fib(n) {
    if (cache.has(n)) return cache.get(n);
    const result = fib(n - 1) + fib(n - 2);
    cache.set(n, result);
    return result;
  }

  return fib;
}

const fib = memoizedFib();
fib(35); // 30 million calls collapse to 36

Das ist Memoization, angewandt auf Rekursion, manchmal „Top-down Dynamic Programming" genannt – dieselbe Idee wie beim generischen memoize()-Wrapper, nur von Hand innerhalb der rekursiven Funktion angewendet, sodass jeder Aufruf den Cache prüft, bevor er weiter rekursiert.

Cache-Wachstum ist der Kompromiss, keine Fußnote

Ein unbegrenzter Map-Cache ist ein Speicherleck in Wartestellung, wenn die Funktion über die Lebensdauer der App mit vielen unterschiedlichen Argumenten aufgerufen wird – ein memoisierter Handler pro Anfrage in einem langlaufenden Server ist ein klassischer Weg, den Speicher unbegrenzt langsam wachsen zu lassen. Begrenze den Cache mit einer LRU-Verdrängung (Least Recently Used), sobald das ein echtes Risiko ist:

function memoizeWithLimit(fn, maxSize = 100) {
  const cache = new Map();

  return function memoized(...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) {
      const value = cache.get(key);
      cache.delete(key);
      cache.set(key, value); // move to "most recently used" position
      return value;
    }

    const result = fn.apply(this, args);
    cache.set(key, result);

    if (cache.size > maxSize) {
      const oldestKey = cache.keys().next().value; // Map preserves insertion order
      cache.delete(oldestKey);
    }

    return result;
  };
}

Map iteriert in Einfügereihenfolge, und das erneute Einfügen eines Schlüssels beim Zugriff (löschen, dann setzen) verschiebt ihn ans Ende – das genügt, um LRU-Verdrängung ohne separate verkettete Liste zu implementieren.

Warum useMemo nicht „Memoization, nur für React" ist

useMemo(() => computeThing(a, b), [a, b]) sieht aus wie das generische Muster, hat aber React-spezifische Semantik, die man kennen sollte:

Der Cache hält genau einen Eintrag – das letzte Abhängigkeits-Array. Es ist keine Map, die nach jeder je gesehenen Eingabe indiziert ist; ein neues Abhängigkeits-Array verdrängt das vorherige Ergebnis vollständig.
React darf den memoisierten Wert ausdrücklich verwerfen und trotzdem neu berechnen (aus Speicherdruck-Gründen), useMemo ist also ein Performance-Hinweis, keine Korrektheitsgarantie – verlasse dich nie darauf für Seiteneffekte oder um zu vermeiden, etwas mit beobachtbaren Effekten erneut auszuführen.
Es existiert nur für die Lebensdauer der Komponenteninstanz.

Ein generisches memoize() mit Map-Cache hat nichts von diesen Einschränkungen und nichts von diesen Sicherheitsgeländern – weshalb es genau deshalb in einer Komponente das falsche Werkzeug ist (unbegrenztes Wachstum über Renderings hinweg) und für eine eigenständige reine Funktion das richtige.

Wann man nicht memoisieren sollte

Memoization tauscht Speicher gegen CPU-Zeit. Sie passt schlecht, wenn die Funktion ohnehin billig ist (der Cache-Lookup kann mehr kosten als das bloße Neuberechnen), wenn Argumente selten wiederholt werden (ein Cache, der nie getroffen wird, ist reiner Overhead) oder wenn die Funktion gar nicht rein ist (etwas zu memoisieren, das von veränderlichem externem Zustand abhängt, liefert bereitwillig veraltete, falsche Antworten). Miss, bevor du danach greifst – Memoization behebt einen gemessenen Hotspot, sie ist kein Standard, den man über jede Funktion streut.