eliminar - ¿Cuál es el rendimiento de Objetos/Arrays en JavaScript?(específicamente para Google V8)

javascript definicion

Question

El rendimiento asociado con matrices y objetos en JavaScript (especialmente Google V8) sería muy interesante de documentar. No encuentro ningún artículo completo sobre este tema en Internet.

Entiendo que algunos objetos usan clases como su estructura de datos subyacente. Si hay muchas propiedades, a veces se trata como una tabla hash.

También entiendo que las matrices a veces se tratan como matrices C ++ (es decir, indexación aleatoria rápida, eliminación lenta y cambio de tamaño). Y, otras veces, se tratan más como Objetos (indexación rápida, inserción / eliminación rápida, más memoria). Y, tal vez, a veces se almacenan como listas vinculadas (es decir, indexación aleatoria lenta, extracción / inserción rápida al principio / final)

¿Cuál es el rendimiento preciso de las recuperaciones y manipulaciones de Array / Object en JavaScript? (específicamente para Google V8)

Más específicamente, ¿cuál es el impacto en el rendimiento de:

• Agregar una propiedad a un objeto
• Eliminar una propiedad de un objeto
• Indexar una propiedad en un objeto
• Agregar un elemento a una matriz
• Eliminar un elemento de una matriz
• Indexar un elemento en una matriz
• Llamando a Array.pop ()
• Llamando a Array.push ()
• Llamar a Array.shift ()
• Llamar a Array.unshift ()
• Llamando a Array.slice ()

Cualquier artículo o enlace para más detalles sería apreciado, también. :)

EDITAR: Realmente me pregunto cómo funcionan las matrices y los objetos de JavaScript bajo el capó. Además, ¿en qué contexto "sabe" el motor V8 para "cambiar" a otra estructura de datos?

Por ejemplo, supongamos que creo una matriz con ...

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

¿Qué está pasando realmente aquí?

O ... ¿qué hay de esto ...?

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

Para matrices convencionales, el rendimiento sería terrible; mientras que si se usó una LinkedList ... no tan mal.

Answer 1

En un nivel básico que se mantiene dentro de los dominios de JavaScript, las propiedades de los objetos son entidades mucho más complejas. Puede crear propiedades con setters / getters, con diferente enumerabilidad, capacidad de escritura y configurabilidad. Un elemento de una matriz no puede personalizarse de esta manera: existe o no existe. En el nivel de motor subyacente, esto permite una optimización mucho mayor en términos de organización de la memoria que representa la estructura.

En términos de identificación de una matriz de un objeto (diccionario), los motores JS siempre han establecido líneas explícitas entre los dos. Es por eso que hay una gran cantidad de artículos sobre métodos para tratar de crear un objeto semifinal similar a un Array que se comporte como uno pero que permita otras funcionalidades. La razón por la cual esta separación existe es porque los motores JS almacenan los dos de manera diferente.

Las propiedades se pueden almacenar en un objeto de matriz, pero esto simplemente demuestra cómo JavaScript insiste en hacer de todo un objeto. Los valores indexados en una matriz se almacenan de forma diferente a las propiedades que decida establecer en el objeto de la matriz que representa los datos de la matriz subyacente.

Siempre que uses un objeto legítimo de matriz y uses uno de los métodos estándar para manipular esa matriz, estarás presionando los datos subyacentes de la matriz. Específicamente en V8, estas son esencialmente las mismas que una matriz de C ++, por lo que se aplicarán esas reglas. Si por alguna razón estás trabajando con una matriz que el motor no puede determinar con confianza es una matriz, entonces estás en un terreno mucho más inestable. Sin embargo, con las versiones recientes de V8, hay más espacio para trabajar. Por ejemplo, es posible crear una clase que tenga Array.prototype como su prototipo y aún obtener acceso eficiente a los diversos métodos de manipulación de matrices nativas. Pero este es un cambio reciente.

Los enlaces específicos a los cambios recientes en la manipulación de la matriz pueden ser útiles aquí:

• 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

Como algo extra, aquí está Array Pop y Array Push directamente de la fuente de V8, ambos implementados en JS:

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

Answer 2

Me gustaría complementar las respuestas existentes con una investigación a la pregunta de cómo se comportan las implementaciones con respecto a las matrices en crecimiento: si las implementan de la manera "habitual", se verían muchos empujones rápidos con impulsos lentos e intercalados, en cuyo punto la implementación copia la representación interna de la matriz de un búfer a uno más grande.

Puedes ver este efecto muy bien, esto es 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

Aunque cada inserción está perfilada, la salida solo contiene aquellas que llevan un tiempo superior a un determinado umbral. Para cada prueba, personalicé el umbral para excluir todas las pulsaciones que parecen representar los empujes rápidos.

Entonces, el primer número representa qué elemento se ha insertado (la primera línea es para el elemento 17), el segundo es cuánto tiempo tomó (para muchas matrices, el punto de referencia se realiza en paralelo), y el último valor es la división del primer número por el de la primera línea.

Todas las líneas que tienen menos de 2 ms de tiempo de ejecución están excluidas para Chrome.

Puede ver que Chrome aumenta el tamaño de la matriz en potencias de 1.5, más algunas compensaciones para tener en cuenta las matrices pequeñas.

Para Firefox, es un poder de dos:

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

Tuve que subir un poco el umbral en Firefox, por eso comenzamos en el # 126.

Con IE, obtenemos una mezcla:

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

Es un poder de dos al principio y luego se mueve a poderes de cinco tercios.

Entonces, todas las implementaciones comunes usan la forma "normal" para las matrices (en vez de volverse locas con las ropes , por ejemplo).

Aquí está el código de referencia y aquí está el violín .

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

Answer 3

Mientras corría bajo node.js 0.10 (basado en v8) estaba viendo un uso de CPU que parecía excesivo para la carga de trabajo. Remonté un problema de rendimiento a una función que estaba verificando la existencia de una cadena en una matriz. Entonces realicé algunas pruebas.

• cargado 90,822 hosts
• la configuración de carga tomó 0.087 segundos (array)
• la configuración de carga tomó 0.152 segundos (objeto)

Cargar 91k entradas en un array (con validate & push) es más rápido que establecer obj [key] = value.

En la siguiente prueba, busqué cada nombre de host en la lista una vez (91k iteraciones, para promediar el tiempo de búsqueda):

• la configuración de búsqueda tomó 87.56 segundos (matriz)
• la búsqueda de configuración tomó 0.21 segundos (objeto)

La aplicación aquí es Haraka (un servidor SMTP) y carga la lista de host una vez al inicio (y después de los cambios) y posteriormente realiza esta búsqueda millones de veces durante la operación. Cambiar a un objeto fue una gran ganancia de rendimiento.

Answer 4

ACTUALIZACIÓN: Tenga en cuenta que JSPref está actualmente abajo

(He guardado una copia del caso de prueba, y actualizaré la respuesta una vez que JSPref sea reparado / se encuentre un sucesor)

Hmm ... tal vez una exageración por la respuesta ... pero creé un conjunto de pruebas, precisamente para explorar estos problemas (y más) ( copia archivada ).

Y en ese sentido, puede ver los problemas de rendimiento en este comprobador de casos de prueba de más de 50 (llevará mucho tiempo).

También, como su nombre lo sugiere, explora el uso del uso de la naturaleza de la lista vinculada nativa de la estructura DOM.

(Actualmente abajo, reconstruido en progreso) Más detalles en mi blog con respecto a esto .

El resumen es el siguiente

• La matriz V8 es rápida, MUY RÁPIDA
• Array push / pop / shift es ~ aproximadamente 20x + más rápido que cualquier objeto equivalente.
• Sorprendentemente Array.shift() es rápido ~ aproximadamente 6 veces más lento que un array pop, pero es ~ aproximadamente 100 veces más rápido que una eliminación de atributo de objeto.
• De manera Array.push( data ); , Array.push( data ); es más rápido que Array[nextIndex] = data por casi 20 (matriz dinámica) a 10 (matriz fija) por encima.
• Array.unshift(data) es más lento, como se esperaba, y es aproximadamente 5 veces más lento que una nueva propiedad.
• Anular la array[index] = null valores array[index] = null es más rápido que eliminarla delete array[index] (indefinida) en una matriz por ~ aproximadamente 4x ++ más rápido.
• Sorprendentemente, anular un valor en un objeto es obj[attr] = null ~ aproximadamente 2 veces más lento que simplemente borrar el atributo delete obj[attr]
• Como era de esperar, mid array Array.splice(index,0,data) es lento, muy lento.
• Sorprendentemente, Array.splice(index,1,data) se ha optimizado (sin cambio de longitud) y es 100 veces más rápido que simplemente empalmar Array.splice(index,0,data)
• Como era de esperar, divLinkedList es inferior a una matriz en todos los sectores, excepto dll.splice(index,1) eliminación (Donde se rompió el sistema de prueba).
• LA SORPRESA MÁS GRANDE de todo [como Jjrv señaló], las escrituras de matrices V8 son ligeramente más rápidas que las lecturas de V8 = O

Nota: Estas métricas se aplican solo a la matriz grande / objetos que v8 no "optimiza completamente". Puede haber casos de rendimiento optimizados muy aislados para el tamaño de matriz / objeto menor que un tamaño arbitrario (24?). Se pueden ver más detalles en varios videos de Google IO.

Nota 2: Estos maravillosos resultados de rendimiento no se comparten entre navegadores, especialmente *cough* IE. Además, la prueba es enorme, por lo tanto, aún debo analizar y evaluar completamente los resultados: edítelo en =)

Nota actualizada (diciembre de 2012): los representantes de Google tienen videos en YouTube que describen el funcionamiento interno de Chrome (como cuando se cambia de una matriz de listas vinculadas a una matriz fija, etc.) y cómo optimizarlos. Consulte GDC 2012: de la consola a Chrome para obtener más información.

Nota actualizada (feb 2013): Thx @badunk, por proporcionar el enlace de video en el punto exacto

Nota actualizada (junio de 2016): Thx @Benedikt, con respecto a la diferencia de rendimiento del empuje de matriz en arreglos fijos / dinámicos.