The bidirectional layout can be seen as a way of tuning the basic C++ object layout approach [Str87] to work well with current architectures and programming practice. Almost all the optimizations defined here can be applied to C++ compilers in a straightforward manner.
Much work on object layout has focused on assigning non-conflicting indices so each class has a single dispatch vector [DMSV89]. The resulting dispatch vectors may be sparse and contain multiple holes, so compressing them is a major concern [Dri93][PW90].
There are two important problems with these techniques: first, they are not compatible with separate compilation. Adding a new class or classes to the system can require recomputing method indices for other portions of the system, since the entire type hierarchy must be analyzed to select method indices. Second, in a large system, the complex (usually coloring-based) algorithms can require a lot of time; times on the order of an hour have been reported for the Smalltalk-80 hierarchy [AR92]. For many systems, these techniques are impractical, and a scheme based on fast local rules is preferable.
Rose [Ros88] investigates how to perform the method dispatch operation and settles on fat dispatch tables, where method code is placed directly in the dispatch vector. Fat dispatch vectors will work with bidirectional layout, but seem unlikely to improve on the standard dispatch sequence - the sequences usually take the same amount of time, and fat entries take a performance hit when the method is too large to fit, because an extra jump instruction is required. In addition, fat entries may hurt cache performance.
The implementation techniques for multiple inheritance described in Section 4 involve compiling different versions of method code for different inheriting contexts, a technique similar to the production of specialized code in SELF [Cha92][CUL89] - though the technique is used there to solve a more general problem, since SELF is not statically typed. In the SELF implementation, different versions of the code are produced for every inheriting class, so code sharing is minimal and code duplication can become a problem. The two techniques suggested in Section 4 preserve code sharing better. The more general technique produces at most two versions of the inherited code, and thus does not suffer from excessive code duplication.
Andrew C. Myers. Bidirectional Object Layout for Separate Compilation.
Proceedings of OOPSLA '95, pp. 124-139.
Copyright © 1995 Association for Computing Machinery