RE: 1 new message in 1 topic - digest

Hi Eliot,
  -----Original Message-----
  From: Eliot Miranda
  Sent: Friday, June 29, 2007 12:51 PM
  To: strongtalk-general group
  Subject: Re: 1 new message in 1 topic - digest


  Dave,


    Date: Sun, Jun 24 2007 9:50 am
    From: "David Griswold"

    > -----Original Message-----
    > From: Josh Scholar [mailto:[email protected]]
    >  [...]

    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.

Actually it is trickier than that in Strongtalk (as usual): Strongtalk uses
customization, so the target method polymorphism *does* equal the receiver
class polymorphism, unlike in other VMs.  However, that is only true for
compiled methods, not interpreted methods, since customization is done
lazily at compilation time, to prevent blowup in the number of customized
methods.  So it depends on which you are talking about.

But you raise a good point, and it makes clear that customization definitely
involves a tradeoff.   If the dispatch technique measures polymorphism by
number of inheriting classes rather than by original method polymorphism,
then customization involves a tradeoff: it increases method polymorphism but
decreases polymorphism inside the method body, which is usually a big win.
But as with most optimizations, in certain situations it may be that
customization hurts rather than helps.

  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?

Good questions, which I too would like to know the answer to.  I would think
it could be designed so that subsequent indirect branches wouldn't need to
stall, by keeping a small queue of pending speculated branches; you only
need one total path of speculation that keeps taking the predicted branch,
but as the predictions are proved correct, you move on to testing the
subsequent branch prediction.   But given the huge latency these days of
going to main memory, the speculation could get very far ahead over multiple
dispatches if the vtables aren't in the cache.  Although I suppose that the
vtable caching and the method caching are strongly correlated, so that if
the vtable entries aren't in cache, the method isn't likely to be either, so
maybe it wouldn't be a problem.

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