Simple and Efficient Subclass Tests
Date Friday, 30NOV01
Time 2-3pm
Speaker Jonathan Bachrach
Affiliation MIT AI Lab
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.
Location 200 Technology Square (aka "NE43")
Room 8th Floor Playroom