Data processing: software development – installation – and managem – Software program development tool – Translation of code
Reexamination Certificate
2000-03-31
2003-12-02
Nguyen-Ba, Hoang-Vu Antony (Department: 2122)
Data processing: software development, installation, and managem
Software program development tool
Translation of code
C717S116000, C717S140000, C717S148000, C717S165000
Reexamination Certificate
active
06658657
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to reducing the burden placed on computer systems and more specifically to reducing the overhead of virtual method invocations.
2. Description of Related Art
Since the advent of computers, computer scientists and engineers have strived to make computers faster. Programming languages such as object-oriented programming languages (e.g., Java, C++, etc.) create additional burden on a computer system through invocation of virtual method calls which affects the time involved in executing program instructions. Virtual method calls cannot be easily eliminated because the compiler is unaware of which callee of the virtual method callee (“callee”) will be invoked. Invoking a callee depends upon the class hierarchy being used. Class hierarchy is a way of organizing information in which related classes are connected in a tree-like structure.
FIGS. 1 and 2
illustrate two simple class hierarchies that show how a callee is invoked.
FIG. 1
illustrates a simple class hierarchy in which “A” is a superclass of “B”. The arrow from class B to A means that A is a superclass of B as in FIG.
1
. Invoking a call to foo for “B” objects should invoke “A's” foo method. Foo is a function call. A function call may include parameters such as a subroutine or may be without parameters such as a function. Using the principle presented in
FIG. 1
,
FIG. 2
illustrates another class hierarchy that is slightly more complex in which A is a superclass of B and B is a superclass of C. C_object is converted to type “B” and is passed to method bar ( ). Method bar ( ) is a name of a function. In method bar ( ), b_object.foo ( ) invokes “C's” foo method instead of “A's” foo method. If “A's” foo method is the correct callee but “C's” foo was invoked instead, the method is inaccurate because the wrong foo was called.
Inlining is a technique used in compilers to reduce the overhead of method invocations by replacing a call site (i.e., a call instruction) with the method body of the callee. When inlining a virtual method, multiple instances of the method may be invoked. Compilers, therefore, must ensure that the right instance of the method is executed. There are generally two conventional inlining approaches that may be used to reduce virtual method calls: (1) checking virtual tables as illustrated in
FIG. 4
, and (2) checking foo addresses as illustrated in FIG.
6
.
In order to understand these two conventional approaches, object layouts, which directly influences inlining, are explained.
FIG. 3
depicts the object layout used in most implementations of object-oriented languages (e.g., C++, Java, etc.). Reference x points to an object
200
. As shown in
FIG. 3
, object
200
contains data
205
of the object
200
such as different types of fields, integer floating points, other types of pointers, or other data. The first field to which the object points is the virtual method table (“vtable”)
210
. Vtable
210
contains all of the function pointer entries. More specifically, for each virtual method of the object, there is a dedicated entry in the vtable pointing to the native code of the method. To access the address of a virtual method foo, the pointer must be dereferenced. Dereferencing involves retrieving information from an address by a pointer. The pointer indicates the location of the data. It will be appreciated that every time a dereference occurs, a memory access occurs. The first dereference accesses vtable
210
(t=[x]). “T” refers to the beginning point of vtable
210
. The second dereference accesses the address of foo ([t+64])
230
. “T +64” is the amount of off-set from “t.” This entry of the reference accesses the actual native code object address which is foo. Vtable also contains entries pointing to other methods such as bar
220
.
As the virtual method gets inlined, the compiler such as a just-in-time (JIT) compiler generates a run-time test to verify if the inlined callee is the right instance to be invoked. The typical method invocation code sequence is executed if the verification fails. The run-time test is typically implemented by checking the vtable
210
or by checking foo of the actual target address of the method invocation. Checking the vtable
210
involves comparing the object's vtable
210
with the vtable of the class of the inlined method. If the comparison is successful (i.e., object
200
matches the vtable of the class of the inlined method), it is safe to execute the inlined code because the inlined method will be dynamically dispatched at runtime. If the comparison fails (i.e., object
200
does not match the vtable of the class of the inlined method), the conventional dispatching code sequence is executed to invoke the virtual method call.
FIG. 5
shows the iA32 native code sequence. For clarity, the control flow graph of the inlined code is depicted in FIG.
4
. The conventional dispatching code is shown at
410
of FIG.
4
. The benefit of this conventional approach is that only one memory access ([x])
400
is involved to determine if either “A's” foo is inlined at operation
420
or the conventional call sequence
410
should be executed as illustrated in FIG.
4
. For instance, if [x] =“A's” vtable, “A's” foo is inlined at operation
420
. Additionally, only one comparison must be performed of the vtable address, and one comparison of the branch to the vtable (e.g., branch to the inline version). But one drawback to this conventional approach is that checking the vtable is conservative and less accurate. For example, referring to
FIG. 2
, if “x” is always a type B class, the checking always fails because “A” and “B” objects have distinct vtables. More specifically, “A” is a superclass of “B” and “C”. “C's” object is “B”'s object and “A's” object, but not vice versa. After this process,
FIG. 4
shows a merge point occurs at
430
. A merge point is where the computer program returns to another operation that may be unrelated to an inlining operation.
The second conventional approach illustrated in
FIG. 6
relates to inserting code to compare the actual method address that x.foo ( ) is invoking with the address of “A's” foo. Although the second conventional approach is more precise at inlining “A's” foo
520
than the first conventional approach, checking the target address requires at least two memory accesses (i.e., [x] and [t+64]) such as operations
500
,
510
. In JIT compiler, a method is compiled before its first execution. If A's foo is not yet compiled, the actual address of A's foo is unknown. The JIT compiler then allocates memory space in which to fill the address of A's foo as soon as A's foo is compiled. In such a circumstance, the test requires 3 memory accesses.
FIG. 7
shows the iA32 native code sequence that implements this approach. OXBE762Ch is the address of the place holding the address of the inlined method. It is therefore desirable to have a method that reduces the number of memory accesses and improves accuracy of inlining a method bar.
REFERENCES:
patent: 5615400 (1997-03-01), Cowsar et al.
patent: 5692195 (1997-11-01), Conner et al.
patent: 5740443 (1998-04-01), Carini
patent: 5857105 (1999-01-01), Ayers et al.
patent: 5920723 (1999-07-01), Peyton, Jr. et al.
patent: 6345382 (2002-02-01), Hughes
Calder et al., Reducing Indirect Function Call Overhead In C++ Programs, Jun. 1994, ACM Principles and Practice of Programming Languages, Portland, Oregon.*
Burke et al., The Jalapeno Dynamic Optimizing Compiler for Java, Mar. 1999, ACM.*
Suganuma, Overview of the IBM java Just-in-Time Compiler, Jan. 2000, IBM Systems Journal, vol. 39, No. 1.*
Calder et al., Reducing Indirect Function Call Overhead In C++ Programs, Jun. 1994, ACM Principles and Practice of Programming Languages, Portland, Oregon.*
Burke et al., The Jalapeno Dynamic Optimizing
LandOfFree
Method and apparatus for reducing the overhead of virtual... 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 reducing the overhead of virtual..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for reducing the overhead of virtual... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3168564