Fast Constant Time Type Inclustion Tests
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.
Near Optimal Hierarchical Encoding of Types
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. We developed a new algorithm based on graph
coloring which computes a near optimal hierarchical encoding of type
hierarchies. The algoritm is described in an article which will appear at
ECOOP'97 (
abstract
and
article
(73583 bytes)).
To evaluate the algorithm the complete source code and test data is available
for download (98304 bytes). The source code
is written in ANSI C and has been tested on Digital Unix, SunOS and MacOS with
Metrowerks C.
Efficient Type Inclusion Tests
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. These algoritms
and performance data are described in an article which will appear at
OOPSLA'97 (
abstract
and
article
(92305 bytes)).
To evaluate the algorithm the complete source code and test data wil be
available soon for download. The source code is written in ANSI C++ and has been
tested on Digital Unix, SunOS, NextStep and MacOS with Metrowerks C.
Last updated by Andreas Krall on
July 15th 1997.