Implement list fusion using streams instead of foldr/build

[simonpj]

We'd like to try using the stream-fusion idea of Don Stewart, Duncan Coutts and Roman Leshchinskiy, and replace the (somewhat fragile) foldr/build stuff.

See #876.

[dons]

This task has its own website now:

 http://www.cse.unsw.edu.au/~dons/streams.html.

[guest]

it will be great to see this included in ghc base if this work is already completed

[duncan]

It's not done yet. There's a paper on it but we still have issues with complex list comprehensions.

The new streams stuff will be included in the new bytestring-1.0 package though (as you know, the base package is being split up and ByteString? will be in its own package).

[dons]

We should also rerun the benchmarks in the light of the changes that made it into head since April when the fusion library was last benchmarked. There's no that much more to do here, to finish the job.

[dons]

This library has been written and released,

 http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion

To replace GHC's existing list fusion, we'll need to work out how concatMap is optimised, and push the desugaring for list comprehensions into GHC.

For now though, users can just use the library, and avoid list comprehensions and [n .. m] (use enumFromTo).

[LouisWasserman]

I'm interested in pursuing this. What obstacles are present? Perhaps most importantly, what changes need to be made to make this work? Is it just GHC.List, Data.List, etcetera that need to be changed?

[batterseapower]

AFAIK this ticket is no closer to being practical now that when dons added that comment 18 months ago. To implement it you need to change:

• The list libraries, to use Stream based definitions
• The desugaring for list comprehensions in GHC

However, it is still the case that noone knows how to implement concat / concatMap efficiently and without improving GHCs Core optimisers. Since concatMap is crucial to the the desugaring of list comprehensions, and also kind of important to users generally, stream fusion isn't really ready for prime time yet, IMHO.

An alternative to coming up with a clever library modification would be to improve GHCs optimiser. I found that the suggested approach of running a SAT pass in a fixed point loop with constructor specialisation was fairly reliable, but I haven't got around to either committing my improved SAT pass or making the fixed point I used not so much of a hack. Even if I did so, it is upsetting that stream fusion requires so much more work on the part of the optimiser to get right, compared to the fairly simply rewrite rule story with foldr/build.

(Both approaches suffer from fragility in the face of a lack of INLINE pragmas).

[ezyang]

For those playing along at home, more details on the inability to efficiently optimize concat/concatMap (more generally, fusion on nested lists) can be found in Section 7.2 of the  "Stream Fusion" paper. T'would probably be nice if the GHC optimizer experiments were public somewhere.

[Blaisorblade]

Replying to batterseapower:

AFAIK this ticket is no closer to being practical now that when dons added that comment 18 months ago.[...]

However, it is still the case that noone knows how to implement concat / concatMap efficiently and without improving GHCs Core optimisers.[...]

An alternative to coming up with a clever library modification would be to improve GHCs optimiser.

[...I]t is upsetting that stream fusion requires so much more work on the part of the optimiser to get right, compared to the fairly simply rewrite rule story with foldr/build.

I wanted to focus on this part of the comment, which is about whether you actually want to merge the code. If this is agreed upon, then one needs to find somebody willing to finish the job, but that's easier with an agreement.

The paper argues (or claims) that the improved optimization is generally useful and not specific to stream fusion. Do you disagree? Is the code exceedingly ugly? Would you be ready to publish it somewhere? Are there any benchmark results from applying the optimization alone, compared with the standard optimizer? The paper mentions shortly that usually improves nofib performance slightly.

I also wonder: is sometimes the SAT transformation done by hand by programmers for performance?

[dfeuer]

The package on hackage no longer compiles.

[igloo]

Duncan, Don,

Is concat/concatMap still an unsolved problem?

If so, can we close this ticket as requiring more research, rather than merely implementation?

[duncan]

Replying to igloo:

Is concat/concatMap still an unsolved problem?

Sort-of. I describe a potential solution in my  thesis (section 4.8.3).

If so, can we close this ticket as requiring more research, rather than merely implementation?

Yes.