#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