Какие массивы смоделированы как внутренние так быстро или что я делаю не так?

Question

Я сел и провел некоторую оптимизацию перфоманса в моей служебной библиотеке: goodcore , когда заметил что-то неожиданное: Array.indexOf (в узле 10.9) быстро выполняет поиск CRAZY, но не всегда O (1).

Вот распечатка части тестов, которая находит средний элемент в массиве целых 10 КБ на моем ноутбуке.

    Array::indexOf x 828,360,306 ops/sec ±1.25% (87 runs sampled)
    Arr.indexOfElement x 133,620,554 ops/sec ±0.87% (86 runs sampled)
    Arr.indexOfElement (no native) x 172,043 ops/sec ±0.92% (92 runs sampled)
    _.indexOf x 174,273 ops/sec ±0.87% (95 runs sampled)
Fastest is Array::indexOf

800 миллионов indexOf в секунду - это БЫСТРО!

Делая массив меньше (200 записей), он остается на том же номере. Увеличение массива до 1000 КБ замедляет его до 1582 операций в секунду

Так что, может быть, он держит хэш-карту за кадром, но не расширяет пространство поиска ключа за пределами некоторого числа, а затем получает линейный поиск? Кто-нибудь знает, так ли это и какой номер?

А может, я что-то не так сделал в своем коде:

const SIZE = 10000;
let intArray10k = MocData.numericArray(SIZE, MocDataType.RandomInt, 0, 100000);
let intArray100 = MocData.numericArray(100, MocDataType.RandomInt, 0, 100000);
intArray10k[SIZE/2 - 1] = -1;

function complete(suite: Benchmark.Suite) {
    console.log(chalk.green('Fastest is ' + (suite.filter('fastest') as any).map('name') + "\n"));
}
function cycle(event: any) {
    console.log(chalk.grey("\t" + String(event.target)));
}
export const suites = [ 
    new Benchmark.Suite()
    .add('Array::indexOf', function () {
        intArray10k.indexOf(-1);
    })
    .add('Arr.indexOfElement', function () {
        Arr.indexOfElement(intArray10k, -1);
    })
    .add('Arr.indexOfElement (no native)', function () {
        Test.Env.forceNotNative = true;
        Arr.indexOfElement(intArray10k, -1);
        Test.Env.forceNotNative = false;
    })
    .add('_.indexOf', function () {
        _.indexOf(intArray10k, -1);
    })
    // add listeners
    .on('cycle', function (event: any) {
        cycle(event);
    })
    .on('complete', function () {
        complete(this);
    }),

РЕДАКТИРОВАТЬ : Спасибо @jmrk за помощь в назначении значения, чтобы избежать его оптимизации. Теперь времена выглядят намного более разумными без 100-метровых значений К вашему сведению, высокое значение сплайсинга связано с тем, что я склеиваю и добавляю такое же количество значений, чтобы размер массива оставался. Кажется, что функция сплайсинга не выполняет эту оптимизацию.

    Array::indexOf x 162,893 ops/sec ±2.05% (87 runs sampled)
    Arr.indexOfElement x 171,492 ops/sec ±0.82% (91 runs sampled)
    Arr.indexOfElement (no native) x 165,929 ops/sec ±1.07% (91 runs sampled)
    _.indexOf x 169,678 ops/sec ±0.84% (92 runs sampled)

Самый быстрый - Arr.indexOfElement

    Array::slice x 130,022 ops/sec ±1.02% (91 runs sampled)
    Arr.slice x 131,115 ops/sec ±0.94% (91 runs sampled)
    Arr.shallowCopy x 130,130 ops/sec ±1.29% (89 runs sampled)
    Arr.slice (no native) x 52,057 ops/sec ±0.96% (91 runs sampled)
    Arr.shallowCopy (no native) x 59,676 ops/sec ±0.90% (92 runs sampled)
    _.slice x 60,078 ops/sec ±1.08% (94 runs sampled)

Самым быстрым является Arr.slice, Array :: slice, Arr.shallowCopy

    Array::reverse x 18,420 ops/sec ±1.18% (90 runs sampled)
    Arr.reverse x 133,600 ops/sec ±0.74% (92 runs sampled)
    _.reverse x 18,075 ops/sec ±1.83% (85 runs sampled)

Самый быстрый - обратный.

    Array::filter x 7,749 ops/sec ±10.31% (88 runs sampled)
    Arr.filter x 11,752 ops/sec ±6.92% (88 runs sampled)
    _.filter x 5,939 ops/sec ±0.64% (93 runs sampled)

Самый быстрый - Arr.filter

    Array::forEach x 42,613 ops/sec ±34.98% (87 runs sampled)
    Arr.forEach x 126,806 ops/sec ±23.89% (91 runs sampled)
    _.forEach x 11,489 ops/sec ±1.23% (88 runs sampled)

Самый быстрый - Arr.forEach

    Array::map x 17,592 ops/sec ±18.32% (88 runs sampled)
    Arr.map x 39,564 ops/sec ±14.55% (88 runs sampled)
    _.map x 8,419 ops/sec ±1.34% (87 runs sampled)

Самый быстрый - Arr.map

    Array::reduce x 29,784 ops/sec ±29.35% (88 runs sampled)
    Arr.reduce x 63,781 ops/sec ±18.30% (86 runs sampled)
    _.reduce x 9,444 ops/sec ±2.25% (88 runs sampled)

Самый быстрый - Arr.reduce

    Array::splice x 914,209 ops/sec ±1.42% (90 runs sampled)
    Arr.splice x 4,777,243 ops/sec ±0.78% (91 runs sampled)
    Arr.splice (no native) x 5,111,231 ops/sec ±0.90% (88 runs sampled)

Самым быстрым является Arr.splice (без нативного)

    Array::splice(1) x 281,206 ops/sec ±10.53% (30 runs sampled)
    Arr.removeAt x 256,947 ops/sec ±1.23% (92 runs sampled)
    Arr.removeAt (no native) x 110,562 ops/sec ±1.03% (91 runs sampled)

Самым быстрым является массив :: splice (1), Arr.removeAt

    Array::find x 124,197 ops/sec ±32.06% (90 runs sampled)
    Arr.find x 159,169 ops/sec ±9.55% (92 runs sampled)
    _.find x 23,077 ops/sec ±1.12% (88 runs sampled)

Самый быстрый - Arr.find

Answer 1

V8 разработчик здесь. Когда вы видите сотни миллионов операций в секунду, это обычно означает, что оптимизирующий компилятор отбросил тестовый код, и все, что вы измеряете, это пустой цикл. Вы можете использовать флаг командной строки --print-opt-code для проверки. Обходное решение, которое часто работает, - это присвоение результата глобальной переменной, например:

var result;
function easily_misleading_microbenchmark() {
  result = intArray10k.indexOf(-1);
}
for (var i = 0; i < 1e6; i++) {
  easily_misleading_microbenchmark();
}

чтобы обмануть компилятор, думая, что результат используется для чего-то.

Остерегайтесь микробенчмарков, так как они легко могут ввести вас в заблуждение, чтобы сделать неправильные выводы! : -)

В общем, ожидайте, что Array.indexOf(value) будет иметь сложность O (n) для массива с n элементами. Это никогда не O (1). (Если ваш результат измерения O (1), то все, что вы измеряете, не Array.indexOf().)