Работа с массивами в V8 (проблема с производительностью)

Я пробовал следующий код (он показывает похожие результаты в Google Chrome и 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

Я также запустил следующие тесты:

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

Но в Firefox все выглядит отлично с первым вариантом:

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

Что происходит в V8?

UPD * Волшебное снижение производительности *

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

Ответ 1

Если вы предварительно выделите, не используйте .push, потому что вы создадите разреженный массив, поддерживаемый хэш-таблицей. Вы можете предварительно распределить разреженные массивы до 99999 элементов, которые будут поддерживаться массивом C, после чего это хэш-таблица.

Во втором массиве вы добавляете элементы смежным способом, начиная с 0, поэтому он будет поддерживаться реальным массивом C, а не хеш-таблицей.

Так грубо:

Если индексы вашего массива идут хорошо от 0 до Length-1, без отверстий, то он может быть представлен быстрым массивом C. Если у вас есть дыр в вашем массиве, то он будет представлен гораздо более медленной хэш-таблицей. Исключением является то, что если вы предварительно распределите массив от размера < 100000, то вы можете иметь отверстия в массиве и все еще получать массив C:

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

Ответ 2

Как вы, наверное, уже знаете, если вы предварительно выделили массив s > 10000 элементами в Chrome или Node (или, более общо, в V8), они возвращаются в режим словаря, делая вещи uber-slow.

Благодаря некоторым комментариям в этой теме мне удалось отследить все до object.h kInitialMaxFastElementArray.

Затем я использовал эту информацию в файл проблемы в репозитории v8, который теперь начинает приобретать некоторую тягу, но он все равно возьмет в то время как. И я цитирую:

Надеюсь, мы сможем в конце концов выполнить эту работу. Но он все еще вероятно, далеко.