#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