Re: [GHC] #9398: Data.List.cycle is not a good producer

4 Aug 2014

      #9398: Data.List.cycle is not a good producer
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  bug         |           Status:  new
              Priority:  normal      |        Milestone:  7.8.4
             Component:              |          Version:  7.8.3
  libraries/base                     |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Easy (less than 1
  Unknown/Multiple                   |  hour)
       Type of failure:  Runtime     |       Blocked By:
  performance bug                    |  Related Tickets:
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by nomeata):

 Don’t be discouraged! I think this is very much worth it, and if people
 use `cycle` in list comprehensions (which they likely do), there might be
 real-world benefit in this. We just need to avoid regressions.

 I tried to reproduce your findings. I do observe the higher allocation,
 but the accumulator `Int#` is still unboxed. The extra allocations seem to
 stem from the `ys1` allocated here:

 {{{
 Rec {
 go :: [GHC.Types.Int] -> GHC.Prim.Int# -> GHC.Types.Int
 go =
   \ (ds :: [GHC.Types.Int]) ->
     case ds of _ {
       [] -> Main.main_cyc;
       : y ys ->
         let {
           ys1 :: GHC.Prim.Int# -> GHC.Types.Int
           ys1 = go ys } in
         \ (eta :: GHC.Prim.Int#) ->
           case GHC.Prim.tagToEnum# (GHC.Prim.<=# eta 1) of _ {
             GHC.Types.False ->
               case y of _ { GHC.Types.I# x ->
               case ys1 (GHC.Prim.-# eta 1) of _ { GHC.Types.I# y1 ->
               GHC.Types.I# (GHC.Prim.+# (GHC.Prim.*# x 13) y1)
               }
               };
             GHC.Types.True ->
               case y of _ { GHC.Types.I# x -> GHC.Types.I# (GHC.Prim.*# x
 13) }
           }
     }

 Main.main_cyc :: GHC.Prim.Int# -> GHC.Types.Int
 Main.main_cyc = go lvl9
 end Rec }
 }}}

 This is an interesting case. It seems to be a shortcoming in the call
 arity analysis: One might think it should be able to infer that `go` is
 always called with two arguments (and hence move the `\eta` out of the
 `let` and `case`).

 But it (rightfully) doesn’t do that because `main_cyc` is a thunk, and
 eta-expanding it would duplicate the case analysis done by `case ds`.

 The regular arity analysis also refuses to improve that code, for a
 similar reason: It considers to move the `\eta` up, but it would escape
 the `let ys1`, and the arity analysis is unable to determine if that would
 be expensive or not.

 Interesting case!

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9398#comment:19
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler