Quelle est la performance de Objects / Arrays en JavaScript? (spécifiquement pour Google V8)


Answers

À 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 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 il ne l'est pas. Au niveau du moteur sous-jacent, cela permet beaucoup plus d'optimisation en termes d'organisation de la mémoire qui représente la structure.

En termes d'identification d'un tableau 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 pour essayer de créer un objet semblable à un Array semi-faux qui se comporte comme un seul mais qui permette d'autres fonctionnalités. La raison de cette séparation existe même parce 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 que tout soit un objet. Les valeurs indexées dans un tableau sont stockées différemment des propriétés que vous décidez de définir sur l'objet tableau qui représente les données du tableau sous-jacent.

Chaque fois que vous utilisez un objet tableau légitime et que vous utilisez l'une des méthodes standard de manipulation de ce tableau, vous allez toucher les données du tableau sous-jacent. Dans V8 en particulier, ceux-ci sont essentiellement les mêmes qu'un tableau C ++ donc ces règles s'appliqueront. Si, pour une raison ou une autre, vous travaillez avec un tableau que le moteur n'est pas en mesure de déterminer en toute confiance est un tableau, alors vous êtes sur un terrain beaucoup plus difficile. 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 le prototype est Array.prototype et de bénéficier d'un accès efficace aux diverses méthodes de manipulation du tableau natif. Mais c'est un changement récent.

Des liens spécifiques aux modifications récentes apportées à la manipulation des tableaux peuvent s'avérer utiles ici:

Comme un peu 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;
}
Question

Les performances associées aux tableaux et objets en JavaScript (notamment Google V8) seraient très intéressantes à documenter. Je ne trouve aucun article complet sur ce sujet n'importe où 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 une indexation aléatoire rapide, une suppression lente et un redimensionnement). Et, d'autres fois, ils sont traités plus comme des objets (indexation rapide, insertion / suppression rapide, plus de mémoire). Et, parfois, ils sont stockés sous forme de listes liées (par exemple, indexation lente et aléatoire, suppression / insertion rapide au début / à la fin)

Quelle est la performance précise des récupérations Array / Object et des manipulations 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
  • Suppression d'une propriété d'un objet
  • Indexer une propriété dans un objet
  • Ajouter un élément à un tableau
  • Supprimer 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 ()
  • Appeler Array.unshift ()
  • Appel de Array.slice ()

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

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» 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 ... et à propos 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 baies conventionnelles, la performance serait terrible; alors, si un LinkedList a été utilisé ... pas si mal.




Je voudrais compléter les réponses existantes par une recherche sur la manière dont les implémentations se comportent pour les tableaux croissants: Si elles les implémentent de la manière "habituelle", on verrait beaucoup de poussées rapides avec des poussées lentes, intercalées et lentes. la représentation interne du tableau d'un tampon à un plus grand.

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

Même si chaque poussée est 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 tous les poussoirs qui semblent représenter les poussées rapides.

Donc le premier nombre représente quel élément a été inséré (la première ligne est pour le 17ème élément), le second est combien de temps il a fallu (pour de nombreux tableaux le benchmark est fait en parallèle), et la dernière valeur est la division du premier nombre par celui de 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 voir que Chrome augmente la taille du tableau dans les 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û mettre un peu le seuil dans Firefox, c'est pourquoi nous commençons à # 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

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

Ainsi, toutes les implémentations courantes utilisent la méthode "normale" pour les tableaux (au lieu de devenir fous avec des ropes , 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;
    }
}