Qual é o desempenho de Objetos / Arrays em JavaScript? (especificamente para Google V8)

O desempenho associado a matrizes e objetos em JavaScript (especialmente Google V8) seria muito interessante de documentar. Não encontro nenhum artigo abrangente sobre esse tópico em qualquer lugar da Internet.

Eu entendo que alguns objetos usam classes como sua estrutura de dados subjacente. Se houver muitas propriedades, às vezes é tratado como uma tabela hash?

Eu também entendo que as matrizes às vezes são tratadas como matrizes C ++ (ou seja, indexação aleatória rápida, exclusão e redimensionamento lento). E, outras vezes, são tratados mais como Objetos (indexação rápida, inserção / remoção rápida, mais memória). E, às vezes, eles são armazenados como listas vinculadas (ou seja, indexação aleatória lenta, remoção / inserção rápida no início / fim)

Qual é o desempenho preciso de recuperações e manipulações de Array / Objeto em JavaScript? (especificamente para Google V8)

Mais especificamente, qual é o impacto no desempenho de:

• Adicionando uma propriedade a um objeto
• Removendo uma propriedade de um objeto
• Indexando uma propriedade em um objeto
• Adicionando um item a uma matriz
• Removendo um item de uma matriz
• Indexando um item em uma matriz
• Chamando Array.pop ()
• Chamando Array.push ()
• Chamando Array.shift ()
• Chamando Array.unshift ()
• Chamando Array.slice ()

Quaisquer artigos ou links para mais detalhes também serão apreciados. :)

EDIT: Estou realmente me perguntando como os arrays e objetos JavaScript funcionam nos bastidores. Além disso, em que contexto o motor V8 "sabe" como "alternar" para outra estrutura de dados?

Por exemplo, suponha que eu crie uma matriz com ...

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

O que realmente está acontecendo aqui?

Ou ... que tal isso ... ???

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 matrizes convencionais, o desempenho seria terrível; Considerando que, se um LinkedList foi usado ... não é tão ruim.

Criei um conjunto de testes, precisamente para explorar esses problemas (e mais) ( cópia arquivada ).

E, nesse sentido, você pode ver os problemas de desempenho neste testador de mais de 50 casos de teste (vai demorar muito).

Também como o próprio nome sugere, ele explora o uso do uso da natureza de lista vinculada nativa da estrutura DOM.

(Atualmente inativo, reconstruído em andamento) Mais detalhes no meu blog sobre isso .

O resumo é o seguinte

• V8 Array é rápido, MUITO RÁPIDO
• Array push / pop / shift é aproximadamente 20x + mais rápido do que qualquer objeto equivalente.
• Surpreendentemente, Array.shift()é rápido ~ aproximadamente 6x mais lento do que um pop de array, mas é aproximadamente 100x mais rápido do que a exclusão de um atributo de objeto.
• Curiosamente, Array.push( data );é mais rápido do que Array[nextIndex] = dataquase 20 (matriz dinâmica) a 10 (matriz fixa) vezes.
• Array.unshift(data) é mais lento como esperado e é aproximadamente 5x mais lento do que a adição de uma nova propriedade.
• Anular o valor array[index] = nullé mais rápido do que excluí-lo delete array[index](indefinido) em uma matriz em aproximadamente 4x ++ mais rápido.
• Surpreendentemente anular um valor em um objeto é obj[attr] = nullaproximadamente 2x mais lento do que apenas excluir o atributodelete obj[attr]
• Não Array.splice(index,0,data)é novidade que o mid array é lento, muito lento.
• Surpreendentemente, Array.splice(index,1,data)foi otimizado (sem alteração de comprimento) e é 100x mais rápido do que apenas emendarArray.splice(index,0,data)
• sem surpresa, o divLinkedList é inferior a uma matriz em todos os setores, exceto dll.splice(index,1)remoção (onde quebrou o sistema de teste).
• A MAIOR SURPRESA de tudo [como jjrv apontou], as gravações de matriz V8 são ligeiramente mais rápidas do que as leituras V8 = O

Observação: essas métricas se aplicam apenas a grandes matrizes / objetos que a v8 não "otimiza totalmente". Pode haver casos de desempenho otimizado muito isolados para tamanho de array / objeto menor que um tamanho arbitrário (24?). Mais detalhes podem ser vistos amplamente em vários vídeos do Google IO.

Observação 2: esses resultados de desempenho maravilhosos não são compartilhados entre navegadores, especialmente o *cough*IE. Além disso, o teste é enorme, por isso ainda não analisei e avaliei totalmente os resultados: edite-o em =)

Nota atualizada (dezembro de 2012): Os representantes do Google têm vídeos em youtubes que descrevem o funcionamento interno do cromo em si (como quando ele muda de um array de lista vinculada para um array fixo, etc) e como otimizá-los. Consulte GDC 2012: do console ao Chrome para mais informações.

Em um nível básico que permanece dentro dos domínios do JavaScript, as propriedades dos objetos são entidades muito mais complexas. Você pode criar propriedades com setters / getters, com enumerabilidade, gravabilidade e configurabilidade diferentes. Um item em uma matriz não pode ser personalizado desta forma: ou existe ou não. No nível do mecanismo subjacente, isso permite muito mais otimização em termos de organização da memória que representa a estrutura.

Em termos de identificação de uma matriz de um objeto (dicionário), os motores JS sempre fizeram linhas explícitas entre os dois. É por isso que há uma infinidade de artigos sobre métodos de tentativa de fazer um objeto semi-falso do tipo Array que se comporta como um, mas permite outra funcionalidade. A razão pela qual essa separação existe é porque os próprios mecanismos JS armazenam os dois de maneira diferente.

As propriedades podem ser armazenadas em um objeto de matriz, mas isso simplesmente demonstra como o JavaScript insiste em tornar tudo um objeto. Os valores indexados em uma matriz são armazenados de maneira diferente de quaisquer propriedades que você decida definir no objeto da matriz que representa os dados da matriz subjacente.

Sempre que você estiver usando um objeto de array legítimo e usando um dos métodos padrão de manipulação desse array, você atingirá os dados de array subjacentes. Especificamente no V8, eles são essencialmente iguais a uma matriz C ++, portanto, essas regras se aplicam. Se, por algum motivo, você estiver trabalhando com um array que o motor não consegue determinar com confiança é um array, então você está em um terreno muito mais instável. Com as versões recentes do V8, há mais espaço para trabalhar. Por exemplo, é possível criar uma classe que tenha Array.prototype como seu protótipo e ainda obter acesso eficiente aos vários métodos de manipulação de matriz nativa. Mas esta é uma mudança recente.

Links específicos para mudanças recentes na manipulação de array podem ser úteis aqui:

• 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 um pouco a mais, aqui estão Array Pop e Array Push diretamente do código-fonte do V8, ambos implementados no próprio 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;
}

Eu gostaria de complementar as respostas existentes com uma investigação para a questão de como as implementações se comportam em relação a matrizes crescentes: Se eles implementarem da maneira "usual", veríamos muitos pushes rápidos com pushes lentos raros intercalados em que ponto a implementação copia a representação interna da matriz de um buffer para um maior.

Você pode ver esse efeito muito bem, isso é do 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

Mesmo que cada push tenha o perfil definido, a saída contém apenas aqueles que levam tempo acima de um determinado limite. Para cada teste, personalize o limite para excluir todos os envios que parecem representar os envios rápidos.

Assim, o primeiro número representa qual elemento foi inserido (a primeira linha é para o 17º elemento), o segundo é quanto tempo levou (para muitos arrays o benchmark é feito em paralelo), e o último valor é a divisão do primeiro número por aquele da linha anterior.

Todas as linhas com menos de 2 ms de tempo de execução são excluídas do Chrome.

Você pode ver que o Chrome aumenta o tamanho do array em potências de 1,5, mais algum deslocamento para compensar os pequenos arrays.

Para o Firefox, é um poder de dois:

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

Tive que aumentar um pouco o limite no Firefox, é por isso que começamos em # 126.

Com o IE, temos uma combinação:

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

É uma potência de dois no início e depois passa para potências de cinco terços.

Portanto, todas as implementações comuns usam o caminho "normal" para matrizes (em vez de enlouquecer com cordas , por exemplo).

Aqui está o código de referência e aqui está o violão em 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;
    }
}

Durante a execução em node.js 0.10 (construído em v8), eu estava vendo o uso da CPU que parecia excessivo para a carga de trabalho. Eu localizei um problema de desempenho em uma função que estava verificando a existência de uma string em um array. Então, fiz alguns testes.

• carregou 90.822 hosts
• carregar a configuração levou 0,087 segundos (matriz)
• carregar a configuração levou 0,152 segundos (objeto)

Carregar 91k entradas em uma matriz (com validar e empurrar) é mais rápido do que definir obj [chave] = valor.

No próximo teste, pesquisei cada nome de host na lista uma vez (91k iterações, para calcular a média do tempo de pesquisa):

• a pesquisa de configuração levou 87,56 segundos (matriz)
• a pesquisa de configuração levou 0,21 segundos (objeto)

O aplicativo aqui é Haraka (um servidor SMTP) e carrega o host_list uma vez na inicialização (e após as alterações) e, subsequentemente, executa essa pesquisa milhões de vezes durante a operação. Mudar para um objeto foi uma grande vitória de desempenho.