Inlining heuristic trouble

[Rémi Forax]

On 06/21/2011 12:27 AM, John Rose wrote:
> On Jun 20, 2011, at 1:11 PM, Mark Roos wrote:
>
>> So we do not have a path that can be assumed to be not taken (except the last in the chain).
>>
>> Perhaps in the JVM this is a poor choice for implementation of a small polymorphic inline cache.  Here I defer to the real experts
> Both monomorphic and polymorphic inline caches are a central use case for invokedynamic.  For more details and references, see the VMIL paper linked here:
>    http://blogs.oracle.com/jrose/entry/vmil_paper_on_invokedynamic
>
> See section 5, "Case Study: Inline Caches and invokedynamic".
>
> A small (non-megamorphic) polymorphic cache can be represented as a cascade or decision tree of GWT combinators, probably with a control block of some sort that can rebalance from time to time.
>
> A megamorphic call site can be represented using the class pattern of a two-step dispatch plus indirect function call. The foldArguments combinator is intended to support this pattern.  (You fold some arguments together, yielding a MH to prepend to the argument list, and then you jump to an invoker.)  This can support vtable or metaclass dispatches, or more subtle ones like the CLOS dispatch via a hash of relevant argument attributes.
>
> (I'm getting hungry for Remi's cookbook, because it will have this sort of example in it nicely worked out.)

The bi-morphic inlining cache is the example you're looking for:
http://code.google.com/p/jsr292-cookbook/source/browse/trunk/bimorphic-cache/src/jsr292/cookbook/bicache/RT.java

It first creates a tree of GWTs and if there are more than two possible 
classes/targets for one callsite,
it create a dispatch table* + foldArguments (around line 42).

> -- John

Rémi
* the current implementation uses a synchronized map but I have an 
immutable version on my laptop,
I have to do some perf test.