Re: 1 new message in 1 topic - digest

Dave,

On 6/26/07, strongtalk-general group <[email protected]> wrote:
>
>
> Strongtalk-general
> http://groups.google.com/group/strongtalk-general?hl=en
>
> [email protected]
>
> Today's topics:
>
> * Learning about VMs: syllabus - 1 messages, 1 author
>
> http://groups.google.com/group/strongtalk-general/browse_thread/thread/1059e236d4ded8ca?hl=en
>
>
> ==============================================================================
> TOPIC: Learning about VMs: syllabus
>
> http://groups.google.com/group/strongtalk-general/browse_thread/thread/1059e236d4ded8ca?hl=en
>
> ==============================================================================
>
> == 1 of 1 ==
> Date: Sun, Jun 24 2007 9:50 am
> From: "David Griswold"
>
>
>
>
> > -----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.


your megamorphic argument isn't necessarily correct.  Remember that the
indirect branch prediction buffer predicts targets not degrees of
polymorphism.  So at a given megamorphic site the effectiveness of a
processor's indirect branch prediction doesn't depend on the degree of
polymorphism, but instead depends on the number of target methods.  e.g. for
the method isNil at a given megamorphic site teh degree of polymorphism
could easily be the number of classes in the system but the number of
targets is still only going to be 2.

That said I don't see how indirect branch prediction in processors is ever
going to win except in micro-benchmarks.  Silicon spent on indirect branch
prediction is silicon not applied elsewhere ('cept they can't think of
anything to do with it except cache these days :/) so they'll always be
limited in size, and right now 36 entries is way too small for real systems.

Anybody know how these things cope with potential invalidation?  Do they
speculatively execute until the prediction is proved correct (found to match
the slow fetch of the target)?  If so, what happens when an indirect branch
follows only a few instructions after another?  Does the processor stall on
the second branch until the first one is validated?

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
-~----------~----~----~----~------~----~------~--~---