4 ms·
From the conclusion: "Performance does suffer for nontrivial programs, because the compiler will not understand the algebraic structure of the custom functions
by tehsauce 7y ago
From the conclusion:
"Performance does suffer for nontrivial programs, because the compiler will not understand the algebraic structure of the custom functions, and so will not perform important structural optimisations."
I wonder what it would take for the compiler to understand this algebraic structure? Is this something feasible with more developer resources?
- dbaupp 7y agoGHC Haskell offers in-source rewrite rules, which can be used to get this sort of deforestation optimisation: https://wiki.haskell.org/GHC/Using_rules https://wiki.haskell.org/GHC/Using_rules Rust iterators (including the parallel ones in the Rayon library) and C++ ranges are explicitly lazy without being connected to some in-memory structure and so "automatically" have this optimisation (different to Haskell's [a] list type).
- Athas 7y ago> I wonder what it would take for the compiler to understand this algebraic structure? Is this something feasible with more developer resources? Possible, but not feasible. Map-reduce fusion in particular is difficult when the reduction is expressed non-primitively, because the compiler has to be careful not to duplicate work. The tree reduction is particularly challenging because of the sequential loop that obscures the producer-consumer relationship, but even the chunked reduction would require index analysis to ensure that inlining the map does not duplicate work. It gets even worse for more complex optimisations. For example, there is no realistic chance that the compiler will be able to efficiently sequentialise any of the hand-written reductions, in those cases where they are nested inside other parallel constructs and their own parallelism is not necessary.