Skip to content

[request] expand simple reductions into loops #2828

Open

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Assignees

No one assigned

    Labels

    P3enhancementtriage-doneHas been reviewed by someone on triage rotation.

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions