Opened 11 years ago

Closed 9 years ago

#2684 closed task (wontfix)

Stack overflow in stream-fusion library with GHC 6.10 RC

Reported by: dons Owned by: dons
Priority: high Milestone: 7.2.1
Component: Compiler Version: 6.9
Keywords: Cc:
Operating System: Unknown/Multiple Architecture: Unknown/Multiple
Type of failure: None/Unknown Test Case:
Blocked By: Blocking:
Related Tickets: Differential Rev(s):
Wiki Page:

Description

Regression from GHC 6.8.x to GHC 6.10 release candidate,

$ runhaskell Setup.lhs configure 
Configuring stream-fusion-0.1.1...
$ runhaskell Setup.lhs build     
Preprocessing library stream-fusion-0.1.1...
Building stream-fusion-0.1.1...
...
Data/Stream.hs:575:4:
    Warning: Pattern match(es) are non-exhaustive
             In the definition of `next':
                 Patterns not matched: (_ :!: (Just (L _))) :!: S2
[2 of 3] Compiling Data.List.Stream ( Data/List/Stream.hs, dist/build/Data/List/Stream.o )
stack overflow: use +RTS -K<size> to increase it

The stack overflow was not present with GHC 6.8.x

You can get the code here: http://hackage.haskell.org/cgi-bin/hackage-scripts/package/stream-fusion

Attachments (2)

Stream.hs (1.2 KB) - added by igloo 11 years ago.
Stream.2.hs (432 bytes) - added by igloo 11 years ago.

Download all attachments as: .zip

Change History (12)

comment:1 Changed 11 years ago by igloo

difficulty: Unknown
Milestone: 6.10.1
Priority: normalhigh

I haven't tracked down exactly what's going on here, but it seems to be going round some sort of loop in functions like simplNonRecE and simplLam, with binders [ds_dC6, ds_dC7] and body

 case ds_dC7 of _ {
   [] -> GHC.Types.[] @ b;
   : x [ALWAYS Once Nothing] xs [ALWAYS Once Nothing] ->
     GHC.Types.:
       @ b (ds_dC6 x) (Data.List.Stream.mapx @ a @ b ds_dC6 xs)

I'll attach a cut-down example.

Changed 11 years ago by igloo

Attachment: Stream.hs added

Changed 11 years ago by igloo

Attachment: Stream.2.hs added

comment:2 Changed 11 years ago by igloo

Compile with:

ghc --make -O -Wall -XBangPatterns -XExistentialQuantification -XMagicHash -XTypeOperators Data.Stream Data.List.Stream -fforce-recomp

comment:3 Changed 11 years ago by simonpj

I know more or less what is happening now. Here's the diagnosis. Stream.2.hs contains this:

mapx f (x:xs) = f x : mapx f xs
{-# NOINLINE [1] mapx #-}

{-# RULES
    "mapx -> fusible" [~1] forall f xs.
        mapx f xs = unstream (mapy f (stream xs))
    "mapx -> unfused" [1] forall f xs.
        unstream (mapy f (stream xs)) = mapx f xs
  #-}

(Note that the second of these rules is an orphan.) After applying the fusible rule, at the end of Phase 1 GHC sees

mapx f (x:xs) = f x : unstream (mapy f (stream xs))

Now mapx looks non-recursive; after all, mapy is imported. So when the occurrence analyser runs in Phase 0 mapx is not marked as a loop breaker and can be inlined freely. However the unfused rule fires, and makes mapx recursive after all. Before the occurrence analyser runs again, though, the simplifier processes the next definition:

initsx (x:xs) = [] : mapx (x:) (initsx xs)

Since mapx is not a loop breaker, it's just inlined repeatedly; result infinite loop.

You may say that the occurrence analyser should be run again after finishing each definition. But that is only sticking plaster. Suppose we had

  mapx x = mapy x

(non-recursive, no rules) and imported that into a scope where there was an orphan rule

  RULES "x" mapy = mapx

Then you can see that would make GHC loop. (Inline mapx, run the RULE, and repeat.)

What to do? In general it's very hard to do much about RULES that give rise to loops, esp when they are orphans. When they are defined in the same module as the function they are RULES for, GHC is pretty good; but otherwise it's difficult.

In this case the obvious thing is to add

{-# NOINLINE [~1] mapx #-}

to stop it being inlined after Phase 1. That should cure the loop, but I'm not sure if the optimisations you have in mind would still work. (Curiously the exact inverse annotation is provided in the test case, saying don't inline until Phase 1.)

I'm surprised 6.8.3 works on this example; I suspect it's a fluke. (Should check this.)

Bottom line: I can't see a quick fix. Need to discuss how important this pattern is. At least we know what the problem is.

Simon

comment:4 Changed 11 years ago by rl

FWIW, I don't think it is necessary to do anything about this. The library code and the pattern in general are arguably wrong since the fusible rule really shouldn't be applied in the rhs of mapx. It is also easily fixed:

mapx = id mapz
mapz f (x:xs) = f x : mapz f xs
{-# INLINE [1] mapx #-}

{-# RULES
    "mapx -> fusible" [~1] forall f xs.
        mapx f xs = unstream (mapy f (stream xs))
    "mapx -> unfused" [1] forall f xs.
        unstream (mapy f (stream xs)) = mapz f xs
  #-}

or simply

mapx f xs = unstream (mapy f (stream xs))
mapz f (x:xs) = f x : mapz f xs
{-# INLINE mapx #-}

{-# RULES
  "mapx -> unfused" [1] forall f xs.
    unstream (mapy f (stream xs)) = mapz f xs
  #-}

comment:5 Changed 11 years ago by simonpj

Excellent. So who is responsible for the library stream-fusion? Can he or she take advantage of Roman's advice?

Meanwhile I'd like to leave this ticket open, to remind someone (ideally not me) to add some Wiki docs to http://haskell.org/haskellwiki/GHC/Using_rules to explain in a more standalone way what I documented above. Pretty please?

Simon

comment:6 Changed 11 years ago by dons

@simonpj

He/she is me, and yes, I'll apply Roman's advice.

comment:7 Changed 11 years ago by igloo

Priority: highnormal

comment:8 Changed 11 years ago by simonpj

Milestone: 6.10.1Not GHC
Owner: set to dons

comment:9 Changed 9 years ago by igloo

Milestone: Not GHC7.2.1
Priority: normalhigh
Type: bugtask
Type of failure: None/Unknown

Don, are you planning to write something about this on the wiki page?

We should either write it, or admit defeat and close the ticket.

comment:10 Changed 9 years ago by igloo

Resolution: wontfix
Status: newclosed

Admitting defeat.

Note: See TracTickets for help on using tickets.