google / google/closure-compiler
[request] expand simple reductions into loops
- 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
Assessment
This issue has not been assessed yet.