[GHC] #13227: Loss of full laziness in mapFB

2 Feb 2017

      #13227: Loss of full laziness in mapFB
-------------------------------------+-------------------------------------
           Reporter:  simonpj        |             Owner:
               Type:  bug            |            Status:  new
           Priority:  normal         |         Milestone:
          Component:  Compiler       |           Version:  8.0.1
           Keywords:                 |  Operating System:  Unknown/Multiple
       Architecture:                 |   Type of failure:  None/Unknown
  Unknown/Multiple                   |
          Test Case:                 |        Blocked By:
           Blocking:                 |   Related Tickets:
Differential Rev(s):                 |         Wiki Page:
-------------------------------------+-------------------------------------
 I've just discovered this
 {{{
 g4 x expensive ys = let h = \7 -> y + expensive x
                     in map h ys
 }}}
 Of course we'd expect the `(expensive x)` call to be floated out of the
 `\y`-abstraction, so that it is only done once.

 But it isn't! Here's the simplified core with -O:
 {{{
 g4 = \ (@ b_aPG)
        (@ p_atr)
        ($dNum_aPP :: Num b)
        (x_arW :: p)
        (expensive_arX :: p -> b)
        (ys_arY :: [b]) ->
        map @ b @ b
          (\ (y_as0 [OS=ProbOneShot] :: b) ->
             + @ b $dNum_aPP y_as0 (expensive_arX x_arW))
          ys_arY
 }}}
 Yikes!  What is happening?

 Answer: look at that suspicious `ProbOneShot` on the `\y` above.  Read
 `Note [Computing one-shot info, and ProbOneShot]` in `Demand.hs`.

 When `FloatOut` runs we have
 {{{
 g4 = \ (@ b_aPL)
        (@ p_atw)
        ($dNum_aPU :: Num b)
        (x_as1 :: p)
        (expensive_as2 :: p -> b)
        (ys_as3 :: [b]) ->
        GHC.Base.build @ b
          (\ (@ b1_aQs)
             (c_aQt [OS=OneShot] :: b -> b1 -> b1)
             (n_aQu [OS=OneShot] :: b1) ->
             GHC.Base.foldr @ b @ b1
               (GHC.Base.mapFB @ b @ b1 @ b
                  c_aQt
                  (\ (y_as5 [OS=ProbOneShot] :: b) ->
                     + @ b $dNum_aPU y_as5 (expensive_as2 x_as1)))
               n_aQu
               ys_as3)
 }}}
 Why is the `\y` marked `ProbOneShot`?  Because the occurrence analyser
 marked it so, based on the cardinality info from `mapFB`, even though
 `mapFB` was not saturated.

 So `Demand.argsOneShots` makes a deliberate choice to play risky, and that
 choice backfires badly for use of `map`.  Not good!

 The offending commit, which introduced this behaviour, is (I think)
 {{{
 commit 80989de947dc7edb55999456d1c1e8c337efc951
 Author: Simon Peyton Jones <simonpj@microsoft.com>
 Date:   Fri Nov 22 17:13:05 2013 +0000

     Improve the handling of used-once stuff

     Joachim and I are committing this onto a branch so that we can share
 it,
     but we expect to do a bit more work before merging it onto head.

     Nofib staus:
       - Most programs, no change
       - A few improve
       - A couple get worse (cacheprof, tak, rfib)
     Investigating the "get worse" set is what's holding up putting this
     on head.

     The major issue is this.  Consider

         map (f g) ys

     where f's demand signature looks like

        f :: <L,C1(C1(U))> -> <L,U> -> .

     So 'f' is not saturated.  What demand do we place on g?
     Answer
             C(C1(U))
     That is, the inner C1 should stay, even though f is not saturated.

     I found that this made a significant difference in the demand
 signatures
     inferred in GHC.IO, which uses lots of higher-order exception
 handlers.

     I also had to add used-once demand signatures for some of the
     'catch' primops, so that we know their handlers are only called once.
 }}}
 The commit isn't explicit about exactly what the "significant differences"
 are.  Moreover note that in the comment the outer C1 is replaced by C, but
 nothing like that seems to happen in the code.

 This needs investigation.

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/13227>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

GHC

tags

participants (1)