¿Por qué la concatenación de cadenas es más rápida que la combinación de matrices?

Question

Hoy, leo this thread sobre la velocidad de concatenación de cadenas.

Sorprendentemente, la concatenación de cadenas fue el ganador:

http://jsben.ch/#/OJ3vo

El resultado fue lo contrario de lo que pensaba. Además, hay muchos artículos sobre esto que explica de manera opuesta como this o this.

Puedo adivinar que los navegadores están optimizados para la cadena concat en la última versión, pero ¿cómo lo hacen? ¿Podemos decir que es mejor usar + para concatenar cadenas?

Answer 1

optimizaciones cadena Navegador han cambiado la concatenación de cadenas imagen.

Firefox fue el primer navegador en optimizar la concatenación de cadenas. A partir de la versión 1.0, la técnica de matriz es realmente más lenta que usar el operador más en todos los casos. Otros navegadores también han optimizado la concatenación de cadenas, por lo que Safari, Opera, Chrome e Internet Explorer 8 también muestran un mejor rendimiento con el operador más. Internet Explorer anterior a la versión 8 no tenía esa optimización, por lo que la técnica de matriz siempre es más rápida que el operador más.

- Writing Efficient JavaScript: Chapter 7 – Even Faster Websites

El V8 Javascript motor (usado en Google Chrome) utiliza this code hacer concatenación de cadenas:

// 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, ""); 
} 

Así, internamente optimizarlo mediante la creación de un InternalArray (la variable parts), que luego se llena. La función StringBuilderConcat se llama con estas partes. Es rápido porque la función StringBuilderConcat es un código C++ muy optimizado. Es demasiado largo para citar aquí, pero busque en el archivo runtime.cc para RUNTIME_FUNCTION(MaybeObject*, Runtime_StringBuilderConcat) para ver el código.

Answer 2

Supongo que, aunque cada versión lleva el costo de muchas concatenaciones, las versiones de unión están construyendo matrices además de eso.

Answer 3

Yo diría que con cadenas es más fácil preasignar un buffer más grande. Cada elemento tiene solo 2 bytes (si UNICODE), por lo que incluso si es conservador, puede preasignar un búfer bastante grande para la cadena. Con arrays cada elemento es más "complejo", porque cada elemento es Object, por lo que una implementación conservadora preasignará espacio para menos elementos.

Si intenta agregar un for(j=0;j<1000;j++) antes de cada for, verá que (en cromo) la diferencia de velocidad se reduce. Al final, todavía era 1.5x para la concatenación de cadenas, pero más pequeño que el 2.6 anterior.

Y al tener que copiar los elementos, un carácter Unicode es probablemente menor que una referencia a un objeto JS.

Tenga en cuenta que existe la posibilidad de que muchas implementaciones de motores JS tienen una optimización para las matrices de tipo único que haría todo lo que he escrito :-) inútil

Answer 4

Firefox es rápido porque usa algo llamado Ropes (Ropes: an Alternative to Strings). Una cuerda es básicamente solo un DAG, donde cada Nodo es una cadena.

Entonces, por ejemplo, si hiciera a = 'abc'.concat('def'), el objeto recién creado se vería así. Por supuesto, esto no es exactamente como se ve en la memoria, porque todavía necesita tener un campo para el tipo de cadena, longitud y tal vez otra.

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

Y b = a.concat('123')

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

Así, en el caso más sencillo, la máquina virtual tiene que ver casi ningún trabajo. El único problema es que esto ralentiza un poco las otras operaciones en la cadena resultante. También esto, por supuesto, reduce la sobrecarga de memoria.

Por otro lado, ['abc', 'def'].join('') generalmente asigna memoria para diseñar la nueva cadena plana en la memoria. (Tal vez esto debe ser optimizado)

Answer 5

Esto claramente depende de la implementación del motor de JavaScript. Incluso para diferentes versiones de un motor, puede obtener resultados significativamente diferentes. Debes hacer tu propio punto de referencia para verificar esto.

Yo diría que String.concat tiene un mejor rendimiento en las versiones recientes de V8. Pero para Firefox y Opera, Array.join es un ganador.

Answer 6

This test muestra la penalidad de utilizar realmente una cadena hecha con concatenación de asignación en comparación con el método array.join. Si bien la velocidad total de la tarea sigue siendo dos veces más rápida en Chrome v31, ya no es tan grande como cuando no se usa la cadena resultante.

Answer 7

Los puntos de referencia son triviales. Concatenando repetidamente los mismos tres elementos, los resultados serán probables deterministas y memominados, el gestor de basura simplemente arrojará objetos de matriz (que no tendrán nada en cuanto a tamaño) y probablemente solo se empujarán y saldrán de la pila debido a que no referencias externas y porque las cadenas nunca cambian. Me impresionaría más si la prueba fuera una gran cantidad de cadenas generadas al azar. Como en un concierto o dos vale la pena.

Array.join FTW!