google / google/closure-compiler

[request] expand simple reductions into loops

Open
#2,828 4 comments 0 reactions 0 assignees View on GitHub
enhancement P3 triage-done
Dominant language
JavaScript
Stars
7.7k
Forks
1.2k
Avg merge
2d 12h
Merged PRs (30d)
6

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:

```js
var total = array.reduce((a, e) => a + (e === 7), 0)
```

This might be abstracted into a function, like:
```js
/**
* @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):
```js
/**
* @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:

```js
result = array.reduce(nonDeletingCombination), initial)
```

can be transformed into:

```js
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:

```js
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.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.