Readme.md

This benchmark script (functional-bench.js) and the supporting files were written during the development of Underscore's functional branch, in order to assess the performance impact of the code changes. The script runs microbenchmarks across a wide range of Underscore functions, datasets and iteratees, in an attempt to obtain a substantial sample of possible usage scenarios. Still, I believe that performance testing with real-world applications is much more informative, but I publish these scripts anyway so that others can verify my claims and perhaps reuse some of the code.

From early experiments, it became clear that running the entire script at once gives less reliable (and more extreme) results than just running small portions of it. This might be due to garbage collection kicking in during longer runs. Running small portions is also much faster if the aim is to compare multiple commits in quick succession. For these reasons, I recommend that you comment out portions of the benchmark script in order to restrict it to a particular combination of data, iteratee and function. This can be done as follows.

• In benchData on lines 15-34, pick two sizes of a single data type and comment out everything else. For example, the following edit will run your chosen function and iteratee only with tiny and large numeric arrays. I recommend picking two sizes, because the smaller size (which runs first) will help to ensure that the iteratee and the function have already entered the hot path of the optimizer by the time the larger size is tested.

var benchData = {
    numArray: {
        tiny: tinyArray,
        // small: smallArray,
        // medium: mediumArray,
        large: largeArray
    },
    objArray: {
        // tiny: _.map(tinyArray, asObject),
        // small: _.map(smallArray, asObject),
        // medium: _.map(mediumArray, asObject),
        // large: _.map(largeArray, asObject)
    },
    objObject: {
        // tiny: _.mapObject(tinyArray, asObject),
        // small: _.mapObject(smallArray, asObject),
        // medium: _.mapObject(mediumArray, asObject)
        // No "large" (huge) object, because that's a bit unrealistic.
    }
};

• In iteratees on lines 37-48, comment out all iteratees except for one or two. Note that you need numberCallback in order to test _.times.
• The functions array on lines 80-84 and the nameless object on lines 159-166 together contain all functions that can be tested. Comment out all of them except for one.
• Unless you're testing _.flatten, you can optionally comment out line 157 (var chunks = runChunk();) in order to save a little bit of time.

Once you have edited functional-bench.js to restrict the combinations of data and functions that will be benchmarked, you're ready to run the benchmark in the engine of your choice. There are two wrappers, functional-bench-node.js for Node.js and functional-bench.html for browsers. The latter will print the results using document.write so you don't have to open the developer console.

During development, I have often found the need to compare test results between a series of commits. To automate this, I used a shell loop of the following general form:

for hash in hash1 hash2 hash3 ... do
    # something with $hash (see below)
done

where hash1 hash2 hash3 ... could for example be 311b04e c22e1e9 5c04427 a930809 ed1851a (commit hashes). In Node.js, something with $hash can be a fully automatic run-save:

git checkout $hash underscore.js && node functional-bench-node.js >$hash-$common_prefix-data-node.csv

$common_prefix is optional and can be anything you choose; I used it to record the chosen combination of function, iteratee and dataset in the filename.

For the browser, a little bit of manual intervention is still needed because I didn't bother to set up WebDriver. In order to keep repetitive manual labour at a minimum, I replaced something with $hash by the following:

echo $hash
git checkout $hash underscore.js && open -a Firefox functional-bench.html
read -sq

in which open -a BrowserName is specific to macOS. On Linux, you might be able to use xdg-open while in the Windows Command Prompt, you can use start. Consult the manual of your platform for details.

