#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

#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]:

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...

If it were added, it wouldn't be called `Queue`, because (unlike the real banker's queue) it's actually incapable of implementing `uncons` efficiently. It's really just a very limited, but very fast and light, list builder. If it's useful for things other than implementing `inits`, I would not be opposed to adding it in a separate module with some sufficiently clear name. I don't know enough about what sorts of things should and should not be provided by base to really comment much beyond that. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

Replying to [comment:1 nomeata]:

...

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...

If it were added, it wouldn't be called `Queue`, because (unlike the real banker's queue) it's actually incapable of implementing `uncons` efficiently. It's really just a very limited, but very fast and light,

#9345: Data.List.inits is extremely slow -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | 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 nomeata): Replying to [comment:4 dfeuer]: list builder. If it's useful for things other than implementing `inits`, I would not be opposed to adding it in a separate module with some sufficiently clear name. I don't know enough about what sorts of things should and should not be provided by base to really comment much beyond that. After reading more of the code I agree that this not too big “just for” inits, and I’m in favor of adding it. I also thought about ways to make it even faster. In particular, I tried to make `GHC` get rid of `Queue` and simply pass the three values around as arguments to the inner loop, and also make this fuse. With this definition it works: {{{ myScanl' :: (b -> a -> b) -> b -> [a] -> [b] myScanl' f a bs = build $ \c n -> a `seq` a `c` foldr (\b g x -> (let b' = f x b in b' `seq` (b' `c` g b'))) (\b -> b `seq` n) bs a initsQ2 :: [a] -> [[a]] initsQ2 = map toListQ . myScanl' snocQ emptyQ }}} and yields consistently better results than `initsQ`. (See attached report, `initsQ2`. Ignore `initsQDL`, thats the same, but with the rear list implemented as a difference list, which makes little difference.) This raises the question whether we want such a fusing strict `scanl'` in `Data.List` as well – it turned out to be useful here. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9345: Data.List.inits is extremely slow -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | 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 nomeata):

That's a neat idea. If I'm not mistaken, seq in the argument to build leads to a proof obligation to justify the safety of the fusion. Do you have a proof?

No. What exactly is the proof obligation in this case? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:8 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9345: Data.List.inits is extremely slow -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | 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): I've worked on it a bit, and if I'm not mistaken, `myScanl'` is safe if, whenever `a /= _|_`, and however I choose `evil`, `wrong`, and `f`, the "correct" expression {{{ e1 = a `evil` foldr evil wrong $ foldr (\b g x -> (let b' = f x b in b' `seq` (b' : g b'))) (\b -> b `seq` []) bs a }}} gives the same result as the fused expression {{{ e2 = a `evil` foldr (\b g x -> (let b' = f x b in b' `seq` (b' `evil` g b'))) (\b -> b `seq` wrong) bs a }}} But I'm not sure how to prove this or find a counterexample. Any ideas? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:10 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9345: Data.List.inits is extremely slow -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | 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:11 nomeata]:

I forgot to attach the report mentioned in comment:6, doing that now.

I was finally able to figure out how to read that file, and ''wow''. Those are some impressive results. If we can verify that the fusion on the left is safe, `initsQ2` is clearly the way to go. If we can't, it looks like we probably want to use the same thing, but without the `build`. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:12 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9345: Data.List.inits is extremely slow -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: Type: bug | Status: new Priority: normal | 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:13 nomeata]:

If we are worried about `seq` we can simply inline my `myScanl'` in `initsQ2` and replace the `seq` by `case` statements. Or leave the `seq` but argue that we are always applying them to values of type `Queue`, nothing breaks. And by that argument, as long as `myScanl` is only used for `initsQ2`, we should be safe.

I guess we only should worry about actually adding `scanl'` to the

We could also write `initsQ` in the completely inlined form, i.e. the core above. Plus point: No need to define the `Queue` datatype (which would be dead code anyways). Minus point: Doesn’t look elegant, no fusion

