Quantifying and Evaluating the Space Overhead in C++ Memory Layouts (Revised April 2, 1999)

This paper develops a formalism that precisely characterizes when class tables are required for C++ memory layouts. A memory layout is a particular choice of data structures fom implementing run-time support for object-oriented languages. We use this formalism and other techniques to quantify and evaluate, on a set of benchmarks, the space overhead for a set of C++ memory layouts. In particular, this paper studies the space overhead due to three language features: virtual dispatch, virtual inheritance, and dynamic typing. To date, there has been no scientific quantification or evaluating of C++ memory layouts. Our approach can help C++ implementors. This work has already influenced the memory layout design choices in the next version of IBM's Visual Age C++ compiler.

Applying our approach to a set of five benchmarks, we demonstrate that the impact of object-oriented space overhead can vary dramatically between applications (ranging from 0.42% to 99.79% for our benchmarks). In particular, applications whose object space is dominated by objects that heavily use object-oriented language features will be significantly impacted by the choice of a memory layout. The two end points in the spectrum of our memory layouts differ by at least 95% for each of our benchmarks.