H2H: For-loop search vs the .indexOf() method

Searching for a specific element in an array is a common task in programming. Two popular methods for searching arrays in JavaScript are iterating over each element using a for loop and Array.prototype.indexOf(). The former is a simple search algorithm that checks each element in an array sequentially until the target value is found while Array.prototype.indexOf(), still a linear search function, is a built-in JavaScript method that searches for a target value in an array and returns its index if found, or -1 if not found.

In this article, I document my journey of attempting to comprehend the performance discrepancies between the two approaches, the extent of the variation, and above all, the underlying reasons for these differences.

The tests

To test the performance of these two methods, I wrote a simple benchmark script that records the running times of each search method over multiple random-number arrays of varying lengths. The script then calculates the average time taken for each function on each array size.

It's worth noting that these tests specifically measure the worst-case scenario, where the target element is either non-existent or located at the tail end of the array. In situations where the target is at the beginning of the array, both functions perform almost equally and maintain consistent performance across different array sizes. Additionally, when the target is somewhere within the array, the performance of both functions scales proportionally to their respective worst-case times.

Let's break down the code into sections:

Setting up the parameters: We first define

1. ARR_SIZES - the array lengths we want to test,

2. K_TIMES - the number of times we want to run each function,

3. TARGET - target value we are searching for in the array.

I chose a high K_TIMES value to account for the fact that there will be some variance between each test's performance time.

let ARR_SIZES = [1,10,100,1000,10_000,100_000,1_000_000,10_000_000,100_000_000];
let K_TIMES = 10000;
let TARGET = 999_999_999_999;
let results = {};

Generating the test array: We define a function to generate a new array of random numbers for each test run. The array is of length arrSize.

let generateArray = (arrSize) => {
    // reset the array for each test
    let array = [];
    // populate the array with random nums
    for(let i=0; i<arrSize; i++) {
        array.push(Math.floor(Math.random()*1_000_000))
    }
    return array;
}

The search methods: We define the two search methods we want to test: for-loop search and Array.prototype.indexOf().

 let loopFind = (array, target) => {
    const length = array.length;
    // loop through the array until the value is found
    for(let i=0; i<length; i++) {
        if(array[i] === target){ 
            return i
        }
    }
    return -1;
}

let indexOfFind = (array, target) => {
    return array.indexOf(target)
}

Running the tests: We define a function testRun to run each search function K_TIMES times on the test array, record the time taken for each run and calculate the average time taken for each function for that specific array size.

let testRun = (testName, testFunction, arraySize) => {
    // generate a new array for each test
    let array = generateArray(arraySize);

    // run the test K_TIMES times and record the 
    // time taken for each run in the results object
    let i = K_TIMES
    while (i--) {

        // The fun part
        // performance.now() returns a high-precision timestamp down to 1/1000th of a millisecond
        let startTime = performance.now();
        testFunction(array, TARGET);
        let endTime = performance.now();

        // create a new array if the test name is not in the results
        if(!results[testName]) {
            results[testName] = [];
        }
        // push the time taken (milliseconds) to the results
        results[testName].push(endTime-startTime);
    }

    // calculate the average time taken for the test
    let avg = results[testName].reduce((a,b) => a+b)/K_TIMES;

    if(!results['avgs']) { 
        results['avgs'] = {}
    }
    results['avgs'][testName] = Number(avg.toFixed(4));
}

Loop over all the array sizes and call the test runner with the function to be tested alongside all the necessary values it will need.

ARR_SIZES.forEach((arrSize) => {
    testRun('loopFind', loopFind, arrSize);
    testRun('indexOf', indexOfFind, arrSize);
});

Test results

Here are the test results:

Looking at the results, we can see that for small arrays with up to 100 elements, both loopFind() and indexOfFind() have similar performance, with both methods taking less than 1 microsecond to complete the search.

However, for larger arrays, loopFind() starts to perform better than indexOfFind(). For example, past 10,000 elements, loopFind() performs up to twice as fast as indexOfFind(). This indicates that as the size of the array increases, loopFind() becomes more efficient than indexOfFind().

Why?

There could be a ton of reasons why there is a significant contrast between the two on various occasions. One of them is how Array.prototype.indexOf() is implemented in various javascript engines.

The guidelines for how various functions are implemented are outlined by Ecma International in a specification known as ECMAScript. If you're interested in the details of the Array.prototype.indexOf() spec, check out Array.Prototype.indexof(). The function has multiple steps which I'll roughly summarise as follows:

1. Casting the array to an object. This is common in many methods of Array.prototype, including Array.prototype.indexOf(). This ensures that the functions can handle array-like objects, which are simply objects with indexed properties and a length property e.g., HTMLCollections, NodeLists, strings, the arguments object etc.

2. Initializing all the necessary state variables. These variables include the current index of the search, the target value, and a Boolean flag to indicate whether the target value has been found.

3. Looping through the object's keys while testing whether the key's value is equal to the target is the core of the function. The loop iterates through the object's keys, and for each key, the function checks whether the key's value is equal to the target value. If the key's value is equal to the target value, the function returns the key. If the key's value is not equal to the target value, the function continues looping.

Although the extra steps are necessary to handle different types of objects consistently, they add overhead to what may seem like a simple search algorithm and have a compounding effect on the performance of the function.

Moreover, the implementation of JavaScript's built-in functions and objects varies across JavaScript engines or runtimes, with each engine employing different optimization techniques. This can result in potential slight differences in overall performance across different environments.

If you're interested in where the devil is at, here are links to where you can find the source code of some popular JavaScript engines:

• V8: https://github.com/v8/v8.

• SpiderMonkey: https://searchfox.org/mozilla-central/source/js.

• JavaScriptCore: https://github.com/WebKit/WebKit/tree/main/Source/JavaScriptCore

Verdict

When considering the choice between iterating over each element using a for loop and the built-in indexOf method for your solution, here are some considerations:

Code Simplicity

indexOf is a built-in method in JavaScript, so it follows established conventions and is widely understood by developers. Using indexOf can make your code more readable and easier to understand by other programmers. If the performance difference is not critical or the code readability is more important, I recommend using the built-in indexOf.

Array Length

For small arrays, the performance difference between the two is negligible. Both methods can be used interchangeably without significant impact. However, as the array size grows larger, iterating over each element tends to outperform indexOf in the worst-case scenario.

Final

It's important to note that the choice between the two can be subjective and depends on the specific context and requirements of your problem. It's always good to perform benchmark tests in your target environment to evaluate the actual performance and make an informed decision.