[GHC] #7994: Make foldl into a good consumer

[GHC]

#7994: Make foldl into a good consumer
-------------------------------------+------------------------------------
        Reporter:  simonpj           |            Owner:
            Type:  bug               |           Status:  new
        Priority:  normal            |        Milestone:
       Component:  Compiler          |          Version:  7.6.3
      Resolution:                    |         Keywords:
Operating System:  Unknown/Multiple  |     Architecture:  Unknown/Multiple
 Type of failure:  None/Unknown      |       Difficulty:  Unknown
       Test Case:                    |       Blocked By:
        Blocking:                    |  Related Tickets:
-------------------------------------+------------------------------------

Comment (by nomeata):

 Heh, in the previous numbers, I passed the arguments to `nofib-analyze` in
 the wrong order. So please swap signs.

 I now made sure that the `oneShot` makes it into the unfolding for
 `foldl`, which is a clear win. Now, relative to `master` again, I get this
 very nice result:

 {{{
 --------------------------------------------------------------------------------
         Program           Size    Allocs   Runtime   Elapsed  TotalMem
      bernouilli          -0.1%     +1.5%      0.14      0.14     +0.0%
    cryptarithm2          -0.0%     -0.5%      0.01      0.01     +0.0%
             fem          -0.0%     -2.8%      0.02      0.02     +0.0%
            fft2          -0.1%    -55.9%      0.04      0.04     +0.0%
     gen_regexps          -0.0%    -33.6%      0.00      0.00     +0.0%
       integrate          -0.1%    -59.4%      0.13      0.13     -1.0%
         minimax          -0.0%    -15.6%      0.00      0.00     +0.0%
        nucleic2          +0.9%     +1.7%      0.05      0.05     +0.0%
             scs          -0.0%     -0.9%     +1.0%     +0.5%     +0.0%
          simple          -0.1%     -9.4%      0.14      0.14     +0.0%
            x2n1          -0.1%    -74.5%      0.01      0.01     +0.0%
 --------------------------------------------------------------------------------
             Min          -0.2%    -74.5%     -3.0%     -3.0%    -50.0%
             Max          +0.9%     +1.7%     +4.0%     +3.4%    +10.4%
  Geometric Mean          -0.0%     -3.7%     -0.2%     -0.3%     -0.6%
 }}}

 So it seems to be well worth turning `foldl` into a good consumer, even if
 the resulting code is not perfect for complicated cases like `foldl .. ..
 $ concat $ ..`.

 The increase for `bernouilli` comes from this code line:
 {{{
 sum $ zipWith (*) powers (tail $ tail combs)
 }}}
 where originally, because `sum` is not a good consumer, no list fusion
 happens and a `sum` specialized to `Integer` is used, while after the
 change, `sum` is fused with `zipWith`, but not further, so now we have
 {{{
 foldr2 (\x y r eta -> r (eta + (x * y))) id powers (tail $ tail combs) 0.
 }}}
 This means that we are have elimiated one intermediate list, but we are
 allocating PAP ’s on each iteration, which is more expensive (three
 arguments instead of two!). This is verified by looking at ticky numbers.
 Maybe foldr2 should have been inlined here. Or we just live with it.

 Is this (explicit `oneShot`ness-annotations using a magic function) a path
 we want to go?

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