9
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ Java has Stream (explicit collect), and Kotlin has Sequence (lazy) $\endgroup$
    – Seggan
    Oct 27, 2023 at 0:39
  • 10
    $\begingroup$ 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, this and this. I believe the technique GHC currently used is derived from foldr/build fusion. $\endgroup$ Oct 27, 2023 at 4:03
  • 4
    $\begingroup$ 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). $\endgroup$ Oct 27, 2023 at 4:04
  • $\begingroup$ 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. $\endgroup$
    – Bergi
    Oct 28, 2023 at 16:35

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ You can find info about loop fusion here, here and here $\endgroup$
    – Chris Dodd
    Oct 27, 2023 at 8:59
  • $\begingroup$ 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. $\endgroup$
    – apropos
    Oct 27, 2023 at 9:01
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chris Dodd
    Oct 27, 2023 at 9:17
  • $\begingroup$ There's a reason most every sequence algorithm in Swift is @inlinable. (Go on, scroll through SequenceAlgorithms, see for yourself!) Swift also has .lazy for when you need to make it explicit. $\endgroup$
    – Bbrk24
    Oct 28, 2023 at 2:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – Corbin
    Oct 28, 2023 at 12:28
1
$\begingroup$

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

$\endgroup$
10
  • $\begingroup$ Useful answer for many languages, although the examples of Haskell and Rust suggest that the OP was thinking primarily of compile-time optimizations. $\endgroup$
    – Davislor
    Oct 27, 2023 at 8:19
  • $\begingroup$ @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. $\endgroup$
    – Michael Homer
    Oct 27, 2023 at 8:41
  • 2
    $\begingroup$ 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. $\endgroup$
    – Michael Homer
    Oct 27, 2023 at 18:06
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Homer
    Oct 27, 2023 at 22:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Michael Homer
    Oct 27, 2023 at 23:30

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .