#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): Sorry, still confused. :( How are `coercionKind` and `coercionRole` ''mutually'' recursive? I see that `coercionRole` calls `coercionKind` but not the other way around. But you're right that I'm trying to understand better why there's a 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. On the other hand, the separated version really is quadratic... and yet it's faster (on this test case)! That's the conundrum. 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. :) -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/11735#comment:40 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler