vtables for dynamic dispatch - an "invention"?

S

Stefan Ram

I read someone "invented" vtables. But to me it seems that
they are obvious in the sense that a class is a list of
methods (simplified), which gives the vtable, and an object
has a class, which means that the object holds a pointer to
a vtable.

I cannot think of another means to implement virtual member
functions.

Is there something non-obvious about vtables that has to be
"invented"?

Are there other reasonable possibilities to implement
virtual calls?
 
V

Victor Bazarov

I read someone "invented" vtables. But to me it seems that
they are obvious in the sense that a class is a list of
methods (simplified), which gives the vtable, and an object
has a class, which means that the object holds a pointer to
a vtable.

I cannot think of another means to implement virtual member
functions.

Is there something non-obvious about vtables that has to be
"invented"?

Are there other reasonable possibilities to implement
virtual calls?

It is obvious when you already know the answer... ;-) Generally
speaking the object doesn't have to hold a pointer to the class'
"vtable". It could hold some other identifier that can be used in run
time to find the proper function to call. Imagine one possible solution
where the dynamic dispatcher is a large 'switch' statement.

V
 
A

Alf P. Steinbach

I read someone "invented" vtables. But to me it seems that
they are obvious in the sense that a class is a list of
methods (simplified), which gives the vtable, and an object
has a class, which means that the object holds a pointer to
a vtable.

I cannot think of another means to implement virtual member
functions.

In Smalltalk and in Borland/Turbo Pascal's support for Windows window
message dispatching (Borland's "ObjectWindows" framework, IIRC), a call
to a virtual method resulting in a dynamic search up "the" (there was
only one) superclass (C++ base class) chain, starting with the object's
own most derived class.

Thus each class had some kind of method table, a method "dictionary",
that included only the class' own methods and not inherited methods.

The final effect is the same as with the now more common vtables.

Is there something non-obvious about vtables that has to be
"invented"?

Yes.

When you try to implement them in C, you discover that there's a lot of
casting involved.

Essentially virtual functions give you TYPE SAFE DOWNCASTING, which you
have to express more explicitly in C (not so type safe then).

Are there other reasonable possibilities to implement
virtual calls?

In addition to the Smalltalk/TP dynamic search described above, an often
used technique in C is a struct with direct function pointer members.


Cheers & hth.,

- Alf
 
A

Alf P. Steinbach

(e-mail address removed)-berlin.de (Stefan Ram) wrote in @ram.dialup.fu-berlin.de:

If you add multiple and virtual inheritance, I'm sure there is lot of
things that are not obvious. Virtual inheritance has to be declared in a
"wrong" place for example, is it just in order to make an efficient vtable
implementation possible? As said, it's not so obvious.

Stroustrup on the implementation of multiple inheritance, C/C++ Users
Journal 1999:

http://phobos.ramapo.edu/~ldant/oop/stroustrup_multiple_inheritance.pdf

I'd forgotten this until I saw your posting (and AFAICS he doesn't
mention it in this article), but Stroustrup postponed introducing
multiple inheritance until he had made sure that it /could/ be
implemented efficiently in terms of vtables.


Cheers,

- Alf
 
J

James Kanze

On 15 Nov 2013 19:30:42 GMT, (e-mail address removed)-berlin.de (Stefan Ram)
wrote:
Hash tables or binary tree dispatch are alternatives, although their
extra functionality doesn't bring anything to C++, so there never(?)
used there. For example, languages which support duck typing
generally cannot use the simple vptr/vtable approach.

As far as I know, C++ was the first language to use the
vptr/vtable approach. Smalltalk generally used hash tables.

In general, vtables are only applicable to languages with
constrained genericity, where the client can only call functions
declared in the (base)type he has at hand. Languages which
don't impose this, like Python, will usually use the hash table
approach.
 
W

W Karas

Not sure, but I think that C++ got the idea of using vtables from Simula.

Function dispatch is the center of two common myths as to why C++ is a "high overhead" language.

The first is that (like Smalltalk, Flavors and other more weakly typed OO languages) C++ function dispatch requires an associative look-up.

The second is that there is a hidden pointer added to a class for each and every virtual member function it has.

The prevalence of these myths is a good indication that the vtables idea is not entirely obvious.
 
W

W Karas

.
In general, vtables are only applicable to languages with
constrained genericity, where the client can only call functions
declared in the (base)type he has at hand. Languages which
don't impose this, like Python, will usually use the hash table
approach.

This is why C++ needs templates, to make limited genericity that is not constrained by common base type/interface available, as long as it can be resolved at compile time.

This may be an argument for teaching programmers Python or Smalltalk first (before C++). So they can come to understand generic implementation in a language that supports it in a simple rather than a performance-optimal way first.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top