Praca z tablicami w wersji V8 (problem z wydajnością)

Wypróbowałem następny kod (pokazuje podobne wyniki w Google Chrome i 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

Przeprowadziłem też kolejne testy: 

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

Ale w Firefoksie wszystko wygląda dobrze z pierwszym wariantem: 

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

Co się dzieje w V8?

UPD * magicznie zmniejszająca się wydajność *

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

W przypadku prealokacji nie używaj .push, ponieważ utworzysz rzadką tablicę wspieraną przez hashtable. możesz prealokować rzadkie tablice do 99999 elementów , które będą wspierane przez tablicę C, po czym będzie to hashtable.

Z drugą tablicą dodajesz elementy w sposób ciągły zaczynając od 0, więc będzie ona wspierana przez prawdziwą tablicę C, a nie tabelę hash.

Tak z grubsza:

Jeśli indeksy tablicy idą od 0 do długości-1, bez dziur, to może być reprezentowana przez szybką tablicę C. Jeśli masz dziury w tablicy, wtedy będzie ona reprezentowana przez znacznie wolniejszą tabelę hash. Wyjątkiem jest to, że jeśli wstępnie ustawisz tablicę rozmiar 

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/doraprojects.net/template/agent.layouts/content.php on line 54
2013-06-25 02:47:24

Jak zapewne już wiesz, jeśli wstępnie przydzielisz tablicę z > 10000 elementów w Chrome lub Node (lub bardziej ogólnie, W V8), wrócą one do trybu słownikowego, co spowolni Uber.

Dzięki niektórym komentarzom w tym wątku udało mi się wyśledzić wszystko do obiektu.h ' S kInitialMaxFastElementArray .

Następnie użyłem tej informacji, aby zgłosić problem w repozytorium v8 , który zaczyna teraz nabierać przyczepności, ale nadal zajmie to while. Cytuję:

Mam nadzieję, że w końcu uda nam się wykonać tę pracę. Ale to wciąż pewnie daleko stąd.

 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/doraprojects.net/template/agent.layouts/content.php on line 54
2014-11-04 14:18:32