Skip-less stream fusion: a missed opportunity
A simple stream chain
chain :: Int -> Int
chain = sum . filter even . enumFromTo 1
doesn't fuse under a Skip-less stream on GHC 8.2-rc3 -O2.
Benchmarked against a Skip stream (LLVM backend):
benchmarking Skip-less
time 248.9 ms (243.3 ms .. 257.3 ms)
0.998 R² (0.995 R² .. 0.999 R²)
mean 250.9 ms (248.1 ms .. 254.7 ms)
std dev 5.985 ms (4.831 ms .. 7.311 ms)
benchmarking Skip
time 61.26 ms (60.39 ms .. 62.44 ms)
0.998 R² (0.997 R² .. 0.999 R²)
mean 62.45 ms (61.96 ms .. 62.91 ms)
std dev 1.387 ms (1.190 ms .. 1.669 ms)
Relevant core (chain1 is Skip-less, chain2 has Skip):
-- RHS size: {terms: 51, types: 27, coercions: 0, joins: 1/2}
Main.$wchain1 [InlPrag=NOINLINE] :: Int# -> Int#
[GblId, Arity=1, Caf=NoCafRefs, Str=<S,U>]
Main.$wchain1
= \ (ww_s9ep :: Int#) ->
letrec {
$wloop_s9ea [InlPrag=[0], Occ=LoopBreaker] :: Int# -> Step1 Int Int
[LclId, Arity=1, Str=<S,U>, Unf=OtherCon []]
$wloop_s9ea
= \ (ww1_s9e8 :: Int#) ->
case tagToEnum# @ Bool (># ww1_s9e8 ww_s9ep) of {
False ->
case remInt# ww1_s9e8 2# of {
__DEFAULT -> $wloop_s9ea (+# ww1_s9e8 1#);
0# ->
Main.Yield1
@ Int @ Int (GHC.Types.I# (+# ww1_s9e8 1#)) (GHC.Types.I# ww1_s9e8)
};
True -> Main.Done1 @ Int @ Int
}; } in
joinrec {
$wloop1_s9el [InlPrag=[0], Occ=LoopBreaker] :: Int# -> Int# -> Int#
[LclId[JoinId(2)], Arity=2, Str=<S,U><S,U>, Unf=OtherCon []]
$wloop1_s9el (ww1_s9ef :: Int#) (ww2_s9ej :: Int#)
= case $wloop_s9ea ww2_s9ej of {
Done1 -> ww1_s9ef;
Yield1 s'_a497 x_a498 ->
case x_a498 of { GHC.Types.I# y_a66i ->
case s'_a497 of { GHC.Types.I# ww4_X9hA ->
jump $wloop1_s9el (+# ww1_s9ef y_a66i) ww4_X9hA
}
}
}; } in
jump $wloop1_s9el 0# 1#
-- RHS size: {terms: 33, types: 9, coercions: 0, joins: 1/1}
Main.$wchain2 [InlPrag=NOINLINE] :: Int# -> Int#
[GblId, Arity=1, Caf=NoCafRefs, Str=<S,U>]
Main.$wchain2
= \ (ww_s9dZ :: Int#) ->
joinrec {
$wloop_s9dV [InlPrag=[0], Occ=LoopBreaker] :: Int# -> Int# -> Int#
[LclId[JoinId(2)], Arity=2, Str=<S,U><S,U>, Unf=OtherCon []]
$wloop_s9dV (ww1_s9dP :: Int#) (ww2_s9dT :: Int#)
= case tagToEnum# @ Bool (># ww2_s9dT ww_s9dZ) of {
False ->
case remInt# ww2_s9dT 2# of {
__DEFAULT -> jump $wloop_s9dV ww1_s9dP (+# ww2_s9dT 1#);
0# -> jump $wloop_s9dV (+# ww1_s9dP ww2_s9dT) (+# ww2_s9dT 1#)
};
True -> ww1_s9dP
}; } in
jump $wloop_s9dV 0# 1#
The code was adapted from M. Snoyman's blog post "Iterators and Streams in Rust and Haskell".