Background

Recently I have been reading about the extra performance you gain when using tail call in recursion with the new tail call optimisation that was added to ES6. I wanted to compare the performance of the native ES6 foreach with a version of foreach that uses the tail call optimisation. While at it I thought why not throw lodash and underscore in the mix just for fun!

Setup

I have created 5 foreach functions for each version and I have used benchmark to test the result. Here is the spec where I ran this test

• OS: Ubuntu 16.04.2 LTS
• CPU: AMD A10-7300 Radeon R6, 10 Compute Cores 4C+6G
• RAM: 8GB

Running the Script

Clone the repo and cd in the directory then run

npm run start

The Script

I am dividing the script into 4 chunks so it is easier to reason about.

Prepare the scene

Here I am importing the bits I need and creating a dummy array which will be used by each function. I am also printing the total items in the array so you can tell which method is faster compared to the number of items in the array. Note that this number can be passed as a parameter.

import * as randomstring from 'randomstring';
import * as benchmark from 'benchmark';
import * as lodash from 'lodash';
import * as underscore from 'underscore';

const totalItems = +process.argv[2] || 10000;
var suite = new benchmark.Suite;

let dummyArray = [];
for (let i = 0; i < totalItems; i++) {
    dummyArray.push(randomstring.generate(20));
}

console.log(`Total items in the array: ${totalItems}`);

The foreach functions

The setup is simple for every function. Just loop through the items and assign each item to a local variable itemPlaceholder. Note that there are 2 versions when using tail recursion foreach, one with a callback and one without. The original implementation for the foreach tail recursion was taken from here. Here is a description for each function.

• es6Foreach: Native ES6 foreach
• tailForeachWithCallback: tail recursion with a callback
• tailForeach: tail recursion
• lodashForeach: foreach using loadash forEach function
• underscoreForEach: foreach using underscore each function

The reason I created tail recursion with and without callback is simple: If you are going to use the tail recursion you will need to grab the item or you will end up creating a tail recursion every time you want to create a foreach. The last scenario may make sense in extreme cases as you will see in the test results.

function es6Foreach(arr: string[]) {
    let itemPlaceholder;
    for (let item of arr) {
        itemPlaceholder = item;
    }
}

function tailForeachWithCallback(arr, callback, start = 0) {
    if (0 <= start && start < arr.length) {
        callback(arr[start], start, arr);
        return tailForeachWithCallback(arr, callback, start + 1);
    }
}

function tailForeach(arr, start = 0) {
    let itemPlaceholder;
    if (0 <= start && start < arr.length) {
        itemPlaceholder = arr[start];
        return tailForeach(arr, start + 1);
    }
}

function lodashForeach(arr) {
    let itemPlaceholder;
    lodash.forEach(dummyArray, function (item) {
        itemPlaceholder = item;
    });
}

function underscoreForEach(arr) {
    let itemPlaceholder;
    underscore.each(dummyArray, function (item) {
        itemPlaceholder = item;
    });
}

Benchmark setup

Nothing special here. I am just adding what I want benchmark to test so 5 functions. The name of the function is the first argument to the add method. The actual function call is in the arrow function which is passed as a second argument to the add function.

suite.add('es6Foreach', () => {
    es6Foreach(dummyArray);
})
    .add('tailForeach', () =>  {
        tailForeach(dummyArray);
    })
    .add('tailForeachWithCallback', () =>  {
        let itemPlaceholder;
        tailForeachWithCallback(dummyArray, (arrItem, index, actualArray) => { itemPlaceholder = arrItem; });
    })
    .add('underscoreForEach', () => {
        underscoreForEach(dummyArray);
    })
    .add('lodashForEach', () => {
        lodashForeach(dummyArray);
    })    
    .on('cycle', (event) => {
        console.log(String(event.target));
    })
    .on('complete', function () {
        console.log('Fastest is ' + this.filter('fastest').map('name'));
    })
    .run({ 'async': true });

The results

Total items: 10,000

Total items in the array: 10000
es6Foreach x 1,367 ops/sec ±2.94% (79 runs sampled)
tailForeach x 4,860 ops/sec ±1.95% (77 runs sampled)
tailForeachWithCallback x 2,499 ops/sec ±3.34% (72 runs sampled)
underscoreForEach x 3,366 ops/sec ±2.29% (78 runs sampled)
lodashForEach x 3,223 ops/sec ±1.40% (78 runs sampled)
Fastest is tailForeach

Total items: 1,000

Total items in the array: 1000
es6Foreach x 13,263 ops/sec ±3.15% (75 runs sampled)
tailForeach x 52,009 ops/sec ±1.13% (80 runs sampled)
tailForeachWithCallback x 26,979 ops/sec ±2.08% (81 runs sampled)
underscoreForEach x 33,730 ops/sec ±2.83% (77 runs sampled)
lodashForEach x 32,377 ops/sec ±1.72% (80 runs sampled)
Fastest is tailForeach

Total items: 100

Total items in the array: 100
es6Foreach x 135,498 ops/sec ±0.48% (76 runs sampled)
tailForeach x 670,924 ops/sec ±0.30% (81 runs sampled)
tailForeachWithCallback x 276,847 ops/sec ±4.08% (72 runs sampled)
underscoreForEach x 320,132 ops/sec ±2.88% (76 runs sampled)
lodashForEach x 289,314 ops/sec ±3.02% (73 runs sampled)
Fastest is tailForeach

Total items: 10

Total items in the array: 10
es6Foreach x 964,557 ops/sec ±2.75% (79 runs sampled)
tailForeach x 5,950,644 ops/sec ±0.42% (78 runs sampled)
tailForeachWithCallback x 1,964,577 ops/sec ±7.74% (67 runs sampled)
underscoreForEach x 1,975,446 ops/sec ±3.17% (79 runs sampled)
lodashForEach x 1,842,895 ops/sec ±2.29% (76 runs sampled)
Fastest is tailForeach

OK so use tail recursion all the way? not really!

Few notes on the benchmark test output. The higher the number of operations per second (ops/sec) the better performance the function is. With that out of the way let's analyse these numbers.

From the result above clearley using the tail rescursion (without callback) is the fastest by far. However remember that this is the one without a callback. If you check the tail recursion that is with a callback you will notice that underscore outperformed it by far. The reason why you don't wan't to use the non callback version is simple: code reuse. If you wan't the ultimate performance then you will need to create a tail recursion function everytime you want a foreach. That can be cumbersome and time consuming. However there is a case for it, for example if you have to loop through a large number of items (10,000+) for reasons beyond my knowledge then definitley it is an option worth considering. Here is a summary of the findings.

Putting the tail call without a callback option aside, here is what this test tells us:

• For small number of items like 10 then the tail recursion with callback and lodash scored the best performance
• For miduim to large number of items in an array like 100 to 10,000 then underscore performed the best.
• Never use the ES6 foreach because it has the worst performance compared to the others in this test.

Conclusion

In this blog post I compared the performance of running foreach function in 5 different ways. Nameley ES6 foreach, tail recursion foreach (without a callback), tail recursion foreach (with a callback), underscore each and lodash each. I have used benchmark to compare the performance of each method.