Talk:Virtual method table

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computing  
WikiProject icon This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
 ???  This article has not yet received a rating on the project's quality scale.
 ???  This article has not yet received a rating on the project's importance scale.
 

I want to express, the introduction (cat/speak/meow/roar) is really great. This has helped me understand the matter for the first time. --ThorstenStaerk (talk) 08:35, 21 July 2009 (UTC)

I am not satisfied with reference [2]. It is outdated, predates any optimizing compiler, and is based on simulations on a fictuous processor (the P96). Also, it is likely that, except for trivial functions, the cost of an indirect call on a REAL processor is negligible compared to the evaluation of the arguments and to what the function actually does. This obsolete (and bad) reference only helps during myths about c++ performance. —Preceding unsigned comment added by 69.90.176.110 (talk) 12:07, 15 October 2008 (UTC)

I am not satisfied with this article. While it is technically correct, I think it could be worded better. Anyone out there want to try editing it? John 17:42, Sep 21, 2004 (UTC)

I am not satisfied with the title "virtual table". The table itself is not virtual. I suggest to move this article to "virtual method table", or may be to "virtual-method table". --Knorxx 11:28, 18 September 2005 (UTC)

I have changed the title to "virtual method table". --Knorxx 12:06, 3 October 2005 (UTC)

In fact "virtual method table" itself is bound too closely to C++, I suggest it be referenced simply as a "method table". Methods are after all polymorphic.

I agree with the unsigned comment. Also, it's misleading to say that compiled languages have to use vtables; even C++ can be implemented in other ways. And it's worth discussing the tradeoffs--you get efficiency and simple representation for SI, but extra complexity for MI, double-sized pointers-to-methods, no multimethods, etc. References to D&E, the history of cfront, Lippman's book, etc. might be useful. Falcotron 06:43, 7 June 2006 (UTC)

There is this part on invocation: "(*((*d)[0]))(d) Where *d refers to the virtual method table of D and [0] refers to the first method in the vtable. The parameter d becomes the "this" pointer to the object."

It may make a little bit more sense to use actual C++ notation for setting 'd' as the "this" for the object? C++ does have notation for that: (d->*((*d)[0])) (/* arguments go here ... */); — Preceding unsigned comment added by Liubian (talkcontribs) 02:46, 20 August 2014 (UTC)


Example[edit]

The example takes a lot of space to show only a fraction of the useful information. There's no reason to use a deep hierarchy with 9 methods.

Without a vtable for one of the base classes (a subset of the derived vtables), it's not clear why a DES object can be used as a SymmetricAlgorithm. It also means there's no demonstration of how abstract methods are implemented (.long 0, which explains the "= 0" syntax hack).

Listing Clear in the vtable without including the declaration of it as a virtual function (presumably in Algorithm) is potentially confusing. And type_info probably shouldn't be shown without at least some explanation.

It needs to be clear that this is how a particular C++ compiler implements vtables (and which one?), and that the standard doesn't even require vtables at all.

Also, there should be some indication of how the compiler and runtime find the vtable for an object--a hidden vptr as the first member of the class (most compilers), a vptr at the end of the class and size tracking (old Apple MPW?), a pointer/offset combination (cfront 3?), or any other possibilities that I don't recall).

Finally, all of the tricky/interesting stuff has to do with multiple inheritance, and that isn't even hinted at here.

Demonstrating a dynamic cross-cast in a simple 3-class MI hierarchy in gcc 4 and in cfront 3 would cover all of these issues, without any confusion, in (probably) less space. Falcotron 06:35, 7 June 2006 (UTC)

Changed the examples. However, I have only been able to give examples based on the Microsoft C++ compiler. Will change/add examples to reflect gcc later. --isbor 16:38, 7 July 2006 (UTC)
Changed examples to reflect g++/gcc behaviour. Could someone please verify? --isbor 07:31, 8 July 2006 (UTC)
Thanks for adding the examples. By the way, I don't think it was necessary to replace the VC8 version with gcc3; I just suggested gcc4 because it's one compiler that I knew for sure doesn't do things the old way. They both seem to do things essentially the same way (is VC8 optimizing out D::B1's f2 because it can never be called virtually except through a B2?), so either one makes the point equally well. (And thanks for making me take a look at how VC8 does it--otherwise, it might have been a while before I noticed how much better the debugger has gotten for exploring vtables, rtti and exception stuff, etc.) Falcotron 20:05, 11 July 2006 (UTC)
I opted for gcc because I think referencing to free software would be better, especially in a free encyclopedia ;) --isbor 18:00, 14 July 2006 (UTC)
One thing: The functions are called b1 and b2 in the code, f1 and f2 in the layout. I'll fix that. Falcotron 20:05, 11 July 2006 (UTC)

See [C++ ABI for IA-64: Code and Implementation Examples] for a good discussion of some of the issues in designing a vtable implementation. Falcotron 08:57, 7 June 2006 (UTC)

Rewrite[edit]

