Introduction à la mémoïsation en JavaScript

Comment optimiser les performances d’une fonction en évitant de calculer plusieurs fois la même chose

Published in

Le JavaScript

7 min readJul 25, 2020

La mémoïsation est une technique permettant de mémoriser les valeurs retournées par une fonction pour éviter d’avoir à refaire des calculs qui auraient déjà été réalisés précédemment.

Cette technique est en particulier très utile lorsque nous avons une fonction qui est appelée régulièrement et en particulier lorsque le calcul est coûteux.

Nous supposons ici que nous travaillons avec des fonctions pures. En particulier, elles doivent toujours retourner la même valeur pour une même liste d’arguments qui leurs sont passés en paramètres : nous pouvons donc ainsi stocker sans crainte cette valeur pour un usage ultérieur, nous permettant ainsi de court-circuiter un calcul qui serait redondant.

Un exemple simple

Une fonction nous permettant de calculer la n-ième valeur de la suite de Fibonacci s’écrirait naïvement de la façon suivante :

const fib = n => n < 2n ? n : fib(n - 1n) + fib(n - 2n);

Remarque : dans cet exemple, nous travaillons avec des objets de type bigint. Ne soyez donc pas surpris par la présence de valeurs littérales suffixées par le caractère n qui indique que nous travaillons avec des bigint et qui n’a rien avoir avec le paramètre n ! Nous omettrons parfois ce caractère pour ne pas encombrer les explications qui suivent.

Cette formulation pose problème. Examinons les calculs réalisés lors de l’appel fib(5) :

fib(5): fib(4) + fib(3)
fib(4): fib(3) + fib(2)
fib(3): fib(2) + fib(1)
fib(2): fib(1) + fib(0)

Nous observons que certaines valeurs sont calculées à plusieurs reprises. Plus précisément, nous aurions pu éviter 5 des 9 appels récursifs significatifs en ignorant les appels fib(0) et fib(1) qui sont de toutes les façons moins coûteux qu’une recherche dans le cache.

Nous pouvons cependant éviter ce problème en mettant en place un cache qui mémoriserait les valeurs calculées et qui permettrait de les retrouver au besoin :

const memoFib = n => {
  const cache = [];  const fib = n => {
    if (n in cache) {
      return cache[n];
    }    if (n < 2n) {
      return n;
    }    return cache[n] = fib(n - 1n) + fib(n - 2n);
  };  return fib(n);
};

Cette solution consiste à créer une fermeture (ou closure) sur un tableau cache dans lequel nous enregistrons les valeurs retournées non déjà rencontrées dans nos différents appels récursifs.

Dans cette version optimisée, l’appel memoFib(5) engendre les calculs suivants, sachant que la pile des appels récursifs se dépile à partir des dernières valeurs ajoutées :

fib(5): fib(4) + fib(3), cache: [,, fib(2), fib(3), fib(4), fib(5)]
fib(4): fib(3) + fib(2), cache: [,, fib(2), fib(3), fib(4)]
fib(3): fib(2) + fib(1), cache: [,, fib(2), fib(3)]
fib(2): fib(1) + fib(0), cache: [,, fib(2)]

Les valeurs affichées en gras correspondent aux valeurs récupérées à partir du cache et n’engendrent donc pas d’appel récursif subséquent. Ainsi, notre version optimisée réalise seulement 4 appels récursifs au lieu des 9 précédents et le fossé se creuse d’autant plus que la valeur de n est grande.

Une solution générique

Introduction

Dans cette section, nous proposons d’écrire une fonction memoize de telle sorte que nous puissions écrire la fonction memoFib optimisée de la façon concise suivante :

const memoFib = memoize(fib);

Étant donné que nous souhaitons écrire une solution générique, et donc une solution acceptant une fonction pouvant prendre n’importe quel nombre d’arguments en paramètres, il faut garder à l’esprit que nous ajoutons ce faisant à notre fonction un coût supplémentaire correspondant à la récupération de la valeur, dans le cache, correpondant à la liste des arguments passés en paramètres à notre fonction. Ainsi, la mémoïsation engendre un coût supplémentaire même si nous pouvons espérer que le gain obtenu lui soit supérieur : tout est question de compromis et il ne s’agit pas, à partir d’aujourd’hui, de vous mettre à mémoïser toutes vos fonctions !

Après tout, si la mémoïsation était gratuite, elle serait implémentée par défaut et vous n’auriez pas à vous en faire lorsque vous calculez plusieurs fois la même valeur.

Une solution possible

Il nous faut trouver dans un premier temps un mécanisme nous permettant de vérifier si les arguments rencontrés lors de l’appel à une fonction ont déjà été rencontrés lors d’un appel précédent. Si cela se fait simplement à l’aide de l’opérateur === lorsqu'il s'agit de valeurs primitives, que faisons-nous lorsqu'il s'agit de références ? L'opérateur === dans ce cas nous permet de vérifier si deux objets ont la même référence mais pas si deux objets de références différentes sont effectivement similaires. Il nous faut donc une fonction nous permettant de comparer deux objets autrement.

