<p>How do different programming languages deal with the chaining of higher-order functions (ex. <code>[1,2,3].foldl((a, b) =&gt; a+b, 0)</code>, <code>[1,2,3].map(x =&gt; x+1)</code>) without losing performance? In a naive implementation, chaining a <code>foldl</code> function to a <code>map</code> function applied to a list would iterate through the entire list <strong>twice</strong>, when it could be iterated through only once.</p>
<p>I know Haskell does not need to worry about this by virtue of being lazy. I know Rust emulates laziness by having higher order functions return special types that must be <code>collect()</code>ed into a result once done. What do other languages do? Are there ways to approach this problem that do not require a language to be totally lazy, or require an explicit <code>collect()</code> invocation?</p>

<functions><functional-programming>
How do languages chain higher-order functions while still keeping performance?
CC BY-SA 4.0
2023-10-27T00:39:02.550Z
Java has `Stream` (explicit collect), and Kotlin has `Sequence` (lazy)
Seggan
CC BY-SA 4.0
2023-10-27T04:03:57.600Z
I would definitely not say that Haskell doesn't need to worry about this. There actually has been a decent amount of work into getting this to be efficient in Haskell. A lot of this work is under the names "stream fusion," "list fusion" and "`foldr`/`build` fusion."  There are several papers on this, including [this](https://dl.acm.org/doi/10.1145/1291151.1291199), [this](https://dl.acm.org/doi/10.1145/165180.165214) and [this](https://www.cs.ox.ac.uk/people/ralf.hinze/publications/IFL10.pdf). I believe the technique GHC currently used is derived from `foldr`/`build` fusion.
David Young
CC BY-SA 4.0
2023-10-27T04:04:38.153Z
The general idea of fusion is that you eliminate the intermediate lists (note that this is *not* automatically done by laziness alone). More generally, you eliminate the intermediate *data structures*. So, with fusion, `map f . map g` becomes something that's more akin to `map (f . g)`, which only has one list traversal (where the `.` operator is function composition).
David Young
CC BY-SA 4.0
2023-10-28T16:35:02.837Z
Are you asking about iterators/streams/lists specifically? I'm not sure how to understand your question in the context of arbitrary higher-order functions.
Bergi
<p>These days, the first answer to any “how can languages retain performance while <em>X</em>” question is <strong>optimising JITs</strong>, rather than needing necessarily to be part of the language or library design. These will automatically perform type specialisation, inlining, loop fusion, and so on, using the information available at run time (including about the concrete data being processed) at performance-critical points in the program.</p>
<p>This is an especially powerful technique for exactly the kind of situation you describe: sequential heavily-used loops with local short-lived allocations, with repeated sequences of functions called in order many times. Conventional performance intuitions are not reliable with these systems (sometimes in both directions). Even the naive implementation of those higher-order function chains is likely to have fairly good performance in a hot loop in modern high-performance virtual machines, like the JVM, CLR, or browser JavaScript engines, even in the presence of virtual dispatch or heterogeneous data.</p>
<hr />
<p>Bespoke JIT implementations aren’t as complex to build today as in the past, with tools like <a href="https://www.graalvm.org/latest/graalvm-as-a-platform/language-implementation-framework/" rel="nofollow noreferrer">Truffle/Graal</a> or PyPy allowing you to build an interpreter and any language-specific optimisation steps, then get access to standard optimisations along with that, or the implementation can simply target an existing optimising VM’s bytecode.</p>
<p>Traditional static optimisations are also very effective in these sequential-loop cases and avoid the JIT overhead, but don’t have the ability to respond to information unknown at compile time. Inlining lambdas and higher-order functions, performing loop fusion and unrolling, array bounds optimisation, peephole optimisation of the revealed instruction sequences, and other standard compiler optimisation techniques also produce good performance for exactly this type of code. While they can be implemented directly, compilers targeting existing compiler backends like LLVM are able to take advantage of their optimisations “for free” as well.</p>
<hr />
<p>Only if these standard optimisations aren’t effective, or for targets where JIT compilation is not possible or suitable, is a language design change necessary for good performance. Systems languages (like Rust) or those targeting embedded systems can be instances of those. However, other languages could have conventional usage patterns that weren’t friendly to these as well (particularly JIT compilation).</p>
<p>There is another side of performance where enabling parallelism may be a more valuable benefit, and one that that API or language design can assist. Automatic parallelisation of sequential code is notoriously hard and an active research topic, but is likely to require specific language design choices in practice, like purity or isolation guarantees.</p>

