GHC 8.10 performance regression (rewrite rule and/or simplifer related)
Hi, the ticket is created based on https://www.reddit.com/r/haskell/comments/mwlj81/is_there_known_rewrite_rule_regression_in_810/. I'm a newbie so my apologies the info here are kind of messy copy-paste.
Hi, I'm trying to figure out a performance regression between ghc 8.8 vs. 8.10 in this code. I've seen some rewrite rules are not firing in 8.10, but they do in 8.8.
Here is the diff -u 88.log 810.log, where I can see two missing fired BUILTIN $p1Monad p1Applicative rules then the rest of SC:
w$ rules. The linked logs have ghc dump core code.
Rule fired: unpack (GHC.Base)
Rule fired: unpack (GHC.Base)
Rule fired:
SPEC/Main $fMembertr @ (State Int) @ '[State Int, Identity] (Main)
Rule fired: Class op inj (BUILTIN)
Rule fired: SPEC/Main freer @ '[State Int, Identity] (Main)
Rule fired: Class op inj (BUILTIN)
Rule fired: SPEC/Main freer @ '[State Int, Identity] (Main)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op $p1Applicative (BUILTIN)
Rule fired: Class op fmap (BUILTIN)
Rule fired: Class op >>= (BUILTIN)
Rule fired: Class op return (BUILTIN)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op pure (BUILTIN)
Rule fired: Class op >>= (BUILTIN)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op pure (BUILTIN)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op pure (BUILTIN)
Rule fired: unpack-list (GHC.Base)
Rule fired: unpack-list (GHC.Base)
Rule fired: Class op $p1Monad (BUILTIN)
Rule fired: Class op >>= (BUILTIN)
Rule fired: Class op >>= (BUILTIN)
-Rule fired: Class op $p1Monad (BUILTIN)
-Rule fired: Class op $p1Applicative (BUILTIN)
-Rule fired: SC:$w$sfreer0 (Main)
-Rule fired: Class op >>= (BUILTIN)
-Rule fired: Class op >>= (BUILTIN)
-Rule fired: SC:$w$sfreer0 (Main)
-Rule fired: SC:$w$sfreer0 (Main)
100x slow down 8.8 vs. 8.10 runs.
benchmarking Countdown Bench/countDown
-time 19.19 μs (19.13 μs .. 19.25 μs)
- 1.000 R² (1.000 R² .. 1.000 R²)
-mean 19.18 μs (19.13 μs .. 19.26 μs)
-std dev 200.2 ns (125.4 ns .. 365.9 ns)
+time 1.178 ms (1.173 ms .. 1.184 ms)
+ 1.000 R² (0.999 R² .. 1.000 R²)
+mean 1.181 ms (1.172 ms .. 1.202 ms)
+std dev 42.91 μs (15.26 μs .. 86.97 μs)
From above linked logs:
In GHC 8.8.4, main8 calls a complete monomorphic $sfreer1 that can takes a higher order function like f x -> m x (i.e. both f and m become concrete types).
-- RHS size: {terms: 3, types: 2, coercions: 0, joins: 0/0}
main9 :: Applicative (StateT Int Identity)
main9 = $fApplicativeStateT $fFunctorIdentity $fMonadIdentity
Rec {
-- RHS size: {terms: 22, types: 74, coercions: 5, joins: 0/0}
$sfreer1
:: ((forall x.
Union '[State Int, Identity] x -> Int -> Identity (x, Int))
~R# (forall x.
Union '[State Int, Identity] x -> StateT Int Identity x))
-> Applicative (StateT Int Identity) => Int -> Identity (Int, Int)
$sfreer1
= \ (sg
:: (forall x.
Union '[State Int, Identity] x -> Int -> Identity (x, Int))
~R# (forall x.
Union '[State Int, Identity] x -> StateT Int Identity x))
(sc :: Applicative (StateT Int Identity))
(eta :: Int) ->
case eta of wild { I# x ->
case <=# x 0# of {
__DEFAULT -> $sfreer1 @~ <Co:1> sc (I# (-# x 1#));
1# -> ((pure sc wild) `cast` <Co:4>) wild
}
}
end Rec }
-- RHS size: {terms: 9, types: 8, coercions: 40, joins: 0/0}
main8 :: Int -> Identity (Int, Int)
main8
= \ (w :: Int) ->
case ($sfreer1 @~ <Co:31> main9 w) `cast` <Co:4> of { (a1, b1) ->
(b1, a1) `cast` <Co:5>
}
In GHC 8.10.4, it seems main8 trying to figure out m in seperate and indirect steps, where Applicative (StateT Int Identity) parameter in 8.8 becomes (@ m) (w :: Monad m) unknown dictionary (even though types for it are known as main10 shows). From there, I'm kind of lost what's the cause what's the effect.
-- RHS size: {terms: 10, types: 63, coercions: 0, joins: 0/0}
$sfreer1
:: forall (m :: * -> *).
Monad m =>
(forall x. Union '[State Int, Identity] x -> m x) -> m Int
$sfreer1
= \ (@ (m :: * -> *))
(w :: Monad m)
(w1 :: forall x. Union '[State Int, Identity] x -> m x) ->
case w of { C:Monad ww1 ww2 ww3 ww4 -> $w$sfreer ww1 ww2 w1 }
-- RHS size: {terms: 1, types: 0, coercions: 21, joins: 0/0}
$sfreer :: Eff '[State Int, Identity] Int
$sfreer = $sfreer1 `cast` <Co:21>
end Rec }
-- RHS size: {terms: 2, types: 2, coercions: 0, joins: 0/0}
main10 :: Monad (StateT Int Identity)
main10 = $fMonadStateT $fMonadIdentity
-- RHS size: {terms: 27, types: 82, coercions: 267, joins: 0/0}
main9
:: forall x.
Union '[State Int, Identity] x -> Int -> Identity (x, Int)
main9
= \ (@ x) (u1 :: Union '[State Int, Identity] x) (eta :: Int) ->
case u1 of { Union @ t1 dt a1 ->
case dt of {
__DEFAULT -> (a1 `cast` <Co:9>, eta) `cast` <Co:5>;
0## ->
case a1 `cast` <Co:7> of {
Get co -> (eta, eta) `cast` <Co:123>;
Modify co f ->
case f eta of vx { I# ipv -> ((), vx) `cast` <Co:123> }
}
}
}
-- RHS size: {terms: 10, types: 11, coercions: 64, joins: 0/0}
main8 :: Int -> Identity (Int, Int)
main8
= \ (w :: Int) ->
case (((($sfreer `cast` <Co:20>) main10 (main9 `cast` <Co:31>))
`cast` <Co:4>)
w)
`cast` <Co:4>
of
{ (a1, b1) ->
(b1, a1) `cast` <Co:5>
}