Pourquoi la concaténation de chaînes est-elle plus rapide que la jointure de tableau?

Aujourd'hui, j'ai lu ce fil sur la vitesse de concaténation de chaînes.

Étonnamment, la concaténation de chaînes a été le gagnant:

http://jsben.ch/#/OJ3vo

Le résultat était à l'opposé de ce que je pensais. Par ailleurs, il y a beaucoup d' articles sur ce qui expliquent de manière opposée comme cela .

Je peux deviner que les navigateurs sont optimisés pour la chaîne concatsur la dernière version, mais comment font-ils cela? Peut-on dire qu'il est préférable d'utiliser +lors de la concaténation de chaînes?

Mettre à jour

Ainsi, dans les navigateurs modernes, la concaténation de chaînes est optimisée, donc l'utilisation de +signes est plus rapide que l'utilisation joinlorsque vous souhaitez concaténer des chaînes.

Mais @Arthur a souligné que joinc'est plus rapide si vous voulez réellement joindre des chaînes avec un séparateur.

Mise à jour - 2020
Chrome: Array joinest presque 2 times fasterString concat + Voir: https://stackoverflow.com/a/54970240/984471

À noter:

• Array joinest meilleur si vous avezlarge strings
• Si nous avons besoin de générer several small stringsdans la sortie finale, il est préférable d'utiliser string concat +, car sinon, utiliser Array nécessitera plusieurs conversions de tableau en chaîne à la fin, ce qui est une surcharge de performances.

Les optimisations de chaînes du navigateur ont modifié l'image de concaténation de chaînes.

Firefox a été le premier navigateur à optimiser la concaténation de chaînes. À partir de la version 1.0, la technique de tableau est en fait plus lente que l'utilisation de l'opérateur plus dans tous les cas. D'autres navigateurs ont également optimisé la concaténation de chaînes, de sorte que Safari, Opera, Chrome et Internet Explorer 8 affichent également de meilleures performances en utilisant l'opérateur plus. Internet Explorer avant la version 8 n'avait pas une telle optimisation, et donc la technique de tableau est toujours plus rapide que l'opérateur plus.

- Écriture de JavaScript efficace: Chapitre 7 - Sites Web encore plus rapides

Le moteur javascript V8 (utilisé dans Google Chrome) utilise ce code pour effectuer la concaténation de chaînes:

// ECMA-262, section 15.5.4.6
function StringConcat() {
  if (IS_NULL_OR_UNDEFINED(this) && !IS_UNDETECTABLE(this)) {
    throw MakeTypeError("called_on_null_or_undefined", ["String.prototype.concat"]);
  }
  var len = %_ArgumentsLength();
  var this_as_string = TO_STRING_INLINE(this);
  if (len === 1) {
    return this_as_string + %_Arguments(0);
  }
  var parts = new InternalArray(len + 1);
  parts[0] = this_as_string;
  for (var i = 0; i < len; i++) {
    var part = %_Arguments(i);
    parts[i + 1] = TO_STRING_INLINE(part);
  }
  return %StringBuilderConcat(parts, len + 1, "");
}

Ainsi, en interne, ils l'optimisent en créant un InternalArray (la partsvariable), qui est ensuite rempli. La fonction StringBuilderConcat est appelée avec ces pièces. C'est rapide car la fonction StringBuilderConcat est un code C ++ fortement optimisé. Il est trop long de citer ici, mais recherchez dans le fichier runtime.cc pour RUNTIME_FUNCTION(MaybeObject*, Runtime_StringBuilderConcat)voir le code.

Firefox est rapide car il utilise quelque chose appelé Ropes ( Ropes: an Alternative to Strings ). Une corde n'est en fait qu'un DAG, où chaque nœud est une chaîne.

Ainsi, par exemple, si vous le faites a = 'abc'.concat('def'), l'objet nouvellement créé ressemblerait à ceci. Bien sûr, ce n'est pas exactement à quoi cela ressemble en mémoire, car vous devez toujours avoir un champ pour le type de chaîne, la longueur et peut-être autre.

a = {
 nodeA: 'abc',
 nodeB: 'def'
}

Et b = a.concat('123')

