Praca z tablicami w V8 (emisja wydajność)

Question

próbowałem następny kod (to pokazuje podobne rezultaty 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 

również prowadzona 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 Firefox wszystko wygląda dobrze w pierwszym wariancie:

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

Co dzieje się w V8?

UPD * magicznie zmniejszając 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 

Answer 1

Jeśli przydzielenia, nie używaj .push ponieważ będzie stworzyć rzadki tablicę poparte hashtable. You can preallocate sparse arrays up to 99999 elements, które będą wspierane przez tablicę C, po której jest tablica haszująca.

W drugiej tablicy dodaje się elementy w sposób ciągły, począwszy od 0, więc będzie on wspierany przez prawdziwą tablicę C, a nie tablicę skrótów.

Tak z grubsza:

Jeśli indeksy tablicy przejść ładnie od 0 do długości 1, bez dziur, to może być reprezentowany przez fast C tablicy. Jeśli masz w swoich tablicach otwory , będzie reprezentowana przez znacznie wolniejszą tabelę skrótów. Wyjątkiem jest to, że jeśli przydzielenia tablicę wielkości < 100000, wtedy można mieć otwory w tablicy i wciąż wspierany przez C tablicy:

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 

Answer 2

Jak już zapewne wiecie, jeśli przydzielenia tablica z> 10000 elementami w Chrome lub Node (lub bardziej ogólnie, w V8), wracają do trybu słownika, co sprawia, że ​​rzeczy wolą wolne.

Dzięki niektórym komentarzom w tym wątku udało mi się śledzić rzeczy do object.h's kInitialMaxFastElementArray.

Następnie wykorzystałem tę informację do file an issue in the v8 repository, która teraz zaczyna nabierać trakcji, ale to jeszcze trochę potrwa. I cytuję:

Mam nadzieję, że uda nam się w końcu wykonać tę pracę. Ale nadal jest to prawdopodobnie z dala.