¿Cuál es el rendimiento de objetos / matrices en JavaScript? (específicamente para Google V8)

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 / remoción rápida, más memoria). Y, tal vez a veces se almacenan como listas vinculadas (es decir, indexación aleatoria lenta, eliminación / inserción rápida al principio / final)

¿Cuál es el rendimiento preciso de las recuperaciones y manipulaciones de matrices / objetos 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
• Indexación de un elemento en una matriz
• Llamando a Array.pop ()
• Llamar a Array.push ()
• Llamar a Array.shift ()
• Llamar a Array.unshift ()
• Llamando a Array.slice ()

También se agradecería cualquier artículo o enlace para obtener más detalles. :)

EDITAR: Realmente me pregunto cómo funcionan las matrices y objetos de JavaScript bajo el capó. Además, ¿en qué contexto el motor V8 "sabe" "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 las matrices convencionales, el rendimiento sería terrible; mientras que, si se utilizó una LinkedList ... no tan mal.

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 probador de más de 50 casos de prueba (llevará mucho tiempo).

Además, como sugiere su nombre, explora el uso de la naturaleza de lista enlazada nativa de la estructura DOM.

(Actualmente inactivo, reconstruido en progreso) Más detalles en mi blog al respecto .

El resumen es el siguiente

• V8 Array es rápido, MUY RÁPIDO
• Array push / pop / shift es aproximadamente 20 veces más rápido que cualquier objeto equivalente.
• Sorprendentemente, Array.shift()es rápido ~ aproximadamente 6 veces más lento que una matriz emergente, pero es ~ aproximadamente 100 veces más rápido que la eliminación de un atributo de objeto.
• Curiosamente, Array.push( data );es más rápido que Array[nextIndex] = dataen casi 20 (matriz dinámica) a 10 (matriz fija) veces.
• Array.unshift(data) es más lento como se esperaba, y es ~ aproximadamente 5 veces más lento que la adición de una nueva propiedad.
• Anular el valor array[index] = nulles más rápido que eliminarlo delete array[index](indefinido) en una matriz ~ 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 eliminar el atributodelete obj[attr]
• Como era de esperar, la matriz media Array.splice(index,0,data)es lenta, muy lenta.
• Sorprendentemente, Array.splice(index,1,data)se ha optimizado (sin cambio de longitud) y es 100 veces más rápido que solo empalmarArray.splice(index,0,data)
• como era de esperar, divLinkedList es inferior a una matriz en todos los sectores, excepto en la dll.splice(index,1)eliminación (donde rompió el sistema de prueba).
• LA MAYOR SORPRESA de todo [como señaló jjrv], las escrituras de matriz V8 son ligeramente más rápidas que las lecturas V8 = O

Nota: estas métricas se aplican solo a grandes conjuntos / objetos que la versión 8 no "optimiza completamente". Puede haber casos de rendimiento optimizado muy aislados para un 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, todavía tengo que analizar y evaluar completamente los resultados: edítelo en =)

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

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

En términos de identificar una matriz de un objeto (diccionario), los motores JS siempre han hecho líneas explícitas entre los dos. Es por eso que hay una multitud de artículos sobre métodos para intentar hacer un objeto similar a una matriz semi-falso que se comporte como uno pero que permita otras funciones. La razón por la que esta separación incluso existe es porque los propios 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 convertir todo en un objeto. Los valores indexados en una matriz se almacenan de manera diferente a cualquier propiedad que decida establecer en el objeto de matriz que representa los datos de la matriz subyacente.

Siempre que esté utilizando un objeto de matriz legítimo y use uno de los métodos estándar para manipular esa matriz, estará golpeando los datos de la matriz subyacente. Específicamente en V8, estos son esencialmente lo mismo que un arreglo de C ++, por lo que se aplicarán esas reglas. Si por alguna razón está trabajando con una matriz que el motor no puede determinar con confianza es una matriz, entonces se encuentra 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 así obtener un acceso eficiente a los diversos métodos nativos de manipulación de matrices. Pero este es un cambio reciente.

Los enlaces específicos a cambios recientes en la manipulación de matrices pueden resultar ú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 un poco más, aquí está Array Pop y Array Push directamente desde la fuente de V8, ambos implementados en JS mismo:

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

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 impulsos rápidos con impulsos lentos raros e intercalados, momento en el que la implementación se 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 se perfila cada impulso, la salida contiene solo aquellos que toman tiempo por encima de un cierto umbral. Para cada prueba, personalicé el umbral para excluir todos los impulsos que parecen representar los impulsos 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 el tiempo que tomó (para muchas matrices, el punto de referencia se realiza en paralelo) y el último valor es la división de la primer número por el de la línea anterior.

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

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

Para Firefox, es una potencia 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 n. ° 126.

Con IE, obtenemos una combinación:

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 una potencia de dos al principio y luego se mueve a potencias de cinco tercios.

Entonces, todas las implementaciones comunes usan la forma "normal" para las matrices (en lugar de volverse locas con cuerdas , 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;
    }
}

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

• cargado 90,822 hosts
• cargar la configuración tomó 0.087 segundos (matriz)
• cargar la configuración tomó 0.152 segundos (objeto)

Cargar 91k entradas en una matriz (con validar y empujar) es más rápido que configurar obj [clave] = valor.

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 la configuración tomó 0.21 segundos (objeto)

La aplicación aquí es Haraka (un servidor SMTP) y carga el host_list 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.