[request] expand simple reductions into loops

[alexchandel]

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.

[MatrixFrog]

Is this true for other array methods as well? Is there a gain from changing a forEach or map to a for loop? I suspect there is in some cases (at the cost of a slightly higher code size) but I haven't done any measurements myself.

[alexchandel]

A simple implementation of map with a for loop is indeed slightly faster than Array.map (59% for me), though not nearly as fast as with reduce: http://jsben.ch/DRAFz.

reduce, especially with an inline-able predicate, is probably where this optimization would be worth the most.

[concavelenz]

For V8 at least, the Array methods are being replaced with more optimizable versions. The linked jsben.ch how shows "map" being faster.

[brad4d]

Created Google internal issue b/119639281