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

[GHC]

#9345: Data.List.inits is extremely slow
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |             Owner:
                  Type:  bug         |            Status:  new
              Priority:  normal      |         Milestone:
             Component:              |           Version:  7.8.3
  libraries/base                     |          Keywords:
            Resolution:              |  Operating System:  Unknown/Multiple
Differential Revisions:              |   Type of failure:  Runtime
          Architecture:              |  performance bug
  Unknown/Multiple                   |         Test Case:
            Difficulty:  Easy (less  |          Blocking:
  than 1 hour)                       |
            Blocked By:              |
       Related Tickets:              |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 Replying to [comment:1 nomeata]:
 > Interesting. Can you elaborate (just for the record here) when `initsQ`
 is faster?
 >
 > I would find it strange to add such complexity “just for” `inits`. Now,
 if we had such a `Queue` type (which looks useful in general) in base
 anyways, using it would be a different story...
 >
 > How is the performance when the existing `Seq` is used instead of
 `Queue`?

 I'm attaching the Criterion comparison of `initsR`, `initsQ`, and a new
 `initsS` that uses `Data.Sequence`. On most tests, `initsS` is much slower
 than `initsQ`, reflecting the fact that sequences are much heavier data
 structures than these snoc-builder almost-queues.

 `initsQ` is faster when the heads (or more generally the first few
 elements) of several of the elements of the result list are inspected by
 traversing the result list. If you just calculate `head $ initsR [1..n] !!
 n`, then the time required to reverse the final list can be amortized over
 the steps in `!!n`. But if you were to calculate, for some inexplicable
 reason, `sum $ map head $ initsR [1..n]`, you only have `n` steps over
 which to amortize `n^2` work. The vague notion I've had in the back of my
 mind for a vaguely realistic example is some sort of breadth-first
 traversal of `inits [1..n]`.

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