[GHC] #9345: Data.List.inits is extremely slow
GHC
ghc-devs at haskell.org
Mon Sep 1 06:09:00 UTC 2014
#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
More information about the ghc-tickets
mailing list