Efficient Type Inclusion Tests

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

and

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

Abstract

A type inclusion test determines whether one type is a subtype of another. Efficient type testing techniques exist for single subtyping, but not for languages with multiple subtyping. To date, the only fast constant-time technique relies on a binary matrix encoding of the subtype relation with quadratic space requirements. In this paper, we present three new encodings of the subtype relation, the packed encoding, the bit-packed encoding and the compact encoding. These encodings have different characteristics. The bit-packed encoding delivers the best compression rates: on average 85% for real life programs. The packed encoding performs type inclusion tests in only 4 machine instructions. We present a fast algorithm for computing these encoding which runs in less than 13 milliseconds for PE and BPE, and 23 milliseconds for CE on an Alpha processor. Finally, we compare our results with other constant-time type inclusion tests on a suite of 11 large benchmark hierarchies.