b = {
  nodeA: a, /* {
             nodeA: 'abc',
             nodeB: 'def'
          } */
  nodeB: '123'
}           

Ainsi, dans le cas le plus simple, la machine virtuelle ne doit pratiquement pas faire de travail. Le seul problème est que cela ralentit un peu les autres opérations sur la chaîne résultante. De plus, cela réduit naturellement la surcharge de la mémoire.

D'un autre côté, ['abc', 'def'].join('')il suffit généralement d'allouer de la mémoire pour disposer la nouvelle chaîne à plat en mémoire. (Peut-être que cela devrait être optimisé)

Je sais que c'est un vieux fil, mais votre test est incorrect. Vous faites output += myarray[i];alors que cela devrait être plus output += "" + myarray[i];parce que vous avez oublié, que vous devez coller des éléments avec quelque chose. Le code concat devrait être quelque chose comme:

var output = myarray[0];
for (var i = 1, len = myarray.length; i<len; i++){
    output += "" + myarray[i];
}

De cette façon, vous effectuez deux opérations au lieu d'une en raison du collage d'éléments ensemble.

Array.join() est plus rapide.

Pour une grande quantité de données, la jointure est plus rapide, la question est donc mal posée.

let result = "";
let startTime = new Date().getTime();
for (let i = 0; i < 2000000; i++) {
    result += "x";
}
console.log("concatenation time: " + (new Date().getTime() - startTime));

startTime = new Date().getTime();
let array = new Array(2000000);
for (let i = 0; i < 2000000; i++) {
    array[i] = "x";
}
result = array.join("");
console.log("join time: " + (new Date().getTime() - startTime));

Testé sur Chrome 72.0.3626.119, Firefox 65.0.1, Edge 42.17134.1.0. Notez que c'est plus rapide même avec la création de tableau incluse!

Les repères là-bas sont triviaux. La concaténation répétée des trois mêmes éléments sera intégrée, les résultats se révéleront déterministes et mémorisés, le gestionnaire de déchets rejettera simplement des objets de tableau (qui n'auront presque rien en taille) et probablement juste poussé et sauté de la pile en raison de non références externes et parce que les chaînes ne changent jamais. Je serais plus impressionné si le test était un grand nombre de chaînes générées aléatoirement. Comme dans un concert ou deux de cordes.

Array.join FTW!

Je dirais qu'avec des chaînes, il est plus facile de préallouer un tampon plus grand. Chaque élément ne fait que 2 octets (si UNICODE), donc même si vous êtes prudent, vous pouvez préallouer un tampon assez gros pour la chaîne. Avec arrayschaque élément est plus "complexe", parce que chaque élément est un Object, donc une implémentation conservatrice préallouera de l'espace pour moins d'éléments.

Si vous essayez d'ajouter un for(j=0;j<1000;j++)avant chacun, forvous verrez que (sous chrome) la différence de vitesse devient plus petite. En fin de compte, il était toujours 1,5x pour la concaténation de chaînes, mais plus petit que le 2,6 qui était avant.

ET avoir à copier les éléments, un caractère Unicode est probablement plus petit qu'une référence à un objet JS.

Sachez qu'il est possible que de nombreuses implémentations de moteurs JS aient une optimisation pour les tableaux de type unique qui rendrait tout ce que j'ai écrit inutile :-)

Ce test montre la peine d'utiliser réellement une chaîne créée avec la concaténation d'affectation par rapport à la méthode array.join. Bien que la vitesse globale d'attribution soit toujours deux fois plus rapide dans Chrome v31, elle n'est plus aussi énorme que lorsque vous n'utilisez pas la chaîne résultante.

Cela dépend clairement de l'implémentation du moteur javascript. Même pour différentes versions d'un même moteur, vous pouvez obtenir des résultats significativement différents. Vous devez faire votre propre benchmark pour vérifier cela.

Je dirais que cela String.concata de meilleures performances dans les versions récentes du V8. Mais pour Firefox et Opera, Array.joinc'est un gagnant.

Je suppose que, bien que chaque version supporte le coût de nombreuses concaténations, les versions de jointure créent des tableaux en plus de cela.