Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-10-06
2001-11-13
Courtenay, III, St. John (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C717S152000
Reexamination Certificate
active
06317796
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the increasing the execution speed of object-oriented programs. More specifically, the invention relates to utilizing information collected during execution of an object-oriented program for subsequent executions.
The fundamental idea behind object-oriented languages is the combination of both data and the methods (or functions) that operate on that data into a single unit, which is called an object. An object's functions typically provide the only way to access the data that is encapsulated by the object. The data is accessed by sending a message to the object instructing the object to invoke the method specified by the message.
Efficient message dispatch is of paramount importance in object-oriented languages. This is because message dispatch is a very frequent operation in object-oriented programs and is performed at runtime; therefore, it should be as fast as possible. Message dispatch, however, is far from being a trivial operation. Unlike procedural programming languages (e.g., the C programming language) that can determine a function's address before runtime, object-oriented languages must determine the method that handles a message that has been dispatched to a receiver object at runtime, and it may involve an extensive search.
In order to better understand the complexities of message dispatch,
FIG. 1
shows a class hierarchy including methods of each class. A class hierarchy
1
includes at its root a parent class A
3
that defines two virtual functions foo( ) and bar( ). Virtual functions are functions that may be defined in a parent class and redefined in the children classes. Classes B
5
and class C
7
inherit the data and methods of the parent class A. As shown, class B does not redefine either of the virtual functions foo and bar. However, class C redefines the virtual function foo. When an object of class C is requested to invoke the method foo, the method invoked will be the method defined by the class C, not the parent class A. Classes D
9
and E
11
also redefine the method foo.
As it is generally impossible to determine the class of an object statically, the search for the correct method is performed at runtime, during message dispatch. There are many known techniques for implementing method dispatch. For example,
FIG. 2
shows an inline cache. Assume a method
51
was originally as follows:
main( )
{
. . .
x.foo( );
. . .
}
Thus, the method main includes a statement x.foo( ) in order to invoke the method foo of object x.
During runtime, the system would have to determine to which class object x belongs before the method to handle the method could be invoked. With an inline cache, the first time the system determines the class to which object x belongs, a direct call to the class's method is written into the computer code.
Assuming that object x is a member of class A, the call x.foo( ) is changed to a direct call A::foo( ). The arrow specifies a method foo for class A
53
. Since the object x may not be of class A every time, a prolog
55
verifies that the object x is of the correct class, which is represented as the expression x=A meaning that it is determined if the class of object x is equal to class A. The class of an object may be determined from a value stored in the object. If the object is of the correct class, a jump is performed to method code
57
that handles the message.
Returning to prolog
55
, if the object is not of class A, a method lookup routine is called in order to determine the correct method. Once the correct method is found, the system updates the message dispatch (or call) site with a direct call to that method. Additionally, the system updates the prolog to specify the new class. As an example, assume that the first time that the system encountered x.foo ( ), object x was of class A and the data structures were modified as shown in FIG.
2
.
Once the data structures are modified as shown, subsequent calls to x.foo( ) will be substantially more efficient if object x is of class A. However, if object x subsequently is of class B, prolog
55
calls a method lookup routine to find the method and let's assume it determines that object x is now of class B. Referring again to
FIG. 1
, it is seen that the method foo for class B is the same method foo as defined in class A (ie., class B did not redefine the virtual function foo). Accordingly, the message dispatch in method
51
will be changed to B::foo ( ) and the condition in prolog
55
will be changed to x=B.
An inline cache may be an efficient way of implementing message dispatch if the object at a call site bar remains the same class. However, if the object is of multiple classes, the system is continually calling the method lookup routine and patching the call site and prolog. Thus, the system may be actually less efficient.
Another technique for implementing message dispatch is the use a polymorphic inline cache as shown in FIG.
3
. As before, a method
101
originally included a method dispatch x.foo( ). With a polymorphic inline cache, a stub
103
is generated that is able to perform the message dispatch for different receiver types. The original message dispatch is overwritten with a call to the polymorphic inline cache stub
103
. Each time a new receiver type is encountered, a statement is added to the stub. As shown, three different receiver types of have been encountered thus far. If the receiver type has been encountered, a call is made to the method to handle the message for that receiver type. Otherwise, the method lookup routine is called to determine the appropriate method to handle the message. Typically, a new statement will be added to stub
103
in order to handle each new receiver type.
The polymorphic inline cache is more flexible than the inline cache as it is able to handle multiple receiver types. However, a drawback of the polymorphic inline cache is that as more receiver types are encountered, the stub continues to grow and it becomes less and less efficient at performing message dispatch. For example, the system may need to plow through multiple if statements before finding the right method to handle the message.
FIG. 4
shows another message dispatch technique called hashing. In hashing, the original message dispatch in a method
151
, x.foo( ), is overwritten with a call to a hash function
153
. The hash function hashes the receiver type and the message in order to form a hash key, which is typically an index into a hash table
155
. The hash table includes an index
157
, receiver types
159
, messages
161
, and methods
163
. Once the hash function hashes to a row in hash table
155
, the receiver type and message are retrieved from columns
159
and
161
of the hash table. If the receiver type and message at the call site match the receiver type and message in the row of the hash table, the method specified in column
163
of hash table
155
is invoked. Otherwise, a method lookup routine is called in order to find the correct method. Typically, the new method is then added to the hash table.
Although hashing is the most flexible message dispatch technique we have described thus far, it is more computationally and storage intensive then the other techniques. Another drawback of the message dispatch techniques we have described is that none of the techniques are site specific. In other words, none of the message dispatch techniques provide the flexibility of handling message dispatches at different call sites in a different manner. Other method dispatch techniques are described in “Message Dispatch on Pipelined Processors,” by K. Driesen et al., ECOOP, 1995, which is hereby incorporated by reference for all purposes.
None of the message dispatch techniques described above allow for the receiver type information that is collected to be utilized during a subsequent execution of the program. Additionally, it would be desirable if inlining information was available during subsequent program executions. Accordingly, there is a need for tech
Bak Lars
Holzle Urs
Beyer Weaver & Thomas LLP
Courtenay III St. John
Sun Microsystems Inc.
LandOfFree
Inline database for receiver types in object-oriented systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Inline database for receiver types in object-oriented systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Inline database for receiver types in object-oriented systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2586698