#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): Just to keep us on the same page, I rewrote `scanl'` like this so it can be written back to a simple form. {{{#!hs {-# NOINLINE [1] scanl' #-} scanl' :: (b -> a -> b) -> b -> [a] -> [b] scanl' f q ls = q `seq` q : (case ls of [] -> [] x:xs -> scanl' f (f q x) xs) {-# RULES "scanl'" [~1] forall f a bs . scanl' f a bs = build (\c n -> a `c` foldr (scanlFB' f c) (flipSeqScanl' n) bs a) "scanl'List" [1] forall f a bs . foldr (scanlFB' f (:)) (flipSeqScanl' []) bs a = tailScanl' f a bs #-} {-# INLINE [0] scanlFB' #-} scanlFB' f c = \b g x -> let b' = f x b in b' `seq` b' `c` g b' {-# INLINE [0] flipSeqScanl' #-} flipSeqScanl' = flip seq {-# NOINLINE [1] tailScanl' #-} tailScanl' f a bs = a `seq` foldr (scanlFB' f (:)) (flip seq []) bs a }}} This doesn't seem to affect the problem, however. I am curious if there is a way to manually force whatever's getting the wrong arity to get the right one. Bertram pointed out that fusing `inits` on the right with an expensive producer is ''really'' bad, and I realized that fusing it on the right with something that leads to lots of reboxing is also really bad. So for now, probably the best thing is just to NOINLINE inits altogether. Unrelatedly: I was successful in my quest to write rules to make `concat` and `inits` fuse into something that's actually good (in case anyone actually uses such a thing). Interestingly the arity/strictness analysis only works on it if it's inlined (maybe you can figure out a fix for that?): {{{#!hs -- We don't particularly like the idea of inlining this function, since it's -- a bit large, but it appears to be necessary to get the analyses to work -- right and avoid eating all available memory. Making this INLINE [0] to -- be able to rewrite it to a simpler form unfortunately seems to make it miss some -- analysis that speeds it up by a relatively small but still significant amount. -- There may be some way around this problem, but I haven't found it yet. {-# INLINE concatInitsFB #-} concatInitsFB xs 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::Int) 0 xs {-# RULES -- We might catch concat before it's rewritten. "concatInits1" forall xs . concat (inits xs) = build (concatInitsFB xs) -- If not, we might be able to recognize its rewritten form. "concatInits2" forall c n xs . foldr (\x y -> foldr c y x) n (inits xs) = concatInitsFB xs c n #-} }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9345#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler