Qual è la performance di Objects / Arrays in JavaScript? (in particolare per Google V8)

Le prestazioni associate a matrici e oggetti in JavaScript (in particolare Google V8) sarebbero molto interessanti da documentare. Non trovo alcun articolo completo su questo argomento da nessuna parte su Internet.

Capisco che alcuni oggetti usano le classi come struttura dati sottostante. Se ci sono molte proprietà, a volte è trattata come una tabella hash?

Capisco anche che gli array sono a volte trattati come array C ++ (cioè indicizzazione casuale veloce, cancellazione lenta e ridimensionamento). E, altre volte, sono trattati più come oggetti (indicizzazione veloce, inserimento / rimozione veloce, più memoria). E, a volte, possono essere archiviati come liste concatenate (es. Indicizzazione casuale lenta, rimozione / inserimento veloce all’inizio / fine)

Qual è la prestazione precisa dei recuperi e delle manipolazioni di Array / Object in JavaScript? (in particolare per Google V8)

Più in particolare, qual è l’impatto sulle prestazioni di:

  • Aggiunta di una proprietà a un object
  • Rimozione di una proprietà da un object
  • Indicizzazione di una proprietà in un object
  • Aggiunta di un elemento a una matrice
  • Rimozione di un elemento da una matrice
  • Indicizzazione di un elemento in una matrice
  • Chiamando Array.pop ()
  • Chiamare Array.push ()
  • Chiamare Array.shift ()
  • Chiamare Array.unshift ()
  • Chiamare Array.slice ()

Qualsiasi articolo o link per maggiori dettagli sarebbe apprezzato, pure. 🙂

EDIT: Mi sto davvero chiedendo come funzionano gli array e gli oggetti JavaScript sotto il cofano. Inoltre, in quale contesto il motore V8 “sa” di “passare” a un’altra struttura dati?

Ad esempio, supponiamo di creare un array con …

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

Cosa sta succedendo davvero qui?

O … che mi dici di questo … ???

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

Per gli array convenzionali, la performance sarebbe terribile; mentre, se è stata utilizzata una lista collegata … non così male.

AGGIORNAMENTO: nota che JSPref è attualmente inattivo

(Ho salvato una copia del test case e aggiornerò la risposta una volta che JSPref è stato corretto / un successore è stato trovato)


Hmm … forse un overkill per la risposta … ma ho creato una suite di test, proprio per esplorare questi problemi (e altro) ( copia archiviata ).

E in questo senso, puoi vedere i problemi di prestazioni in questo tester test 50+ (ci vorrà molto tempo).

Inoltre, come suggerisce il nome, esplora l’utilizzo dell’utilizzo della natura dell’elenco link nativo della struttura DOM.

(Attualmente inattivo, ricostruito in corso) Maggiori dettagli sul mio blog a riguardo .

Il riassunto è come seguito

  • La matrice V8 è veloce, MOLTO VELOCE
  • Il push / pop / shift della matrice è ~ circa 20 volte più veloce di qualsiasi object equivalente.
  • Sorprendentemente Array.shift() è veloce ~ circa 6 volte più lento di un array pop, ma è ~ circa 100 volte più veloce di una cancellazione di attributo object.
  • Divertente, Array.push( data ); è più veloce di Array[nextIndex] = data di quasi 20 (array dinamico) a 10 (array fisso) volte.
  • Array.unshift(data) è più lento come previsto ed è ~ circa 5 volte più lento di una nuova aggiunta di proprietà.
  • Nullare l’ array[index] = null valori array[index] = null è più veloce di cancellarlo delete array[index] (indefinito) in un array di ~ approx 4x ++ più veloce.
  • Sorprendentemente Nullare un valore in un object è obj[attr] = null ~ circa 2 volte più lento del solo cancellare l’attributo delete obj[attr]
  • Non sorprende che il Array.splice(index,0,data) sia lento, molto lento.
  • Sorprendentemente, Array.splice(index,1,data) è stato ottimizzato (nessun cambio di lunghezza) ed è 100 volte più veloce di un semplice splice Array.splice(index,0,data)
  • non sorprendentemente, la divLinkedList è inferiore a un array su tutti i settori, tranne la dll.splice(index,1) (dove ha rotto il sistema di test).
  • GRANDE SORPRESA di tutto ciò [come sottolineato da jjrv], le scritture di array V8 sono leggermente più veloci di V8 reads = O

Nota: queste metriche si applicano solo a grandi array / oggetti che v8 non “ottimizza completamente”. Ci possono essere casi di prestazioni ottimizzati molto isolati per dimensioni di array / object meno di una dimensione arbitraria (24?). Ulteriori dettagli possono essere visti in modo estensivo su diversi video IO di Google.

Nota 2: questi meravigliosi risultati delle prestazioni non sono condivisi tra i browser, in particolare *cough* IE. Anche il test è enorme, quindi devo ancora analizzare e valutare completamente i risultati: per favore modificalo in =)

Nota aggiornata (dic 2012): i rappresentanti di Google hanno video su youtubes che descrivono il funzionamento interno di chrome stesso (come quando passa da un array di liste di collegamenti a un array fisso, ecc.) E su come ottimizzarli. Vedi GDC 2012: da Console a Chrome per ulteriori informazioni.

Nota aggiornata (febbraio 2013): Thx @badunk, per fornire il collegamento video nel punto esatto

Nota aggiornata (giugno 2016): Thx @Benedikt, riguardante la differenza delle prestazioni di spinta dell’array negli array fissi / dinamici.

A un livello base che rimane all’interno dei regni di JavaScript, le proprietà sugli oggetti sono quadro molto più complesse. È ansible creare proprietà con setter / getter, con diverse enumerabilità, scrivibilità e configurabilità. Un articolo in un array non può essere personalizzato in questo modo: esiste o non lo è. Al livello del motore sottostante ciò consente una maggiore ottimizzazione in termini di organizzazione della memoria che rappresenta la struttura.

In termini di identificazione di una matrice da un object (dizionario), i motori JS hanno sempre fatto linee esplicite tra i due. Ecco perché c’è una moltitudine di articoli sui metodi per provare a creare un object semi-falso simile ad Array che si comporta come uno ma consente altre funzionalità. La ragione per cui questa separazione esiste anche perché i motori JS stessi memorizzano i due in modo diverso.

Le proprietà possono essere archiviate su un object array ma ciò dimostra semplicemente come JavaScript insiste nel rendere tutto un object. I valori indicizzati in una matrice vengono memorizzati in modo diverso da qualsiasi proprietà che si decide di impostare sull’object matrice che rappresenta i dati dell’array sottostante.

Ogni volta che si utilizza un object array legittimo e si utilizza uno dei metodi standard di manipolazione di tale array, si verrà colpiti dai dati dell’array sottostante. In V8 in particolare, questi sono essenzialmente gli stessi di un array C ++, quindi queste regole verranno applicate. Se per qualche motivo stai lavorando con un array che il motore non è in grado di determinare con sicurezza è un array, allora sei su un terreno molto più shakier. Con le versioni recenti di V8 c’è però più spazio per lavorare. Ad esempio, è ansible creare una class che ha Array.prototype come prototipo e ottenere comunque un accesso efficiente ai vari metodi di manipolazione degli array nativi. Ma questo è un cambiamento recente.

Link specifici alle recenti modifiche alla manipolazione dell’array possono tornare utili qui:

Come extra, ecco gli array Array Pop e Array Push direttamente dalla sorgente V8, entrambi implementati in JS stesso:

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

Durante l’esecuzione di node.js 0.10 (basato sulla v8) vedevo un utilizzo della CPU eccessivo per il carico di lavoro. Ho rintracciato un problema di prestazioni in una funzione che stava verificando l’esistenza di una stringa in un array. Quindi ho eseguito alcuni test.

  • caricato 90.822 host
  • la configurazione di caricamento ha impiegato 0,087 secondi (array)
  • la configurazione di caricamento ha richiesto 0.152 secondi (object)

Il caricamento di voci 91k in un array (con convalida e push) è più veloce dell’impostazione di obj [chiave] = valore.

Nel test successivo, ho cercato ogni hostname nell’elenco una volta (91k iterazioni, per calcolare la media del tempo di ricerca):

  • la ricerca ha richiesto 87,56 secondi (array)
  • la ricerca della configurazione ha richiesto 0,21 secondi (object)

L’applicazione qui è Haraka (un server SMTP) e carica l’host_list una volta all’avvio (e dopo le modifiche) e successivamente esegue questa ricerca milioni di volte durante l’operazione. Passare a un object è stata una grande vittoria per le prestazioni.

Vorrei integrare le risposte esistenti con un’indagine alla domanda su come si comportano le implementazioni riguardo gli array in crescita: se le implementano nel modo “normale”, si vedrebbero molte spinte veloci con spinte lente rare e intervallate, a quel punto le copie di implementazione la rappresentazione interna dell’array da un buffer ad uno più grande.

Puoi vedere questo effetto molto bene, questo è da 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 

Anche se ogni push è profilato, l’output contiene solo quelli che richiedono un tempo superiore a una determinata soglia. Per ogni test ho personalizzato la soglia per escludere tutti i push che sembrano rappresentare le push veloci.

Quindi il primo numero rappresenta quale elemento è stato inserito (la prima riga è per il 17 ° elemento), il secondo è quanto tempo ci è voluto (per molti array il benchmark è fatto in parallelo), e l’ultimo valore è la divisione del primo numero da quello di quello nella prima riga.

Tutte le linee con tempi di esecuzione inferiori a 2 ms sono escluse per Chrome.

Puoi vedere che Chrome aumenta le dimensioni dell’array con potenze di 1,5, più un po ‘di offset per tenere conto di piccoli array.

Per Firefox, è una potenza di due:

 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 

Ho dovuto mettere un po ‘la soglia in Firefox, ecco perché iniziamo dalla # 126.

Con IE, otteniamo un mix:

 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 

All’inizio è un potere di due e poi passa a poteri di cinque terzi.

Quindi tutte le implementazioni comuni usano il modo “normale” per gli array (invece di impazzire con le corde , per esempio).

Ecco il codice di riferimento e qui è il violino in cui è.

 var arrayCount = 10000; var dynamicArrays = []; for(var j=0;j 10) { console.log(i + ": " + span + "ms" + " " + (i / lastLongI)); lastLongI = i; } }