[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:              |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 Replying to [comment:22 nomeata]:
 > Didn’t look at the core yet, but this might be a case of non-linear
 recursion where an arity analysis in insufficient to get good code for a
 left fold, see 5.1.1 in
 http://pp.ipd.kit.edu/uploads/publikationen/breitner14callarity.pdf.
 >
 > I can have a closer look later. Can you, with these examples, please
 always include one complete self-contained file? Otherwise there is a risk
 that I might be testing with the wrong version of inits/scanl'/whatever. I
 assume you are on GHC HEAD?

 I've attached a complete, self-contained test case. As I mentioned in an
 email, you should keep a close eye on RAM usage or run this program with
 heap limits set if you don't want to crash your computer. If this is an
 arity analysis problem that's too hard to fix, we can work around it by
 writing `inits xs = don'tFuse . map toListQ . scanl' snocQ emptyQ` to
 ensure that `inits` doesn't fuse on the problematic (and, in fact, rather
 unimportant) side.

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