I believe I have now pretty much completed the proof. It's very ugly, because I don't have a sufficiently firm understanding of the higher-order fold involved, but here's the outline (minus horrors of immature mathematics): {{{ foldr evil wrong (scanl' f a bs) = foldr evil wrong $ a `seq` a : foldr (\b g x -> let b' = f x b in b' `seq` (b` : g b')) (\b -> b `seq` []) bs a -- Call this e1 a bs =?= (\c n -> a `seq` a `c` foldr (\b g x -> let b' = f x b in b' `seq` (b' `c` g b')) (\b -> b `seq` n) bs a) evil wrong -- Call this e2 a bs }}} There are two trivial base cases: {{{#!haskell e1 [] = e2 [] = evil a wrong e1 _|_ = e2 _|_ = evil a _|_ }}} Then the part I found difficult was proving that {{{#!haskell e1 a (q:bs) = evil a $ let b1' = f a q in b1' `seq` e1 b1' bs }}} to match the much simpler {{{#!haskell e2 a (q:bs) = evil a $ let b1' = f a q in b1' `seq` e2 b1' bs }}} For the infinite case, I don't know the formalism involved, but the general idea is that `evil` can only inspect a finite amount of its second argument before producing something, so we can always (temporarily) cut off the list somewhere past that. libraries, but that’s a different issue and should be discussed in #9356 I guess. Yes, but I now think we should. possible. It doesn't look bad at all, but I think it's pretty much write-only code—it's hard to see what it's doing and why, and hard to experiment with as we've been doing (swapping modular pieces around to try different things). Giving up possible fusion to attain less clarity does not look like a good plan to me. I'm going to do some benchmarking and profiling myself; I'd like to toss a fusable non-strict scanl into the ring for comparison, and ramp up the scale on some of the benchmarks to improve resolution. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:14 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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: | -------------------------------------+------------------------------------- Changes (by dfeuer): * status: new => patch Comment: My testing indicates that for large lists (e.g., 10,000 elements), Bertram Felgenhauer's simple and mostly very clean `initsT'` implementation is much better than any variation on `initsQ` when concatenating the results. I wrapped it up in `build` to get a ''little'' fusion potential (not essential) and uploaded a patch. I would still like very much to understand why using `take'` gives slightly better performance than using `take`, but it very clearly does. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:16 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 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? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:18 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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): I've attached a new patch without the `build` or inlining, and upgrading from `Int` to `Word` to double the number of lists we can pull from `inits . cycle` before the world explodes. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:20 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 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? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:22 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 nomeata): Thanks. I changed it to `foo = sum $ concat $ initsQ' $ [1..10000::Int]` (so that I don’t get any print-related stuff), and `-ddump-call-arity` gives me this code: {{{ #!hs [LclId, Arity=2, CallArity=2, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=2, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [0 0] 150 0}] c = \ (x :: [Int]) (y [OS=OneShot] :: Int -> Int) -> letrec { go [Occ=LoopBreaker] :: [Int] -> Int -> Int [LclId, Arity=1, CallArity=1, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=1, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [30] 110 60}] go = \ (ds :: [Int]) -> case ds of _ [Occ=Dead] { [] -> y; : y ys -> let { ds1 [OS=OneShot] :: Int -> Int [LclId, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=False, ConLike=False, WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 20 0}] ds1 = go ys } in \ (ds2 :: Int) -> ds1 ($fNumInt_$c+ ds2 y) }; } in go x foo :: Int [LclIdX, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=True, Arity=0, Value=False, ConLike=False, WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 634 0}] foo = c (++ ([]) (reverse1 ([]) ([]))) (letrec { go [Occ=LoopBreaker] :: Int# -> Queue Int -> Int -> Int [LclId, Arity=2, CallArity=2, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=2, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [80 20] 464 0}] go = \ (x :: Int#) (eta :: Queue Int) -> let { b :: Int [LclId, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 20}] b = I# x } in case eta of _ [Occ=Dead] { Queue dt f r -> let { a :: Word# [LclId, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=False, ConLike=False, WorkFree=False, Expandable=True, Guidance=IF_ARGS [] 1 0}] a = plusWord# dt (__word 1) } in let { r :: [Int] [LclId, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=True, ConLike=True, WorkFree=True, Expandable=True, Guidance=IF_ARGS [] 10 30}] r = : b r } in case word2Int# (popCnt# a) of _ [Occ=Dead] { __DEFAULT -> c (++ f (reverse1 r ([]))) (case x of wild { __DEFAULT -> go (+# wild 1) (Queue a f r); 10000 -> \ (eta :: Int) -> eta }); 1 -> let { ipv :: [Int] [LclId, Str=DmdType, Unf=Unf{Src=<vanilla>, TopLvl=False, Arity=0, Value=False, ConLike=False, WorkFree=False, Expandable=False, Guidance=IF_ARGS [] 60 0}] ipv = ++ f (reverse1 r ([])) } in c (++ ipv (reverse1 ([]) ([]))) (case x of wild { __DEFAULT -> go (+# wild 1) (Queue a ipv ([])); 10000 -> \ (eta :: Int) -> eta }) } }; } in go 1 a) (I# 0) }}} The `go` inside `foo` is the interesting function. Its type has three arguments, but its outermost lambda only takes two. This is common when fusing a left-fold. Only that Call Arity is not sufficient to see that we’d want this to be expanded to thre arguments (`CallArity=3`). Would `CallArity=3` be correct? Yes, because the recursive calls to `go` call it with two arguments, pass that to `c`, which calls it at most once (so no sharing could be lost) with at least one argument. Unfortunately, that information is currently not available to the call arity analysis (§5.1.1 in the paper linked above). Call Arity is a forward analysis, so it is hard to see how it could make use of that. And even if it did, it would still have to pass a function (in that case a PAP) to `c`... :-( -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:24 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#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 nomeata):

This doesn't seem to affect the problem, however.

Yes, I don’t think the problem in this particular case lies with init per se. I think it’s more like concat, but only when part of the recursion (the `c` above) is not inlined. That might also be what you observe.

I am curious if there is a way to manually force whatever's getting the wrong arity to get the right one

Not with list fusion as we have it right now, I think. It should work with https://github.com/takano-akio/ww-fusion (which I should follow up on again). I don’t think a rule for `concat (inits)` is worth it, but it may help us understand the problem better. I wonder if maybe the rule for `concat` can be rewritten so that the resulting recursion is nicer, but I don’t see it right now (but I’m too jetlagged to think anyways). -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:26 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9345: Data.List.inits is extremely slow -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: bug | Status: patch Priority: high | Milestone: 7.8.4 Component: Core | Version: 7.8.3 Libraries | 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: Phab:D329 | -------------------------------------+------------------------------------- Changes (by dfeuer): * cc: core-libraries-committee@… (added) * status: new => patch * differential: => Phab:D329 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:29 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9345: Data.List.inits is extremely slow -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: bug | Status: patch Priority: high | Milestone: 7.8.4 Component: Core | Version: 7.8.3 Libraries | 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: Phab:D329 | -------------------------------------+------------------------------------- Comment (by Joachim Breitner ): In [changeset:"cde3a77f9703966145cae481ee35f52dcca2cf7d/ghc"]: {{{ #!CommitTicketReference repository="ghc" revision="cde3a77f9703966145cae481ee35f52dcca2cf7d" Make Data.List.Inits fast Fixes #9345. Use a modified banker's queue to achieve amortized optimal performance for inits. The previous implementation was extremely slow. Reviewed By: nomeata, ekmett, austin Differential Revision: https://phabricator.haskell.org/D329 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:32 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9345: Data.List.inits is extremely slow -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: bug | Status: closed Priority: high | Milestone: 7.10.1 Component: Core | Version: 7.8.3 Libraries | Keywords: Resolution: fixed | 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: Phab:D329 | -------------------------------------+------------------------------------- Changes (by thoughtpolice): * milestone: 7.8.4 => 7.10.1 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:34 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#9345: Data.List.inits is extremely slow -------------------------------------+------------------------------------- Reporter: dfeuer | Owner: ekmett Type: bug | Status: closed Priority: high | Milestone: 7.8.4 Component: Core | Version: 7.8.3 Libraries | Keywords: Resolution: fixed | 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: Phab:D329 | -------------------------------------+------------------------------------- Changes (by thoughtpolice): * status: merge => closed Comment: Merged. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:36 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler