Pourquoi est-array.pousser parfois plus vite que tableau[n] = valeur?

Question

Comme résultat de tests de code que j'ai écrit une petite fonction pour comparer la vitesse de l'aide de la matrice.méthode push vs adressage direct (tableau[n] = valeur). À ma grande surprise, la méthode push souvent montré pour être plus rapide en particulier dans Firefox et parfois dans google Chrome. Juste par curiosité: quelqu'un a une explication pour ça? Vous pouvez trouver le test @cette page (cliquez sur "les méthodes de Tableau de comparaison')

Answer 1

Toutes sortes de facteurs entrent en jeu, la plupart des JS implémentations utilisent un tableau plat qui convertit à la faible densité de stockage s'il devient nécessaire plus tard.

Fondamentalement, la décision de devenir rare est une heuristique basée sur ce que les éléments sont en cours de définition, et de combien d'espace serait perdu dans le but de rester à plat.

Dans votre cas, vous définissez le dernier élément de la première, ce qui signifie que le moteur JS va voir un tableau qui doit avoir une longueur d' n , mais seulement un seul élément. Si n est assez grand ce sera immédiatement faire le tableau d'un tableau fragmenté -- dans la plupart des moteurs, ce qui signifie que toutes les insertions prendre la lente tableau fragmenté cas.

Vous devez ajouter un test dans lequel vous remplissez le tableau à partir de l'indice 0 à l'indice n-1 -- il devrait être beaucoup plus rapide.

En réponse à @Christoph et d'une volonté de remettre à plus tard, voici une description de la façon dont les tableaux sont (en général), mis en œuvre en JS -- les détails varient d'un moteur JS JS moteur, mais le principe général est le même.

Tous les JS Objects (donc pas de chaînes de caractères, nombres, true, false, undefinedou null) héritent d'un type d'objet de base-exactement la mise en œuvre varie, il peut être en C++ à l'héritage, ou manuellement en C (il y a des avantages à le faire dans les deux sens) -- le type d'Objet de base définit la valeur par défaut de la propriété méthodes d'accès, par exemple.

interface Object {
    put(propertyName, value)
    get(propertyName)
private:
    map properties; // a map (tree, hash table, whatever) from propertyName to value
}

Ce type d'Objet gère l'ensemble de la norme de l'accès à la propriété de la logique, de la chaîne de prototype, etc. Alors la Matrice de mise en œuvre devient

interface Array : Object {
    override put(propertyName, value)
    override get(propertyName)
private:
    map sparseStorage; // a map between integer indices and values
    value[] flatStorage; // basically a native array of values with a 1:1
                         // correspondance between JS index and storage index
    value length; // The `length` of the js array
}

Maintenant, lorsque vous créez un Tableau en JS le moteur crée quelque chose qui s'apparente à la structure de données. Lorsque vous insérez un objet dans le Tableau d'exemple, le Tableau est mis méthode vérifie si le nom de la propriété est un entier (ou peut être converti en un entier, par exemple, "121", "2341", etc.) entre 0 et 2^32-1 (ou éventuellement 2^31-1, je ne sais plus exactement). Si elle ne l'est pas, alors la méthode put est transmis à l'Objet de base de la mise en œuvre, et la norme [[]] la logique est fait. Sinon, la valeur est placée dans la Matrice de stockage, si les données sont suffisamment compact alors le moteur de l'usage de l'appartement de la matrice de stockage, dans lequel cas d'insertion (et récupération) est un tableau d'indexation de fonctionnement, sinon le moteur va convertir la matrice de stockage limité, et put/get utiliser une carte pour obtenir de propertyName à la valeur de l'emplacement.

Je suis honnêtement pas sûr si l'un JS moteur convertit éparse de stockage à plat après que la conversion se produit.

Anyhoo, c'est un niveau assez élevé aperçu de ce qui se passe et laisse de côté un certain nombre de la plus dégueulasse de détails, mais c'est la mise en œuvre générale de motif. Les détails de la façon dont l'espace de stockage supplémentaire, et comment mettre/obtenir sont distribué diffère de moteur à moteur, mais c'est la plus claire que je ne peut vraiment décrire la conception/mise en œuvre.

