Le Blog d'un Ninja codeur

Le type Array en JavaScript peut être manipulé à l'aide de diverses méthodes.
Intéressons-nous ici à deux paires d'entre elles : push/pop et shift/unshift.

Ces quatre méthodes font partie de la catégorie des mutators, c'est-à-dire que ces fonctions modifient le tableau qui est passé en paramètre.

Les méthodes push() et pop() considèrent le tableau comme une pile (stack) tel que push() ajoute un élément à la fin du tableau, et pop() supprime le dernier élément du tableau.

Les méthodes shift() et unshift() considèrent le tableau comme une pile inversée tel que unshift() ajoute un élément en début du tableau et unshift() supprime le premier élément du tableau.

A première vue, ces deux paires de méthodes sont similaires, seule change la position d'insertion ou de suppression de l'élément.

Cependant, en terme de performance, les différences sont considérables comme on peut le voir sur le comparatif ci-dessous réalisé via jsperf.com sur un tableau à six éléments :

La différence de performance entre les deux jeux d'instructions est de l'ordre de 1 à 100 ce qui peut paraître à priori très surprenant.

Mais si on considère plus en détail le fonctionnement de ces instructions, il devient vite évident que shift/unshift est nécessairement moins performant que push/pop.

Les méthodes shift() et unshift() modifient le tableau non seulement en ajoutant ou supprimant un élément, mais également en réindexant tous les éléments existants. Opération très coûteuse, surtout si on considère qu'un tableau en JavaScript est en réalité une table de hachage sans un réel adressage direct aux éléments comme cela pourrait être le cas en langage C/C++.
Les méthodes push() et pop() quand à elles se contentent d'ajouter ou de supprimer un élément du tableau sans réindexer les éléments préexistants.

Cela signifie également que le temps d'exécution des méthodes shift() et unshift() dépendent de la taille du tableau à traiter alors que les méthodes push() et pop() ont à priori un temps d'exécution indépendant de la taille du tableau.

Si on réitère la même expérience que précédemment, mais sur un tableau de 145 éléments, nous pouvons vérifier ces hypothèses :

On constate bien que push() et pop() sont des opérations en temps constant, tandis que shift() et unshift() sont selon toute vraisemblance des opérations en temps logarithmique.

Pour conclure, évitez autant que possible d'utiliser shift() et unshift() et privilégiez push() et pop().