RE: Learning about VMs: syllabus

> -----Original Message-----
> From: Josh Scholar [mailto:[email protected]]
> Sent: Friday, June 22, 2007 9:34 PM
> To: David Griswold
> Subject: Re: Learning about VMs: syllabus
>
> On Oct 14 2006, 6:24 am, "David Griswold" <[email protected]>
> wrote:
> > Hi all,
>
> > - how method dispatch has traditionally been done in Smalltalk
> > (inline-caching) and why it works (most sends have low dynamic
> polymorphism)
> >
> > - some basic facts about modern CPU architecture: why
> self-modifying code is
> > very slow, why computed and indirect branches are slow.
> >
> > - how type-feedback and PICs (polymorphic inline-caches) work
>
> Some of this is changing.  According to a document I'm reading Intel
> processors after (but not including) the P4 have VERY sophisticated
> indirect call prediction (based on keeping records of previous calls
> at the site and corellating them with other calls and with repeating
> patterns.  It's much more sophisticated than anything that you could
> ever afford to do in software.  One researcher said that under
> specific conditions a single call site can correctly predict (and
> prefetch) a pattern of 36 different polymorphic targets.
>
> Of course the problem is that it can only do this kind of prediction
> in fairly tight loops because this information is kept in an on-
> processor branch buffer that never spills to memory.

It is certainly true that indirect branch prediction has been the focus of a
lot of improvement in recent processors, however I think that while the
performance advantage of type feedback is getting a bit smaller, they will
never catch up with those kind of techniques.  Here is why:

Dispatch cost:

1) Monomorphic calls are by far the most common case.  Type-feedback can
inline such sends, and when the type test can be hoisted (usually), the cost
of the dispatch is effectively *0*.  Their branch prediction code is not
going to get any better than that, and may well not reach it entirely.
Type-feedback can achieve that performance in the common case on any
architecture; their techniques are processor specific.

2) For monomorphic calls, inline-caching and type-feedback inlining
effectively simulate an *infinite* branch prediction buffer, since the
number of places that they can be applied is "as many as needed".   Their
prediction buffers are always limited in size, and can therefore thrash if
the code working set is large; type-feedback will never thrash like that.
So that is a benefit that hardware approaches can only approach and never
completely equal, as you noticed.

3) It is true that their techniques might provide benefit for moderately
polymorphic calls, which are too polymorphic for inlining but not too
polymorphic to overflow their buffer.  But these are not the common case,
and of all the non-monomorphic calls, very highly polymorphic (megamorphic)
calls are a large (and possibly the largest) fraction, and if there isn't
any temporal locality in them (which is often the case), prediction buffers
can't do anything to optimize them.  However, they could do a better job if
there was temporal locality, which type-feedback can't detect (i.e. sites
which are megamorphic over long periods but mildy polymorphic over shorter
periods).  It would have to be looked at to see how commonly that happens
for megamorphic calls; certainly it sounds plausible that it happens
reasonably often.   A type-feedback VM doesn't gather such data, so I don't
know the answer, although I know that for reflective heap-scanning code
(such as writing an image out), there is definitely very little temporal
locality.

Also, it is not unreasonable to combine the techniques in a complimentary
way, since with the right language and megamorphic dispatch code, a
type-feedback VM can benefit from their optimizations for mildy polymorphic
dispatches too.  For Java this would work well, because megamorphic calls
can be vtable dispatched; in Smalltalk it would have to be looked at to see
if their techniques work for predicting indirect dispatch via a hash table.

So as for dispatch cost, they are simply closing the gap on average.  But
that is not all there is to it:

3) Dispatch optimization is no more than half the peformance benefit of
type-feedback.  Half or more of the total speedup is from the subsequent
context-based optimization due to inlining, which is something that hardware
techniques can't do.

So in toto, such hardware techniques are only likely to close about half the
performance gap with type-feedback, at the most.
-Dave


--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups "Strongtalk-general" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to [email protected]
For more options, visit this group at http://groups.google.com/group/strongtalk-general?hl=en
-~----------~----~----~----~------~----~------~--~---