Near Optimal Hierarchical Encoding of Types

Andreas Krall
Institut für Computersprachen
Technische Universität Wien
Argentinierstraße 8
A-1040 Wien, Austria
andi@complang.tuwien.ac.at

and

Jan Vitek
Object Systems Group
Centre Universitaire d'Informatique
Université de Genève
24, rue Général-Dufour
CH-1211 Genève 4, SWITZERLAND
jvitek@cui.unige.ch

and

Nigel Horspool
Department of Computer Science, University of Victoria
P.O. Box 3055, Victoria, BC, Canada V8W 3P6
nigelh@csr.uvic.ca

Abstract

A type inclusion test is a procedure to decide whether two types are related by a given subtyping relationship. An efficient implementation of the type inclusion test plays an important role in the performance of object oriented programming languages with multiple subtyping like C++, Eiffel or Java. There are well-known methods for performing fast constant time type inclusion tests that use a hierarchical bit vector encoding of the partial ordered set representing the type hierarchy. The number of instructions required by the type inclusion test is proportional to the length of those bit vectors. We present a new algorithm based on graph coloring which computes a near optimal hierarchical encoding of type hierarchies. The new algorithm improves significantly on previous results - it is faster, simpler and generates smaller bit vectors.