Space- and time-efficient memory layout for multiple inheritance

Traditional implementations of multiple inheritance bring about not only an overhead in terms of run-time but also a significant increase in object sp ace. Far example, the number of compiler-generated fields in a certain obje ct can be as large as quadratic in the number of its subobjects. The proble m of efficient object layout is compounded by the need to support two diffe rent semantics of multiple inheritance: shared, in which a base class inher ited along distinct paths occurs only once in the derived class, and repeat ed, in which this base has multiple distinct occurrences in the derived. In this theoretical and foundational paper, we introduce two new techniques t o optimize memory layout for multiple inheritance The main ideas behind the se techniques are the inlining of virtual bases and bidirectional memory la yout. Our techniques never increase time overhead, and usually even decreas e it. We show that in some example hierarchies, more than ten-fold reductio n in the space overhead can be achieved We analyze the complexity of the al gorithms to apply these techniques, and give theorems to estimate the effic acy of this application. For concreteness, techniques and examples are disc ussed in the context of C++.