#10108: Dramatic slowdown with -O2 bytestream and list streams combined. -------------------------------------+------------------------------------- Reporter: Truman | Owner: Type: bug | Status: closed Priority: normal | Milestone: 7.10.2 Component: Compiler | Version: 7.8.4 Resolution: invalid | Keywords: Operating System: Linux | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | break_in.hs Related Tickets: | Blocking: | Differential Revisions: -------------------------------------+------------------------------------- Changes (by rwbarton): * status: new => closed * resolution: => invalid Comment: It's a bug or limitation in the stream-fusion package. This simpler program has the same problem: {{{ import qualified Data.List.Stream as SL bad_sum :: [Int] -> Int bad_sum xs = if null xs then 0 else head xs + bad_sum (SL.tail xs) main = print $ bad_sum [1..20000] }}} The reason is this rewrite rule for `SL.tail`: {{{ {-# RULES "tail -> fusible" [~1] forall xs. tail xs = unstream (Stream.tail (stream xs)) --"tail -> unfused" [1] forall xs. -- unstream (Stream.tail (stream xs)) = tail xs #-} }}} Note that the second rule is commented out! So each recursive call adds a layer of something similar to `foldr (:) []` to the remainder of the list, and the total time is quadratic. You might submit a bug report on stream-fusion, though I don't know whether it is still maintained. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/10108#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler