Quelles sont les performances des objets/tableaux en JavaScript ? (spécifiquement pour Google V8)

Question

Il serait très intéressant de documenter les performances associées aux tableaux et aux objets en JavaScript (notamment Google V8). Je ne trouve aucun article complet sur ce sujet sur Internet.

Je comprends que certains objets utilisent des classes comme structure de données sous-jacente. S'il y a beaucoup de propriétés, elles sont parfois traitées comme une table de hachage ?

Je comprends également que les tableaux sont parfois traités comme des tableaux C++ (c'est-à-dire indexation aléatoire rapide, suppression et redimensionnement lents). Et, d'autres fois, ils sont traités davantage comme des objets (indexation rapide, insertion/suppression rapide, plus de mémoire). Et, parfois, ils sont stockés comme des listes liées (c'est-à-dire indexation aléatoire lente, suppression/insertion rapide au début/à la fin).

Quelles sont les performances précises des récupérations et des manipulations de tableaux/objets en JavaScript ? (spécifiquement pour Google V8)

Plus précisément, quel est l'impact sur les performances de :

• Ajout d'une propriété à un objet
• Suppression d'une propriété d'un objet
• Indexation d'une propriété dans un objet
• Ajout d'un élément à un tableau
• Suppression d'un élément d'un tableau
• Indexer un élément dans un tableau
• Appel de Array.pop()
• Appel de Array.push()
• Appel de Array.shift()
• Appel de Array.unshift()
• Appel de Array.slice()

Tout article ou lien pour plus de détails serait également apprécié :)

EDIT : Je me demande vraiment comment les tableaux et les objets JavaScript fonctionnent sous le capot. De plus, dans quel contexte Le moteur V8 "sait-il" qu'il faut "passer" à une autre structure de données ?

Par exemple, supposons que je crée un tableau avec...

var arr = [];
arr[10000000] = 20;
arr.push(21);

Qu'est-ce qui se passe vraiment ici ?

Ou... que dire de ce... ???

var arr = [];
//Add lots of items
for(var i = 0; i < 1000000; i++)
    arr[i] = Math.random();
//Now I use it like a queue...
for(var i = 0; i < arr.length; i++)
{
    var item = arr[i].shift();
    //Do something with item...
}

Pour les tableaux classiques, les performances seraient terribles, alors que si l'on utilise une liste chaînée (LinkedList)... pas si mal.

Answer 1

J'ai créé une suite de tests, précisément pour explorer ces questions (et plus encore) ( copie archivée ).

Et dans ce sens, vous pouvez voir les problèmes de performance dans ce test de plus de 50 cas d'essai (cela prendra beaucoup de temps).

Comme son nom l'indique, il explore l'utilisation de la liste liée native de la structure DOM.

(Actuellement hors service, en cours de reconstruction) Plus de détails sur mon blog à ce sujet .

Le résumé est le suivant

• V8 Array est rapide, TRÈS RAPIDE
• Le push / pop / shift d'un tableau est environ 20 fois plus rapide que n'importe quel objet équivalent.
• Étonnamment Array.shift() est rapide ~approx 6x plus lent qu'un pop de tableau, mais est ~approx 100x plus rapide qu'une suppression d'attribut d'objet.
• C'est amusant, Array.push( data ); est plus rapide que Array[nextIndex] = data de près de 20 (réseau dynamique) à 10 (réseau fixe) fois plus.
• Array.unshift(data) est plus lent comme prévu, et est ~approximativement 5x plus lent que l'ajout d'une nouvelle propriété.
• Mise à zéro de la valeur array[index] = null est plus rapide que de l'effacer delete array[index] (non défini) dans un tableau par ~approx 4x++ plus rapide.
• Étonnamment, la mise à zéro d'une valeur dans un objet est obj[attr] = null ~Environ deux fois plus lent que la suppression de l'attribut. delete obj[attr]
• Sans surprise, le tableau intermédiaire Array.splice(index,0,data) est lent, très lent.
• Étonnamment, Array.splice(index,1,data) a été optimisé (pas de changement de longueur) et est 100x plus rapide que le simple splice Array.splice(index,0,data)
• Sans surprise, la divLinkedList est inférieure à un tableau dans tous les secteurs, à l'exception de dll.splice(index,1) suppression (où il a cassé le système de test).
• LA PLUS GRANDE SURPRISE comme l'a souligné jjrv, les écritures de tableaux V8 sont légèrement plus rapides que les lectures V8 =O

Note : Ces mesures ne s'appliquent qu'aux tableaux/objets de grande taille que la v8 n'a pas "entièrement optimisés". Il peut y avoir des cas très isolés de performances optimisées pour des tableaux/objets de taille inférieure à une taille arbitraire (24 ?). Plus de détails peuvent être vus à travers plusieurs vidéos de google IO.

Note 2 : Ces merveilleux résultats de performance ne sont pas partagés entre les navigateurs, en particulier *cough* IE. De plus, le test est énorme, donc je dois encore analyser et évaluer complètement les résultats : veuillez l'éditer =)

Note mise à jour (déc 2012) : Les représentants de Google ont des vidéos sur YouTube qui décrivent le fonctionnement interne de Chrome (par exemple, quand il passe d'un tableau de listes chaînées à un tableau fixe, etc. Voir GDC 2012 : De la console à Chrome pour plus.

Answer 2

À un niveau de base qui reste dans le domaine du JavaScript, les propriétés des objets sont des entités beaucoup plus complexes. Vous pouvez créer des propriétés avec des setters/getters, avec différentes possibilités d'énumération, d'écriture et de configuration. Un élément dans un tableau ne peut pas être personnalisé de cette manière : il existe ou n'existe pas. Au niveau du moteur sous-jacent, cela permet une optimisation beaucoup plus importante en termes d'organisation de la mémoire qui représente la structure.

En ce qui concerne l'identification d'un tableau à partir d'un objet (dictionnaire), les moteurs JS ont toujours fait une distinction explicite entre les deux. C'est pourquoi il existe une multitude d'articles sur les méthodes permettant de créer un objet semi-faux de type tableau qui se comporte comme tel mais permet d'autres fonctionnalités. La raison pour laquelle cette séparation existe est que les moteurs JS eux-mêmes stockent les deux objets différemment.

Les propriétés peuvent être stockées dans un tableau, mais cela démontre simplement que JavaScript insiste pour que tout soit un objet. Les valeurs indexées d'un tableau sont stockées différemment de toutes les propriétés que vous décidez de définir sur l'objet tableau qui représente les données sous-jacentes du tableau.

Chaque fois que vous utilisez un objet tableau légitime et que vous utilisez l'une des méthodes standard pour manipuler ce tableau, vous allez frapper les données du tableau sous-jacent. Dans V8, ces données sont essentiellement les mêmes que celles d'un tableau C++, donc ces règles s'appliquent. Si, pour une raison quelconque, vous travaillez avec un tableau que le moteur n'est pas en mesure de déterminer avec certitude comme étant un tableau, alors vous êtes sur un terrain beaucoup plus fragile. Avec les versions récentes de V8, il y a plus de place pour travailler. Par exemple, il est possible de créer une classe dont l'objet est Array.prototype. prototype tout en bénéficiant d'un accès efficace aux diverses méthodes natives de manipulation des tableaux. Mais il s'agit d'un changement récent.

Des liens spécifiques vers des modifications récentes de la manipulation des tableaux peuvent s'avérer utiles ici :

• http://code.google.com/p/v8/source/detail?r=10024
• http://code.google.com/p/v8/source/detail?r=9849
• http://code.google.com/p/v8/source/detail?r=9747

En guise d'extra, voici Array Pop et Array Push directement à partir de la source de V8, tous deux implémentés en JS lui-même :

function ArrayPop() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.pop"]);
  }

  var n = TO_UINT32(this.length);
  if (n == 0) {
    this.length = n;
    return;
  }
  n--;
  var value = this[n];
  this.length = n;
  delete this[n];
  return value;
}

