Trabajar con matrices en V8 (problema de rendimiento)

Probé el siguiente código (muestra resultados similares en Google Chrome y nodejs): 

var t = new Array(200000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 27839.499ms
undefined

También hice las siguientes pruebas: 

var t = []; console.time('wtf'); for (var i = 0; i < 400000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 449.948ms
undefined
var t = []; console.time('wtf'); for (var i = 0; i < 400000; ++i) {t.push(undefined);} console.timeEnd('wtf');
wtf: 406.710ms
undefined

Pero en Firefox todo se ve bien con la primera variante:

>>> var t = new Array(200000); console.time('wtf'); ...{t.push(Math.random());} console.timeEnd('wtf');
wtf: 602ms

¿Qué sucede en V8?

UPD * rendimiento mágicamente decreciente*

var t = new Array(99999); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 220.936ms
undefined
var t = new Array(100000); t[99999] = 1; console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1731.641ms
undefined
var t = new Array(100001); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1703.336ms
undefined
var t = new Array(180000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 1725.107ms
undefined
var t = new Array(181000); console.time('wtf'); for (var i = 0; i < 200000; ++i) {t.push(Math.random());} console.timeEnd('wtf');
wtf: 27587.669ms
undefined
Author: yttrium, 2013-06-06
Source

2 answers

Si preasignas, no uses .push porque crearás una matriz dispersa respaldada por una tabla hash. Puede preasignar matrices dispersas hasta 99999 elementos que estarán respaldados por una matriz C, después de eso es una tabla hash.

Con el segundo array está agregando elementos de una manera contigua a partir de 0, por lo que estará respaldado por un array C real, no por una tabla hash.

Así que aproximadamente:

Si los índices de su matriz van bien de 0 a Length-1, sin agujeros, entonces puede ser representado por una matriz C rápida. Si usted tiene agujeros en su matriz, entonces se representará por una tabla hash mucho más lenta. La excepción es que si se pre-asigna un array de tamaño 

var a = new Array(N); 

//If N < 100000, this will not make the array a hashtable:
a[50000] = "sparse";

var b = [] //Or new Array(N), with N >= 100000
//B will be backed by hash table
b[50000] = "Sparse";
//b.push("Sparse"), roughly same as above if you used new Array with N > 0
 56
Author: Esailija,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-06-25 02:47:24

Como probablemente ya sabes, si preasignas un array con > 10000 elementos en Chrome o Node (o más generalmente, en V8), vuelven al modo diccionario, lo que hace que las cosas sean súper lentas.

Gracias a algunos de los comentarios en este hilo, pude rastrear las cosas a object.h's kInitialMaxFastElementArray .

Luego usé esa información para archivar un problema en el repositorio v8 que ahora está empezando a ganar algo de tracción, pero todavía tomará un tiempo mientras. Y cito:

Espero que podamos hacer este trabajo eventualmente. Pero sigue siendo probablemente muy lejos.

 2
Author: Domi,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-11-04 14:18:32