Inspired by isbor's new examples and explanations, I reorganized the page, rewrote chunks of it, and expanded various parts. Hopefully most of what I added or changed is both correct (although someone should look it over and make sure I got the right number of *'s in the pseudocode and so forth), readable (again, someone check), and non-controversial. There are a few things I wanted to point out specifically:

  • I removed the "see also" link to virtual inheritance, because vtables have nothing to do with virtual inheritance in particular (as opposed to single inheritance or non-virtual multiple inheritance).
  • The last two paragraphs may be too combative (in which direction?) or too wishy-washy. Or maybe both. Clearly the vtable is an intentional compromise; it gets part of Smalltalk's dynamism for much less cost, using a very C-hacker-style design. But without quoting D&E extensively (and explaining why Java and D have kept essentially the same tradeoff), I'm not sure how to get this across. Falcotron 00:11, 12 July 2006 (UTC)

Errors[edit]

some of your examples have minor errors. for example

*((d->"pointer to virtual method table of D (for B1)")[12])(d)

you say this is supposed to call B1::f1() but in reality it calls D::f2()

A problem in the Multiple inheritance and thunks section is that I don't believe you can dynamic_cast from a base class to a derived class due to the type-safety checking that dynamic_cast performs. This should probably be changed to static_cast, which does not do such checking and therefore allows potentially dangerous casts in that direction that could result in unfinished objects. Skijmpr (talk) 18:53, 30 October 2008 (UTC)

I might be missing something but I am not sure if this really calls D::f2 (*(*(d[0]/*pointer to virtual method table of D (for both B1 and D)*/)[1]))(d) When calling D::f2, shouldn't the "this pointer" that is passed in be fixed to point to the B2 in D? Also the vtable being used looks to be the wrong one... Cenkerg (talk) 13:58, 3 October 2009 (UTC)


Errors in Invocation[edit]

There are some errors in the 'Invocation' part; the 'this' pointer in the following call is incorrect :

  (*(*(d[+8]/*pointer to virtual method table of D (for B2)*/)[0]))(d+8) /* Call d->f2() */

The 'this' pointer passed to f2() function is the one of class D, because the f2() function has been overriden in D. So the correct version would be :

  (*(*(d[+8]/*pointer to virtual method table of D (for B2)*/)[0]))(d) /* Call d->f2() */

If f2() had not been overriden in class D, then in fact, the 'this' pointer would have been d+8.

The phrase It is impossible to call B2::f2 since it has been overridden in D's implementation. is also wrong; we can call both implementations like this :

  d->f2();   // normal virtual call, it invokes f2() as defined in D
  d->B2::f2();  // force call to f2 as defined in B2

Both aspects have been tested with a compiler, here is the test :

 
#include <iostream>
using namespace std;
 
class B1 {
public:
	void f0() {}
	virtual void f1() { cout << "'this' in B1::f1() is 0x" << this << endl; }
	int int_in_b1;
};
 
class B2 {
public:
	virtual void f2() { cout << "'this' in B2::f2() is 0x" << this << endl; }
	int int_in_b2;
};
 
class D : public B1, public B2 {
public:
	void d() {}
	void f2() { cout << "'this' in  D::f2() is 0x" << this << endl; }
	int int_in_d;
};
 
__declspec(noinline) void main()
{
	D*  d = new D();
 
	cout << "D  0x" << static_cast<D*>(d) << "\nB1 0x" << static_cast<B1*>(d) << "\nB2 0x" << static_cast<B2*>(d) << "\n\n";
 
	d->f1();
	d->f2();
	d->B2::f2();
}

Output :

D  0x00895250
B1 0x00895250
B2 0x00895258
'this' in B1::f1() is 0x00895250
'this' in  D::f2() is 0x00895250
'this' in B2::f2() is 0x00895258

Question[edit]

In the memory layout for the object b2, it has been shown that destructor of the class B2 exists in the VTABLE. But, in the B2 class declaration, no destructor is defined. Is the compiler generated destructor virtual by default?

Gowthamgowthamgowtham 15:33, 18 August 2007 (UTC)

What did the author mean with "There are exceptions for special cases as posed by the default constructor." (end of Example §) ? I don't have the answer, but I would really be interested in it... —Preceding unsigned comment added by Nielk.S (talkcontribs) 14:01, 23 August 2010 (UTC)

How about Java?[edit]

How is runtime binding implemented in Java-land? Thanks. 83.67.217.254 19:16, 26 August 2007 (UTC)

Lack of charts[edit]

This article badly needs illustrative images to explain the things that is hard to explain in text. If anybody can provide such images/find the proper way of requesting them, please do.--Henke37 21:11, 16 September 2007 (UTC)

Comparison with Objective-C[edit]

I think that a comparison with Objective-C would be nice since both it and C++ are extensions to C (and the dynamic nature of Obj-C is directly applicable to a discussion of v-tables in C++). —Preceding unsigned comment added by 131.107.0.73 (talk) 19:42, 31 October 2007 (UTC)

No Illustrations? BAD...[edit]

No illustrations or pictures? Hope someone to draw some pictures to help us understand better! 221.239.34.194 (talk) 04:43, 2 August 2008 (UTC)