Nous pouvons faire cela en nous ramenant au cas de valeurs primitives. Par exemple, une fonction de hash nous permettrait de faire cela aisément et de façon concise :

const memoize = fn => {
  const cache = {};

  return (...args) => {
    const key = JSON.stringify(args);
    if (key in cache) {
      return cache[key];
    }

    return cache[key] = fn(...args);
  };
};

La fonction de hash utilisée dépend de vos besoins mais dans le cas présent, nous proposons d'utiliser simplement JSON.stringify pour créer un hash des arguments passés à notre fonction.

Il est par ailleurs une bonne pratique que d’ajouter un paramètrehash à notre fonction memoize : de cette façon, nous pourrions créer notre propre fonction de mémoïsation en choisissant une fonction de hash hashFn de notre choix, avec optionnellement une valeur par défaut :

const memoizeFactory = (hashFn = JSON.stringify) =>
  fn => {
    const cache = {};

    return (...args) => {
      const key = hashFn(args);
      if (key in cache) {
        return cache[key];
      }

      return cache[key] = fn(...args);
    };
  };

Remarque : dans ce cas particulier où on utilise des bigint (type introduit avec la spécification ES2020), JSON.stringify ne fonctionnerait pas car ne sachant pas sérialiser ce nouveau type. Étant donné que de toutes les façons nous n'avons qu'un seul argument dont la valeur est primitive, notre fonction de hash consistera simplement à retourner le premier argument de la liste d'arguments.

Application

Nous pouvons maintenant créer puis utiliser notre fonction memoize aisément pour tenter d'optimiser notre fonction fib initiale :

import memoizeFactory from './memoizeFactory';

const memoize = memoizeFactory(args => args[0]);

const fib = n => n < 2n ? n : fib(n - 1n) + fib(n - 2n);
const memoFib = memoize(fib);

Si vous avez testé cette nouvelle fonction mémoïsée, vous avez peut-être observé que les performances n’étaient pas au rendez-vous. En effet, si certains des appels suivants de la fonction memoFib seront plus rapides, les appels récursifs internes font toujours référence à la fonction non mémoïsée fib plutôt que memoFib !

En pratique, la solution ci-dessus n’apporte pas vraiment de gain. Dans la section suivante, nous explorerons deux autres pistes nous permettant d’obtenir un résultat quasiment équivalent à la fonction que nous avions mémoïsée manuellement.

Mémoïsation des appels récursifs au sein d’une fonction

Le problème étant que les appels récursifs font usage de la fonction non mémoïsée, une solution naturelle serait de mémoïser la fonction lors de sa définition :

const fib = memoize(n => n < 2n ? n : fib(n - 1n) + fib(n - 2n));

Nous obtenons ainsi la version correctement mémoïsée étant donné que fib fait maintenant directement référence à la version mémoïsée.

Mais que faire dans le cas où nous importerions une fonction récursive non mémoïsée d’un autre package ? Cela ne devrait pas vous arriver mais pour le plaisir, essayons d’écrire une fonction de mémoïsation qui prenne en paramètre une fonction récursive existante et qui tienne compte de ses appels récursifs.

A priori, le seul moyen de résoudre ce problème serait de réecrire la fonction récursive comme nous l’avions fait plus haut et il est possible de faire cela de façon automatique en utilisant les fonctionnalités de métaprogrammation de JavaScript à notre disposition.

Voici à quoi pourrait ressembler une solution à notre problème :

Retenez simplement qu’il s’agit là de générer dynamiquement une fonction sur le même modèle que celle que nous avions mémoïsée immédiatement lors de sa définition.

Analyse des performances

Maintenant que nous disposons d’une première solution acceptable, nous devons vérifier que la mémoïsation apporte effectivement un gain en performances. Si cela semble évident dans le cas présent, cela n’est pas toujours le cas et il faut donc mesurer le gain lié à la mémoïsation.

Nous pouvons écrire le test de performance suivant indiquant le temps d’exécution de l’appel à chacune de nos fonctions pour n = 42 :

const testFib = logger => n => ([label, fib]) => {
  const startFib = performance.now();
  const val = fib(n);
  const endFib = performance.now();

  const duration = (endFib - startFib).toFixed(4);  logger(`[ ${ duration }ms ] -> ${ val } : ${label}`);
};const myTest = testFib(console.log)(42n);

Ensuite, supposons que nous souhaitions tester les trois fonctions fib, manualMemoFibet memoFib définies des trois façons vues précédemment (sans cache, avec un cache manuel et enfin en utilisant la fonction memoizeFactory généralisée aux fonctions récursives). Nous pouvons alors exécuter la fonction myTest sur chacune de ces trois fonctions :

[
  ['default implementation', fib],
  ['manually memoized', manualMemoFib],
  ['automatically memoized', memoFib]
].forEach(myTest);

Nous obtenons les résultats suivants :

[ 38967.3392ms ] -> 267914296 : default implementation
[ 0.0744ms ] -> 267914296 : manually memoized
[ 0.1563ms ] -> 267914296 : automatically memoized

C’est exactement le résultat que nous voulions : nous avons écrit la fonction fib d'une façon expressive et familière sans (trop) perdre en performances grâce à la mémoïsation automatique !