| Abstract |
Fast
subclass tests are crucial for the performance of object-oriented
languages, especially those with dynamic typing. Unfortunately,
fast constant time subclass encodings to date present a difficult
tradeoff: either choose a simple encoding with O(n^2) space
requirements (where n is the number of classes) or a more
complicated and slower to construct encoding with better space
properties. In this paper, we present a new subclass test
encoding, called the Packed Vector Encoding (PVE), that is fast,
simple and requires average case O(n log n) space.
|