PS: Yet More on MI

[Hans-Dieter.Dreier@materna.de]

--MGYTwEF2CaIpt06q9jCxsHjnUNaUZDR0
Content-type: text/plain; charset="ISO-8859-1"
Content-transfer-encoding: quoted-printable

PS: Yet More on MI
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

Rethinking my last class layout proposal (see thread Yet More On MI), I cam=
e upon a similar class layout which trades less memory
for more time while achieving the same goals.

Additionally, I'd like to state the following:

Each mixin should be "open-ended", ie may have to ability to have an arbitr=
ary length (like a stack or an array).
Preferrably this length should also be able to be changed at runtime.
As a consequence, the compiler should not *have to* place objects behind ea=
ch other in the same memory object
since it probably does not know the length of the object for sure.
I'm not demanding that it never should place objects behind each other, how=
ever; since most classes have fixed length it will actually be the norm.
If a class or mixin is known to have fixed length, placing behind it is per=
fectly OK. =



Like my first proposal, this approach would use cMI since IMO the above con=
ditions rule out instance merging.
So one of the base classes will be "more equal" than the others.
I'll call that class the "MI class". The others will be called "mixed-n" cl=
asses here to distinguish them.


The proposed instance layout would be:


this -> - Reference to MI class if used as mixed-class, pointer to this oth=
erwise (Note a)
        - Reference to modified vtable (Note b)
        - (Instance items if any)

The "Reference to ttable" has been dropped.

Note a:
If a reference to this is used in the program itself, a reference to the MI=
 object is wanted rather than a reference to the mixin object.
That's what this instance item is good for.

This item can only be omitted in non-MI cases if global analysis shows that=
 this class is never used as a mixin.


Note b:
There will be an additional entry at the start of the vtable. It will point=
 to a "binary stuff" object (part) that contains
a table of offsets (short: otable), each corresponding to a vtable pointer.
The otable contains offsets from the start of the MI class (found at the st=
art of each mixin) to a place inside the memory object of the MI class wher=
e a reference
to the start of the mixin can be found. That pointer will be used as the mi=
xin virtual function's this pointer.

Thus this construction serves the same purpose as the ttable.
The ttable made lookup easy: Just take the n-th ttable entry (for virtual f=
unction n) and there is the correct this pointer.
The drawback was that this table had to be kept per instance, resulting in =
a serious memory hit if there are many virtual items.

The otable, OTOH, is shared among all instances of a class since it just co=
ntains offsets that are the same for each instance
and not actual this pointers which are differenct for each instance.
To fetch the virtual function's this pointer, an additional indirection mus=
t be used, however:
Take the n-th otable entry (for virtual function n-1), add its value (offse=
t) to the start of the MI instance.
Fetch the reference found at the resulting location and use it as the this =
pointer for the mixin's virtual function.

A prerequisite for this scheme to work as described is that a pointer to th=
e start of each mixin as well as a pointer to the start
of the MI instance can be found inside the MI instance.
Obviously this is always the case for direct mixins since cMI is used.

It is equally true for the MI instance itself:
Either it is not used as a mixin, then it is the MI instance, therefore the=
 condition is true.
Or it is used as a mixin, then there must be a pointer to this (now mixin) =
MI instance inside the toplevel instance.
This will not be at offset 0.
But since other virtual overrides are most likely, another vtable (and otab=
le) must be used anyway.

For "indirect" mixins (ie mixins within mixins) usually there will no be a =
reference to that indirect mixin inside the MI instance.
Most often it will be possible to place the mixin (which contains such a re=
ference) in the memory object of the MI instance, at a fixed offset
to the start of the MI instance. Thus in those cases there is no problem ei=
ther.

When there is no reference to a (indirect) mixin available at a fixed offse=
t from the start of the MI instance,
the compiler must add one (as a hidden instance item) and take care of its =
proper initialisation.


Behind the pointer to the otable there will be the vtable as commonly used =
(and described in my first proposal).


Here's the (adjusted) example from my first proposal. Offsets will be given=
 in sizeof (reference) rather than bytes.

class A {int a; virtual va1; virtual va2;}	// not "pure virtual" but overri=
deable is meant
class B {int b; virtual vb1; virtual vb2;
    virtual va1 =3D 0;}                           // va1 is pure virtual (i=
e used here, defined elsewhere)
class C {int c; mixin A ca; mixin B cb;         // contains 2 mixins
    int va2; int vb2;                           // va2 and vb2 are overridd=
en
    virtual va1 =3D 0;}                           // va1 is pure virtual (i=
e used here, defined elsewhere)

A AnA;      // A used standalone
C aC;       // A used as a mixin (together with B)


The memory layout looks like this:

AnA: =

    AnA            // MI class instance: If you check "this =3D=3D aC" insi=
de A standalone you get false because this is AnA
    vtable of A standalone
    a

vtable of A standalone:
    otable of A standalone
    va1 of A
    va2 of A

otable of A standalone:
    0
    0

(This was easy.)


aC:
    aC              // MI class instance
    vtable of C
    c
    ca
    cb

vtable of C:
    otable of C
    va1 of A

otable of C:
    3 (offset of ca in C)  // va1 always operates on an A if taken from A

ca:
    aC             // MI class: If you check "this =3D=3D aC" inside mixin =
A ca you get true
    vtable of mixin A ca
    a

vtable of mixin A ca:
    otable of mixin A ca
    va1 of A
    va2 of C       // overridden by C

otable of mixin A ca:
    3 (offset of ca in C)
    0

cb:
    aC
    vtable of mixin B cb
    b

vtable of mixin B cb:
    otable of B cb
    vb1 of B
    vb2 of C       // overridden by C
    va1 of A       // found in A

otable of cb:
    4 (offset of cb in C)
    0 (offset of aC in C)
    3 (offset of ca in C)
    =


Example for which to add a hidden reference to an indirect mixin:

class X {x1; virtual vx1; };

class Y : X {int y[*]; mixin X yx};             // length is unknown to com=
piler

class Z : Y {int z[*]; mixin Y zy};             // length is unknown to com=
piler

Z aZ;


Since we assume that the length of aZ is not known to the compiler, it will=
 not be able to place zy _behind_ z.
Neither will it be able to place zy _before_ z because the length of zy is =
unknown too.
So it must place Y in a separate memory object and since there is no fixed =
offset from aZ to the object zy,
yx cannot be accessed at a fixed offset from aZ.

Class layout could be as follows:

aZ:
	aZ
	vtable of Z
	zy
	yx			// this (hidden) reference was inserted by the compiler to solve the =
problem
	z...

(Next memory object)

vtable of Z:
	otable of Z
	vx1 of X yx

otable of Z:
	3 (offset of yx in Z)

zy:
	aZ
	vtable of Y
	yx
	y...

(Next memory object)

vtable of Y:
	otable of Y
	vx1 of X yx

otable of Y:
	3 (offset of yx in Z)

yx:
	aZ
	vtable of X
	x1

vtable of X:
	otable of X
	vx1 of X

otable of X:
	3 (offset of yx in Z)



The vtables and otables may be shared since the all are the same.


--

Regards,

Hans-Dieter Dreier
(Hans-Dieter.Dreier@materna.de)

--MGYTwEF2CaIpt06q9jCxsHjnUNaUZDR0
Content-type: text/plain; charset="ISO-8859-1"
Content-transfer-encoding: quoted-printable

IDENTIFIKATIONSANGABEN:
a11758a.txt IA5 DX-MAIL X.400 User Agent=

--MGYTwEF2CaIpt06q9jCxsHjnUNaUZDR0--