CC BY-SA 4.0
2023-10-27T02:45:05.683Z
2023-10-27T02:45:05.683Z
Michael Homer
CC BY-SA 4.0
2023-10-27T08:19:33.720Z
Useful answer for many languages, although the examples of Haskell and Rust suggest that the OP was thinking primarily of compile-time optimizations.
Davislor
CC BY-SA 4.0
2023-10-27T08:41:35.667Z
@Davislor It's possible, though I took it more as focusing on language *design* aspects (lazy evaluation, use of collectors/dynamic stream constructors) rather than seeking optimisations specifically, and I think that's not (necessarily) the right focus to have. It's a premature optimisation to change the language to deal with prospective performance problems that may be eliminated by the JIT or static optimisation.
Michael Homer
CC BY-SA 4.0
2023-10-27T09:07:10.450Z
There's fundamentally no difference between a JIT compiler and static compiler, other than the tuning tradeoffs (compile time vs run time).  Any optimization technique that can be used in a JIT compiler can be used in a static compiler (and vice versa).
Chris Dodd
CC BY-SA 4.0
2023-10-27T13:29:47.273Z
@ChrisDodd not necessarily. Static compilers have no information about e.x. the branches taken which can optimize the generated code
Seggan
CC BY-SA 4.0
2023-10-27T18:06:41.540Z
That’s certainly not true in the case of a dynamically-typed system, for example, but there are other optimisations only practical with run-time information too (possibly PGO in a static compiler). You don’t know what’s going to be a hot loop until you get there, and optimisations can pessimise instead if you get it wrong. The thing with a JIT is that the assumptions it makes are always *correct* for this specific concrete execution. It’s good enough that this should be the first port of call when it’s viable.
Michael Homer
CC BY-SA 4.0
2023-10-27T22:09:53.577Z
@Seggan: static compilers certainly can have that info -- it's called "profile driven optimization" and requires more work at build time (generating a profiling version of the code and running that on typical inputs before doing the full compile), but there's nothing specific to JIT compilers about it.
Chris Dodd
CC BY-SA 4.0
2023-10-27T22:12:09.177Z
@MichaelHomer:  JIT compilers can also pessimize instead of optimze if the information they use from early executions of a function doesn't match later executions.
Chris Dodd
CC BY-SA 4.0
2023-10-27T22:20:30.867Z
They can, though they will also detect and fix it automatically in that case, so that long-run steady-state execution is as close to optimal as achievable. Virtually all optimisation transformations are available to static compilers and JITs equally, but their risk profiles are quite different.
Michael Homer
CC BY-SA 4.0
2023-10-27T22:50:50.123Z
The closest you can say to a "real" difference between static and JIT is that with a static compiler, there's some point in time after which you'll never recompile anything.  But in practice that point never comes as there are always updates and upgrades and bugfixes.  Other than that, its just all tuning tradeoffs.  To get back to the question, the ways to improve the performance of higher-order functions are largely identical between static and JIT.
Chris Dodd
CC BY-SA 4.0
2023-10-27T23:30:49.853Z
I do think that “just all tuning tradeoffs” is disregarding close to every relevant factor in service of making them indistinguishable, but most optimisations are *available* to both, yes. Knowing where to hit it is quite important, and handwaving that off to PGO and future deployments is too dismissive of the real practicalities of language development. The answer says that *in the first instance* targeting an existing high-performance JITing VM is today the typical and correct move before any bespoke design or optimisation to address observed problems, when that’s possible, and that’s right.
Michael Homer
<h3>Lazy Types</h3>
<p>This is pretty much what you're talking about with your Rust example -- even if the language isn't lazy, it can support lazy types (either built-in or in a way the user can add them) to get laziness.  You can even support implicit conversion of lazy types to non-lazy types (obviating the need for an explicit <code>collect()</code>), though that can be suprising to unwary users who might trigger the conversion when they're not expecting it</p>
<h3>Inlining</h3>
<p>Simple function inlining is suprisingly effective (and important) in making this kind of code run fast.  Inlining enables many other standard optimizations, giving them many more opportunities.  In your chained fold+map, after inlining, loop fusion can combine the iterations into one.  Recusively inlining the lambdas as well opens up many opportunities for CSE (common subexpression elimination) improvements as well as giving your instruction scheduler more to work with.</p>

CC BY-SA 4.0
2023-10-27T00:51:15.377Z
2023-10-27T08:18:17.840Z
2023-10-27T08:18:17.840Z
Chris Dodd
CC BY-SA 4.0
2023-10-27T08:59:16.657Z
You can find info about loop fusion [here](https://en.wikipedia.org/wiki/Loop_fission_and_fusion), [here](https://www.intel.com/content/www/us/en/docs/programmable/683521/21-4/loop-fusion.html) and [here](https://compileroptimizations.com/category/loop_fusion.htm)
Chris Dodd
CC BY-SA 4.0
2023-10-27T09:01:54.223Z
Hm, but those are all pretty trivial examples. I don't see how loop fusion would work when both loops are operating on the same data.
apropos
CC BY-SA 4.0
2023-10-27T09:17:23.383Z
All that is needed for loop fusion is that second loop not carry dependencies from later iterations of the first loop.  That is pretty much automatic for the map loop.
Chris Dodd
CC BY-SA 4.0
2023-10-28T02:16:17.143Z
There's a reason most every sequence algorithm in Swift is `@inlinable`. (Go on, scroll through [SequenceAlgorithms](https://github.com/apple/swift/blob/main/stdlib/public/core/SequenceAlgorithms.swift), see for yourself!) Swift also has `.lazy` for when you need to make it explicit.
Bbrk24
CC BY-SA 4.0
2023-10-28T12:28:36.840Z
Laziness/non-strictness is a red herring; strict languages can also witness fused looping operations. More important is referential transparency, so that rewrites are algebraically valid.
Corbin
# How do languages chain higher-order functions while still keeping performance?
Posted by: username_0 on 2023-10-27
How do different programming languages deal with the chaining of higher-order functions (ex. `[1,2,3].foldl((a, b) => a+b, 0)`, `[1,2,3].map(x => x+1)`) without losing performance? In a naive implementation, chaining a `foldl` function to a `map` function applied to a list would iterate through the entire list **twice**, when it could be iterated through only once.

I know Haskell does not need to worry about this by virtue of being lazy. I know Rust emulates laziness by having higher order functions return special types that must be `collect()`ed into a result once done. What do other languages do? Are there ways to approach this problem that do not require a language to be totally lazy, or require an explicit `collect()` invocation?
**Tags:** functions functional-programming
> **Comments:**
> **username_1**: Java has `Stream` (explicit collect), and Kotlin has `Sequence` (lazy)  
> **username_2**: I would definitely not say that Haskell doesn't need to worry about this. There actually has been a decent amount of work into getting this to be efficient in Haskell. A lot of this work is under the names "stream fusion," "list fusion" and "`foldr`/`build` fusion."  There are several papers on this, including [this](https://dl.acm.org/doi/10.1145/1291151.1291199), [this](https://dl.acm.org/doi/10.1145/165180.165214) and [this](https://www.cs.ox.ac.uk/people/ralf.hinze/publications/IFL10.pdf). I believe the technique GHC currently used is derived from `foldr`/`build` fusion.  
> **username_2**: The general idea of fusion is that you eliminate the intermediate lists (note that this is *not* automatically done by laziness alone). More generally, you eliminate the intermediate *data structures*. So, with fusion, `map f . map g` becomes something that's more akin to `map (f . g)`, which only has one list traversal (where the `.` operator is function composition).  
> **username_3**: Are you asking about iterators/streams/lists specifically? I'm not sure how to understand your question in the context of arbitrary higher-order functions.  
---
## 2 answers
### Answer by username_6 on 2023-10-27. Score: 8 | Accepted answer
### Lazy Types

This is pretty much what you're talking about with your Rust example -- even if the language isn't lazy, it can support lazy types (either built-in or in a way the user can add them) to get laziness. You can even support implicit conversion of lazy types to non-lazy types (obviating the need for an explicit `collect()`), though that can be suprising to unwary users who might trigger the conversion when they're not expecting it

### Inlining

Simple function inlining is suprisingly effective (and important) in making this kind of code run fast. Inlining enables many other standard optimizations, giving them many more opportunities. In your chained fold+map, after inlining, loop fusion can combine the iterations into one. Recusively inlining the lambdas as well opens up many opportunities for CSE (common subexpression elimination) improvements as well as giving your instruction scheduler more to work with.
> **Comments:**
> **username_6** (2023-10-27): You can find info about loop fusion [here](https://en.wikipedia.org/wiki/Loop_fission_and_fusion), [here](https://www.intel.com/content/www/us/en/docs/programmable/683521/21-4/loop-fusion.html) and [here](https://compileroptimizations.com/category/loop_fusion.htm)  
> **username_0** (2023-10-27): Hm, but those are all pretty trivial examples. I don't see how loop fusion would work when both loops are operating on the same data.  
> **username_6** (2023-10-27): All that is needed for loop fusion is that second loop not carry dependencies from later iterations of the first loop.  That is pretty much automatic for the map loop.  
> **username_7** (2023-10-28): There's a reason most every sequence algorithm in Swift is `@inlinable`. (Go on, scroll through [SequenceAlgorithms](https://github.com/apple/swift/blob/main/stdlib/public/core/SequenceAlgorithms.swift), see for yourself!) Swift also has `.lazy` for when you need to make it explicit.  
> **username_8** (2023-10-28): Laziness/non-strictness is a red herring; strict languages can also witness fused looping operations. More important is referential transparency, so that rewrites are algebraically valid.  
---
### Answer by username_4 on 2023-10-27. Score: 1
These days, the first answer to any “how can languages retain performance while *X*” question is **optimising JITs**, rather than needing necessarily to be part of the language or library design. These will automatically perform type specialisation, inlining, loop fusion, and so on, using the information available at run time (including about the concrete data being processed) at performance-critical points in the program.

This is an especially powerful technique for exactly the kind of situation you describe: sequential heavily-used loops with local short-lived allocations, with repeated sequences of functions called in order many times. Conventional performance intuitions are not reliable with these systems (sometimes in both directions). Even the naive implementation of those higher-order function chains is likely to have fairly good performance in a hot loop in modern high-performance virtual machines, like the JVM, CLR, or browser JavaScript engines, even in the presence of virtual dispatch or heterogeneous data.

---

Bespoke JIT implementations aren’t as complex to build today as in the past, with tools like [Truffle/Graal](https://www.graalvm.org/latest/graalvm-as-a-platform/language-implementation-framework/) or PyPy allowing you to build an interpreter and any language-specific optimisation steps, then get access to standard optimisations along with that, or the implementation can simply target an existing optimising VM’s bytecode.

Traditional static optimisations are also very effective in these sequential-loop cases and avoid the JIT overhead, but don’t have the ability to respond to information unknown at compile time. Inlining lambdas and higher-order functions, performing loop fusion and unrolling, array bounds optimisation, peephole optimisation of the revealed instruction sequences, and other standard compiler optimisation techniques also produce good performance for exactly this type of code. While they can be implemented directly, compilers targeting existing compiler backends like LLVM are able to take advantage of their optimisations “for free” as well.

---

Only if these standard optimisations aren’t effective, or for targets where JIT compilation is not possible or suitable, is a language design change necessary for good performance. Systems languages (like Rust) or those targeting embedded systems can be instances of those. However, other languages could have conventional usage patterns that weren’t friendly to these as well (particularly JIT compilation).

There is another side of performance where enabling parallelism may be a more valuable benefit, and one that that API or language design can assist. Automatic parallelisation of sequential code is notoriously hard and an active research topic, but is likely to require specific language design choices in practice, like purity or isolation guarantees.
> **Comments:**
> **username_5** (2023-10-27): Useful answer for many languages, although the examples of Haskell and Rust suggest that the OP was thinking primarily of compile-time optimizations.  
> **username_4** (2023-10-27): @Davislor It's possible, though I took it more as focusing on language *design* aspects (lazy evaluation, use of collectors/dynamic stream constructors) rather than seeking optimisations specifically, and I think that's not (necessarily) the right focus to have. It's a premature optimisation to change the language to deal with prospective performance problems that may be eliminated by the JIT or static optimisation.  
> **username_6** (2023-10-27): There's fundamentally no difference between a JIT compiler and static compiler, other than the tuning tradeoffs (compile time vs run time).  Any optimization technique that can be used in a JIT compiler can be used in a static compiler (and vice versa).  
> **username_1** (2023-10-27): @ChrisDodd not necessarily. Static compilers have no information about e.x. the branches taken which can optimize the generated code  
> **username_4** (2023-10-27): That’s certainly not true in the case of a dynamically-typed system, for example, but there are other optimisations only practical with run-time information too (possibly PGO in a static compiler). You don’t know what’s going to be a hot loop until you get there, and optimisations can pessimise instead if you get it wrong. The thing with a JIT is that the assumptions it makes are always *correct* for this specific concrete execution. It’s good enough that this should be the first port of call when it’s viable.  
> **username_6** (2023-10-27): @Seggan: static compilers certainly can have that info -- it's called "profile driven optimization" and requires more work at build time (generating a profiling version of the code and running that on typical inputs before doing the full compile), but there's nothing specific to JIT compilers about it.  
> **username_6** (2023-10-27): @MichaelHomer:  JIT compilers can also pessimize instead of optimze if the information they use from early executions of a function doesn't match later executions.  
> **username_4** (2023-10-27): They can, though they will also detect and fix it automatically in that case, so that long-run steady-state execution is as close to optimal as achievable. Virtually all optimisation transformations are available to static compilers and JITs equally, but their risk profiles are quite different.  
> **username_6** (2023-10-27): The closest you can say to a "real" difference between static and JIT is that with a static compiler, there's some point in time after which you'll never recompile anything.  But in practice that point never comes as there are always updates and upgrades and bugfixes.  Other than that, its just all tuning tradeoffs.  To get back to the question, the ways to improve the performance of higher-order functions are largely identical between static and JIT.  
> **username_4** (2023-10-27): I do think that “just all tuning tradeoffs” is disregarding close to every relevant factor in service of making them indistinguishable, but most optimisations are *available* to both, yes. Knowing where to hit it is quite important, and handwaving that off to PGO and future deployments is too dismissive of the real practicalities of language development. The answer says that *in the first instance* targeting an existing high-performance JITing VM is today the typical and correct move before any bespoke design or optimisation to address observed problems, when that’s possible, and that’s right.  
---