Unclear wording[edit]

What on earth does the following mean? "When an object is created, a pointer to this vtable, called the virtual table pointer or vpointer, is added as a hidden member of this object (becoming its first member unless it's made the last[2])." The parenthetical remark seems to be saying that "Something is X, unless, of course, it isn't." Which conveys nothing. What is really meant here? —Preceding unsigned comment added by 173.50.151.91 (talk) 22:27, 30 September 2009 (UTC)

dynamic dispatch == run-time method binding?[edit]

Currently, this article states the following

A virtual method table, virtual function table, dispatch table, or vtable, is a mechanism used in a programming language to support dynamic dispatch (or run-time method binding).

Is dynamic dispatch the same as run-time method binding? Or does this statement want to point out that vtables are used for different purposes? --Abdull (talk) 20:55, 1 October 2010 (UTC)

Pointer fixup is not a virtual thing[edit]

A virtual call requires at least an extra indexed dereference, and sometimes a "fixup" addition, compared to a non-virtual call, which is simply a jump to a compiled-in pointer. It's not precise as it's suggests the pointer fixup is a disadvantage of virtual functions compared to non-virtual ones. But even if you call a "normal" function you may need the pointer fixup simply to provide the method with the memory layout it knows so it is able to access the correct fields. The vpointer is just one of possible fields it may need to access. An example:

#include <iostream>
 
class A1
{
public:
	void* a1() { return this; }
	int value_a1; 
};
 
class A2
{
public:
	void* a2() { return this; }
	int value_a2;
};
 
class B : public A1, public A2
{
};
 
int main()
{
	B b;
	std::cout << "this in a1(): " << b.a1() << "\nthis in a2(): " << b.a2() << std::endl;
}

No virtual functions here, no overridden functions even, but if you compile and run it (tested with g++ 4.4.5) the "thises" displayed will differ (unless you remove the fields, then no fixup is needed). I think this sentence and possibly the ending of the previous section need to be edited. Lampak (talk) 22:55, 6 February 2011 (UTC)

Locating the correct vtable?[edit]

In the section Invocation, the information about how the correct vtable is located is omitted. This information is central to the topic and should be added the the article! If anyone know this, please improve the article by expanding it on this point!

That is, how is pointer value at the position marked with "/*pointer to virtual method table of D (for B1)*/" computed?

This requires something similar to a hash map lookup, right? (Which can be optimised in a lot of cases of course.)

Liiiii (talk) 15:16, 4 August 2014 (UTC)

How could we possibly improve this article to make it more clear for the next person who has exactly the same question? Liiiii, when you figure this out, could you edit the article to make this more clear for the next person?

At compile time, yes, the compiler computes the offsets using something similar to a hash map lookup. As you suggested, that hash map lookup is optimized by the compiler. At run time, there is (practically) no computation -- all the offsets have already been hard-coded into the executable by the compiler.

I found the little picture on p. 14 of "Object-oriented programming with ANSI-C" helpful.

When the source code says

    void some_function( B1 * input ){
        ...
        input->f1();
        ...
    }

the compiler turns that line into assembly-language code that looks something like this:

    ...
    ; input->f1();
    LOAD R2:=[R1 + 16] ; get pointer to vtable into R2 from RAM
    LOAD R3:=[R2 + 24] ; get pointer to f1() into R3 from RAM
    CALL R3 ; execute function f1()
    ...

When some_function() is called, initially the input pointer (the "this" pointer) is in R1, pointing at some object that is "a kind of" B1 -- perhaps it is simply a B1, or perhaps it is some instance of a derived class like a D.

The indirect call through R3 supports polymorphism while also retaining W^X compatibility (i.e., the executable code never changes at run time).

This particular compiler uses the "+16" hidden member of every instance of everything that is "a kind of" B1 to hold a pointer to the one common shared vtable for that particular class. At run time, all objects of type D point to one and the same D vtable. All objects that are simply a type B1 point to some other vtable -- the B1 vtable. At run time, there is typically a vtable in memory for each class of objects in the program.

This compiler stores a pointer to the f1() method in location "+24" in every vtable of every class that is "a kind of" B1. At run time, because the D class overrides the default B1::f1() method with a different D1::f1() method, the D1 vtable (in location "+24") points to D1::f1().

My understanding is that practically all C++ compilers work very similarly. Recompiling the exact same source code with 2 different compilers, or even different versions of the same compiler, will likely produce offsets different from each other and from the "+16" and "+24" offsets in this example. But no matter what particular offsets are used, the net effect is the same:

That function is polymorphic -- when it is passed a pointer to an instance of D, it effectively does

    CALL _D1_f1 ; call D1::f1()

and later during the same run, when it is passed an instance that is simply a B1, it effectively does

    CALL _B1_f1 ; call B1::f1()

Does that answer your question about how the correct vtable is located at run time? (Or did you also want to know how the correct vtable is located at compile time?) --DavidCary (talk) 21:01, 20 November 2014 (UTC)