function ArrayPush() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined",
                        ["Array.prototype.push"]);
  }

  var n = TO_UINT32(this.length);
  var m = %_ArgumentsLength();
  for (var i = 0; i < m; i++) {
    this[i+n] = %_Arguments(i);
  }
  this.length = n + m;
  return this.length;
}

Answer 3

J'aimerais compléter les réponses existantes par une enquête sur le comportement des implémentations en ce qui concerne la croissance des tableaux : Si elles les implémentent de la manière "habituelle", on verra beaucoup de poussées rapides avec de rares poussées lentes entrecoupées, au cours desquelles l'implémentation copie la représentation interne du tableau d'un tampon à un autre plus grand.

Vous pouvez voir cet effet très joliment, c'est à partir de Chrome :

16: 4ms
40: 8ms 2.5
76: 20ms 1.9
130: 31ms 1.7105263157894737
211: 14ms 1.623076923076923
332: 55ms 1.5734597156398105
514: 44ms 1.5481927710843373
787: 61ms 1.5311284046692606
1196: 138ms 1.5196950444726811
1810: 139ms 1.5133779264214047
2731: 299ms 1.5088397790055248
4112: 341ms 1.5056755767118273
6184: 681ms 1.5038910505836576
9292: 1324ms 1.5025873221216042

Bien que chaque poussée soit profilée, la sortie ne contient que celles qui prennent du temps au-dessus d'un certain seuil. Pour chaque test, j'ai personnalisé le seuil pour exclure toutes les poussées qui semblent représenter les poussées rapides.

Ainsi, le premier nombre représente l'élément qui a été inséré (la première ligne concerne le 17e élément), le deuxième est le temps que cela a pris (pour de nombreux tableaux, le benchmark est effectué en parallèle), et la dernière valeur est la division du premier nombre par celui de la première ligne.

Toutes les lignes dont le temps d'exécution est inférieur à 2 ms sont exclues pour Chrome.

Vous pouvez constater que Chrome augmente la taille des tableaux par puissances de 1,5, plus un certain décalage pour tenir compte des petits tableaux.

Pour Firefox, c'est une puissance de deux :

126: 284ms
254: 65ms 2.015873015873016
510: 28ms 2.0078740157480315
1022: 58ms 2.003921568627451
2046: 89ms 2.0019569471624266
4094: 191ms 2.0009775171065494
8190: 364ms 2.0004885197850513

J'ai dû augmenter un peu le seuil dans Firefox, c'est pourquoi nous commençons au numéro 126.

Avec IE, nous obtenons un mélange :

256: 11ms 256
512: 26ms 2
1024: 77ms 2
1708: 113ms 1.66796875
2848: 154ms 1.6674473067915691
4748: 423ms 1.6671348314606742
7916: 944ms 1.6672283066554338

Au début, c'est une puissance de deux, puis ça passe à des puissances de cinq tiers.

Ainsi, toutes les implémentations courantes utilisent la méthode "normale" pour les tableaux (au lieu de s'emballer avec des Cordes par exemple).

Voici le code de référence et voici le violon c'est dedans.

var arrayCount = 10000;

var dynamicArrays = [];

for(var j=0;j<arrayCount;j++)
    dynamicArrays[j] = [];

var lastLongI = 1;

for(var i=0;i<10000;i++)
{
    var before = Date.now();
    for(var j=0;j<arrayCount;j++)
        dynamicArrays[j][i] = i;
    var span = Date.now() - before;
    if (span > 10)
    {
      console.log(i + ": " + span + "ms" + " " + (i / lastLongI));
      lastLongI = i;
    }
}

Answer 4

Lors de l'exécution sous node.js 0.10 (construit sur v8), j'ai constaté une utilisation du CPU qui semblait excessive pour la charge de travail. J'ai attribué un problème de performance à une fonction qui vérifiait l'existence d'une chaîne dans un tableau. J'ai donc effectué quelques tests.

• a chargé 90 822 hôtes
• le chargement de la configuration a pris 0.087 secondes (tableau)
• le chargement de la configuration a pris 0.152 secondes (objet)

Charger 91k entrées dans un tableau (avec validate & push) est plus rapide que de définir obj[key]=value.

Dans le test suivant, j'ai cherché chaque nom d'hôte dans la liste une fois (91k itérations, pour faire la moyenne du temps de recherche) :

• la recherche de la configuration a pris 87,56 secondes (tableau)
• la recherche de la configuration a pris 0,21 seconde (objet)

L'application ici est Haraka (un serveur SMTP) et elle charge la host_list une fois au démarrage (et après les modifications) et effectue ensuite cette recherche des millions de fois pendant le fonctionnement. Le passage à un objet a permis de gagner énormément en performance.