Un mineur de plus point, tandis que l'ES spec désigne propertyName comme une chaîne de caractères JS moteurs ont tendance à se spécialiser sur l'entier des recherches, ainsi someObject[someInteger] ne sera pas convertir un entier en chaine de caractère si vous êtes à la recherche d'un objet qui a entier propriétés, par exemple. Array, String, et DOM types (NodeLists, etc).

Answer 2

Ces sont le résultat de votre test

sur Safari:

• Tableau.push(n) 1 000 000 de valeurs: 0.124 sec
• Tableau[n .. 0] = valeur (décroissant) 1 000 000 de valeurs: 3.697 sec
• Array[0 .. n] = valeur (croissant) 1 000 000 de valeurs: 0.073 sec

sur FireFox:

• Tableau.push(n) 1 000 000 de valeurs: 0.075 sec
• Tableau[n .. 0] = valeur (décroissant) 1 000 000 de valeurs: 1.193 sec
• Array[0 .. n] = valeur (ascendant) 1 000 000 de valeurs: 0.055 sec

sur IE7:

• Tableau.push(n) 1 000 000 de valeurs: 2.828 sec
• Tableau[n .. 0] = valeur (décroissant) 1 000 000 de valeurs: 1.141 sec
• Array[0 .. n] = valeur (ascendant) 1 000 000 de valeurs: 7.984 sec

En fonction de votre test de le pousser méthode semble être de mieux en mieux sur IE7 (la différence est énorme), et depuis sur les autres navigateurs, la différence est faible, il semble être le pousser méthode vraiment la meilleure façon d'ajouter un élément dans un tableau.

Mais j'ai créé un autre simple script de test pour vérifier que la méthode est rapide pour ajouter des valeurs à un tableau, les résultats m'a vraiment surpris, à l'aide du Tableau.longueur semble être beaucoup plus rapide par rapport à l'aide du Tableau.pousser, donc je ne sais vraiment pas quoi dire ou penser de plus, je suis paumé.

BTW: sur mon IE7 votre script s'arrête et les navigateurs me demande si je veux le laisser aller sur (vous savez, le typique IE message qui dit: "Arrêtez enflammée ce script? ...") Je recoomend à réduire un peu les boucles.

Answer 3

push() est un cas particulier de la plus générale [[]] et, par conséquent, peut être optimisée:

Lors de l'appel de [[]] sur un objet de tableau, l'argument doit être converti en un entier non signé, d'abord parce que tous les noms de propriété - y compris les indices de tableau - sont des chaînes de caractères. Alors, il doit être par rapport à la longueur de la propriété de la matrice afin de déterminer si oui ou non la longueur doit être augmenté. Lors de la poussée, aucune conversion ou la comparaison a lieu: il suffit d'utiliser la longueur actuelle en tant que tableau d'index et de l'augmenter.

Bien sûr il y a d'autres choses qui aura une incidence sur le moment de l'exécution, par exemple en appelant push() devrait être plus lente que d'appeler [[]] via [] parce que le prototype de la chaîne doit être vérifiée à l'ancienne.

---

Comme olliej souligné: ECMAScript implémentations d'optimiser la conversion, c'est à dire pour les noms de propriété, pas de conversion de chaîne à uint est fait, mais juste une simple vérification de type. L'hypothèse de base devraient toujours tenir, bien que son impact sera moins j'ai d'abord supposé.

Answer 4

Voici un bon banc d'essai, ce qui confirme que l'affectation directe est beaucoup plus rapide que le push: http://jsperf.com/array-direct-assignment-vs-push.

Edit: il semble y avoir un certain problème en montrant que les résultats cumulatifs de données, mais j'espère que c'est résolu bientôt.

Answer 5

Pousser l'ajoute à la fin, tandis que tableau[n] est d'aller à travers le tableau pour trouver le bon endroit. Dépend probablement sur le navigateur et sa manière de manipuler des tableaux.