About uncacheable singly implemented messages

Hi Andres,

Given a typical implementation

       Object>>isKindOf: targetClass
               ^self class includesBehavior: targetClass

       Behavior>>includesBehavior: targetClass
               ^self == targetClass
                       or:     [superclass includesBehavior: targetClass]

the lookups are a bit expensive.

(Maybe that's a good thing, in this particular case,
 as it may just discourage the use of #isKindOf:.)

The image I'm running solves the problem by
implementing the method as a primitive.

Short of that, another approach would be to go the #basic route,
and implement a far less general version, for use in the typical
case - which I suspect is virtually indistinguishable from 100%
of all uses:

Object>>isKindOf: targetClass
   ^self class isKindOf: targetClass

class>>isKindOf: targetClass
   ^self basicIsKindOf: targetClass

class>>basicIsKindOf: targetClass
   | doh |
   doh := self.
   [ doh == targetClass or: [doh == UndefinedObject]
   ] whileFalse:
       [ doh := doh superclass ].
   ^doh == targetClass

The implementation doesn't generalize, per se,
to whatever other methods you have in mind,
but the idea itself might:

   If the PIC is adding useless overhead,
   and said overhead is in fact compounding,
   then the "pure" semantics of method sends
   and extreme late binding isn't providing
   a realizable value in the case at hand,
   -- so we can safely drop the pretense,
   and expense, of maintaining the illusion,
   if there is reason to do so.

   And there may be reason to do so,
   whenever such a case is of relatively
   high occurance.

Regards,

-cstb

At 01:27 PM 4/15/2010, Andres Valloud wrote:
>Hello,
>
>Typically, with ICs and PICs, messages like isKindOf: are uncacheable.
>This is because if you do something like
>
>LargePositiveInteger isKindOf: Object
>
>then isKindOf: does, essentially:
>
>1.  LargePositiveInteger == Object?  No, so send isKindOf: to LargePositiveInteger's superclass.
>
>2.  LargeInteger == Object?  No, so send isKindOf: to LargeInteger's superclass.
>
>3.  Integer == Object?  No, so send isKindOf: to Integer's superclass.
>
>4.  Magnitude == Object?  No, so send isKindOf: to Magnitude's superclass.
>
>5.  Object == Object?  Yes, done.
>
>Note how, in every line, there are multiple forced lookups the VM must perform.  Each isKindOf: send requires a lookup because the class of the receiver's class changes.  Each send of superclass requires a lookup because of the receiver's class changes.  Fortunately, == can be implemented as a special bytecode that does not require actual message sends.  However, the problem is that the code runs horribly slow due to the numerous lookups.  I know this because changing VW's sorted collection method dictionary approach with an actual hashed collection results in speedups close to 2x in code such as
>
>| receivers |
>receivers := Object withAllSubclasses reverse.
>Time millisecondsToRun: [receivers do: [:each | each yourself]]
>
>Are there any bits of interesting information on how to cache or otherwise speed up these lookup-rich cases?
>
>Andres.
>
>
>--
>To unsubscribe, reply using "remove me" as the subject.
>
>

>__________ Information from ESET NOD32 Antivirus, version of virus signature database 4826 (20100202) __________
>
>The message was checked by ESET NOD32 Antivirus.
>
>http://www.eset.com
>
>

On Tue, May 4, 2010 at 23:50, cstb <[hidden email]> wrote:
> At 04:46 PM 5/3/2010, Andres Valloud wrote:
>> It could be isKindOf:, or printString, or yourself... generally
>> speaking, all these messages can't / shouldn't be implemented
>> as primitives.

#printString and especially #yourself are rarely megamorphic call sites though.

> My point was that the following method *should* inline,
> yet produce the same result as the typical implementation
> as long as the constraint holds (i.e. singly implemented).

True, however the possible receiver's classes will still be many,
precluding the use of PICs.  For the particular case of super sends,
you can convert tail recursion like you did, or implement inline
caching tricks, but it won't help for other megamorphic sends that
have a single implementation.  In fact, even #isKindOf: will be one of
them.  For all these sends, you still have to do useless lookups and
(though they are only one per call site) you still cannot use PICs.

So, while you and I provided a solution to this particular problem,
neither of us provided a solution to the general problem of
singly-implemented methods with megamorphic call sites.

> Object class>>basicIsKindOf: targetClass
>     | doh |
>     doh := self.
>     [ doh == targetClass or: [doh == UndefinedObject]
>     ] whileFalse:
>         [ doh := doh superclass ].
>     ^doh == targetClass

There is already a similar method (#includesBehavior:).  Note however that

 Object>>isKindOf: targetClass
    | doh |
    doh := self class.

    [ doh == targetClass or: [doh == UndefinedObject]
    ] whileFalse:
        [ doh := doh superclass ].
    ^doh == targetClass

 Behavior>>includesBehavior: targetClass

    | doh |
    doh := self.
    [ doh == targetClass or: [doh == UndefinedObject]
    ] whileFalse:
        [ doh := doh superclass ].
    ^doh == targetClass

are perfectly safe _and_ equivalent to the corresponding recursive
implementations. You know that the superclass of Object is nil, thus
once you reach this implementation no superclass will be able to
change to another one.

Paolo

Eliot,

On 5/5/10 9:27 , Eliot Miranda wrote:

In Cog, however, all the open PICs are stored on a linked list and so megamorphic sites with the same selector share open PICs.  Further, step 2 will short-circuit directly to step 5 if a failing monomorphic send site's selector matches an Open PIC on the Open PIC list.  This saves a lot of cache flushes as a closed PIC for a likely megamorphic selector grows.

Don't the savings depend on the send site?

 Wouldn't it be better to use the open PICs as lookup caches for IC / PIC misses instead?

 At least you can do it because you share open PICs on a selector basis.  Also, why do you need to do any cache flushing?  Assuming you're flushing intentionally, a mere jmp instruction is enough on x86, and it's very likely you are already executing one of those.  You must have meant something else, what is it?

Andres.