NodeJS array.indexof is orders of magnitude faster than set.has and set.has is orders of magnitude faster than array.indexof !== -1

Question

I know that time complexity kicks in for large inputs, but for any input array.indexof is faster. E.g. for n=20.000, array takes 0.008ms, while set takes 0.4ms

I've tested array vs set using this code:

const NS_PER_SEC = 1e9;
const MS_PER_NS = 1e-6

function runTest(test) {
    let time = process.hrtime();
    test();
    let diff = process.hrtime(time);
    return (diff[0] * NS_PER_SEC + diff[1])  * MS_PER_NS 
}

function makeRandomString() {
    let length = Math.round(Math.random() * 4 + 2);
    let result = '';
    let characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789- ';
    let charactersLength = characters.length;
    for (let i = 0; i < length; i++) {
        result += characters.charAt(Math.floor(Math.random() * charactersLength));
    }
    return result;//Math.floor(Math.random()); //result;
}

function main() {
    let testCases = [10, 100, 200, 500, 1000, 2000, 5000, 10000, 20000, 40000, 100000, 10000000];
    let times = 5000;
    let words = [];
    for (let i = 0; i < times; i++) {
        words.push(makeRandomString());
    }

    for (let tci = 0; tci < testCases.length; tci++) {
        let array = [];
        const items = testCases[tci];
        for (let i = 0; i < items; i++) {
            array.push(makeRandomString());
        }
        console.log('List ' + items);
        for (let i = 0; i < 10; i++) {
            let res = runTest( () => {
                for (let j = 0; j < times; j++) {
                    let tmp = array.indexOf(words[j]);
                }
            });
            console.log(res);
        }
        console.log('Set ' + items);
        let set = new Set(array);
        for (let i = 0; i < 10; i++) {
            let res = runTest(() => {
                for (let j = 0; j < times; j++) {
                    let tmp = set.has(words[j]);
                }
            });
            console.log(res);
        }
    }
}
main();

But by only changing the following line:

                    let tmp = array.indexOf(words[j]);

into:

                    let tmp = array.indexOf(words[j]) !== -1;

I get expected results - e.g. for n=20.000, array takes 333ms, and set 0.4ms.

How can this be? Surely !== -1 can't slowdown the line by orders of magnitude.

Answer 1

I do not agree that Set.has is "orders of magnitude" slower than Array.indexOf. I think there is some kind of V8 code caching mechanism triggering and that's why you see those results.

As I look at your code I see that you are running the same test with the same values for 10 times:

for (let i = 0; i < 10; i++) {
    let res = runTest(() => {
        for (let j = 0; j < times; j++) {
            let tmp = array.indexOf(words[j]);
        }
    });
    console.log(res);
}

I am not sure that your tests are correctly done. When I tweak your script to look like this:

const NS_PER_SEC = 1e9;
const MS_PER_NS = 1e-6

function runTest(test) {
    let time = process.hrtime();
    test();
    let diff = process.hrtime(time);
    return (diff[0] * NS_PER_SEC + diff[1]) * MS_PER_NS
}

function makeRandomString() {
    let length = Math.round(Math.random() * 4 + 2);
    let result = '';
    let characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789- ';
    let charactersLength = characters.length;
    for (let i = 0; i < length; i++) {
        result += characters.charAt(Math.floor(Math.random() * charactersLength));
    }
    return result;
}

function main() {

    let testCases = [100000, 200000, 300000, 400000];
    let times = 5000;
    let testResults = {};

    for (let tci = 0; tci < testCases.length; tci++) {
        let array = [];
        let words = [];
        const items = testCases[tci];

        for (let i = 0; i < times; i++) {
            words.push(makeRandomString());
        }

        for (let i = 0; i < items; i++) {
            array.push(makeRandomString());
        }

        let set = new Set(array);
        let msSetTest = runTest(() => {
            for (let j = 0; j < times; j++) {
                let tmp = set.has(words[j]);
            }
        });

        let msArrayIndexOfTest = runTest(() => {
            for (let j = 0; j < times; j++) {
                let tmp = array.indexOf(words[j]);
            }
        });

        let msArrayIndexOfEqTest = runTest(() => {
            for (let j = 0; j < times; j++) {
                let tmp = array.indexOf(words[j]) !== -1;
            }
        });

        testResults[`${items} items`] = { 'Set.has (ms)': msSetTest, 'Array.indexOf (ms)': msArrayIndexOfTest, 'Array.indexOf !== -1 (ms)': msArrayIndexOfEqTest };
    }

    console.table(testResults);
}

main();

I see the following output:

┌──────────────┬────────────────────┬────────────────────┬───────────────────────────┐
│   (index)    │    Set.has (ms)    │ Array.indexOf (ms) │ Array.indexOf !== -1 (ms) │
├──────────────┼────────────────────┼────────────────────┼───────────────────────────┤
│ 100000 items │ 1.0594569999999999 │    1335.504929     │        1341.52334         │
│ 200000 items │      2.264941      │    2004.631142     │    2931.9868469999997     │
│ 300000 items │ 2.2363969999999997 │      0.851231      │        4597.312417        │
│ 400000 items │      1.05495       │ 5333.842428999999  │        5308.093365        │
└──────────────┴────────────────────┴────────────────────┴───────────────────────────┘

Note the value for 300000 items Array.indexOf is 0.851231 ms the code caching probably took place and when using !== cache was not able to take place.