Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!purdue!decwrl!bothner
From: bothner@decwrl.dec.com (Per Bothner)
Newsgroups: comp.lang.c++
Subject: Efficiency of Multiple Inheritance
Message-ID: <1484@bacchus.dec.com>
Date: 12 Jun 89 04:53:59 GMT
Organization: DEC Western Software Lab
Lines: 70

If one adds a feature to a language, a general goal is that
a user should only have to pay to cost of the feature when
using it. Adding multiple inheritance to C++ violates this
rule: Now \every/ virtual function call must do an extra addition,
to adjust the 'this' pointer properly. In most cases (including
all cases of single inheritance), the adjustment is zero,
but that cannot be determined at compile time. So when a virtual
function is called, the adjustment is taken from the virtual
function table, added to the 'this' pointer, and the result passed
to the called routine.

An alternative is to have the \called/ routine do the adjustment,
instead of the \caller/. The trick is to have stub routines,
which adjust 'this' and then jump to the real routine.

E.g.:

class A {
   ...
};

class B {
   virtual void f();
   virtual void g();
};

class D : public A, public B {
   virtual void f();
};

Consider the virtual function table used when a D instance
is pointed to by a B pointer. It has two slots:
The g slot points directly to B::g.
However, the f slot points to this compiler-generated stub:

void __D_via_B_f(THIS)
{
    ((D*)((char*)THIS - sizeof(A))->D::f(); // essentially
}

The obvious problem is that this costs an extra stack frame,
copying all the parameters, and an extra procedure call.
However, if you are generating machine instructions directly
(instead of translating to C), you can simplify each stub to two
instructions: an add (of a constant to a parameter register or
stack location), and a jump (to the known address of D::f). (*)
Even if you are translating to C, you can win it your target
C compiler does proper tail-call elimination (which is
required for Scheme compilers, but unusual for C compilers).

Another advantage of this scheme is that the virtual function
table does not need to store the adjustment values, so each
slot remains 32 bits (typically) instead of doubling to 64 bits.

Comments? Am I missing something?

(*) On some machines (including ones made by a well-known mini-computer
manufacturer), the start of a procedure is not its first instruction,
but an entry mask instead. This complicates life. The stub routine
must jump to the first instruction, skipping the entry mask.
More bothersome is that we must make sure that the stub routine
has the same entry mask as the real routine. It is possible to
copy over the entry mask when the program is initialized (using
mechanisms similar to those used to call constructores for static
instances). [The entry mask is not known at compile time, though
it is known at link time. Suitable linker magic could work.]
-- 
	--Per Bothner
Western Software Lab, Digital Equipment, 100 Hamilton Ave, Palo Alto CA 94301
bothner@wsl.dec.com ...!decwrl!bothner