Xref: utzoo comp.lang.eiffel:311 comp.lang.c++:3982 comp.lang.misc:3072
Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!mailrus!tut.cis.ohio-state.edu!cs.utexas.edu!usc!randvax!florman
From: florman@randvax.UUCP (Bruce Florman)
Newsgroups: comp.lang.eiffel,comp.lang.c++,comp.lang.misc
Subject: Re: Record layout for multiple inheritance
Message-ID: <2129@randvax.UUCP>
Date: 12 Jul 89 20:45:22 GMT
References: <18498@mimsy.UUCP>
Reply-To: florman@rand-unix.UUCP (Bruce Florman)
Organization: Rand Corp., Santa Monica, Ca.
Lines: 166

In article <18498@mimsy.UUCP> pugh@mimsy.UUCP (Bill Pugh) writes:
>I've several rumors about techniques for record layout with multiple
>inheritance, but no solid information. Does anyone know for any 
>results in this area?
>
>The basic problem is as follows. We have record types with the following
>fields:
>  type x = {a : int, b : int}; 
>	y = {a : int, c : int};
>	z = {a : int, b : int, c : int};
>
>  We wish to have z be a subtype of both x and y. How can we layout the
>fields in x, y and z so that, for example, we can extract the field c
>in constant time from a record that might be either type y or z.
>
>  One answer is to place a at offset 0, b at offset 4 and c at offset -4. 
>By not always having pointers to records point to the first field, we
>can get simple constant time access to fields. It is not always possible
>to layout fields this way (for example, it is not possible in the case of
>triple inheritance).
>
>  I heard that Bjarne Stroustrup originated this idea, but have been unable
>to find any references. In his book, Bertrand Meyer also claims to have a 
>technique for doing constant-time access (section 15.4.2), although he
>does not give any details. Is this described anywhere?
>
>In summary, does anyone have pointers to published work on this technique?


    I don't have any pointers to published material, but I can tell you 
how I've gone about it in an object system that I wrote.  As it happens, 
the system that I wrote was Lisp based, but the techniques are applicable 
anywhere.  I don't know how Eiffel or C++ (or Smalltalk or Trellis-Owl or 
whatever) do it, but I suspect that they use some variation on this 
approach.

    First, the exact nature of the object system in your example above is 
not clear to me.  Does the fact that both x and y have a field named `a' 
indicate that they are both subtypes of some other record with a field 
named a?  To facilitate my explanation, I will change the example a little 
bit, so we won't have to deal with this question.

    Suppose the source declarations are as follows (in some pseudo-
Pascalish syntax).

    X = object()
	a: integer;
	b: integer;
    end;

    Y = object()
	c: integer;
	d: integer;
	e: integer;
    end;

    Z = object(X, Y)
	f: integer;
    end;

This syntax is intended to convey that type Z inherits from both X and Y, 
and it also defines its own field named f.

    At compile-time, we can determine an offset to each of these fields, 
which I will call the "field offset."  To simplify this example, I will 
assume that the size of an integer is 1.  You can scale the offsets 
appropriately for your own architecture.  So the offsets associated with 
each field are ...

	X.a -> 0
	X.b -> 1

	Y.c -> 0
	Y.d -> 1
	Y.e -> 2

	Z.f -> 0

    At link-time (system assembly time in Eiffel), it is possible to 
assign a unique integer index, called the "class index" to every class 
in the system.  For this simple example the indices could be ...

	X -> 0
	Y -> 1
	Z -> 2

    At run-time, there is a data structure called the "class descriptor" 
associated with each class in the system.  One of the things stored in 
the class descriptor is a dope vector, which is indexed by the class 
indices.  The values stored in this vector are offsets from the address 
of an object to the start of that class' fields, and we'll call them the 
"dynamic offsets."  For our simple example, the class descriptors would 
look something like this.

	X -> dope vector: [ 1, -, - ] other stuff: ...
	Y -> dope vector: [ -, 1, - ] other stuff: ...
	Z -> dope vector: [ 1, 3, 6 ] other stuff: ...

The dope vector for class X has a dynamic offset at index 0, because 0 
is the class index of X.  The other entries are unused, because X does 
not inherit from Y or Z.  Similarly, the dope vector for Y has only one 
valid entry, at index 1.  Z on the other hand, which inherits from both 
X and Y, and also has its own fields, has valid dynamic offsets at all 
the indices.

    So finally, the run-time layout of the instances of these classes is 
as follows.

	instance of X:	[ X, a, b ]
	instance of Y:	[ Y, c, d, e ]
	instance of Z:	[ Z, a, b, c, d, e, f ]

The first chunk of data in an object is something which identifies 
the class to which it belongs.  This might be a pointer to the class 
descriptor itself, or it might simply be a tag.  The remainder of the 
fields are laid out sequentially, keeping all the fields from any one 
class together.

    Now, to access field d of an object which might be an instance of 
either Y or Z, the following steps are executed.

    1.	Fetch the class descriptor from the object.
    2.	Fetch the dope vector from the class descriptor.
    3.	Fetch the dynamic offset at index 1 from the dope vector (since 
	1 is the "class index" of Y, and d was defined in class Y).
    4.	Add 1 to the dynamic offset (since 1 is the "field offset" of d), 
	giving d's actual offset from the address of the object.

In the case where the object is an instance of Y, the value fetched in 
step 3 is 1, so the actual offset of d is 2.  In the case where the 
object is an instance of Z, the value fetched in step 3 is 3, so the 
actual offset of d is 4.  We can see from the run-time object structures 
that these offsets are correct.  If the compiler had chosen to lay out 
an instance of Z differently, say like [ Z, f, c, d, e, a, b ], then Z's 
dope vector would have looked like [ 5, 2, 1 ] and d's actual offset 
would be 2 + 1 = 3.

    From an efficiency standpoint, this may look rather grim, since 
accessing a field requires three memory fetches and another addition.  
Fortunately there are ways to optimize some of this away.  For instance, 
if the dope vector is the first item within the class descriptor, then 
step 2 is essentially a no-op.  Also, in well designed o-o code, most of 
the field accesses will be from the "self" object ("current" in Eiffel, 
"this" in C++), therefore the dope vector and even the dynamic offsets 
may be cached.  Thus the *average* cost of computing the address of a 
field may approach the cost of the single addition, which isn't too bad.

    As I said before, I don't know for sure what techniques are used in 
Eiffel or C++.  This is how I've done it.  If anyone sees any glaring 
inefficiencies in this system, I'd really like to hear about them.  One 
obvious place to look for improvement is in the storage of the dope 
vectors.  When the inheritance hierarchy is very wide but shallow, the 
dope vectors will have a whole lot of empty space in them.  I imagine 
that someone can find a clever scheme to pack them into a smaller space.  
Any suggestions?


>	Bill Pugh
>	Assistant Professor
>	University of Maryland, College Park
>	pugh@mimsy.umd.edu

    Bruce Florman
    Associate Computer Scientist
    The RAND Corporation
    florman@rand.org