On Wed, Jan 7, 2015 at 1:04 PM, Jonathan S. Shapiro <[email protected]> wrote: > 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.
Right, witnessed instance coherence is important, but doesn't pose any of the scale or separate compilation problems that instance coherence does. > 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. Yep, that's saying the same thing: if we don't require instance coherence, sortBy doesn't need to exist at all. Fewer functions is good. Geoffrey _______________________________________________ bitc-dev mailing list [email protected] http://www.coyotos.org/mailman/listinfo/bitc-dev
