Alternative virtual mechanism implementations?

Question

C++ supports dynamic binding through virtual mechanism. But as I understand the virtual mechanism is an implementation detail of the compiler and the standard just specifies the behaviors of what should happen under specific scenarios. Most compilers implement the virtual mechanism through the virtual table and virtual pointer. And yes I am aware of how this works, So my question is not about implementation detail of virtual pointers and table. My questions are:

1. Are there any compilers which implement Virtual Mechanism in any other way other than the virtual pointer and virtual table mechanism? As far as i have seen most(read g++,Microsoft visual studio) implement it through virtual table, pointer mechanism. So practically are there any other compiler implementations at all?
2. The sizeof of any class with just a virtual function will be size of an pointer (vptr inside this) on that compiler, So given that virtual ptr and tbl mechanism itself is compiler implementation, will this statement I made above be always true?

Answer 1

It is not true that vtable pointers in objects are always the most efficient. My compiler for another language used to use in-object pointers for similar reasons but no longer does: instead it uses a separate data structure which maps the object address to the required meta-data: in my system this happens to be shape information for use by the garbage collector.

This implementation costs a bit more storage for a single simple object, is more efficient for complex objects with many bases, and it is vastly more efficient for arrays, since only a single entry is required in the mapping table for all objects in the array. My particular implementation can also find the meta-data given a pointer to any point interior to the object.

The actual lookup is extremely fast, and the storage requirements very modest, because I am using the best data structure on the planet: Judy arrays.

I also know of no C++ compiler using anything other than vtable pointers, but it is not the only way. In fact, the initialisation semantics for classes with bases make any implementation messy. This is because the complete type has to see-saw around as the object is constructed. As a consequence of these semantics, complex mixin objects lead to massive sets of vtables being generated, large objects, and slow object initialisation. This probably isn't a consequence of the vtable technique as much as needing to slavishly follow the requirement that the run-time type of a subobject be correct at all times. Actually there's no good reason for this during construction, since constructors are not methods and can't sensibly use virtual dispatch: this isn't so clear to me for destruction since destructors are real methods.

Answer 2

To my knowledge, all C++ implementations use a vtable pointer, although it would be quite easy (and perhaps not so bad perf wise as you might think given caches) to keep a small type-index in the object (1-2 B) and subsequently obtain the vtable and type information with a small table lookup.

Another interesting approach might be BIBOP (http://foldoc.org/BIBOP) -- big bag of pages -- although it would have issues for C++. Idea: put objects of the same type on a page. Get a pointer to the type descriptor / vtable at the top of the page by simply and'ing off the less signficant bits of the object pointer. (Doesn't work well for objects on the stack, of course!)

Another other approach is to encode certain type tags/indices in the object pointers themselves. For example, if by construction all objects are 16-byte aligned, you can use the 4 LSBs to put a 4-bit type tag in there. (Not really enough.) Or (particularly for embedded systems) if you have guaranteed unused more-significant-bits in addresses, you can put more tag bits up there, and recover them with a shift and mask.

While both these schemes are interesting (and sometimes used) for other language implementations, they are problematic for C++. Certain C++ semantics, such as which base class virtual function overrides are called during (base class) object construction and destruction, drive you to a model where there is some state in the object that you modify as you enter base class ctors/dtors.

You may find my old tutorial on the Microsoft C++ object model implementation interesting. http://www.openrce.org/articles/files/jangrayhood.pdf

Happy hacking!

Answer 3

Are there any compilers which implement Virtual Mechanism in any other way other than the virtual pointer and virtual table mechanism? As far as i have seen most(read g++,Microsoft visual studio) implement it through virtual table, pointer mechanism. So practically are there any other compiler implementations at all?

None that I'm aware of C++ compilers using, though you might find it interesting to read about Binary Tree Dispatch. If you're interested in exploiting the expectation of virtual dispatch tables in any way, you should be aware that compilers can - where the types are known at compile time - sometimes resolve virtual function calls at compile time, so may not consult the table.

The sizeof of any class with just a virtual function will be size of an pointer(vptr inside the this) on that compiler, So given that virtual ptr and tbl mechanism itself is compiler implementation, will this statement I made above be always true?

Assuming no base classes with their own virtual members, and no virtual base classes, it's overwhelmingly likely to be true. Alternatives can be envisaged - such as whole-program analysis revealing only one member in the class heirarchy, and a switch to compile-time dispatch. If run-time dispatch is required, it's hard to imagine why any compiler would introduce further indirection. Still, the Standard deliberately doesn't stipulate these things precisely so that implementations can vary, or be varied in future.

Answer 4

IIRC Eiffel uses a different approach and all overrides of a method end up merged and compiled in the same address with a prologue where the object type is checked (so every object must have a type ID, but it's not a pointer to a VMT). This for C++ would require of course that the final function is created at link time. I don't know any C++ compiler that uses this approach, however.

Answer 5

Are there any compilers which implement Virtual Mechanism in any other way other than the virtual pointer and virtual table mechanism? As far as i have seen most(read g++,Microsoft visual studio) implement it through virtual table, pointer mechanism. So practically are there any other compiler implementations at all?

All current compilers that I know of use the vtable mechanism.

This is an optimization that's possible because C++ is statically type checked.

In some more dynamic languages there is instead a dynamic search up the base class chain(s), searching for an implementation of a member function that's called virtually, starting in the most derived class of the object. For example, that's how it worked in original Smalltalk. And the C++ standard describes the effect of a virtual call as if such a search had been used.

In Borland/Turbo Pascal in the 1990's such dynamic search was employed for finding handlers of Windows API "window messages". And I think possibly the same in Borland C++. It was in addition to the normal vtable mechanism, used solely for message handlers.

If it was used in Borland/Turbo C++ – I can't remember – then it was in support of a language extensions that allowed you to associate message id's with message handler functions.

The sizeof of any class with just a virtual function will be size of an pointer(vptr inside the this) on that compiler, So given that virtual ptr and tbl mechanism itself is compiler implementation, will this statement I made above be always true?

Formally no (even with assumption of vtable mechanism), it depends on the compiler. Since the standard doesn't require the vtable mechanism it says nothing about placement of vtable pointer in each object. And other rules let the compiler freely add padding, unused bytes, at the end.

But in practice perhaps. ;-)

However it's not something that you should rely on, or that you need to rely on. But in the other direction you can require this, for example if you're defining an ABI. Then any compiler that doesn't, simply doesn't conform to your requirement.

Cheers & hth.,

Answer 6

1. I don't think there are any modern compilers with an approach other than vptr/vtable. Indeed, it would be hard to figure out something else that is not just plain inefficient.

   However, there is still a pretty large room for design tradeoffs within that approach. Maybe especially regarding how virtual inheritance is handled. So it makes sense to make this implementation-defined.

   If you are interested in this kind of stuff, I strongly suggest reading Inside the C++ Object Model.

2. sizeof class depends on the compiler. If you want portable code, don't make any assumptions.