MULTIPLE INHERITANCE

In languages that permit a class D to extend several parent classes A, B, C (that is, where A is not a subclass of B, or vice versa), finding field offsets and method instances is more difficult. It is impossible to put all the A fields at the beginning of D and to put all the B fields at the beginning of D. Global graph coloring One solution to this problem is to statically analyze all classes at once, finding some offset for each field name that can be used in every record containing that field. We can model this as a graph-coloring problem: There is a node for each distinct field name, and an edge for any two fields which coexist (perhaps by inheritance) in the same class.^[1] The offsets 0, 1, 2;… are the colors. Image 14.4 shows an example.
Image 14.4: Multiple inheritance of data fields.

The problem with this approach is that it leaves empty slots in the middle of objects, since it cannot always color the N fields of each class with colors with the first N colors. To eliminate the empty slots in objects, we pack the fields of each object and have the class descriptor tell where each field is. Image 14.5 shows an example. We have done graph coloring on all the field names, as before, but now the "colors" are not the offsets of those fields within the Objects but within the descriptors. To fetch a field a of object x, we fetch the a-word from x's descriptor; this word contains a small integer telling the position of the actual a data within x.
Image 14.5: Field offsets in descriptors for multiple inheritance.

In this scheme, class descriptors have empty slots, but the objects do not; this is acceptable because a system with millions of objects is likely to have only dozens of class descriptors. But each data fetch (or store) requires three instructions instead of one:

1. Fetch the descriptor pointer from the object.
2. Fetch the field-offset value from the descriptor.
3. Fetch (or store) the data at the appropriate offset in the object.

In practice, it is likely that other operations on the object will have fetched the descriptor pointer already, and multiple operations on the same field (e.g., fetch then store) won't need to refetch the offset from the descriptor; commonsubexpression elimination can remove much of this redundant overhead. Method lookup Finding method instances in a language with multiple inheritance is just as complicated as finding field offsets. The global graph-coloring approach works well: The method names can be mixed with the field names to form nodes of a large interference graph. Descriptor entries for fields give locations within the objects; descriptor entries for methods give machine-code addresses of method instances. Problems with dynamic linking Any global approach suffers from the problem that the coloring (and layout of class descriptors) can be done only at link time; the job is certainly within the capability of a special-purpose linker. However, many object-oriented systems have the capability to load new classes into a running system; these classes may be extensions (subclasses) of classes already in use. Link-time graph coloring poses many problems for a system that allows dynamic incremental linking. Hashing Instead of global graph coloring, we can put a hash table in each class descriptor, mapping field names to offsets and method names to method instances. This works well with separate compilation and dynamic linking. The characters of the field names are not hashed at run time. Instead, each field name a is hashed at compile time to an integer hash_a in the range [0, N − 1]. Also, for each field name a unique run-time record (pointer) ptr_a is made. Each class descriptor has a field-offset table Ftab of size N containing field-offsets and method instances, and (for purposes of collision detection) a parallel key table Ktab containing field-name pointers. If the class has a field x, then field-offset-table slot number hash_x contains the offset for x, and key-table slot number hash_x contains the pointer ptr_x. To fetch a field x of object c, the compiler generates code to

1. Fetch the class descriptor d at offset 0 from object c.
2. Fetch the field name f from the address offset d + Ktab + hash_x.
3. Test whether f = ptr_x; if so
4. Fetch the field offset k from d + Ftab + hash_x.
5. Fetch the contents of the field from c + k.

This algorithm has four instructions of overhead, which may still be tolerable. A similar algorithm works for dynamic method-instance lookup.

The algorithm as described does not say what to do if the test at line 3 fails. Any hash-table collision-resolution technique can be used. ^[1]Distinct field name does not mean simple equivalence of strings. Each fresh declaration of field or method x (where it is not overriding the x of a parent class) is really a distinct name.