Opened 5 years ago

Closed 5 years ago

#9356 closed bug (fixed)

scanl does not participate in list fusion

Reported by: dfeuer Owned by:
Priority: normal Milestone:
Component: Compiler Version: 7.8.3
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: Runtime performance bug Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description (last modified by dfeuer)

nomeata came up with a fusable version of a strict scanl' in a comment on #9345 that uses the same basic technique as the new foldl. I think we should use something like the following non-strict version to replace the current scanl:

scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl f a bs = build $ \c n ->
    a `c`
    foldr (\b g x -> let b' = f x b in (b' `c` g b'))
          (const n)
          bs
          a

While we're at it, we should make sure that map g . scanl f a and scanl f a . map g fuse properly.

Attachments (1)

scanl.diff (1.4 KB) - added by dfeuer 5 years ago.
Patch to make scanl fuse

Download all attachments as: .zip

Change History (10)

comment:1 Changed 5 years ago by dfeuer

Description: modified (diff)
Version: 7.8.27.8.3

Changed 5 years ago by dfeuer

Attachment: scanl.diff added

Patch to make scanl fuse

comment:2 Changed 5 years ago by dfeuer

Status: newpatch

Effects are generally small, but it seems to do a bit of good. The weakness is the let, of course. I'm still not sure we're gaining anything by trying to make this a good producer. Certainly making it a good consumer is good. I'm going to do a bit more hacking and testing.

comment:3 Changed 5 years ago by dfeuer

It looks like strictness analysis can work its magic in nice cases and unbox the accumulator, erasing the let. I think this is probably good to go.

comment:4 Changed 5 years ago by dfeuer

There is some kind of bad interaction that makes sum . concat . inits $ [1..10000] explode (use tons of RAM) when inits is written using a scanl' similar to this scanl. If this is affected, it may not be ready to go after all. I can fix the problem by breaking the pipeline between concat and inits; there also isn't a problem if I drop the sum. If I use foldl' (+) 0 instead of sum, then it doesn't explode anymore, but it still allocates excessively and runs slowly.

comment:5 Changed 5 years ago by dfeuer

Summary: scanl does not participate in stream fusionscanl does not participate in list fusion

It looks like the concat/inits issue is probably not a scanl issue in principle, and it should be safe enough to merge this patch.

comment:6 Changed 5 years ago by nomeata

Status: patchinfoneeded

Can you extend the patch with a bit more comments? In particular, why do you need this tailScanl, when with other functions, the fooList rule writes it back to the direct code?

comment:7 Changed 5 years ago by dfeuer

Status: infoneededpatch

I added an explanation, and simplified some things. Phab:D314

comment:8 Changed 5 years ago by Joachim Breitner <mail@…>

In d45693a5384460d22a6437b9cda463b4ec4b6a37/ghc:

Make scanl fuse; add scanl'

Summary:
Make scanl a good producer and a good consumer for fold/build
fusion. Add strictly-accumulating scanl', which is required for
Data.List.inits.

Reviewers: nomeata, austin

Reviewed By: austin

Subscribers: spacekitteh, thomie, carter, ezyang, simonmar

Differential Revision: https://phabricator.haskell.org/D314

GHC Trac Issues: #9356

comment:9 Changed 5 years ago by nomeata

Resolution: fixed
Status: patchclosed
Note: See TracTickets for help on using tickets.