#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): This originated from commentary on Phab:D2024, though you don't have to read that to understand this ticket. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:1 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by tdammers): * cc: tdammers (added) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:3 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Applying the `coercionKind` patch brings down compilation time for the `Grammar.hs` example from #14683 to about 30 seconds. Relevant profiling data: {{{ Wed Jan 24 14:33 2018 Time and Allocation Profiling Report (Final) ghc-stage2 +RTS -p -RTS -B/home/tobias/well- typed/devel/ghc/inplace/lib Grammar.hs -ddump-stg -ddump-simpl -ddump-to- file -fforce-recomp total time = 32.48 secs (32475 ticks @ 1000 us, 1 processor) total alloc = 43,424,804,608 bytes (excludes profiling overheads) COST CENTRE MODULE SRC %time %alloc CoreTidy HscMain compiler/main/HscMain.hs:1253:27-67 20.3 22.6 subst_ty TyCoRep compiler/types/TyCoRep.hs:2225:28-32 17.7 23.9 Stg2Stg HscMain compiler/main/HscMain.hs:1489:12-44 13.9 16.3 simplCast Simplify compiler/simplCore/Simplify.hs:871:62-87 12.8 10.7 simplCast-addCoerce Simplify compiler/simplCore/Simplify.hs:1225:53-71 11.6 9.2 tc_rn_src_decls TcRnDriver compiler/typecheck/TcRnDriver.hs:(494,4)-(556,7) 6.4 4.6 addCoerce-pushCoTyArg Simplify compiler/simplCore/Simplify.hs:(1236,12)-(1237,72) 5.0 4.3 preprocessFile GhcMake compiler/main/GhcMake.hs:(2416,1)-(2443,37) 1.0 0.0 coercionKind Coercion compiler/types/Coercion.hs:1707:3-7 1.0 1.9 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:7 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: | Unknown/Multiple Type of failure: None/Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Oh wait, I think I get it. Never mind. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:9 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Changes (by simonpj): * failure: None/Unknown => Compile-time performance bug -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:11 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

Refactoring coercionRoleKinds / coercionRole gives us another

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): performance boost That is totally bonkers (in a good way). From 43G down to 29G from that one change. Wow. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:13 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): I can take a look at comment:10 on Friday, but not before. Also, tdammers, thanks thanks thanks for doing this! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:15 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): * In your `coercionRole`, `get_app` never uses its second argument! So you can get rid of it entirely I think {{{ go (InstCo co _) = go co }}} * `Note [Nested InstCos]` applies to `coercionKind` but not, I think, to `coercionRole` * `Note [Computing a coercion kind and role]` claims that computing the result of `coercionRole (NthCo d co)` requires `coercionKind`. But it manifestly does not. '''Richard''' is this note simply wrong? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:19 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:20 goldfire]:

Thanks for finding `Note [Computing a coercion kind and role]`. I believe this note is correct and is as relevant today as it was when I wrote it.

