Re: method dictionary lookups and walking up the inheritance tree

> -----Original Message-----
> From: Andreas Raab [mailto:[hidden email]]
> 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
  else
    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]
  else
    call relink(&prevMethod[firstFreeOrLeastRecentlyUsed,
                    prevClass[firsFreeOrLeastRecentlyused] := receiverClass,
                    mySelector)

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.

Cheers,
Ian