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