I agree that multi-stage programming is the principled green field
solution. It provides the right model in which to think about solutions for
GHC.
For GHC, that model certainly means "Step is just an intermediate data
structure", i.e., any computation involving `Step` should only live at
compile-time ("template polymorphism") and it should be inlined/specialised
for aggressively.This is not too different for the situation with list fusion. Any compiled program that *runs* `map`/`filter`/`foldr`/`build` has a performance bug. You always want to end up with `foldr`'s SAT'd unfolding/explicit `(:)`/`[]` instead of a higher-order function `build` which does the same thing. That is achieved by the intricate multiphase rewrite rule framework. If all goes well, the final program never contains any lists whatsoever; only a nesting of tight recursive loops. Note that there is no code sharing of `map`/`filter`/`foldr` here; they must all have been inlined and rewritten and were purely a compile-time thing. We want the same for stream fusion because it has better fusion support for `zipWith`. Inlining any function involving `Step` is absolutely the right thing to do! Aggressive specialization as well, but that's really difficult to do using SpecConstr because it blows up so easily. The stream fusion paper <https://www.cs.tufts.edu/~nr/cs257/archive/duncan-coutts/stream-fusion.pdf> instead suggests applying the static argument transformation in section 7.2. A draft patch of mine tried to do that on the fly to compute unfoldings for recursive functions with static args: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/4553. It lacks polishing and my time and interest, but I firmly believe this should help the stream fusion use case, because SAT+inlining is *exactly* specialization of recursive functions for static arguments. (Side Note: Andrasz pointed out to me two years ago that there were further complications which I don't recall and which mean that he settled on the practical compromise of going for foldr/build fusion and enabling zip fusion/parallel for with stream fusion.) --- > what happens if you have sharing > let ys :: Stream Int = h x > in f ys + g ys This is a flaw in the way that GHC says "lists are streams". IMO a stream (such as in streamly) should happily duplicate all the work that goes into computing the elements of `ys`, since it is just code. By contrast, data structures such as lists do not have that luxury. `let ys :: [Int] = ...; in f ys ++ g ys` should not try to fuse `ys`. Here's a repo that implements just foldr/build fusion without rewriting lists to/from it: https://github.com/sgraf812/foldr-build. It doesn't have the "fusion duplicates work" flaw because there is no data that should have shared the work in the first place. --- *TLDR;* inlining and specialising `Step` sounds like exactly what is needed. Specialisation of concatMap is the hard part for stream fusion, though, and that means we'll end up with `Step` in the program nonetheless. Btw., Lean's standard `Iterator` framework <https://github.com/leanprover/lean4/blob/6e711bf067a0d9dc6623996b4bd3757ac6c46886/src/Init/Data/Iterators/Basic.lean#L356> (inspired by Rust's <https://doc.rust-lang.org/std/iter/trait.Iterator.html>) will implement "stream fusion". (That's what external iteration is.) I'm not saying that it's simple or that the optimiser is equipped to handle it, though :) Cheers, Sebastian Am Di., 9. Dez. 2025 um 13:45 Uhr schrieb Simon Peyton Jones < [email protected]>: > I think a solution based on multi-stage programming is the most >> natural way to tackle the stream fusion problem in a robust manner. > > > How close are we to being able to do that in Haskell? > > Simon > > On Tue, 9 Dec 2025 at 09:56, Matthew Pickering < > [email protected]> wrote: > >> I think a solution based on multi-stage programming is the most >> natural way to tackle the stream fusion problem in a robust manner. >> >> For example: https://andraskovacs.github.io/pdfs/2ltt_icfp24.pdf >> >> By allowing a programmer to express which parts of the program should >> only exist code generation time, you guarantee that fusion occurs. >> This seems much more aligned with how Haskell programmers think about >> other things. >> >> Cheers, >> >> Matt >> >> On Tue, Dec 9, 2025 at 12:03 AM Harendra Kumar <[email protected]> >> wrote: >> > >> > On Mon, 8 Dec 2025 at 23:35, Jaro Reinders <[email protected]> >> wrote: >> > > >> > > I suggested we could integrate this into GHC by giving an inlining >> discount to >> > > any function which contains function that is also mentioned in a >> rewrite rule. >> > >> > There are two distinct fusion mechanisms under consideration here - >> > foldr/build fusion and stream fusion. Rewrite rules allow us to >> > replace a combination of functions with an equivalent function, >> > forming the basis of foldr/build fusion by fusing or eliminating >> > intermediate functions. Stream fusion on the other hand eliminates >> > intermediate constructors, the key optimizations for achieving this >> > are case-of-case and worker-wrapper. Both types of fusion require >> > inlining but they are clearly different at the implementation level, >> > even though the same high level ideas may apply in both cases. >> > >> > The fusion-plugin deals with stream fusion only -- where inlining and >> > spec-constr are used to expose constructors which are then eliminated >> > by case-of-case (for linear pipelines) or worker wrapper (for >> > recursive loops) transformations. fusion-plugin has been used >> > extensively in streamly and we have been able to fuse almost all cases >> > that we wanted to. I would recommend that you try out fusion-plugin on >> > the vector package, it can help fuse the pesky cases and you can also >> > gain some insight into how much code bloat it actually causes in >> > practice. Vector is primarily based on stream fusion, and even though >> > it uses rewrite rules, those are not for fusion as such I believe. >> > >> > > However, I also noted I think this will have a large impact on code >> size and >> > > compilation time in larger code bases. Simon agreed, but noted that >> Harendra's >> > > plugin is much more selective than what I suggested. >> > >> > Typically we have a pipeline of functions connected by fusible >> > constructors. To fuse the entire pipeline completely we need to inline >> > all the functions involved in the pipeline. Thus instead of having >> > multiple small functions we end up creating one large combined >> > function. However, when we use case-of-case transformation on the >> > combined function, the size often gets reduced dramatically. In fact >> > the total size of the end product is usually smaller than the combined >> > original components in the pipeline. However, ghc requires more memory >> > and CPU to simplify, especially if the loop becomes too large. >> > >> > In our experience aggressive inlining for fusing linear segments of >> > pipelines even if they are pretty big has almost never been a problem. >> > If it becomes large we can always break the pipeline by using a >> > NOINLINE, making a trade off between runtime perf and compile time >> > resource requirement, but we rarely needed to do that. The code bloat >> > comes more often from the spec-constr optimization when we are fusing >> > recursive loops. In some cases we have used >> > -fspec-constr-recursive=16, which I admit is a very large value, the >> > compile times can sometimes increase dramatically due to this. We can >> > always choose to use a lower value which may result in unfused code in >> > some cases. There may be scope of improvement in GHC for making this >> > optimization smarter and more selective. >> > >> > We can also put some hard thresholds or heuristics here for the cases >> > when the resulting monolithic functions become too large. One possible >> > way to decide whether to inline or not could be to check if the size >> > of the combined/optimized function is smaller than or roughly >> > equivalent to the sum of the individual parts. If inlining does not >> > result in elimination of the constructors in subsequent passes, then >> > the inlining is not useful. But we have seen that it is almost always >> > possible to eliminate all or most of the constructors. >> > >> > > Translating this to the fold/build fusion system in GHC today, we >> would force >> > > inlining of any function that calls `foldr` or `build` (or `augment`). >> > > Essentially, we would want to inline any binding that refers to a >> function that >> > > partakes in the rewrite rules for fusion. I'll admit we probably >> don't have to >> > > generalise this to all rewrite rules, but even with this restriction >> it seems >> > > like a rather aggressive optimisation strategy to me. >> > >> > I do not have much experience with using foldr/build. But conceptually >> > this is quite similar to what we do in stream fusion and similar ideas >> > should be applicable here as well. In this case we inline to expose >> > foldr/build primitives and then use rewrite rules to combine those. If >> > the inlining does not result in further elimination or firing of >> > rewrite rules then the inlining is not useful. You can probably try >> > out automatic inlining in the same way as we do in fusion-plugin and >> > see if code-bloat/compilation times become a real issue, and in which >> > particular cases, then put heuristics/thresholds to avoid that. Is >> > there a driving use case for extending this to foldr/build? >> > >> > -harendra >> > _______________________________________________ >> > ghc-devs mailing list -- [email protected] >> > To unsubscribe send an email to [email protected] >> _______________________________________________ >> ghc-devs mailing list -- [email protected] >> To unsubscribe send an email to [email protected] >> > _______________________________________________ > ghc-devs mailing list -- [email protected] > To unsubscribe send an email to [email protected] >
_______________________________________________ ghc-devs mailing list -- [email protected] To unsubscribe send an email to [email protected]
