Empirical Assessment of Object-Oriented Implementations with Multiple Inheritance and Static Typing
Abstract
Object-oriented languages involve a trade-off between three aspects, namely multiple inheritance, runtime efficiency and open world assumption (OWA), i.e. dynamic loading. The runtime efficiency of object-oriented programs is conditioned by the underlying implementation technique and compilation scheme. The former is concerned by the precise data structures that support basic object-oriented mechanisms (namely method invocation, attribute access and subtype testing). The latter consists of the production line of an executable program from the source code files, including compilers, linkers, loaders, virtual machines and so on. Many implementation techniques have been proposed and several compilation schemes can be considered from fully global compilation, under the closed-world assumption, to fully separate compilation, with dynamic loading, under the OWA, with midway solutions that involve separate compilation and global linking. In this article, we review a significant subset of all possible combinations and present a systematic empirical comparison of their respective efficiency with all other things being equal. The testbed consists of the Prm compiler that has been designed to implement various alternative techniques, in different compilation schemes. The considered techniques include C++ subobjects, coloring, perfect hashing and binary tree dispatch. A variety of processors have been considered. Qualitatively, these first results confirm the intuitive or theoretical abstract assessments of the tested approaches---as expected, efficiency increases as CWA strengthens. From a quantitative standpoint, the results are the first to precisely compare the efficiency of techniques that are closely associated with languages, e.g. C++ and Eiffel. They also confirm that perfect hashing should be used for implementing Java interfaces.