#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