Avoiding late binding with trampolines

Consider the toBool method. Every object has one because everybody inherits from Object and Object has it. An object can override toBool to add its own functionality. Standard stuff. Also standard stuff in late bound languages is delaying resolution of methods to runtime: obj.toBool() or if(obj) both invoke the toBool method (directly or indirectly). If the compiler can determine obj’s type, it can call the method directly (with static linking). If it can’t, (eg obj is a variable or function parameter) (remember that this is an untyped language), it has to be punted to runtime when obj is in play and the VM can ask obj to find and run obj’s idea of toBool. This usually involves a query into a hash table, which quick but has a bit of overhead.

But, what if the compiler said “oh, a call to obj.toBool. I don’t know what obj is but I’ll call Object.toBool and let Object figure out what to do”? We get rid of the overhead of a table query but how is Object to be expected to know how to deal with this? Enter trampolines. Object.toBool gets called and says “I’m a generic low level routine that typically just does a default action (like saying “I can’t do that”) but now I need to do something”. That something is to bounce the toBool call out to obj via a trampoline.

Here is an example: fcn f(a) { a.toBool() }
And the compiler output:

Late bound

Fcn: f Prototype: L(“a”)
Code (code: 5 bytes, strings: 7 bytes)
    0:210 arg0
    1:122 reCallZ(toBool)
    4:  0 done

Statically linked

Fcn: f Prototype: L(“a”)
Code (code: 4 bytes, strings: 0 bytes)
    0:210 arg0
    1:119 callOMethodNZ(3:toBool)
    3:  0 done

In addition to one less byte of code, the string “toBool” is not needed.

But how? When obj is built, it has back linkage to Object (so the inheritance from Object works). As part of building obj, Object updates tables to include the trampolines. The trampoline is a small table
   Byte trampolines[15];  // 0xff means no bounce
in each object. (It is important to note that the trampoline table is per object, not per instance. So, while there may be zillions of instances floating about, there is less than one hundred objects & trampolines).

When Object wants to bounce a method call:
   static Instance *
   Object_toBool(Instance *self,pArglist arglist,pVM vm) {
      Instance *r=obounce(self,arglist,TO_BOOL,MIX_TO_BOOL,vm);
      if (r) return r;
      return cantConvertError(self,”toBool”,vm);
   }
obounce does the work:
   Instance *obounce(Instance *self,
          pArglist arglist, int tix,int mix, pVM vm){
      ZKL_Object *obj = OBJECTI(self);
      int         n   = obj->trampolines[tix];
      if (n != 0xff)
        return obj->methodTable[n].method(self,arglist,vm);
      return 0;  // no can do
   }

This is all cool and groovy, so I picked nine methods (toBool, toInt, toFloat, BaseClass, len, isType, isInstanceOf and [] (two methods)) that a scan of a bunch of source code showed being used a lot and compiled up the compiler (9,500+ lines) and took a look. Oh, woe is me! The compiled code (94KB) is about 2% smaller and runs about 3% faster (compiling the parser, which is the big Kahuna at 4,500 lines). I have several guesses as to what is going on, from those methods are just not used that much (best guess sans profiling), too much overhead, to hash tables are pretty good (they are single probe (gperf) but there is overhead).

The fly in the ointment are proxy objects: classes and lazies. Classes because a function can implement/override a method a class method (for example, toInt, toBool). When a lazy object is on the receiving end of a trampoline, it has to decide if the method call needs to force evaluation or not. And avoid infinite loops (by trampolining back through Object). In addition, the BaseClass method always “tunnels” under any proxy behavior (ie no bounce). It is pretty twitchy and twisty enough that it makes my head hurt.

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s