La mémoïsation en JavaScript, au-delà de useMemo

#javascript#performance

La mémoïsation met en cache le résultat d'un appel de fonction en fonction de ses arguments : un nouvel appel avec les mêmes arguments renvoie la valeur en cache au lieu de refaire le travail. La plupart des développeurs JavaScript la rencontrent via useMemo de React, mais ce n'est qu'une application étroite d'une technique générale tout aussi utile dans des fonctions simples, des algorithmes récursifs et du code serveur sans aucun rapport avec le rendu.

Le schéma de base

La mémoïsation exige trois choses : un moyen de dériver une clé de cache à partir des arguments, un magasin pour conserver les résultats en cache, et un wrapper qui consulte le magasin avant d'appeler la vraie fonction.

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)

La fonction de clé par défaut basée sur JSON.stringify convient aux arguments primitifs et aux objets simples, mais échoue pour les fonctions, les arguments Map/Set, ou les objets dont l'ordre des clés n'est pas garanti stable : passez un keyFn personnalisé quand la valeur par défaut ne suffit pas.

Pourquoi cela compte au-delà de React

useMemo existe pour éviter de recalculer une valeur à chaque rendu d'un composant. C'est un vrai cas d'usage, mais la mémoïsation est tout aussi précieuse partout où une fonction est :

Pure (la même entrée produit toujours la même sortie), et
Coûteuse par rapport à une consultation du cache (une requête de base de données, une regex sur une chaîne énorme, un calcul récursif).

Rien de tout cela n'exige React. Un gestionnaire d'API Node.js qui recalcule le même rapport agrégé pour chaque requête d'une rafale, un outil en ligne de commande qui réanalyse le même fichier de configuration à chaque invocation d'un lot, ou un algorithme récursif qui recalcule sans cesse le même sous-problème : tous sont de bons candidats.

Le cas classique : Fibonacci récursif

Le Fibonacci récursif naïf est l'exemple de manuel, car la différence de performance est spectaculaire et facile à voir.

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

fib(35) effectue environ 30 millions d'appels, dont la plupart recalculent les mêmes valeurs : fib(10) est calculé des milliers de fois comme sous-problème de fib(35). La mémoïsation ramène cela à un appel par n distinct :

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

C'est de la mémoïsation appliquée à la récursion, parfois appelée « programmation dynamique descendante » : la même idée que le wrapper générique memoize(), appliquée à la main à l'intérieur de la fonction récursive pour que chaque appel consulte le cache avant de poursuivre la récursion.

La croissance du cache est le compromis, pas une note de bas de page

Un cache Map non borné est une fuite mémoire en puissance si la fonction est appelée avec de nombreux arguments distincts pendant la vie de l'application : un gestionnaire par requête mémoïsé dans un serveur de longue durée est une façon classique de faire croître lentement la mémoire sans limite. Bornez le cache avec une politique d'éviction LRU (least-recently-used) dès que le risque devient réel :

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 itère dans l'ordre d'insertion, et réinsérer une clé lors d'un accès (supprimer puis définir) la place à la fin : cela suffit pour implémenter l'éviction LRU sans liste chaînée séparée.

Pourquoi useMemo n'est pas « la mémoïsation, mais pour React »

useMemo(() => computeThing(a, b), [a, b]) ressemble au schéma générique, mais il a des sémantiques propres à React qu'il vaut mieux connaître :

Le cache contient exactement une entrée : le dernier tableau de dépendances. Ce n'est pas une Map indexée par chaque entrée distincte jamais vue ; un nouveau tableau de dépendances évince entièrement le résultat précédent.
React est explicitement autorisé à jeter la valeur mémoïsée et à la recalculer quand même (pour des raisons de pression mémoire) : useMemo est donc une indication de performance, pas une garantie de correction ; ne vous y fiez jamais pour des effets de bord ni pour éviter de relancer quelque chose qui a des effets observables.
Il n'existe que pendant la durée de vie de l'instance du composant.

Un memoize() générique avec un cache Map n'a aucune de ces contraintes ni aucun de ces garde-fous, ce qui explique précisément pourquoi c'est le mauvais outil dans un composant (croissance sans borne à travers les rendus) et le bon outil pour une fonction pure autonome.

Quand ne pas mémoïser

La mémoïsation échange de la mémoire contre du temps CPU. Elle convient mal quand la fonction est déjà peu coûteuse (la consultation du cache peut coûter plus que le simple recalcul), quand les arguments se répètent rarement (un cache jamais sollicité n'est que du surcoût), ou quand la fonction n'est pas réellement pure (mémoïser quelque chose qui dépend d'un état externe modifiable renverra volontiers des réponses périmées et fausses). Mesurez avant d'y recourir : la mémoïsation corrige un point chaud mesuré, ce n'est pas une valeur par défaut à saupoudrer sur chaque fonction.