Description
A common, functional way to count the number of occurrences (or the number of elements that satisfy a certain predicate) in an array is to use the reduce
method like so:
var total = array.reduce((a, e) => a + (e === 7), 0)
This might be abstracted into a function, like:
/**
* @param {Array<*>} array
* @param {function(*): boolean} predicate
* @return {boolean}
*/
function count (array, predicate) {
return array.reduce((a, e) => a + predicate(e), 0)
}
All good and readable. The problem is this is about 6-7 times slower than a loop when both are fully inlined (tested in jsbench):
/**
* @param {Array<*>} array
* @param {function(*): boolean} predicate
* @return {boolean}
*/
function count (array, predicate) {
var total = 0
for ( var i = array.length; i--; ) {
total += predicate(array[i])
}
return total
}
The performance advantage falls to about 2-3:1 if the predicate can't be inlined at compile time. This would seem to make Array.prototype.reduce
a prime candidate for optimization, when its predicate in known at compile time.
Optimization pattern:
Any reduction of the form:
result = array.reduce(nonDeletingCombination), initial)
can be transformed into:
var result = initial
for (let i = array.length, m = array.length - 1; i--; ) {
result = nonDeletingCombination(result, array[m - i])
}
without loss of generality for a 6x speed boost. The only requirement for preserving reduce
's behavior is that nonDeletingCombination
not delete elements from the array, as this would result in undefined
being passed to it rather than early termination. Such cases can be optimized instead to:
var result = initial
for (let i = 0; i < array.length; i++) {
result = anyCombination(result, array[i])
}
If nonDeletingCombination(accumulator, element)
is of the form nonDeletingCombination(accumulator, predicate(element))
then the binary assignment operator could be inserted as well.