GitLab

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>
      }