Работа с массивами в 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, который теперь начинает приобретать некоторую тягу, но он все равно возьмет в то время как. И я цитирую:
Надеюсь, мы сможем в конце концов выполнить эту работу. Но он все еще вероятно, далеко.