Le pattern Memoization en Javascript

Pour faire simple, la Mémoization consiste à mettre en cache la valeur retournée par une fonction qui demande des ressources importantes ou un long temps de traitement.

En Javascript, le pattern de base consiste à doubler une fonction avec un cache et demande donc de déclarer deux fois chaque fonction.

var foo = function(arg){ return arg; }
var cachedFoo = cache(foo);
cachedFoo(arg);

Examinons le code:

De nombreuses bibliothèques proposent une implémentation de ce pattern. Underscore met, par exemple, à notre disposition la méthode _.memoize(function, [hashFunction]).

Pour comprendre plus en profondeur ce pattern, je vous recommande les deux articles suivants qui sont fort complets.

• S4tori: La mémoization en Javascript
• Addy Osmani: Faster JavaScript Memoization For Improved Application Performance

Quant à cet article, il est une bonne excuse pour quelques essais d’écriture revisitée ne nécessitant pas de doubler la fonction.

Sous forme de méthode de cache

La première implémentation utilise le prototype de Function, à l’instar du pattern de Thomas Fuch, mais, à l’inverse de ce dernier, s’utilise directement, comme une sorte de spécialisation de la fonction.

var foo = function(arg){ return arg; }
foo.cache(arg);

Examinons le code:

Ce code utilise les notions de prototype, closure et IIFE, et fait appel aux méthodes call et apply.

Le comportement de base du code peut être expliqué de la sorte:

1. Une méthode cache est définie de manière commune à toutes les fonctions, par l’intermédiaire de l’attribut prototype du constructeur Function.
2. La closure permet de conserver le cache dans sa seule portée, tout en garantissant le partage de cette variable entre tous les appels de la méthode.
3. Une clé unique pour chaque appel est obtenue par la concaténation du nom de la fonction avec la liste des arguments passés. Une fonction appelée plusieurs fois avec les mêmes arguments possède donc une clé identique. A noter que arguments n’étant pas un Array, il n’est pas possible d’utiliser directement join.
4. Lors du premier appel de la fonction cache, celle-ci évalue la fonction dont elle est l’attribut en lui passant les mêmes arguments qu’elle a reçus, et met en cache le résultat retourné.

Sous forme de fonction de cache

On peut également imaginer une variante où cache n’est plus une méthode de Function, ce qui permet de ne pas toucher au prototype d’une classe native.

var foo = function(arg){ return arg; }
cache(foo)(arg);

Examinons le code:

Consolidation

Attention toutefois, dans les deux cas:

1. Deux noms de méthode identiques mais d’objets différents se confondront dans le cache qui ne référence pas le nom des classes auxquelles chaque méthode appartient.
2. L’attribut name de la fonction n’étant pas standard pour tous les navigateurs, ce script peut échouer, notamment sous IE.
3. Les paramètres de type Object ne sont pas gérés, car il ne supporte pas la sérialisation.

Pour répondre aux deux premiers problèmes, on peut passer this, plutôt que this.name comme clé, ce qui rendra le cache plus lourd mais plus sûr.

Quant au troisième problème, il est plus délicat. Il s’agit de convertir un objet en String, tout en lui conférant une empreinte individuelle en fonction de ses attributs. L’idéal serait sans doute de bénéficier d’un identifiant d’objet, tel qu’une référence mémoire, mais je ne pense pas qu’il soit possible de déduire cela en Javascript.

A la place, JSON.stringify() peut nous servir dans ce cadre, mais n’est disponible que depuis ECMAScript5. Si cette méthode n’est pas présente, il est nécessaire de boucler récursivement sur les propriétés de l’objet qui ne soient pas des méthodes.

Dans tous les cas, nous alourdissons davantage le code pour permettre la compatibilité entre navigateurs. C’est d’ailleurs pour cette raison que certaines bibliothèques tel Underscore acceptent de manière optionnelle une fonction de hashage personnelle comme deuxième argument.

Le code consolidé et redondant ressemble donc à ceci: