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

A 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 diferentes enumerabilidad, escritura y configurabilidad. Un elemento en una matriz no se puede personalizar de esta manera: existe o no. En el nivel del motor subyacente, esto permite mucha más optimización en términos de organización de la memoria que representa la estructura.

En términos de identificación 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 tratar de hacer un objeto similar a una matriz semi-falsa que se comporta como uno pero permite otra funcionalidad. La razón por la que esta separación incluso existe es porque los motores JS almacenan los dos de manera diferente.

Las propiedades se pueden almacenar en un objeto array, pero esto simplemente demuestra cómo JavaScript insiste en hacer que todo sea 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 matriz subyacentes.

Cada vez que usted está utilizando un objeto de matriz de fiar y el uso de uno de los métodos estándar de manipulación de esa matriz que vas a estar golpeando los datos de la matriz subyacente. En V8 específicamente, estos son esencialmente los mismos que una matriz de C++ por lo que esas reglas se aplicarán. Si por alguna razón está trabajando con una matriz que el motor no puede determinar con confianza es una matriz, entonces estás en 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 matriz.prototype como su prototype y aún así obtener un 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 matrices 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 un poco extra, aquí está el Array Pop y el Array Push directamente desde la fuente de V8, ambos implementados en el propio 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;
}

Mientras se ejecuta bajo nodo.js 0.10 (construido en v8) Estaba viendo el uso de la CPU que parecía excesivo para la carga de trabajo. Rastreé un problema de rendimiento a una función que estaba comprobando la existencia de una cadena en una matriz. Así que hice algunas pruebas.

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

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

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

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

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

Me gustaría complementar las respuestas existentes con una investigación a la pregunta de cómo se comportan las implementaciones con respecto a los arrays en crecimiento: Si los implementan de la manera "habitual", uno vería muchos empujones rápidos con empujones lentos raros e intercalados en el momento en que la implementación copia la representación interna del array 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 push está perfilado, la salida contiene solo aquellos que toman tiempo por encima de un cierto umbral. Para cada prueba personalizé el umbral para excluir todos los empujes que parecen representar los empujes rápidos.

Así que 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 muchos arrays el punto de referencia se realiza en paralelo), y el último valor es la división del primer número por el de la línea anterior.

Todas las líneas que tienen menos de 2ms tiempo de ejecución se excluyen para Chrome.

Se puede ver que Chrome aumenta el tamaño de la matriz en potencias de 1.5, además de algunos desplazamientos para dar cuenta de pequeños arreglos.

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 poner el umbral hasta un poco en Firefox, es por eso que empezamos en #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 una potencia de dos al principio y luego se mueve a potencias de cinco tercios.

Así que todas las implementaciones comunes utilice la forma "normal" para los arrays (en lugar de volverse loco con cuerdas, por ejemplo).

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

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