The above loop for the browser will pause every time at read -sq, which I inserted specifically for this reason (you'll probably need to replace this by a different command on Windows). This gives the browser the opportunity to finish running the benchmark before the next run is started in a new tab. Your job as human operator is to wait until the benchmark output appears in the current tab, cmd-tab or alt-tab back to your terminal and press enter in order to resume the loop. This repeats until all commits have been tested. At this point, you can visit the browser tabs one by one to collect the results and use the printed list of commit hashes (which will have the same order as the browser tabs) to check which tab goes with which commit.

Once you have collected your results, the remaining step is to compare them between commits and/or browsers. For this, I used the functional-compare.sh script (which, unfortunately, cannot be ported to Windows in a trivial way, but should work in MinGW or Subsytem for Linux). It expects two arguments, being the names of results files. The two files compared in this way must have corresponding data on corresponding lines. For example, if the first file has the combination each, numArray, tiny, numberCallback on line 2, then the same must be true of the second file.

The output of the functional-compare.sh script will tell you how much faster or slower the results in the second file are, compared to the first file. Since the differences can sometimes be extreme, it does this by giving you the binary logarithm of the speed ratio. That means that you have to mentally translate the numbers shown to a speed ratio as follows:

number shown	interpretation
+3	result in second file is 8 times slower than in first file
+2	result in second file is 4 times slower than in first file
+1	result in second file is 2 times slower than in first file
+0	result in second file is equally fast as in first file
-1	result in second file is 2 times faster than in first file
-2	result in second file is 4 times faster than in first file
-3	result in second file is 8 times faster than in first file

etcetera. This basically means that a value greater than +1 is undesirable, while negative values are good news (unless the comparison is going back in time).

You can optionally pipe the output of functional-compare.sh into functional-compare-summary.sh in order to compute the mean and the standard deviation over these binary logarithms. I have also computed medians by piping the output through sort -rn and then inspecting the middle line. With hindsight, however, these aggregate numbers are not terribly useful, because comparisons tend to focus on a particular combination of function, iteratee and dataset.

bench.js

if (typeof require == 'function') {
  var _ = require('./underscore.js');
}

var { now } = _;

// speed is not going to matter if it isn't in a hot loop.
var MIN_ITERATIONS = 3600000;
var MIN_TIME = 1000; // milliseconds
var CHUNK = 1000; // repeat in multiples of this

results = ['Run, Iterations, Elapsed ms, ms/run'];

// Repeat `singleRun` until enough iterations and time have passed,
// then report the performance.
function bench(label, singleRun, singleRunCount) {
  singleRunCount = singleRunCount || 1;
  var batch = Math.max(1, Math.ceil(CHUNK / singleRunCount));
  var iterations = 0;
  var start = now(), passed;
  while (iterations < MIN_ITERATIONS || (passed = now() - start) < MIN_TIME) {
    for (var i = 0; i < batch; ++i) singleRun();
    iterations += batch * singleRunCount;
  }
  results.push([label, iterations, passed, passed / iterations].join(', '));
}

function report() {
  console.log(results.join('\n'));
}

if (typeof exports == 'object') {
  exports.bench = bench;
  exports.report = report;
}

functional-bench-node.js

_ = require('./underscore.js');
_.extend(global, require('./bench.js'));
require('./functional-bench.js');

functional-bench.html

<script src="underscore.js"></script>
<script src="bench.js"></script>
<script>console.log = function(str) {
    document.write(str.replace(/\n/g, '<br>'));
};</script>
<script src="functional-bench.js"></script>

functional-bench.js

// USAGE: pick a particular combination of data, iteratee and function that
// you're interested in, then comment out all other parts of `benchData`,
// `iteratees`, `functions` and the `{chunk, flatten, range, ...}` object in the
// final inner `_.each`. Running the entire benchmark suite in one go seems to
// give less reliable results than just running small portions of it.

// Test data.
var tinyArray = [1];
var smallArray = _.range(-49, 50);
var mediumArray = _.range(-4999, 5000);
var largeArray = _.range(-499999, 500000);

function asObject(number) { return { a: number }; }

var benchData = {
    numArray: {
        tiny: tinyArray,
        small: smallArray,
        medium: mediumArray,
        large: largeArray
    },
    objArray: {
        tiny: _.map(tinyArray, asObject),
        small: _.map(smallArray, asObject),
        medium: _.map(mediumArray, asObject),
        large: _.map(largeArray, asObject)
    },
    objObject: {
        tiny: _.mapObject(tinyArray, asObject),
        small: _.mapObject(smallArray, asObject),
        medium: _.mapObject(mediumArray, asObject)
        // No "large" (huge) object, because that's a bit unrealistic.
    }
};

// Iteratees that may be reused between benchmarks.
var iteratees = {
    identity: undefined,
    property: 'a',
    matches: { a: 0 },
    // One callback is variadic in order to test the impact on optimizeCb.
    numberCallback: function(value) {
        return value > 0;
    },
    objectCallback: function() {
        return arguments.length >= 1 && arguments[0].a > 0;
    }
};

var numberIteratees = _.pick(iteratees, ['identity', 'numberCallback']);
var objectIteratees = _.pick(iteratees, [
    'identity', 'property', 'matches', 'objectCallback'
]);

function numReducer(accumulator, number) {
    return accumulator + number;
}

function objReducer(accumulator, object) {
    return { a: accumulator.a + object.a };
}

// Trivial context to trigger optimizeCb.
var context = {};

// Generate benchmark callbacks for given function, dataset and iteratee.
function runWithIteratee(func, data, iteratee) {
    return function() {
        return func(data, iteratee, context);
    };
}

function runWithTargetAndIteratee(func, data, target, iteratee) {
    return function() {
        return func(data, target, iteratee, context);
    }
}

// Run benchmarks with a wide range of combinations of functions and data.
var functions = [
    'each', 'map', 'reduce', 'find', 'filter', 'sortBy', 'groupBy',
    'sortedIndex', 'indexOf', 'findIndex', 'findKey', 'mapObject',
    'min', 'contains'
];

// These functions only work on arrays.
var arrayFuncs = ['sortedIndex', 'indexOf', 'findIndex'];

// These functions only work on objects.
var objectFuncs = ['findKey', 'mapObject'];

// These functions require a nontrivial iteratee when the collection contains
// objects.
var orderFuncs = ['sortBy', 'sortedIndex', 'min'];

// These functions don't expect any iteratee at all.
var noIteratee = ['indexOf', 'contains'];

// These functions immediately stop iterating on the first element when using
// the identity or property iteratee.
var finders = ['find', 'findIndex', 'findKey'];

_.each(functions, function(funcName) {
    var func = _[funcName];
    _.each(benchData, function(sizes, category) {
        if (category === 'objObject' && _.contains(arrayFuncs, funcName)) return;
        if (category !== 'objObject' && _.contains(objectFuncs, funcName)) return;
        var iters = _.contains(noIteratee, funcName) ? {
            none: undefined
        } : category === 'numArray' ? (
            funcName === 'each' ? _.pick(iteratees, 'numberCallback') :
            funcName === 'reduce' ? { numReducer } :
            numberIteratees
        ) : (
            funcName === 'each' ? _.pick(iteratees, 'objectCallback') :
            funcName === 'reduce' ? { objReducer } :
            _.contains(orderFuncs, funcName) ? _.omit(objectIteratees, 'identity') :
            objectIteratees
        );
        var target = category === 'numArray' ? 0 : { a: 0 };
        _.each(sizes, function(data, sizeLabel) {
            // Estimate the number of smallest operations within an order of
            // magnitude.
            var size = _.size(data);
            if (funcName == 'sortBy') {
                // Median-of-three quicksort.
                size = Math.ceil(size * Math.log(size) / Math.log(1.75));
            } else if (funcName == 'sortedIndex') {
                // Binary search.
                size = Math.ceil(Math.log2(size + 1));
            }
            // Avoid overly long waits.
            if (size > 2e6) return;
            _.each(iters, function(iteratee, iterName) {
                if (
                    (iterName === 'identity' || iterName === 'property') &&
                    sizeLabel !== 'tiny' && _.contains(finders, funcName)
                ) return;
                var label = [funcName, category, sizeLabel, iterName].join(', ');
                var run = (
                    funcName === 'sortedIndex' || funcName === 'indexOf' ||
                    funcName === 'contains' ?
                    runWithTargetAndIteratee(func, data, target, iteratee) :
                    runWithIteratee(func, data, iteratee)
                );
                bench(label, run, size);
            });
        });
    });
});

_.each(benchData.numArray, function(array, sizeLabel) {
    if (sizeLabel == 'tiny') return;
    var size = _.size(array), subSize = Math.floor(Math.sqrt(size));
    var { chunk, flatten, range, sample, times, uniq } = _;
    function runChunk() { return chunk(array, subSize); }
    var chunks = runChunk();
    var cb = iteratees.numberCallback;
    _.each({
        chunk: runChunk,
        flatten: function() { flatten(chunks); },
        range: function() { range(size); },
        sample: function() { sample(array, Math.ceil(size / 2)); },
        times: function() { times(size, cb); },
        uniq: function() { uniq(array); },
    }, function(run, name) {
        // Estimate the number of smallest operations within an order of
        // magnitude.
        var actualSize = size;
        if (name == 'uniq') actualSize = Math.ceil(size * size / 2);
        // Avoid overly long waits.
        if (actualSize > 2e6) return;
        var iterateeLabel = name == 'times' ? 'numberCallback' : 'none';
        var label = [name, 'numArray', sizeLabel, iterateeLabel].join(', ');
        bench(label, run, actualSize);
    });
});

report();

functional-compare-summary.sh

#!/usr/bin/env zsh

awk -F '\s+' 'BEGIN { s = 0; ss = 0 } ; { s += $1 ; ss += $1 * $1 } ; END { printf "count %d, mean %f, stdev %f", NR, s / NR, sqrt(ss / NR) }' $1

functional-compare.sh

#!/usr/bin/env zsh

paste -d , $1 $2 | awk -F ', ?' '$NF < 7 { printf "%+8.3f  %s %s %s %s\n", log($14 / $7) / log(2), $1, $2, $3, $4 }'