Alternatives to vtable

Question

Vtables are ubiquitous in most OO implementations, but do they have alternatives? The wiki page for vtables has a short blurb, but not really to much info (and stubbed links).

Do you know of some language implementation which does not use vtables?

Are there are free online pages which discuss the alternatives?

Answer 1

Yes, there are many alternatives!

Vtables are only possible when two conditions hold.

1. All method calls can be determined statically. If you can call functions by string name, or if you have no type information about what objects you are calling methods on, you can't use vtables because you can't map each method to the index in some table. Similarly, if you can add functions to a class at runtime, you can't assign all methods an index in the vtable statically.
2. Inheritance can be determined statically. If you use prototypal inheritance, or another inheritance scheme where you can't tell statically what the inheritance structure looks like, you can't precompute the index of each method in the table or what particular class's method goes in a slot.

Commonly, inheritance is implemented by having a string-based table mapping names of functions to their implementations, along with pointers allowing each class to look up its base class. Method dispatch is then implemented by walking this structure looking for the lowest class at or above the class of the receiver object that implements the method. To speed up execution, techniques like inline caching are often used, where call sites store a guess of which method should be invoked based on the type of the object to avoid spending time traversing this whole structure. The Self programming language used this idea, which was then incorporates into the HotSpot JVM to handle interfaces (standard inheritance still uses vtables).

Another option is to use tracing, where the compiler emits code that guesses what the type of the object is and then hardcodes the method to call into the trace. Mozilla Firefox uses this in its JavaScript interpreter, since there isn't a way to build vtables for every object.

I just finished teaching a compilers course and one of my lectures was on implementations of objects in various programming languages and the associated tradeoffs. If you'd like, you can check out the slides here.

Hope this helps!