An example of larger-scale object-oriented programming is the InterViews 3.1 toolkit [LCV88], written in C++ with multiple inheritance. Including component libraries, it comprises about 426 public classes. It has evolved along with C++, so the code contains some historical artifacts: most of these classes are written in a single-inheritance style with no separation of inheritance and subtyping, and have only a single word of dispatch information even with the C++ layout. Nevertheless, perusal of these classes reveals that the bidirectional layout would make many of them more efficient, using the multiple-inheritance extension of Section 4.2. The results are shown in Table 2.
With the bidirectional layout, every class is as compact as in the layouts generated by the DEC C++ compiler cxx (other compilers are similar), and 46 classes are more compact, some by as much as 4 words per object. Additional classes would be more compact if the uses of inheritance were ``virtual'' - the current classes sacrifice inheritability for performance, so the results here are generous to C++.
The total number of dispatch vectors is 465 for the bidirectional layout, and 537 for C++. Assuming that dispatch vectors all contain x words, 66x trampoline procedures must be generated for the bidirectional scheme versus 111x for C++ (Non-trampoline techniques require even more space). The total space used by shared dispatch information in the two layout schemes is 597x words for the bidirectional layout and 759x words for the C++ layout. Again, per-object space overhead is likely to dominate the dispatch vector overhead in real programs.
The attempt to separate inheritance from subtyping is a major source of inefficiency in the InterViews classes. About 30 classes (mostly members of the core InterViews library) hide their implementation in a pointer to a private class. This mechanism is actually less powerful than the separation provided by Theta. The use of private implementation classes suggests that the hierarchy of Figure 1 is common or at least desirable, as assumed.
Unfortunately, the private implementation pointer imposes even more space overhead than multiple inheritance. In addition to an extra object pointer at every level of inheritance, the fragmentation of the object into two pieces imposes at least another word of overhead per object with commonly-used memory allocators. This fragmentation overhead has not been added to Table 2.
It is interesting to note that the InterViews classes use multiple inheritance mostly for abstraction. Among the ten uses of multiple inheritance in the public InterViews classes, there is only one use of true multiple inheritance; the rest permit one class to implement several unrelated interfaces. For example, the classes for which the bidirectional layout generates a three-word dispatch header all implement three unrelated interfaces: Handler, MonoGlyph, and Observer. In a separate-compilation environment where densely-packed method indices are compiled into the code, a three-word dispatch header is minimal for these classes.
Andrew C. Myers. Bidirectional Object Layout for Separate Compilation.
Proceedings of OOPSLA '95, pp. 124-139.
Copyright © 1995 Association for Computing Machinery