On Wed, Dec 31, 2014 at 10:10 AM, Geoffrey Irving <[email protected]> wrote:
What are the types of compiler tricks you're thinking of doing that > require [coherent] type classes? Are you imagining optimizations that > are possible to do on a "sort" function that uses type classes but are > impossible to do on a "sortBy" function that takes an ordering > function explicitly? Most optimizations I can imagine work in both > cases modulo heuristics for when partial evaluation should usefully be > applied, though of course that's a huge "modulo". > That'a s [fairly] short question with a long answer. What is realistic depends a lot on the compilation model (whole program vs. static-separate vs. dynamic) and the specific program. Let me ignore compilation model for a moment, though. Let's start with whole-program. Assuming that we are willing to do enough partial evaluation and/or specialization, function parameters and type classes are very similar. Typically you have a call chain, and somewhere at the top of this chain there is a place where a function parameter or a TC instance parameter was passed. The TC instance is, of necessity, a statically resolvable constant term. The function need not be. But when the function *is* a statically resolvable constant term, you can partially evaluate the parameter away and *eventually* you can inline the function body. Either approach may yield code explosion through over-specialization. How far and how aggressively to instantiate is a pragmatics question that doesn't seem to have a general answer. The value of instance coherence, from a compilation perspective, isn't all that great when taken by itself. The value of *witnessed* instance coherence (that is: (a) the instance is in scope, and (b) any failure of coherence can be detected and diagnosed during static unit-at-time compilation) is high. Witnessed coherence (at least for defaulted type classes) justifies us in inlining the instance methods aggressively, which in turn allows us to drop the class constraint. This inlining can be done *without* having to chase a passed procedure pointer through a call chain in the whole-program way. All of this seems (to me) *very* important at ground types (because, e.g., we really don't want to be calling a procedure to add two integers), and somewhat important at unboxed types (because we really don't want to have to look up field types). I think there is some threshold where the expense of the operation performed by the TC instance method makes the cost of call largely irrelevant. Pass-by-reference is relevant here as well, which is the (in hindsight obvious) point on which BitC v0 foundered. For a whole lot of reasons, I want to preserve separate compilation in BitC, even if I can only do it at the level of assemblies, and I nonetheless want the ability to do aggressive inlining at ground types. There's no way I can see to avoid runtime compilation for general application use (though we can stage that), but I'm damned if I want to have to incrementally JIT my way through hundreds of such expansions before discovering that there was a simple ADD instruction at the bottom. Specifically, if you can optimize "sort" for a given type by noticing > that it has a coherent type class for Ord, you can also optimize > sortBy if you can notice that people seem to pass in the same > comparison function *most* of the time.... Actually, you can specialize "sort" for *any* instance of Ord (coherent or otherwise). It's just partial evaluation. You just have to make sure that you remember which specialization you did so that you call the intended specialization later. That can be done by encoding any non-default resolutions into the name mangling of the specialized sort function. shap
_______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
