Many modern programming language systems, such as Java and C++, are based on object oriented programming. Object oriented programming languages tend to be more flexible and robust because many data types are grouped into generic object classes. Generic object classes are defined so that object instances can share models and reuse the class definitions in their code. Each instantiation of an object class is a subclass, or subtype, with corresponding procedures and data variables that enable processing of the instantiated object. The instantiated object is what actually runs in the computer.
There are two distinct phases in the processing of a computer program by a computer, compile-time and run-time. Compile-time is the initial step of translating programming source code into executable code, which includes both computer instructions and their associated supporting data structures. In contrast, run-time is the final step where the executable code is executed to perform its intended function, such as creating, classifying, and manipulating object instances. Compile-time and run-time are often concurrently active in a modern computing system. For example, run-time execution might initiate compilation activity, or the compiler might make use of data structures created by run-time activities.
Source code often references objects as generic classes. This allows the source code to operate correctly on any object instance that conforms to the generic class. Sometimes, however, object classes are hierarchically organized into a sub-typing array, which is typically a decision tree structure with the generic classes branching under a single object class at the tree's root and multiple levels of object subtypes branching from each parent object class above. This tree structure is often called the “class hierarchy”. Source code may request that an object be tested as to whether it is a subtype of some particular class being sought by the programmer. Such tests are called subtyping tests. If an object passes a subtyping test, the source code which controls subsequent program execution may treat the object as an instance of the sought class, using in conjunction with the original object the sought class's associated procedures and data variables. Subtyping tests are common in many object-oriented applications, and may occur millions of times per second.
Subtyping tests are compiled into executable codes called supertype requests, which search for the desired supertype in the given object's data structures. The executable code of a class includes information to help determine subtyping relationships. In a statically compiled language like C++ this information is directly emitted by the static compiler. The current state of the art in Java, for example, is for the runtime system to store an array or list of supertypes, sometimes referred to a supertyping array, is associated with the class data structure of each class, at the time it is loaded into an application. It should be appreciated that supertyping arrays are created for the compiler's benefit, and usually are created concurrently with the running, or run-time, of the application. Supertyping arrays usually are relatively large because they contain all available object supertype classes. Accordingly, they are not embedded into the class data structures of the executing code, and require the additional loading of a pointer to be searched. Searching the supertyping array is generally a relatively slow process. In current systems, run-time object subtype checks that search the supertyping array are called millions of times per second. Thus, searching the supertyping array for object subtyping presents a significant time penalty.
Certain object types such as data arrays and interfaces are special as they have special subtyping rules, as dictated by the source language. For example, in Java, a data array can be a single or multi-dimensional data structure, whose supertypes are determined in a complex manner from the supertypes of its array element type. An interface is property that holds true over some collection of object classes that are not related to the parent-subtype tree relationship of the class hierarchy. This lack of object interface structure may force each object type in a large tree to be tested for implementation of a particular interface type, as opposed to simply searching up the tree to a generic interface class.
Thus, what is required is a more efficient run-time object subtype test that avoids unnecessarily searching large class hierarchies.