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

[GHC]

#9345: Data.List.inits is extremely slow
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  bug         |           Status:  patch
              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:18 nomeata]:
 > I’m really worryied seeing `INLINE` on such a rather large function.
 Doesn’t that mean that we will never use the compiled `inits` from the
 library but rather re-compile it at every use site? That does not seem to
 be good. (Disclaimer: Have not actually tried it.)
 >
 > I have run criterion on HEAD earlier, I might be able to set it up
 again. Do you have a ready-to-run benchmark that you would like me to run?

 I think we can just skip the `build` and get rid of `INLINE` without any
 significant harm. The fusion potential with this definition is quite
 limited anyway. The most interesting-looking fusion opportunities (not
 enabled by that definition anyway) seem to be `inits/enumFromTo` and
 `concat/inits`. The former is great if things are, and remain, unboxed,
 and horrible otherwise, and we can't tell the difference, unfortunately.
 The latter might be worth thinking about, if anyone actually writes that.
 This looks very good in Core, if we can find a way to accomplish it:

 {{{#!hs
 concat (inits xs) = build (\cons nil ->
   let
     go _ _ []     = nil
     go n k (y:ys)
       | n == k    = go (n+1) 0 xs
       | otherwise = y `cons` go n (k+1) ys
   in go 1 0 xs)
 }}}

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