And, I'm afraid to say that `coercionRole (NthCo ...)` manifestly '''does''' require `coercionKind`. See the call in the `where` clause in the suggested patch.

Correct. The original `coercionKindRole` function recursed via the `go` worker directly, but now that I have rewritten it as `coercionRole`, the `NthCo` case still required the coercion kind to do its thing, so it calls `coercionKindRole`, which, post-unrefactoring, calls both `coercionKind` and `coercionRole`.

However, perhaps the solution lies in including the role of an `NthCo` in the `NthCo`, essentially caching this result. I think this would be easy to do, especially as the caller of `mkNthCo` generally has to know what role its getting -- `mkNthCo` could take this role as a parameter. Lint could check that the supplied role is the same as what would have been calculated. With this change to `NthCo`, then `coercionRole` really would be independent of `coercionKind` and we could separate the functions.

Sounds like a reasonable plan; however, before I venture into implementing this, I would love to have some hard evidence that we actually do have a problem. Do you have any single-module example code ready that I could use to prove that the "un-refactored" code performs significantly worse than current HEAD on some inputs? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:21 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):

I'm afraid to say that coercionRole (NthCo ...) manifestly does require coercionKind

Aha. So it does. Very well, yes let's do this * Cache the role (of the result of `NthCo i co`) in the `NthCo` data constructor * Make `mkNth` compute that cached role by calling `coercionKind` and `coercionRole` (in the final equation where we build `NthCo`). * Possible gloss: in some calls to `mkNthCo` we know the role, and we even know that the various short-cuts in `mkNthCo` won't succeed. So we can just use `NthCo` directly -- or define `mkNthCoDirect = NthCo` and call `mkNthCoDirect`. Perhaps not worth it; but when we do know the role it seems a bit silly not to use it. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:23 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

...

I would love to have some hard evidence that we actually do have a

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:24 simonpj]: problem.

Well, without caching we know that getting the role of `NthCo i1 (NthCo

i2 (NthCo i3 ...))` will take time at least quadratic in the nesting depth. Caching cheaply avoids nasty corner case. And not much code is involved. Fair enough, I'll get to it. Just wanted a test case for practical verification. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:25 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): OK, new profiling result: {{{ Thu Jan 25 13:11 2018 Time and Allocation Profiling Report (Final) ghc-stage2 +RTS -p -RTS -B/home/tobias/well- typed/devel/ghc/inplace/lib Grammar.hs -ddump-stg -ddump-simpl -ddump-to- file -fforce-recomp total time = 20.99 secs (20989 ticks @ 1000 us, 1 processor) total alloc = 29,250,375,256 bytes (excludes profiling overheads) COST CENTRE MODULE SRC %time %alloc CoreTidy HscMain compiler/main/HscMain.hs:1253:27-67 24.2 28.5 Stg2Stg HscMain compiler/main/HscMain.hs:1489:12-44 20.3 24.2 simplCast Simplify compiler/simplCore/Simplify.hs:871:62-87 18.7 15.9 tc_rn_src_decls TcRnDriver compiler/typecheck/TcRnDriver.hs:(494,4)-(556,7) 9.0 6.9 addCoerce-pushCoTyArg Simplify compiler/simplCore/Simplify.hs:(1236,12)-(1237,72) 7.4 6.4 subst_ty TyCoRep compiler/types/TyCoRep.hs:2237:28-32 4.3 5.1 zonkTopDecls TcRnDriver compiler/typecheck/TcRnDriver.hs:(445,16)-(446,43) 1.4 1.1 coercionKind Coercion compiler/types/Coercion.hs:1725:3-7 1.3 3.0 simplExprF1-Lam Simplify compiler/simplCore/Simplify.hs:896:5-39 1.0 1.1 }}} This is the same `Grammar.hs`, compiled with the same GHC code as before, but with `NthCo` extended with an extra `Role` field, and the kind calculation from `coercionRole` moved out into `mkNthCo`. I ended up having to make changes in 16 modules, but most of them were straightforward, discarding or forwarding the extra field in a pattern match. I think this shouldn't have any negative impact, because forwarding the role can only make things better (avoiding future calls to `coercionRole`), and discarding it retains the old status. Conclusions: - We're shaving off another 4 seconds of execution time, and allocations remain the same. So this doesn't seem to make things worse for the `Grammar.hs` case. - We are not actually reducing allocations any further. - CoreTidy is worth looking into. - In order to verify that this change really makes an impact for the better, I would still love to test this against source code that would perform badly without it. Test cases very welcome. - 20 seconds is still awfully long. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:27 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): I still say that most uses of `mkNthCo` already know the right role -- though perhaps this role may not be as obvious to someone who isn't me. Just supplying the role would be much better than computing it, of course. I don't agree with Simon's suggestion about `mkNthCoDirect` -- this is a first step toward invariants that are not upheld. Instead, I would have `mkNthCo` require a role and make a new `mkNthCoNoRole` that computes it. The naming of the functions should discourage the use of the second. The Note explaining why I originally bundled `coercionKind` and `coercionRole` points to a test case. Does that give a concrete testing ground? You might also look in the git history around that note to see if that gives you any pointers. Agreed about not cluttering `IfaceCoercion`. And, yes, I will take a look at `simplCast` tomorrow. (Though it's deeply scary when Simon says "My brain melted" and then asks me to take a look!) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:29 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj):

Instead, I would have mkNthCo require a role and make a new mkNthCoNoRole that computes it.

Yes, but then `mkNthCo` relies on the caller to guarantee the invariant. That's fine; Lint will check. That's all I meant `mkNthCoDirect` to do. But I'm not fussy about naming, so long as the comments are clear. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:31 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:30 goldfire]:

By the way, if @tdammers can make the patch available (on GitHub, say), I could look into patching the patch. That might be easier.

Will do ASAP. I made a bit of a mess with git, but once that's cleaned up I'll upload somewhere (phab?) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:33 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): I have a lingering concern: ''why'' did the old `coercionKindRole` perform so miserably? In a call to `coercionRole`, the kind calculations should never be forced. So what takes up all the memory? Is it really just the tuples? If so, then we've discovered a major way to speed up other areas of GHC: convert tuples to be unboxed. Even better, we've discovered a major missing optimization, which could probably automate the unboxing somehow. So I wonder if there are more opportunities here. None of this changes the current direction of travel (caching is a good idea, regardless of my question here), but perhaps suggests another future line of inquiry. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:35 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

I have a lingering concern: ''why'' did the old `coercionKindRole`

So I wonder if there are more opportunities here. None of this changes

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:35 goldfire]: perform so miserably? In a call to `coercionRole`, the kind calculations should never be forced. So what takes up all the memory? Is it really just the tuples? If so, then we've discovered a major way to speed up other areas of GHC: convert tuples to be unboxed. Even better, we've discovered a major missing optimization, which could probably automate the unboxing somehow. I think the hypothesis was something like this: Suppose we have a deeply nested `NthCo`, and we want to calculate its coercionKind. In order to do that, we need its coercionRole, which involves recursing through the whole thing (O(n)), but once we have that result, we only use it to decide whether we need to keep recursing, and then throw it away. And then in the next step, we calculate the coercionRole again. So the whole thing ends up as O(n²). Whereas if we cache the roles throughout, we only ever calculate each of them once, at construction time, so we never get the quadratic badness. So it's not that the role calculation forces the kind calculation, but the other way around - in order to calculate the correct kind for an NthCo, we need to know its role, but potentially also the roles of all of its children. So in a way, the caching serves as memoization. the current direction of travel (caching is a good idea, regardless of my question here), but perhaps suggests another future line of inquiry. Considering how the Grammar.hs example still takes about 20 seconds to compile, and there are a few rather whopping candidates popping up in the profile, yes, I think it is very likely that we can find other opportunities. I will definitely look into the tuple unboxing thing, and also try to get to the bottom of the CoreTidy and simplCast cost centres. Who knows, maybe they're somehow related, even. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:37 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:38 goldfire]:

I'm sorry -- I don't understand the first part of comment:37. Getting a kind should never require getting a role. That's why there is a version of `coercionKind` that's a standalone function. Let's assume you got these two swapped. Even then, I'm not sure what you're describing; it seems you're describing your 'un-refactored" version keeping roles and kinds separate.

I'm sorry, yes, I was being confused there; `coercionKind` and `coercionRole` are mutually recursive in the "un-refactored" version only. However, the un-refactoring *does* produce a performance improvement, so there must be *something* going on here - I assumed that the original `coercionKindRole` would ultimately amount to a similar recursion pattern, but it probably doesn't.

If they are together (as in HEAD), I don't see the quadratic behavior. And yet, something goes terribly wrong in HEAD, even without this quadratic behavior. But what?? Or maybe I'm completely missing something here.

I think I have found it. For clarity, this is the relevant code on HEAD: {{{ go (NthCo d co) | Just (tv1, _) <- splitForAllTy_maybe ty1 = ASSERT( d == 0 ) let (tv2, _) = splitForAllTy ty2 in (tyVarKind <$> Pair tv1 tv2, Nominal) | otherwise = let (tc1, args1) = splitTyConApp ty1 (_tc2, args2) = splitTyConApp ty2 in ASSERT2( tc1 == _tc2, ppr d $$ ppr tc1 $$ ppr _tc2 ) ((`getNth` d) <$> Pair args1 args2, nthRole r tc1 d) where (Pair ty1 ty2, r) = go co }}} So the rough shape of the recursion is simple - we hit the `otherwise` case repeatedly until we get to the `d == 0` case; O(n). But inside the `otherwise` branch, there's this pesky `getNth` call, which is linear in `d` (being essentially a linked-list lookup), and another one via `nthRole`. The problem goes away when we calculate the role at construction time, because we are either constructing an NthCo that doesn't wrap another NthCo, which makes the role calculation constant-time, or we are constructing one that *does* wrap another NthCo, but that one already has its role calculated, so it is also constant. Hope I'm making sense now. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:39 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): OK. I looked at `pushCoTyArg` and friends, and I have a very simple solution: just move the `isReflexiveCo` case in `addCoerce` (a local function within `Simplify.simplCast`) to the top. That should do it. Then `pushCoTyArg` is never called with a reflexive coercion, and so the `piResultTy` case won't happen. Now, `pushCoArgs` might still call `pushCoTyArg` with a reflexive coercion, but it can be taught not to as well: Have `pushCoArgs` return a `Maybe ([CoreArg], Maybe Coercion)` and `pushCoArg` return a `Maybe (CoreArg, Maybe Coercion)`. If the second return values are `Nothing`, that means that there is no cast (i.e., that the cast would have been reflexive). The only client of `pushCoArg(s)` is `exprIsConApp_maybe`, which simply omits a cast if `pushCoArgs` returns `Nothing`. Then, we never have to bother creating the reflexive coercions. This should be an easy win all around. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:41 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): OK. I've fixed a few testsuite failures. I think this is probably correct now. (CircleCI reports a bunch of errors in `profiling`, but I can't repro locally.) What happens when you benchmark? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:43 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

Sorry, still confused. :(

How are `coercionKind` and `coercionRole` ''mutually'' recursive? I see

But you're right that I'm trying to understand better why there's a

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:40 goldfire]: that `coercionRole` calls `coercionKind` but not the other way around. Sorry for the confusion, I shouldn't be trying to explain things I only half understand myself when tired. Looking at HEAD on `master`, we have the `coercionKindRole` function that is simply recursive for NthCo, and has the `nth` call embedded. So for nested NthCo's, its behavior should be quadratic. The un-refactored version has `coercionKind`, which is simply recursive (O(n)), and we have `coercionRole`, which recurses via `coercionKindRole`. The latter is really just a matter of calling `coercionKind` and `coercionRole` individually though; the `coercionRole` call makes `coercionRole` simply recursive (O(n)), but the `coercionKind` call introduces another O(n), making the entire thing also quadratic. Calling this "mutually recursive" is of course a brainfart on my side, since `coercionKind` never calls back into `coercionRole`. So in terms of big-O, HEAD and "un-refactored" should be the same. Why one perfoms better than the other is somewhat unclear to me though. performance improvement in this patch (even before any caching). In the nested `NthCo` case, I'm pretty sure your refactor would be worse. But in the test case at hand (which I assume doesn't have nested `NthCo`s -- haven't looked), your change is clearly an improvement.

However, I don't think your analysis above is really the problem. I

would expect that the running time of `coercionKind` or `coercionRole` on nested `NthCo`s to be linear in the sum of the `d`s -- that is, we'll have to add together all the indices. You've shown above that the old recursion pattern (from `coercionKindRole`) traverses down the linked list twice (once in `getNth` and once in `nthRole`), but this shouldn't change asymptotic complexity. And, usually, `d` is quite small, and so I wouldn't expect this to show up at all, really. I still don't think we've quite gotten to the bottom of why separating out `coercionKind` and `coercionRole` should effect a performance improvement. Indeed, it's not the problem, or rather, the un-refactoring alone doesn't fix anything - if it makes a difference at all, then it's most likely just a constant-factor improvement, nothing fundamental. But that's not why we did it anyway; the reason we did it was so that we could more easily implement the caching (storing precalculated roles in the NthCo itself), which breaks down one of the linear terms to constant.

On the other hand, the separated version really is quadratic... and yet it's faster (on this test case)! That's the conundrum.

Yes, but we don't know if it's actually big-O-faster, or just happens have a more favorable constant factor.

Please don't let my nit-picking slow you down or discourage you. It's just that I think you've hit something quite interesting, and, well, I'm interested. :)

Absolutely not, your input has been super helpful, and I much prefer hard criticism over empty praise. Bring it on :) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:45 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Currently doing a full test run, and I don't have the full result yet, but it seems that many tests are failing. Not sure if this is due to these particular code changes though, I will look into it once the run finishes. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:47 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

Looking at HEAD on `master`, we have the `coercionKindRole` function

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): Replying to [comment:45 tdammers]: that is simply recursive for NthCo, and has the `nth` call embedded. So for nested NthCo's, its behavior should be quadratic. I disagree here. I think the old `coercionKindRole` was not quadratic in this way (ignoring the `ForAllCo` change). Every `coercionKindRole` recurrence calls `getNth` (twice), but that doesn't lead to quadratic behavior in the depth of `NthCo` nesting, which is what we're worried about. It does mean that running time will be proportional to the sum of the indices in the `NthCo`s, but that's to be expected. Let's put this another way: pretend all the indices in the `NthCo`s are 1, a constant. (This is fairly close to reality, anyway.) Then, we're linear, not quadratic.

The un-refactored version has `coercionKind`, which is simply recursive

(O(n)), and we have `coercionRole`, which recurses via `coercionKindRole`. The latter is really just a matter of calling `coercionKind` and `coercionRole` individually though; the `coercionRole` call makes `coercionRole` simply recursive (O(n)), but the `coercionKind` call introduces another O(n), making the entire thing also quadratic. Agreed here. But note that this would remain quadratic even if all the indices in the `NthCo`s were 1. So, if you call the original `coercionKindRole` quadratic, then this would be ''cubic'' (but I don't think that's a fair characterization -- there's nothing raised to the third power here).

So in terms of big-O, HEAD and "un-refactored" should be the same. Why

one perfoms better than the other is somewhat unclear to me though. Disagree here, as explained above. The old `coercionKindRole` was asymptotically better. But now that we cache roles, it should be good again.

...

On the other hand, the separated version really is quadratic... and yet it's faster (on this test case)! That's the conundrum.

Yes, but we don't know if it's actually big-O-faster, or just happens have a more favorable constant factor.

Fair enough. I'm stymied as to why my patches make things worse. Maybe moving the `isReflexiveCo` check in `addCoerce` to the top was a bad idea? Try moving that back to where it was and then try again. The `simplCast` stuff should be vastly better than it was! Thanks! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:49 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:49 goldfire]:

It does mean that running time will be proportional to the sum of the indices in the `NthCo`s, but that's to be expected.

Ah, you are right, this is where I went wrong - the `nth` calls follow the indices, not the nested NthCos themselves. Also explains why I'm not seeing the kind of differences in the profiles that I expected.

...

The un-refactored version has `coercionKind`, which is simply

recursive (O(n)), and we have `coercionRole`, which recurses via `coercionKindRole`. The latter is really just a matter of calling `coercionKind` and `coercionRole` individually though; the `coercionRole` call makes `coercionRole` simply recursive (O(n)), but the `coercionKind` call introduces another O(n), making the entire thing also quadratic.

Agreed here. But note that this would remain quadratic even if all the

indices in the `NthCo`s were 1. So, if you call the original `coercionKindRole` quadratic, then this would be ''cubic'' (but I don't think that's a fair characterization -- there's nothing raised to the third power here).

...

So in terms of big-O, HEAD and "un-refactored" should be the same. Why

one perfoms better than the other is somewhat unclear to me though.

Disagree here, as explained above. The old `coercionKindRole` was

asymptotically better. But now that we cache roles, it should be good again. Profiling results don't agree, but other than that it seems plausible. Maybe we're hitting some sort of edge case here?

...

...

On the other hand, the separated version really is quadratic... and

...

Yes, but we don't know if it's actually big-O-faster, or just happens

have a more favorable constant factor.

Fair enough.

I'm stymied as to why my patches make things worse. Maybe moving the `isReflexiveCo` check in `addCoerce` to the top was a bad idea? Try moving

yet it's faster (on this test case)! That's the conundrum. that back to where it was and then try again. The `simplCast` stuff should be vastly better than it was! This one has me baffled as well. There's a slight possibility that the profiling runs I did were contaminated with other activity on the same machine, so I might do another run on a separate machine with nothing else going on. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:51 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): `CoreTidy` performance (part 4) moved to #14738. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:53 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Do you have allocation numbers for these runs? The mysterious thing is that `NthCo` caching makes things slightly worse. Of course the `NthCo` constructors have an extra field, but I'm still quite surprised that's a visible worsening. So I think it might be worth a little more digging into the worsening in `8ac966971e`, really just to discover if we have accidentally left money on the table. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:55 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:55 simonpj]:

Do you have allocation numbers for these runs?

The mysterious thing is that `NthCo` caching makes things slightly worse. Of course the `NthCo` constructors have an extra field, but I'm still quite surprised that's a visible worsening. So I think it might be worth a little more digging into the worsening in `8ac966971e`, really just to discover if we have accidentally left money on the table.

Yes, of course. This is `8ac966971e`: {{{ Tue Jan 30 11:25 2018 Time and Allocation Profiling Report (Final) ghc-stage2 +RTS -p -RTS -B/home/tobias/well- typed/devel/ghc/inplace/lib ./cases/Grammar.hs -o ./a -fforce-recomp total time = 12.87 secs (12865 ticks @ 1000 us, 1 processor) total alloc = 14,385,409,080 bytes (excludes profiling overheads) COST CENTRE MODULE SRC %time %alloc simplCast Simplify compiler/simplCore/Simplify.hs:871:62-87 33.7 32.4 addCoerce-pushCoTyArg Simplify compiler/simplCore/Simplify.hs:(1236,12)-(1237,72) 13.1 13.1 tc_rn_src_decls TcRnDriver compiler/typecheck/TcRnDriver.hs:(494,4)-(556,7) 12.3 14.0 subst_ty TyCoRep compiler/types/TyCoRep.hs:2237:28-32 6.7 10.4 CoreTidy HscMain compiler/main/HscMain.hs:1253:27-67 4.4 3.9 coercionKind Coercion compiler/types/Coercion.hs:1725:3-7 2.6 6.0 zonkTopDecls TcRnDriver compiler/typecheck/TcRnDriver.hs:(445,16)-(446,43) 2.0 2.2 load'.checkHowMuch GhcMake compiler/main/GhcMake.hs:(270,9)-(272,27) 2.0 0.0 simplCast-simplCoercion Simplify compiler/simplCore/Simplify.hs:1224:57-77 1.6 1.5 simplExprF1-Lam Simplify compiler/simplCore/Simplify.hs:896:5-39 1.6 2.2 deSugar HscMain compiler/main/HscMain.hs:511:7-44 1.5 1.3 simplCast-addCoerce Simplify compiler/simplCore/Simplify.hs:1225:53-71 1.4 1.3 tcRnImports TcRnDriver compiler/typecheck/TcRnDriver.hs:240:20-50 1.0 0.1 Parser HscMain compiler/main/HscMain.hs:(316,5)-(384,20) 0.9 1.6 }}} Which isn't actually significantly worse than `4eb140f564`: {{{ Tue Jan 30 11:45 2018 Time and Allocation Profiling Report (Final) ghc-stage2 +RTS -p -RTS -B/home/tobias/well- typed/devel/ghc/inplace/lib ./cases/Grammar.hs -o ./a -fforce-recomp total time = 12.38 secs (12380 ticks @ 1000 us, 1 processor) total alloc = 14,385,403,880 bytes (excludes profiling overheads) COST CENTRE MODULE SRC %time %alloc simplCast Simplify compiler/simplCore/Simplify.hs:871:62-87 34.3 32.4 addCoerce-pushCoTyArg Simplify compiler/simplCore/Simplify.hs:(1236,12)-(1237,72) 13.3 13.1 tc_rn_src_decls TcRnDriver compiler/typecheck/TcRnDriver.hs:(494,4)-(556,7) 12.7 14.0 subst_ty TyCoRep compiler/types/TyCoRep.hs:2225:28-32 7.0 10.4 CoreTidy HscMain compiler/main/HscMain.hs:1253:27-67 4.5 3.9 coercionKind Coercion compiler/types/Coercion.hs:1707:3-7 2.9 6.0 zonkTopDecls TcRnDriver compiler/typecheck/TcRnDriver.hs:(445,16)-(446,43) 2.0 2.2 simplExprF1-Lam Simplify compiler/simplCore/Simplify.hs:896:5-39 1.8 2.2 simplCast-simplCoercion Simplify compiler/simplCore/Simplify.hs:1224:57-77 1.7 1.5 deSugar HscMain compiler/main/HscMain.hs:511:7-44 1.6 1.3 simplCast-addCoerce Simplify compiler/simplCore/Simplify.hs:1225:53-71 1.4 1.3 simplIdF Simplify compiler/simplCore/Simplify.hs:868:61-79 1.0 0.5 Parser HscMain compiler/main/HscMain.hs:(316,5)-(384,20) 1.0 1.6 }}} This is only about 4% more execution time, and 0.000035% more allocations. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:57 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): So the allocations are really close. Where does the extra time go? Can you show mutator and GC times? Maybe residency, and hence GC time, is higher? Perhaps just an accident of the moments at which major GC happens. What happens if you use use just one generation? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:59 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): It's nice that `OptCoercion` for `NthCo` gets simpler when we have the role cached.

I allowed a more permissive role in the NthCo

OK, but * I didn't see a change to `mkSubCo` that would take advantage of this (by changing the role rather than wrapping in `SubCo`) * The comment on the constructor `NthCo` should state the invariant. Given `(NthCo r n co)` we require that `lteRole r (nthRole (coercionRole co) n))` or something like that. * Why does't the same flexibility apply for the other coercions that cache roles: `FunCo`, `Refl`, `TyConAppCo`, `UnivCo`? We should state their invariants too... -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:61 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): Note that this last point should have almost no effect at all on performance, and so any data collected now would still be valid. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:63 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"e4ab65bd57b2c39f4af52879654514bb6d5b42a0/ghc" e4ab65bd/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="e4ab65bd57b2c39f4af52879654514bb6d5b42a0" Optimize coercionKind (Trac #11735) Reviewers: simonpj, goldfire, bgamari Reviewed By: simonpj Subscribers: rwbarton, thomie, carter GHC Trac Issues: #11735 Differential Revision: https://phabricator.haskell.org/D4355 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:65 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by Simon Peyton Jones ): In [changeset:"db5a4b83b14bf4f1adb417b7664347fdaf637fd6/ghc" db5a4b83/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="db5a4b83b14bf4f1adb417b7664347fdaf637fd6" Re-center improved perf for T3064 There's a 6% reduction in allocation on T3064. I think it's due to commit e4ab65bd57b2c39f4af52879654514bb6d5b42a0 Author: Tobias Dammers Date: Wed Jan 31 21:39:45 2018 -0500 Optimize coercionKind (Trac #11735) I'm not certain -- but, hey, it's good news }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:67 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:59 simonpj]:

So the allocations are really close. Where does the extra time go?

Can you show mutator and GC times? Maybe residency, and hence GC time, is higher? Perhaps just an accident of the moments at which major GC happens. What happens if you use use just one generation?

I've done a run with `-s`, which gives us: {{{ --- ./cases/Grammar.hs --- 4eb140f564: 12.31 sec, max res. 257,842,544 8ac966971e: 12.70 sec, max res. 425,496,520 8a6aa5030d: 12.31 sec, max res. 254,680,256 --- ./cases/test_rules2.hs --- 4eb140f564: 1.11 sec, max res. 84,030,624 8ac966971e: 1.14 sec, max res. 81,325,072 8a6aa5030d: 1.09 sec, max res. 56,322,200 }}} So it looks like your hunch was about right: in the Grammar.hs case, max residency almost doubles in `8ac...`, but `8a6` then gets us back to normal; for the test_rules2.hs case, we see only improvement. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:69 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by goldfire): I'm not still working on this. I pushed the changes I had in mind to the tdammers branch. If the performance is OK there, could you please Phab and then commit? As for `simplCast`, the changes I had in mind are all on your branch, including removing the inefficient one-variable substitution. If my changes aren't an improvement, try undoing the change I made to the ordering of cases in `simplCast`: I moved the `isReflexiveCo` case to the top, but perhaps that check is too expensive and is better at the bottom. Regardless, the changes I made in CoreOpt should be enough to improve performance. Thanks! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:71 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): Good progress * Let's split the commits for Thing 2 and Thing 3; they are quite different. * We agreed in comment:62 not to do the subtle `SubCo` stuff for `NthCo`; that means some changes (simplifications). * I have not properly reviewed the `simplCast` changes, but they don't appear to follow the plan I suggest in comment:10. Richard can you comment on that? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:73 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by simonpj): OK: once we have a separate Phab for the `simplCast` change, I'll review it. Ping me, Tobias! -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:75 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Replying to [comment:75 simonpj]:

OK: once we have a separate Phab for the `simplCast` change, I'll review it. Ping me, Tobias!

I split up D4385 into https://phabricator.haskell.org/D4394 (the NthCo stuff) and https://phabricator.haskell.org/D4395 (simplCast / Simplify). May I assume that the refactoring mentioned in comment:76 should go in D4394? -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:77 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: | Differential Rev(s): Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Alright, all the changes from the wip/11735 branch should be on either D4394 or D4395 now. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:79 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #14683 #14975 | Differential Rev(s): D4394 D4395 Wiki Page: | -------------------------------------+------------------------------------- Changes (by tdammers): * differential: => D4394 D4395 * related: => #14683 #14975 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:81 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #14683 #14975 | Differential Rev(s): D4394 D4395 Wiki Page: | -------------------------------------+------------------------------------- Comment (by tdammers): Further digging into `simplCast` performance to be handled in #14737. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:83 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #14683 #14975 | Differential Rev(s): D4394 D4395 #14737 | Wiki Page: | -------------------------------------+------------------------------------- Changes (by tdammers): * related: #14683 #14975 => #14683 #14975 #14737 -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:85 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler

#11735: Optimize coercionKind -------------------------------------+------------------------------------- Reporter: goldfire | Owner: (none) Type: task | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.10.3 Resolution: | Keywords: Operating System: Unknown/Multiple | Architecture: Type of failure: Compile-time | Unknown/Multiple performance bug | Test Case: Blocked By: | Blocking: Related Tickets: #14683 #14975 | Differential Rev(s): D4394 D4395 #14737 | Wiki Page: | -------------------------------------+------------------------------------- Comment (by Ben Gamari ): In [changeset:"2fbe0b5171fd5639845b630faccb9a0c3b564df7/ghc" 2fbe0b5/ghc]: {{{ #!CommitTicketReference repository="ghc" revision="2fbe0b5171fd5639845b630faccb9a0c3b564df7" Caching coercion roles in NthCo and coercionKindsRole refactoring While addressing nonlinear behavior related to coercion roles, particularly `NthCo`, we noticed that coercion roles are recalculated often even though they should be readily at hand already in most cases. This patch adds a `Role` to the `NthCo` constructor so that we can cache them rather than having to recalculate them on the fly. https://ghc.haskell.org/trac/ghc/ticket/11735#comment:23 explains the approach. Performance improvement over GHC HEAD, when compiling Grammar.hs (see below): GHC 8.2.1: ``` ghc Grammar.hs 176.27s user 0.23s system 99% cpu 2:56.81 total ``` before patch (but with other optimizations applied): ``` ghc Grammar.hs -fforce-recomp 175.77s user 0.19s system 100% cpu 2:55.78 total ``` after: ``` ../../ghc/inplace/bin/ghc-stage2 Grammar.hs 10.32s user 0.17s system 98% cpu 10.678 total ``` Introduces the following regressions: - perf/compiler/parsing001 (possibly false positive) - perf/compiler/T9872 - perf/compiler/haddock.base Reviewers: goldfire, bgamari, simonpj Reviewed By: simonpj Subscribers: rwbarton, thomie, carter GHC Trac Issues: #11735 Differential Revision: https://phabricator.haskell.org/D4394 }}} -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:87 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler