[GHC] #9345: Data.List.inits is extremely slow

[GHC]

#9345: Data.List.inits is extremely slow
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  bug         |           Status:  new
              Priority:  high        |        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:              |
-------------------------------------+-------------------------------------
Changes (by dfeuer):

 * status:  patch => new


Comment:

 I worked with Bertram Felgenhauer a bit tonight, and it looks like he's
 right; initsQ2 really is better. Unfortunately, it appears that the
 implementation of `scanl'` given here has the potential to blow things up
 for `initsQ2` when combined with `concat`. In particular, if I do

 {{{#!hs
 main = print $ sum $ concat $ initsQ2 [1..10000::Int]
 }}}

 then it uses up all my RAM and takes forever. Interrupting fusion between
 `initsQ2` and `[1..1000]` does not help at all, but interrupting it
 between `concat` and `initsQ2` seems to work. Removing the `sum` also
 prevents it from using all my RAM. If I replace `sum` with `foldl' (+) 0`
 then it runs in a small amount of RAM, but allocation is still very high
 and it's very slow. I'm still struggling to tease apart the interactions
 here. One thing that ''seems'' clear is that at its worst, it fails to
 recognize that it can treat the lazy `foldl` of `sum` as a strict
 `foldl'`, which is disastrous. But that's not the only thing going wrong.

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