<p><sub>(While I'm referring to JS in my example, I don't intend to be constrained to JS: so any comments/answers concerning <em>FP-style</em> APIs for working with collections for any language are welcome and encouraged)</sub></p>
<p>A couple of years ago <a href="https://stackoverflow.com/a/69097515/159145">I answered an SO question asking</a> how to convert a JS fragment using <code>.map + .filter</code> to one using only <code>.reduce</code>. I initially (and blithely) told them to stick with <code>.map + .filter</code> because there is more potential for an optimizing JS compiler/JIT to generate very efficient machine-code compared to shoving all the logic into a single <code>.reduce</code> call.</p>
<p>...my argument being: assuming that <code>.map</code>'s projector argument and <code>.filter</code>'s predicate argument are pure-functions (or at least are const-correct) then the program becomes <em>embarrassingly parallel</em> and a JS JIT could (for example) generate machine-code using vector-extensions like SIMD/SSE/AVX/etc, and sufficiently large-enough collections could be automatically parallelized using threads.</p>
<p>...</p>
<p>Now flash-forward to about a month ago where I found myself eating my words in that QA when <a href="https://jsperf.app/jeqona/6" rel="noreferrer">a new comment-reply benchmarked various approaches</a> to solving the same problem and my first-choice: <code>.filter().map()</code> turned out to be amongst the slowest implementations (in both <a href="https://imgur.com/z3TL2fq" rel="noreferrer">Chrome 130</a> and <a href="https://imgur.com/AgDiHfA" rel="noreferrer">Firefox 132</a>).</p>
<div class="s-table-container"><table class="s-table">
<thead>
<tr>
<th>Chrome 130</th>
<th>Firefox 132</th>
</tr>
</thead>
<tbody>
<tr>
<td><a href="https://i.sstatic.net/53FuNQ6H.png" rel="noreferrer"><img src="https://i.sstatic.net/53FuNQ6H.png" alt="enter image description here" /></a></td>
<td><a href="https://i.sstatic.net/m0S2W1Ds.png" rel="noreferrer"><img src="https://i.sstatic.net/m0S2W1Ds.png" alt="enter image description here" /></a></td>
</tr>
</tbody>
</table></div>
<p>...I've noticed the same thing in other languages that I'd thought <em>should</em> be able to heavily optimize this pattern (again, provided the predicates/projectors/callbacks are side-effect-free or when the side-effects are discarded) but I've found that benchmarks <em>always</em> show an imperative <code>for</code> loop outperforming FP-style (such as C#'s Linq or <a href="https://stackoverflow.com/questions/43677763/why-is-in-my-case-for-loop-faster-vs-map-reduce-and-list-comprehension">Python</a>), at least until a collection is large enough that <code>Parallel.For</code> wipes the floor with good ol' <code>for</code>.</p>
<hr />
<p>I know the ECMAScript specification is somewhat prescriptive; for example, <a href="https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.map:%7E:text=map%20calls%20callback%20once%20for%20each%20element%20in%20the%20array%2C%20in%20ascending%20order%2C" rel="noreferrer">it states that <code>Array.prototype.map</code> <em>should</em> be implemented by iterating first-to-last through the array/collection</a>, which implies <em>serializability</em> of the program, but &quot;<em>should</em>&quot; is not &quot;<em>must</em>&quot; and I reckon a conforming JS JIT could skirt that requirement for JS programs that have provably pure function callbacks because such a program (with stateless callbacks) would have absolutely no way of observing whether or not array elements were iterated in any particular order or even concurrently.</p>
<p>This pet-theory of mine is based on my actual experiences working on <a href="https://github.com/chakra-core/ChakraCore" rel="noreferrer">the Chakra JS engine</a> when I worked at Microsoft; now, this was almost an entire decade ago, and back then (as now) I wasn't exactly a rockstar JIT architect (and none of my contributions to Chakra made it into any released code, lol ugh) but I know for a fact that the JIT had <em>some</em> ability to analyze the program-tree and prototypes and it definitely could identify &quot;trivial&quot; projectors/predicate callbacks, and while (IIRC) Chakra then didn't yet have FP optimizations it was definitely something that could be implemented if there weren't 1,001+ other things that were higher-priority fixes/improvements at the time.</p>
<hr />
<p>My (hardly thorough) thinking is the JIT could do something like this:</p>
<ol>
<li><p>An <code>Array.prototype.map</code> call-site is encountered, e.g. <code>var m = src.map( e =&gt; e + 1 );</code>.</p>
<ul>
<li>I note that the JIT will still need to produce nonoptimized machine-code for <em>JIT bailout</em> cases (e.g. if an exception/error happens inside an optimized function, e.g. an inlined function won't have a helpful stacktrace)).
<ul>
<li>I should point out that this is how Chakra's JIT worked.</li>
</ul>
</li>
</ul>
</li>
<li><p>The JIT examines the projection callback passed into <code>.map</code> (in this case: <code>function( e ) { return e + 1; }</code>) and is satisfied the callback is a side-effect-free pure-function.</p>
<ul>
<li>I know a general-solution to this is likely impossible, but a nonexhaustive (and very cheap) check using pattern-matching for common known-safe expressions would work for most cases, I imagine.</li>
<li>So callbacks like <code>e =&gt; e + 1</code>, <code>e =&gt; e.simpleField1.simpleField2</code> and <code>e =&gt; e.toString()</code> would all be compatible (and would feature cheap runtime precondition checks to <em>bail-out</em> to less-optimized-but-fully-ECMAScript-compliant code if the runtime detects a modified <code>prototype</code> or other potential for trouble).</li>
</ul>
</li>
<li><p>Then the optimizations could be implemented:</p>
<ul>
<li>For <code>map</code>, at least, the JIT would inline the projection callback into an unrolled loop in its internal intermediate-form before the final machine-code translation step, which I hope would use SIMD instructions.</li>
<li>For <code>filter</code> I can think of a few optimizations cribbed from RDBMS query-plans (even without any indexes, if the size of the input array and the selectivity of the predicate are known then that can inform better allocation and copy strategies), not to mention explicit concurrency with a divide-and-conquer strategy - and that's just off-the-top-of-my-head so I'm confident there exist better techniques out there.</li>
<li>For <code>reduce</code>, if the aggregation function conforms to some set of known-optimizable patterns (e.g. given an <code>Array&lt;T&gt;</code>, a <code>.reduce</code> call passes-in <code>seed: new Set&lt;T&gt;()</code> (i.e. a hashset) and accumulates using <a href="https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/add" rel="noreferrer"><code>Set.prototype.add</code></a> then the JIT could rewrite it as a parallizable <em>merge</em> operation and then compile that as normal.</li>
<li>For <code>.map.filter</code> or <code>.filter.map</code> the JIT could reorder the operations (or interweave them) based on any statistical knowledge the runtime holds about a collection (just like <a href="https://www.postgresql.org/docs/current/sql-createstatistics.html" rel="noreferrer">how RDMBS already do</a>).</li>
</ul>
</li>
<li><p>This optimized machine-code from Step 3 would be wrapped in an error-trap that, in the event of something going wrong, would jumps to a normally optimized machine-code version of the program and retries the failed iteration and will have enough information to, for example, throw a correctly populated <code>Error</code> object.</p>
<ul>
<li><sub>As with my point above about codepaths for <em>JIT bailout</em>, what I'm describing here is already how some JIT compilers, like Chakra's, already work.</sub></li>
</ul>
</li>
<li><p>...but these optimizations don't seem to be implemented today: going by the benchmark results <sub>(and without having seen the actual machine-code, sorry)</sub> I'd wager the FP callbacks aren't being inlined into an unrolled loop, otherwise there wouldn't be such a huge gap in the benchmark results between <code>for</code> and <code>.map.filter</code>, for example.</p>
</li>
</ol>
<hr />
<p>...so it <em>seems</em> simple enough to give a boost to (what are now) <a href="https://chromestatus.com/metrics/feature/timeline/popularity/4182" rel="noreferrer">very popular JS features</a>. So, forgive my <em>naïveté</em>, but what challenges or considerations am I overlooking that might prevent this kind of optimization and explains why <code>for</code> still beats <code>map</code> and <code>filter</code>?</p>

<optimization><functional-programming><loops>
What challenges might still prevent compiler or JIT optimizations of common FP operations like map, filter, and reduce?
CC BY-SA 4.0
2024-11-09T07:06:37.390Z
You call checking several complex, yet not overwhelmingly common, preconditions in turn, based on information the JIT does not have from the start but has to heuristically infer at runtime, and having to correctly trap and fallback in case of failed speculation “simple enough”?
user3840170
CC BY-SA 4.0
2024-11-09T07:09:36.370Z
@user3840170 Well, yes. The building-blocks are already there.
Dai
CC BY-SA 4.0
2024-11-09T07:10:45.650Z
I am a bit sceptical that this could have performance value for real-world JavaScript workloads to justify the implementation/maintenance/dynamic overhead; they don't even do tracing any more because it just isn't worth it. Are you looking for answers of that nature, or technical obstacles?
Michael Homer
CC BY-SA 4.0
2024-11-09T09:18:44.743Z
@MichaelHomer Out of curiosity, do you know any reading material (blogs, announcements, …) on "they don't even do tracing any more because it just isn't worth it"?
MisterMiyagi
CC BY-SA 4.0
2024-11-09T09:36:06.017Z
@MisterMiyagi This one's a good read: https://web.archive.org/web/20221207193901/https://www.yuiza.org/baccaml-programming-src-2019.pdf
Dai
CC BY-SA 4.0
2024-11-09T10:44:11.813Z
One issue is that if the optimisation only works for some small class of provably-pure callbacks, this class either will need to be specified precisely so that users can rely on it, or some users will see it as unreliable and hence prefer the imperative style anyway, so they won't benefit from the optimisation. It also means that code relying on this optimisation will be harder to refactor if the callback ever changes to one which isn't included.
kaya3
CC BY-SA 4.0
2024-11-09T10:52:51.350Z
Another issue is that if the optimisation only works on one JS runtime, then people writing for the web probably won't rely on it because not all of their users will be using the correct browser to benefit from the optimisation. Imperative-style code will be more optimisable across different browsers.
kaya3
CC BY-SA 4.0
2024-11-09T17:39:16.143Z
This is not a jit-level optimization, but FYI Anders added a small but useful optimization to the default implementations of Where and Select in .NET so that queries with n Where and Select operations in a row do not generate n subsequences and hence n nested calls along the way. Rather, they generate a single object that runs all the filters and maps "at once" on each item in the sequence. See https://github.com/microsoft/referencesource/blob/51cf7850defa8a17d815b4700b67116e3fa283c2/System.Core/System/Linq/Enumerable.cs#L165 for the details.
Eric Lippert
CC BY-SA 4.0
2024-11-09T19:57:00.200Z
@MisterMiyagi [This blog post](https://blog.mozilla.org/nnethercote/category/tracemonkey/) gives some discussion of the TraceMonkey removal from SpiderMonkey, but you can find other commentary around the IonMonkey introduction circa 2012. The general reason is that traces blow up a lot in code that isn't deep hot loops and breaking out to the slow path costs more time than the tracing gains in real-world scenarios (not deep hot-loop benchmarks). Other languages will have different usage patterns that could change the cost equation, though, tracing and meta-tracing do still have benefits.
Michael Homer
# What challenges might still prevent compiler or JIT optimizations of common FP operations like map, filter, and reduce?
Posted by: username_0 on 2024-11-09
(While I'm referring to JS in my example, I don't intend to be constrained to JS: so any comments/answers concerning *FP-style* APIs for working with collections for any language are welcome and encouraged)

A couple of years ago [I answered an SO question asking](https://stackoverflow.com/a/69097515/159145) how to convert a JS fragment using `.map + .filter` to one using only `.reduce`. I initially (and blithely) told them to stick with `.map + .filter` because there is more potential for an optimizing JS compiler/JIT to generate very efficient machine-code compared to shoving all the logic into a single `.reduce` call.

...my argument being: assuming that `.map`'s projector argument and `.filter`'s predicate argument are pure-functions (or at least are const-correct) then the program becomes *embarrassingly parallel* and a JS JIT could (for example) generate machine-code using vector-extensions like SIMD/SSE/AVX/etc, and sufficiently large-enough collections could be automatically parallelized using threads.

...

Now flash-forward to about a month ago where I found myself eating my words in that QA when [a new comment-reply benchmarked various approaches](https://jsperf.app/jeqona/6) to solving the same problem and my first-choice: `.filter().map()` turned out to be amongst the slowest implementations (in both [Chrome 130](https://imgur.com/z3TL2fq) and [Firefox 132](https://imgur.com/AgDiHfA)).

| Chrome 130 | Firefox 132 |
| --- | --- |
| [enter image description here](https://i.sstatic.net/53FuNQ6H.png) | [enter image description here](https://i.sstatic.net/m0S2W1Ds.png) |

...I've noticed the same thing in other languages that I'd thought *should* be able to heavily optimize this pattern (again, provided the predicates/projectors/callbacks are side-effect-free or when the side-effects are discarded) but I've found that benchmarks *always* show an imperative `for` loop outperforming FP-style (such as C#'s Linq or [Python](https://stackoverflow.com/questions/43677763/why-is-in-my-case-for-loop-faster-vs-map-reduce-and-list-comprehension)), at least until a collection is large enough that `Parallel.For` wipes the floor with good ol' `for`.

---

I know the ECMAScript specification is somewhat prescriptive; for example, [it states that `Array.prototype.map` *should* be implemented by iterating first-to-last through the array/collection](https://tc39.es/ecma262/multipage/indexed-collections.html#sec-array.prototype.map:%7E:text=map%20calls%20callback%20once%20for%20each%20element%20in%20the%20array%2C%20in%20ascending%20order%2C), which implies *serializability* of the program, but "*should*" is not "*must*" and I reckon a conforming JS JIT could skirt that requirement for JS programs that have provably pure function callbacks because such a program (with stateless callbacks) would have absolutely no way of observing whether or not array elements were iterated in any particular order or even concurrently.

This pet-theory of mine is based on my actual experiences working on [the Chakra JS engine](https://github.com/chakra-core/ChakraCore) when I worked at Microsoft; now, this was almost an entire decade ago, and back then (as now) I wasn't exactly a rockstar JIT architect (and none of my contributions to Chakra made it into any released code, lol ugh) but I know for a fact that the JIT had *some* ability to analyze the program-tree and prototypes and it definitely could identify "trivial" projectors/predicate callbacks, and while (IIRC) Chakra then didn't yet have FP optimizations it was definitely something that could be implemented if there weren't 1,001+ other things that were higher-priority fixes/improvements at the time.

---

My (hardly thorough) thinking is the JIT could do something like this:

1. An `Array.prototype.map` call-site is encountered, e.g. `var m = src.map( e => e + 1 );`.

   * I note that the JIT will still need to produce nonoptimized machine-code for *JIT bailout* cases (e.g. if an exception/error happens inside an optimized function, e.g. an inlined function won't have a helpful stacktrace)).
     + I should point out that this is how Chakra's JIT worked.
2. The JIT examines the projection callback passed into `.map` (in this case: `function( e ) { return e + 1; }`) and is satisfied the callback is a side-effect-free pure-function.

   * I know a general-solution to this is likely impossible, but a nonexhaustive (and very cheap) check using pattern-matching for common known-safe expressions would work for most cases, I imagine.
   * So callbacks like `e => e + 1`, `e => e.simpleField1.simpleField2` and `e => e.toString()` would all be compatible (and would feature cheap runtime precondition checks to *bail-out* to less-optimized-but-fully-ECMAScript-compliant code if the runtime detects a modified `prototype` or other potential for trouble).
3. Then the optimizations could be implemented:

   * For `map`, at least, the JIT would inline the projection callback into an unrolled loop in its internal intermediate-form before the final machine-code translation step, which I hope would use SIMD instructions.
   * For `filter` I can think of a few optimizations cribbed from RDBMS query-plans (even without any indexes, if the size of the input array and the selectivity of the predicate are known then that can inform better allocation and copy strategies), not to mention explicit concurrency with a divide-and-conquer strategy - and that's just off-the-top-of-my-head so I'm confident there exist better techniques out there.
   * For `reduce`, if the aggregation function conforms to some set of known-optimizable patterns (e.g. given an `Array`, a `.reduce` call passes-in `seed: new Set()` (i.e. a hashset) and accumulates using [`Set.prototype.add`](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Set/add) then the JIT could rewrite it as a parallizable *merge* operation and then compile that as normal.
   * For `.map.filter` or `.filter.map` the JIT could reorder the operations (or interweave them) based on any statistical knowledge the runtime holds about a collection (just like [how RDMBS already do](https://www.postgresql.org/docs/current/sql-createstatistics.html)).
4. This optimized machine-code from Step 3 would be wrapped in an error-trap that, in the event of something going wrong, would jumps to a normally optimized machine-code version of the program and retries the failed iteration and will have enough information to, for example, throw a correctly populated `Error` object.

   * As with my point above about codepaths for *JIT bailout*, what I'm describing here is already how some JIT compilers, like Chakra's, already work.
5. ...but these optimizations don't seem to be implemented today: going by the benchmark results (and without having seen the actual machine-code, sorry) I'd wager the FP callbacks aren't being inlined into an unrolled loop, otherwise there wouldn't be such a huge gap in the benchmark results between `for` and `.map.filter`, for example.

---

...so it *seems* simple enough to give a boost to (what are now) [very popular JS features](https://chromestatus.com/metrics/feature/timeline/popularity/4182). So, forgive my *naïveté*, but what challenges or considerations am I overlooking that might prevent this kind of optimization and explains why `for` still beats `map` and `filter`?
**Tags:** optimization functional-programming loops
> **Comments:**
> **username_1**: You call checking several complex, yet not overwhelmingly common, preconditions in turn, based on information the JIT does not have from the start but has to heuristically infer at runtime, and having to correctly trap and fallback in case of failed speculation “simple enough”?  
> **username_0**: @user3840170 Well, yes. The building-blocks are already there.  
> **username_2**: I am a bit sceptical that this could have performance value for real-world JavaScript workloads to justify the implementation/maintenance/dynamic overhead; they don't even do tracing any more because it just isn't worth it. Are you looking for answers of that nature, or technical obstacles?  
> **username_3**: @MichaelHomer Out of curiosity, do you know any reading material (blogs, announcements, …) on "they don't even do tracing any more because it just isn't worth it"?  
> **username_0**: @MisterMiyagi This one's a good read: https://web.archive.org/web/20221207193901/https://www.yuiza.org/baccaml-programming-src-2019.pdf  
> **username_4**: One issue is that if the optimisation only works for some small class of provably-pure callbacks, this class either will need to be specified precisely so that users can rely on it, or some users will see it as unreliable and hence prefer the imperative style anyway, so they won't benefit from the optimisation. It also means that code relying on this optimisation will be harder to refactor if the callback ever changes to one which isn't included.  
> **username_4**: Another issue is that if the optimisation only works on one JS runtime, then people writing for the web probably won't rely on it because not all of their users will be using the correct browser to benefit from the optimisation. Imperative-style code will be more optimisable across different browsers.  
> **username_5**: This is not a jit-level optimization, but FYI Anders added a small but useful optimization to the default implementations of Where and Select in .NET so that queries with n Where and Select operations in a row do not generate n subsequences and hence n nested calls along the way. Rather, they generate a single object that runs all the filters and maps "at once" on each item in the sequence. See https://github.com/microsoft/referencesource/blob/51cf7850defa8a17d815b4700b67116e3fa283c2/System.Core/System/Linq/Enumerable.cs#L165 for the details.  
> **username_2**: @MisterMiyagi [This blog post](https://blog.mozilla.org/nnethercote/category/tracemonkey/) gives some discussion of the TraceMonkey removal from SpiderMonkey, but you can find other commentary around the IonMonkey introduction circa 2012. The general reason is that traces blow up a lot in code that isn't deep hot loops and breaking out to the slow path costs more time than the tracing gains in real-world scenarios (not deep hot-loop benchmarks). Other languages will have different usage patterns that could change the cost equation, though, tracing and meta-tracing do still have benefits.  
---
## 0 answers
