Using Continued Fractions for Efficient Subclass Checking

Dynamic subclass checks are common in many sub-paradigms of object-oriented programming. These checks may be simply implemented by following the superclass chain through the objects which represent the class hierarchy. However, in large or data-intensive applications, such as OODBMS, this simple checking strategy may have significant efficiency consequences. Very long class chains, which commonly occur, can cause much pointer following, which in turn has a knock-on effect on the overall performance of memory management. Measurements have shown that memory management is the most significant factor in the performance of large object-oriented systems.This paper describes a way of testing if one class is a subclass of another without involving any pointer accesses. On creation, each class is allocated a unique pair of integers, over which subclass tests may be performed using only arithmetic. The technique only works for single inheritance systems; the essence of the technique is to simulate the tree structure of the class hierarchy using the well-understood mathematical model of continued fractions.