Search code examples
arraysnode.jsperformancev8

What are arrays modelled as internally to be this fast or what am I doing wrong?

I sat and did some perf optimization on my utility library: goodcore when I noticed something unexpected: Array.indexOf (in node 10.9) does lookups CRAZY fast but is not always O(1).

Here is the printout of a part of tests that finds the middle element in a 10k large integer array on my laptop.

    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 million indexOf per sec is FAST!

By making the array smaller (200 entries) it remains at the same number. Increasing the array to 1000k slows it down to 1582 ops/sec

So it could be it keeps a hashmap behind the scenes but do not expand the key lookup space beyond some number and then gets linear search? Does anyone know if this is the case and what number that is?

Or maybe I did something wrong in my code:

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);
    }),

EDIT: Thanks @jmrk for the heads up on assigning the value to avoid optimizing it away. Now the times look much more reasonable with no 100m values. FYI the high splice value is due to me splicing away and adding the same amount of values so that the array size remains. It seem that the splice function does not do this optimization.

    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)

Fastest is 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)

Fastest is 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)

Fastest is Arr.reverse

    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)

Fastest is 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)

Fastest is 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)

Fastest is 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)

Fastest is 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)

Fastest is Arr.splice (no native)

    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)

Fastest is Array::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)

Fastest is Arr.find

Solution

  • V8 developer here. When you see hundreds of millions of operations per second, then it usually means that the optimizing compiler dropped the test code, and all you're measuring is an empty loop. You can use the command-line flag --print-opt-code to check. A workaround that often works is to assign the result to a global variable, like so:

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

    to fool the compiler into thinking that the result is used for something.

    Beware of microbenchmarks, for they will easily mislead you to drawing the wrong conclusions! :-)

    In general, expect Array.indexOf(value) to have O(n) complexity for an Array with n elements. It is never O(1). (If your measurement result is O(1), then whatever you're measuring is not Array.indexOf().)