method dictionary lookups and walking up the inheritance tree

piumarta at piumarta at
Tue May 16 20:41:17 UTC 2006

> -----Original Message-----
> From: Andreas Raab [mailto:andreas.raab at]
> Subject: Re: method dictionary lookups and walking up the inheritance tree
> But isn't the global method cache polymorphic by definition? It maps 
> class+selector -> method (actual class of object; not class where the 
> method is defined in) and unless I got the meaning of the word wrong 
> this is polymorphic, is it not? ;-)

You got the meaning wrong.

A send site with a monomorphic inline cache looks like this:

  if (receiverClass == prevClass)
    call prevMethod
    call relink(&prevMethod, prevClass := receiverClass, mySelector)

where relink() looks up mySelector in receiverClass and overwrites *prevMethod with the target method, then jumps into the method.  (You can also put this test+relink in the method prologue if it's cheap enough to reconstruct &prevMethod and &prevClass from the call return address.)

prevClass and prevMethod can be inline constants overwritten by relink() (provided your architecture makes it easy to poke constants into code and it is really cheap to flush the affected i-cache lines) otherwise they can be a private data structure owned exclusively by the send site whose address is supplied to relink() when necessary.

A send site with a polymorphic inline cache looks like this:

  if (receiverClass == prevClass[0[)
    call prevMethod[0]
  elif (receiverClass == prevClass[1])
    call prevMethod[1]
  elif receiverClass == prevClass[N])
    call prevMethod[N]
    call relink(&prevMethod[firstFreeOrLeastRecentlyUsed,
                    prevClass[firsFreeOrLeastRecentlyused] := receiverClass,

but otherwise works just like the monomorphic case.

Obviously relink() can use a global method cache to refill the inline caches.

The clever way to organise the code is like this:

- When a monomorphic inline cache starts thrashing, promote it into a polyorhic inline cache.

- When a polymorphic inline cache starts thrashing, either turn it off (and go straight to the global method cache) or copy mdict entries down into subclasses until the thrashing stops.


More information about the Vm-dev mailing list