Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-06-30
2004-03-30
Follansbee, John (Department: 2126)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C717S108000
Reexamination Certificate
active
06714991
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to determining relationships between objects in object-based systems. More particularly, the present invention relates to efficiently performing subtype checks on objects in object-based systems.
2. Description of the Relevant Art
Many object-based computing systems are structured such that objects are members of specific classes and sub-classes which define the functionality that is available to the objects. During program execution, a virtual machine typically checks relationships between objects in order to facilitate the execution of the program. By way of example, a virtual machine may check sub-class, or subtype, relationships between objects. In some programming languages, e.g., the Java™ programming language developed by Sun Microsystems, Inc. of Palo Alto, California, constructs within the programming languages involve sub-class checks. Such sub-class checks generally involve determinations of whether a particular object is of a given type. That is, the class structures associated with the program are checked to determine the type of the particular object.
FIG. 1
is a diagrammatic representation of a conventional class structure. A class structure
102
, i.e., a class hierarchy, includes a class
106
and sub-classes
110
. In general, class
106
is an abstract class that may include any number of sub-classes
110
. As shown, sub-class “1”
110
a
, sub-class “2”
110
b
, and sub-class “N”
110
c
are “direct” sub-classes of class
106
, while sub-class “A1”
110
d
is a direct sub-class of sub-class “1”
110
a
. Sub-class “A1”
110
d
may be considered to be an indirect sub-class of class
106
since sub-class “A1”
110
d
is a sub-class of sub-class “1”
110
a
, which is a sub-class of class
106
.
Class
106
typically includes a variety of different functions, or methods. Each sub-class
110
generally contains a different set of functions. By way of example, sub-class “1”
110
a
will generally include functions that are specific to objects which are a part of sub-class “1”
110
a
. An object that is a member of class
106
may perform substantially all functions associated with class
106
. Any object that is a member of any of sub-classes
110
is also a member of class
106
. As such, an object that is a member of any of sub-classes
110
may also perform the functions associated with class
106
. However, an object that is a member of a particular sub-class, e.g., sub-class “1”
110
a
, may not perform the specific functions associated with a different sub-class, e.g., sub-class “2”
110
b
. Therefore, a determination of which sub-class
110
an object belongs to effectively determines the functions that the object may perform.
A narrowing cast may be used at runtime to effectively view an object defined by class
106
as an object defined by sub-class “1”
110
a
. However, since the object defined by class
106
may be defined by sub-class “2”
110
b
, rather than by sub-class “1”
110
a
, a check is typically made to determine whether associated the object with sub-class “1”
110
a
is accurate. As will be appreciated by those skilled in the art, a check regarding whether an object is associated with sub-class “1”
110
a
is effectively a check to determine whether the object is associated with at least sub-class “1”
110
a
. In other words, an object that is associated with sub-class “A
1
”
110
d
will generally be determined to be associated with sub-class “1”
110
a
as well.
In a Java™ environment, a function which determines the subtype of an object, e.g., an is_subtype function, may be statically encoded. While methods used to statically encode the function may vary, one method that is commonly used involves the use of a two-dimensional bit matrix where a bit at a location defined by (i,j) encodes the result of is_subtype(ti,tj). Using such a matrix, a subtype check effectively involves indexing into the matrix to determine the subtype of an object. However, the size of the matrix may be substantial, and the subtype checks are often slow due to the bit manipulation of instructions that is typically required.
In general, when sub-type checks are made, substantially all sub-types of a type, e.g., substantially all sub-classes of a class, must typically be checked to determine the sub-type of a particular object. In some hierarchical class structures, e.g., class structure
102
of
FIG. 1
, the number of sub-classes which must be checked may be relatively high. By way of example, some classes may have hundreds of associated sub-classes. As such, the implementation of subtype checks often proves to be inefficient when multiple subtypes are available, as is the case with interfaces defined in the Java™ programming language. That is, when multiple subtypes are available, the checking of each subtype is typically time-consuming, as mentioned above. In addition, implementing subtype checks in a system which uses multiple inheritance layers, e.g., systems defined in the C++ programming language, is also often inefficient. For a system with multiple inheritance layers, subtype checks are generally difficult to implement efficiently due to the fact that each layer of inheritance must be checked.
The implementation of efficient subtype checks is important since the checks may occur frequently. When the checks occur frequently during the execution of a program the overhead associated with the checks may be relatively high. In some cases, a run-time subtype check, or test, may require on the order of approximately eight instructions which, as will be appreciated by those skilled in the art, may be significant with respect to the overall program, especially if repeated run-time subtype checks are made. Hence, the speed at which the program executes may be compromised by the frequent subtype checks.
Typically, when subtypes are checked during the execution of a program, substantially all classes and methods associated with the program must be known. Data structures are often constructed to list all classes and methods associated with a program, so that the classes and methods are readily accessible. In other words, data structures used in subtype checks must often be computed before program execution. Such data structures are often relatively large, and consume significant system resources. Further, the requirement that all classes and methods associated with a program are known is not compatible with systems which utilize dynamic linking, or dynamic class loading, as dynamic linking allows the classes and methods associated with the program to effectively change. The functionality of a program may be compromised by the inability to utilize dynamic linking. In an environment which uses dynamic linking, the data structures are generally recomputed after every operation which involves class loading, which is time-consuming and, hence, inefficient.
Therefore, what is desired is a method and an apparatus for improving the efficiency with which subtype checks may occur. More particularly, what is desired is a method and an apparatus for efficiently performing subtype checks without requiring that data structures be recomputed each time a class loading operation occurs.
SUMMARY OF THE INVENTION
Methods and apparatus for performing fast subtype checks during program execution are disclosed. According to one aspect of the present invention, a method for quickly and efficiently determining a type associated with an object that is a part of an object-based computing system includes obtaining a candidate type from a dynamic storage location that is associated with a class which is associated with the object, and comparing the candidate type against a first type that is potentially the same as the candidate type. A determination is then made as to whether the candidate type is substantially equal to the first type. When the determination is that the candidate type is substantially equal to the first type, an indication that the candidate type is substantially equal to the firs
Bak Lars
Hölzle Urs
Mitrovic Srdjan
Beyer Weaver & Thomas LLP
Follansbee John
Nguyen Van H.
Sun Microsystems Inc.
LandOfFree
Method and apparatus for implementing fast subclass and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for implementing fast subclass and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for implementing fast subclass and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3253031