#14941: Switching direct type family application to EqPred (~) prevents inlining in code using vector (10x slowdown) -------------------------------------+------------------------------------- Reporter: nh2 | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Description changed by nh2: Old description:

{{{#!hs selectVectorDestructive2 :: (PrimMonad m, VG.Vector v e, Ord e, Show e, VG.Mutable v ~ vm) => Int -> v e -> vm (PrimState m) e -> Int -> Int -> m () -- slow

selectVectorDestructive2 :: (PrimMonad m, VG.Vector v e, Ord e, Show e) => Int -> v e -> VG.Mutable v (PrimState m) e -> Int -> Int -> m () -- fast }}}

These two functions are identical except one has `VG.Mutable v ~ vm` as a constraint, the other one has it in the type signature right of the `=>`.

The second function is 10x faster.

I would expect them to be equally fast.

The code of the functions is identical, I change only the type declaration.

The slowness happens because with the first function, inlining of primitives like `unsafeRead` does not happen, and thus also it boxes the `Int#`s back to `Int`s when calling `unsafeRead`.

In particular, in `-ddump-simpl`, the slow version has

{{{#!hs $wpartitionLoop2_rgEy :: forall (m :: * -> *) (vm :: * -> * -> *) e. (PrimMonad m, MVector vm e, Ord e) => vm (PrimState m) e -> GHC.Prim.Int# -> e -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> m Int $wpartitionLoop2_rgEy = \... -> let { endIndex_a7Ay :: Int ... endIndex_a7Ay = GHC.Types.I# ww2_sfZn } in ... (VGM.basicUnsafeRead ... endIndex_a7Ay) ... }}}

while the fast version has

{{{#!hs $w$spartitionLoop2_rgUN :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.MutableByteArray# GHC.Prim.RealWorld -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, Int #)

...

$spartitionLoop2_rgUP :: VG.Mutable VU.Vector (PrimState IO) Int -> Int -> Int -> Int -> Int -> Int -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, Int #) }}}

So with `VG.Mutable v (PrimState m) e` in the type signature, GHC managed to inline + specialise it all the way down to concrete types (`VUM.MVector`, `IO`, and `Int` as the element type), and consequently inline `basicUnsafeRead` on unboxed `Int#`.

But with `VG.Mutable v ~ vm`, ghc keeps `vm (PrimState m) e` all the way, passes around dictionaries, thus eventually cannot inline `basicUnsafeRead` and re-packs already unboxed values, like `endIndex_a7Ay = GHC.Types.I# ww2_sfZn`, before passing them into the non-inlined call of `basicUnsafeRead`, thus making a tight loop allocate that normally wouldn't allocate.

Why might rewriting the type signature in such a trivial way make this happen?

----

I have tested this on GHC 8.0.2, GHC 8.2.2, and GHC 8.5 HEAD commit cc4677c36ee.

Reproducer:

* https://github.com/nh2/haskell-quickselect-median-of- medians/blob/0efd6293e779fda2d864ec3d75329fb16b8af6d9/Main.hs#L506 * Running instructions are [https://github.com/nh2/haskell-quickselect- median-of-medians/commit/7a49d673990dfaebdb0ba837c3fbbaae0455dba0 in this commit message]; for short: `stack exec -- ghc -O --make Main.hs -rtsopts -ddump-simpl -dsuppress-coercions -fforce-recomp -ddump-to-file -fno- full-laziness && ./Main +RTS -sstderr` * For that file, I have pregenerated `-dverbose-core2core` output here: https://github.com/nh2/haskell-quickselect-median-of- medians/tree/0efd6293e779fda2d864ec3d75329fb16b8af6d9/slowness-analysis * I originally just wanted to write a fast median-of-medians implementation on ZuriHac 2017, but got totally derailed by this performance problem. The version of it that I link here is a total mess because of me mauling it to track down this performance issue.

Trying to increase `-funfolding-use-threshold` or `-funfolding-keeness- factor` did not change the situation.

New description: {{{#!hs selectVectorDestructive2 :: (PrimMonad m, VG.Vector v e, Ord e, Show e, VG.Mutable v ~ vm) => Int -> v e -> vm (PrimState m) e -> Int -> Int -> m () -- slow selectVectorDestructive2 :: (PrimMonad m, VG.Vector v e, Ord e, Show e) => Int -> v e -> VG.Mutable v (PrimState m) e -> Int -> Int -> m () -- fast }}} These two functions are identical except one has `VG.Mutable v ~ vm` as a constraint, the other one has it in the type signature right of the `=>`. The second function is 10x faster. I would expect them to be equally fast. The code of the functions is identical, I change only the type declaration. The slowness happens because with the first function, inlining of primitives like `unsafeRead` does not happen, and thus also it boxes the `Int#`s back to `Int`s when calling `unsafeRead`. In particular, in `-ddump-simpl`, the slow version has {{{#!hs $wpartitionLoop2_rgEy :: forall (m :: * -> *) (vm :: * -> * -> *) e. (PrimMonad m, MVector vm e, Ord e) => vm (PrimState m) e -> GHC.Prim.Int# -> e -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> m Int $wpartitionLoop2_rgEy = \... -> let { endIndex_a7Ay :: Int ... endIndex_a7Ay = GHC.Types.I# ww2_sfZn } in ... (VGM.basicUnsafeRead ... endIndex_a7Ay) ... }}} while the fast version has {{{#!hs $w$spartitionLoop2_rgUN :: GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.MutableByteArray# GHC.Prim.RealWorld -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.Int# -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, Int #) ... $spartitionLoop2_rgUP :: VG.Mutable VU.Vector (PrimState IO) Int -> Int -> Int -> Int -> Int -> Int -> GHC.Prim.State# GHC.Prim.RealWorld -> (# GHC.Prim.State# GHC.Prim.RealWorld, Int #) }}} So with `VG.Mutable v (PrimState m) e` in the type signature, GHC managed to inline + specialise it all the way down to concrete types (`VUM.MVector`, `IO`, and `Int` as the element type), and consequently inline `basicUnsafeRead` on unboxed `Int#`. But with `VG.Mutable v ~ vm`, ghc keeps `vm (PrimState m) e` all the way, passes around dictionaries, thus eventually cannot inline `basicUnsafeRead` and re-packs already unboxed values, like `endIndex_a7Ay = GHC.Types.I# ww2_sfZn`, before passing them into the non-inlined call of `basicUnsafeRead`, thus making a tight loop allocate that normally wouldn't allocate. Why might rewriting the type signature in such a trivial way make this happen? ---- I have tested this on GHC 8.0.2, GHC 8.2.2, and GHC 8.5 HEAD commit cc4677c36ee (edit: in which case I commented out the quickcheck and criterion related stuff because their deps don't build there yet). Reproducer: * https://github.com/nh2/haskell-quickselect-median-of- medians/blob/0efd6293e779fda2d864ec3d75329fb16b8af6d9/Main.hs#L506 * Running instructions are [https://github.com/nh2/haskell-quickselect- median-of-medians/commit/7a49d673990dfaebdb0ba837c3fbbaae0455dba0 in this commit message]; for short: `stack exec -- ghc -O --make Main.hs -rtsopts -ddump-simpl -dsuppress-coercions -fforce-recomp -ddump-to-file -fno-full- laziness && ./Main +RTS -sstderr` * For that file, I have pregenerated `-dverbose-core2core` output here: https://github.com/nh2/haskell-quickselect-median-of- medians/tree/0efd6293e779fda2d864ec3d75329fb16b8af6d9/slowness-analysis * I originally just wanted to write a fast median-of-medians implementation on ZuriHac 2017, but got totally derailed by this performance problem. The version of it that I link here is a total mess because of me mauling it to track down this performance issue. Trying to increase `-funfolding-use-threshold` or `-funfolding-keeness- factor` did not change the situation. -- -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14941#comment:2 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14941: Switching direct type family application to EqPred (~) prevents inlining in code using vector (10x slowdown) -------------------------------------+------------------------------------- Reporter: nh2 | Owner: (none) Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by nh2): This seems to be unrelated to type families and only a problem with `~` in general, because: I now also found a case where using `(val ~ Int) =>` produces slower code than subsituting `val` with `Int` syntactically, or using `SPECIALISE`. {{{ myfun :: forall val . (Eq val, Show val, val ~ Int) => Mytype1 val -> Mytype2 val -> Mytype3 -> Mytype4 -> Mytype5 -> Mytype6 -> IO () }}} is slow, but {{{ {-# SPECIALIZE myfun :: Mytype1 Int -> Mytype2 Int -> Mytype3 -> Mytype4 -> Mytype5 -> Mytype6 -> IO () #-} myfun :: forall val . (Eq val, Show val, val ~ Int) => Mytype1 val -> Mytype2 val -> Mytype3 -> Mytype4 -> Mytype5 -> Mytype6 -> IO () }}} is fast (in my case, a 30% performance difference). Diffing the output of `-ddump-simpl -ddump-to-file -dsuppress-idinfo -dsuppress-coercions -dsuppress-module-prefixes -dsuppress-uniques` shows how the call looks different from a module that calls `myfun`: `val ~ Int` version: {{{ $d~~ :: (Int :: *) ~~ (Int :: *) $d~~ = Eq# @ * @ * @ Int @ Int @~ ... ... $wmyfun @ Int $fEqInt ($d~~ `cast` ...) y wild mything1 ipv7 mything2 ww1 w9) ... }}} `SPECIALISE`d `val ~ Int` version: {{{ myfun y wild mything1 ipv7 mything2 ww1 }}} I would have expect that after the simplifier has run, GHC would have used all information it has to produce the best core (e.g. use the fact that it knows `val ~ Int` even without `SPECIALISE`), but it did not. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14941#comment:4 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14941: Switching direct type family application to EqPred (~) prevents inlining in code using vector (10x slowdown) -------------------------------------+------------------------------------- Reporter: nh2 | Owner: davide Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by davide): * owner: (none) => davide -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14941#comment:6 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14941: Switching direct type family application to EqPred (~) prevents inlining in code using vector (10x slowdown) -------------------------------------+------------------------------------- Reporter: nh2 | Owner: davide Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by davide): * Attachment "simple_case.zip" added. Simple case and benchmark. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14941 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#14941: Switching direct type family application to EqPred (~) prevents inlining in code using vector (10x slowdown) -------------------------------------+------------------------------------- Reporter: nh2 | Owner: davide Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 8.2.2 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Runtime | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Thanks for the simpler example. I think I now understand what is going on. It's all to do with strictness analysis. Consider this function, and suppose it is strict in x: {{{ f1 :: Int -> blah f1 x = ...(case x of I# y -> ...)... }}} The strictness analysis sees that `f1` is strict in `x` and we get a w/w split {{{ f1 :: Int -> blah f1 x = case x of I# y -> $wf y $wf1 :: Int# -> blah $wf1 y = let x = I# y in ...original body of f... }}} Now suppose that we have {{{ type family F a type instance F Bool = Int f2 :: F Bool -> blah f2 x = ...same as before... }}} In fact the strictness analysis still sees that `f2` is strict in `x`, and worker wrapper works too -- all by using the family instances. We get this {{{ f2 :: F Bool -> blah f2 x = case (x |> g1) of I# y -> $wf2 y $wf2 :: Int# -> blah $wf2 y = let x = (I# y) |> sym g in ..as before... }}} Here `g` is a coercion `g :: F Bool ~ Int`, constructed from the family instances. This coersionn is generated by `topNormaliseType_maybe`, itself called from `deepSplitCprType_maybe` in `WwLib`, during worker/wrapper generation. But it's harder if the coercion is purely local. Let's start with this (yes I know you can't write `(~#)` in source Haskell but imagine this is Core: {{{ f3 :: forall a. (a ~# Int) => a -> blah f3 a (g :: (a ~# Int) (x :: a) = ...as before... }}} What we'd like is this: {{{ f3 :: forall a. (a ~# Int) => a -> blah f3 a (g :: (a ~# Int) (x :: a) = case (x |> g) of I# y -> $wf3 a g y $wf3 :: forall a. (a ~# Int) => Int# -> blah $wf3 a g y = let x = (I# y) |> sym g in ...as before... }}} but alas neither the demand analyser, nor the worker/wrapper generator are clever enough to do this. We need a kind of `normaliseType` that can take some local "givens" as well as the top-level family instance envs. This has the same ring as something Ryan wanted in the coverage checker. It's not obvious exactly what "should work". Eg what about `(Int ~# a)`, or even `([Int] ~# [a])`? Finally, there is the question of `(~)` vs `(~#)`. I think we are very aggressive about unboxing `(~)` constraints, so I'd like this: {{{ f4 :: forall a. (a ~ Int) => a -> blah f4 a (g :: (a ~ Int) (x :: a) = case g of MkTwiddle (g2 :: a ~# Int) -> case (x |> g2) of I# y -> $wf4 a g2 y $wf4 :: forall a. (a ~# Int) => Int# -> blah $wf4 a g2 y = let x = (I# y) |> sym g2 g = MkTwiddle g2 in ...as before... }}} Making all this happen will take some work though. How important is it. I'm tempted to say "don't write types like that"! (Although the type checker goes to some trouble to support them well.) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/14941#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler