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

Les performances associées aux tableaux et aux objets en JavaScript (notamment Google V8) seraient très intéressantes à documenter. 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, il est parfois traité 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 lente et redimensionnement). Et, d'autres fois, ils sont traités plus comme des objets (indexation rapide, insertion / suppression rapide, plus de mémoire). Et peut-être qu'ils sont parfois stockés sous forme de 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 manipulations de tableaux / objets en JavaScript? (spécifiquement pour Google V8)

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

• Ajouter une propriété à un objet
• Supprimer une propriété d'un objet
• Indexer une propriété dans un objet
• Ajout d'un élément à un tableau
• Suppression d'un élément d'un tableau
• Indexation d'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 ()

Tous les articles ou liens pour plus de détails seraient également appréciés. :)

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

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

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

Que se passe-t-il vraiment ici?

Ou ... qu'en est-il de ça ... ???

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 conventionnels, les performances seraient terribles; alors que, si une LinkedList était utilisée ... pas si mal.

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

Et en ce sens, vous pouvez voir les problèmes de performances dans ce testeur de cas de test de plus de 50 ans (cela prendra beaucoup de temps).

De plus, comme son nom l'indique, il explore l'utilisation de la nature de liste chaînée native de la structure DOM.

(Actuellement en panne, reconstruit en cours) Plus de détails sur mon blog à ce sujet .

Le résumé est comme suit

• V8 Array est rapide, TRÈS RAPIDE
• Array push / pop / shift est environ 20x + plus rapide que tout autre équivalent d'objet.
• Étonnamment, il Array.shift()est rapide ~ environ 6x plus lent qu'un pop de tableau, mais environ 100x plus rapide qu'une suppression d'attribut d'objet.
• Fait amusant, il Array.push( data );est plus rapide que Array[nextIndex] = datade près de 20 fois (tableau dynamique) à 10 (tableau fixe).
• Array.unshift(data) est plus lent que prévu et environ 5 fois plus lent qu'une nouvelle propriété.
• Il array[index] = nullest plus rapide d' annuler la valeur que de la supprimer delete array[index](non définie) dans un tableau d'environ 4x ++ plus rapidement.
• Étonnamment, l'annulation d'une valeur dans un objet est obj[attr] = nullenviron 2x plus lente que la simple suppression de l'attributdelete obj[attr]
• Sans surprise, le mid array 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 100 fois plus rapide qu'une simple épissureArray.splice(index,0,data)
• sans surprise, le divLinkedList est inférieur à un tableau sur tous les secteurs, sauf le dll.splice(index,1)retrait (où il a cassé le système de test).
• PLUS GRANDE SURPRISE de tout cela [comme jjrv l'a souligné], les écritures de tableau V8 sont légèrement plus rapides que les lectures V8 = O

Remarque: ces métriques s'appliquent uniquement aux grands tableaux / objets dont la v8 ne «optimise pas entièrement». Il peut y avoir des cas de performances optimisées très isolés pour une taille de tableau / objet inférieure à une taille arbitraire (24?). Plus de détails peuvent être consultés en détail sur plusieurs vidéos Google IO.

Remarque 2: ces excellents résultats de performances ne sont pas partagés entre les navigateurs, en particulier *cough*IE. De plus, le test est énorme, donc je n'ai pas encore complètement analysé et évalué les résultats: veuillez le modifier dans =)

Note mise à jour (décembre 2012): les représentants de Google ont des vidéos sur les youtubes décrivant le fonctionnement interne de Chrome lui-même (comme quand il passe d'un tableau de listes liées à un tableau fixe, etc.), et comment les optimiser. Pour en savoir plus, consultez GDC 2012: de la console à Chrome .

À un niveau de base qui reste dans les domaines de JavaScript, les propriétés sur les objets sont des entités beaucoup plus complexes. Vous pouvez créer des propriétés avec des setters / getters, avec une énumération, une écriture et une configurabilité différentes. Un élément d'un tableau ne peut pas être personnalisé de cette façon: il existe ou non. 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 termes d'identification d'un tableau à partir d'un objet (dictionnaire), les moteurs JS ont toujours fait des lignes explicites entre les deux. C'est pourquoi il existe une multitude d'articles sur les méthodes permettant d'essayer de créer un objet semi-faux de type Array qui se comporte comme l'un mais autorise d'autres fonctionnalités. La raison pour laquelle cette séparation existe même est que les moteurs JS eux-mêmes stockent les deux différemment.

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

Chaque fois que vous utilisez un objet de tableau légitime et que vous utilisez l'une des méthodes standard de manipulation de ce tableau, vous allez frapper les données du tableau sous-jacent. Dans V8 en particulier, ce sont essentiellement les mêmes qu'un tableau C ++, donc ces règles s'appliqueront. Si, pour une raison quelconque, vous travaillez avec un tableau que le moteur n'est pas capable de déterminer avec confiance est un tableau, alors vous êtes sur un terrain beaucoup plus instable. Avec les versions récentes du V8, il y a plus de place pour travailler. Par exemple, il est possible de créer une classe qui a Array.prototype comme prototype tout en obtenant un accès efficace aux différentes méthodes de manipulation de tableaux natifs. Mais c'est un changement récent.

Des liens spécifiques vers des modifications récentes de la manipulation de tableaux peuvent être 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 plus, voici Array Pop et Array Push directement à partir de la source de V8, tous deux implémentés dans 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;
}

Je voudrais compléter les réponses existantes par une enquête sur la question du comportement des implémentations vis-à-vis des tableaux croissants: si elles les implémentent de la manière «habituelle», on verrait de nombreuses poussées rapides avec des poussées lentes rares et entrecoupées à quel point l'implémentation copie la représentation interne du tableau d'un tampon à un plus grand.

Vous pouvez voir cet effet très bien, c'est 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

Même si chaque push est profilé, la sortie ne contient que ceux 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 quel élément a été inséré (la première ligne est pour le 17e élément), le second est le temps qu'il a fallu (pour de nombreux tableaux, le benchmark est fait en parallèle), et la dernière valeur est la division du premier numéro par celui de l’ancienne ligne.

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

Vous pouvez voir que Chrome augmente la taille du tableau en 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 n ° 126.

Avec IE, on obtient un mix:

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

C'est une puissance de deux au début, puis elle passe à des puissances de cinq tiers.

Ainsi, toutes les implémentations courantes utilisent la méthode "normale" pour les tableaux (au lieu de devenir fou avec des cordes , par exemple).

Voici le code de référence et voici le violon dans lequel il se trouve.

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;
    }
}

Lors de l'exécution sous node.js 0.10 (basé sur la v8), je voyais une utilisation du processeur qui semblait excessive pour la charge de travail. J'ai tracé un problème de performances à une fonction qui vérifiait l'existence d'une chaîne dans un tableau. J'ai donc fait quelques tests.

• 90822 hôtes chargés
• le chargement de la configuration a pris 0,087 seconde (tableau)
• le chargement de la configuration a pris 0,152 seconde (objet)

Le chargement de 91k entrées dans un tableau (avec validation et push) est plus rapide que de définir obj [clé] = valeur.

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

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

L'application ici est Haraka (un serveur SMTP) et il charge la liste d'hôte une fois au démarrage (et après les modifications) et effectue ensuite cette recherche des millions de fois pendant le fonctionnement. Passer à un objet a été une énorme victoire en termes de performances.