Ticket #915 (closed task: invalid)

Opened 7 years ago

Last modified 9 months ago

Implement list fusion using streams instead of foldr/build

Reported by: simonpj Owned by:
Priority: normal Milestone: 7.6.1
Component: libraries/base Version: 6.8
Keywords: fusion Cc: dons@…, duncan.coutts@…, rl@…, Bulat.Ziganshin@…, johan.tibell@…, Deewiant, pumpkingod@…, mhenrion@…, pho@…, wasserman.louis@…, rturk@…, black.meph@…, ezyang@…, p.giarrusso@…, Jake.McArthur@…, leather@…, fuzxxl@…, favonia@…, hackage.haskell.org@…, the.dead.shall.rise@…, David.Feuer@…
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Difficulty: Project (more than a week)
Test Case: N/A Blocked By:
Blocking: Related Tickets:

Description

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.

Change History

  Changed 7 years ago by simonpj

  • owner set to simonpj

  Changed 7 years ago by igloo

  • testcase set to N/A

  Changed 6 years ago by dons

  • keywords fusion added
  • difficulty changed from Unknown to Project (> 1 week)
  • version changed from 6.4.2 to 6.6
  • architecture changed from Unknown to Multiple

This task has its own website now:

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

  Changed 6 years ago by guest

  • cc Bulat.Ziganshin@… added

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

  Changed 6 years ago by 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).

  Changed 6 years ago by guest

  • cc changed from Bulat.Ziganshin@gmail.com to Bulat.Ziganshin@gmail.com

  Changed 6 years ago by simonmar

  • milestone changed from 6.8 branch to 6.10 branch

  Changed 6 years ago by simonmar

  • owner simonpj deleted

  Changed 6 years ago by dons

  • cc dons@…, duncan.coutts@…, rl@… added
  • version changed from 6.6 to 6.8

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.

  Changed 5 years ago by tibbe

  • cc johan.tibell@… added

  Changed 5 years ago by igloo

  • milestone changed from 6.10 branch to 6.12 branch

  Changed 5 years ago by Deewiant

  • cc Deewiant added

  Changed 5 years ago by 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).

  Changed 5 years ago by simonmar

  • architecture changed from Multiple to Unknown/Multiple

  Changed 5 years ago by simonmar

  • os changed from Unknown to Unknown/Multiple

  Changed 4 years ago by pumpkin

  • cc pumpkingod@… added

  Changed 4 years ago by mux

  • cc mhenrion@… added

  Changed 4 years ago by PHO

  • cc pho@… added

  Changed 4 years ago by simonmar

  • difficulty changed from Project (> 1 week) to Project (more than a week)

  Changed 3 years ago by LouisWasserman

  • failure set to None/Unknown

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?

  Changed 3 years ago by LouisWasserman

  • cc wasserman.louis@… added

follow-up: ↓ 31   Changed 3 years ago by 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).

  Changed 3 years ago by igloo

  • milestone changed from 6.12 branch to 6.12.3

  Changed 3 years ago by igloo

  • priority changed from normal to low
  • milestone changed from 6.12.3 to 6.14.1

  Changed 3 years ago by Remi

  • cc rturk@… added

  Changed 2 years ago by BMeph

  • cc black.meph@… added

  Changed 2 years ago by igloo

  • milestone changed from 7.0.1 to 7.0.2

  Changed 2 years ago by ezyang

  • cc ezyang@… added

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.

  Changed 2 years ago by igloo

  • milestone changed from 7.0.2 to 7.2.1

  Changed 2 years ago by Blaisorblade

  • cc p.giarrusso@… added

in reply to: ↑ 22   Changed 2 years ago by 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?

  Changed 2 years ago by jmcarthur

  • cc Jake.McArthur@… added

  Changed 2 years ago by spl

  • cc leather@… added

  Changed 2 years ago by FUZxxl

  • cc fuzxxl@… added

  Changed 2 years ago by Favonia

  • cc favonia@… added

  Changed 2 years ago by liyang

  • cc hackage.haskell.org@… added

  Changed 23 months ago by refold

  • cc the.dead.shall.rise@… added

  Changed 20 months ago by igloo

  • milestone changed from 7.2.1 to 7.4.1

  Changed 16 months ago by igloo

  • priority changed from low to normal
  • milestone changed from 7.4.1 to 7.6.1

  Changed 9 months ago by dfeuer

  Changed 9 months ago by dfeuer

  • cc David.Feuer@… added

  Changed 9 months ago by dfeuer

The package on hackage no longer compiles.

follow-up: ↓ 44   Changed 9 months ago by igloo

  • status changed from new to infoneeded

Duncan, Don,

Is concat/concatMap still an unsolved problem?

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

in reply to: ↑ 43   Changed 9 months ago by 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.

  Changed 9 months ago by igloo

  • status changed from infoneeded to closed
  • resolution set to invalid
Note: See TracTickets for help on using tickets.