[GHC] #10108: Dramatic slowdown with -O2 bytestream and list streams combined.

[GHC]

#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