Method and apparatus for efficient interface method dispatch

Details Method and apparatus for efficient interface method dispatch Method and apparatus for efficient interface method dispatch

2000-09-01

2003-11-18

Zhen, Wei (Department: 2122)

Data processing: software development, installation, and managem

Software program development tool

Linking

C717S165000, C709S241000

Reexamination Certificate

active

06651248

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention generally relates to object oriented programming (OOP) systems and, more particularly, to OOP systems (such as the Java™ and, C++programming language) that support interfaces.
2. Background Description
An interface specifies a set of methods that must be implemented by any class of objects that declares to implement the interface, but an interface does not provide any implementation of these methods themselves. The Java™ programming model includes such a mechanism. More specifically, a Java™ interface is a public class that includes (among other things) one or more abstract method declarations that provides the method signatures for a set of methods. Any class that declares to implement a given interface (denoted “interface class”) must provide an implementation of the methods specified by the given interface. In Java™, such a class must provide an implementation of the methods specified by the given interface that match the methods signatures specified by the given interface. Note that here a method signature represents the name of a method, the types of its parameters, and its return type. This differs from normal Java™ usage (which does not include the return type). In addition, a given interface may extend (directly or indirectly) another interface. The C++programming model introduced by Microsoft Corporation is another example of a model that supports interfaces.
In OO systems that support interfaces (such as Java™), a field name (or local variable name) whose type is an interface may reference the objects of any interface class that implements the interface. Moreover, the method of an interface class implemented by a given object (which we denote “interface method” for the sake of description) may be called by applying the method name (with arguments) to a field name (or local variable name) that points to the given object. Compilation (or interpretation) of such a method invocation statement typically involves generating a routine that performs dynamic dispatch to the called interface method. A more detailed description of Java™ interfaces can be found in U.S. Pat. No. 5,907,707, commonly assigned to the assignee of the present invention, herein incorporated by reference in its entirety.
Efficient implementation of dynamic dispatch of interface methods is difficult because the virtual methods of different classes that match a particular interface method signature may occur in different offsets in the virtual method tables (VMTs) for the different classes.
FIG. 1
illustrates this point where the pointer to the method bar ( ) is in the second entry in the VMT for class A but is in the fourth entry of class C's VMT.(class C implements virtual methods rim and ged; as well as, foo and bar.)
The schemes to identify the correct entry in the VMT typically revolve around keeping a table (which we denote as itable for the sake of description) for each class and for each interface implemented by the class. This table is a virtual method table for the class restricted to methods for a given interface. To dispatch an interface method, the itable is located and a pointer to the target method body is obtained at a fixed offset within it. Sometimes, a dispatch time search for the itable of a required interface for a given class may be required to determine the address of the implementation of the called method. A more detailed description of such schemes can be found in Fitzgerald et al., “Marmot: An optimizing compiler for Java,” Technical Report 33, Microsoft Research, Jun. 1999; Ramalingam and Srinivasan, “Object Model for Java,” Technical Report 20642, IBM Research Division, Dec. 1996. The principal drawback to these schemes is that the dispatch time search is inefficient and leads to a dispatch mechanism that is computationally more expensive than virtual method dispatch.
In some Java™ implementations, this dispatch time search is optimized for under certain circumstances—when a sequence of instructions containing a method invocation is executed multiple times. In these cases, the method being invoked in the method table can be cached and this cached value can be used to reduce the overhead of the search (“The Java Virtual Machine Specification”, by Tim Lindholm and Frank Yellin; “Method and Apparatus for Resolving Data References in Generated Code”, U.S. Pat. No. 5,367,685 in the name of James Gosling. However, these optimization schemes cannot always completely eliminate the dispatch time search when an interface is implemented by multiple classes, and thus suffer from poor performance when invoking interface methods.
Krall and Grafl, “CACAO—a 64 bit Java VM just-in-time compiler,” Concurrency: Practice and Experience, 9(11), pp. 1017-1030, 1997, describe two schemes for implementing interface method dispatch. The first scheme is a variant of the itable schemes described above. CACAO maintains an interface table with each class. There is (logically) an entry in this interface table for every interface the system has seen (as the time the class is loaded). Thus, the interface table is typically very large and consumes a large amount of storage. The entry for an interface is empty unless the class implements the interface, in which case it contains the appropriate itable. To dispatch an interface method on an object, the interface table is located, the itable for the interface is loaded at a constant offset, and a pointer to the code for the method is obtained at a constant offset into the itable. In this first scheme, an interface method dispatch is one dependent load more expensive than a virtual method dispatch. Thus, the principal drawback to this first scheme is twofold: i) the interface table typically consumes a large amount of storage, and ii) the dispatch time search is inefficient in that it requires an additional load operation than virtual method dispatch.
It appears the a substantial part of the motivation for CACAO 's second scheme is a desire to eliminate this extra dependent load operation. In this second scheme, the interface table and itable are collapsed into a single table (denoted the interface-method table) for a class. This interface-method table has (logically) an entry for every interface-method signature in the interface-method table has (logically) an entry for every interface-method signature in the system. This entry points directly at the body of the method that that implements the signature if the class has one (otherwise it is empty). For this scheme, an interface method dispatch has exactly the same cost as a virtual method dispatch. However, the drawback of this second scheme is that the interface-method table will be very big and very sparsely populated. A technique similar to graph-coloring register allocation (see Chaitin et al., “Register Allocation via coloring,” Computer Languages 6, pgs. 47-57, January 1981) can be used to reduce the size of these tables substantially. More specifically, if two interface method signatures are never implemented by the same class, then they can be assigned the same slot in the interface method tables. However, the drawback to this interface-method coloring scheme is that it requires knowledge of all the interfaces the system will ever see in order to do the coloring. Thus, it is not appropriate in a context, such as the Java programming model, that requires dynamic class loading.
Therefore, there remains a need in the art to provide an efficient mechanism for interface method dispatch that reduces the space and computational overhead associated with the dispatch time processing.
SUMMARY OF THE INVENTION
The above-stated problems and related problems of the prior art are solved with the principles of the present invention, method and apparatus for efficient interface method dispatch, which includes an interface method table (IMT) for a given class of objects. The IMT comprises a table of entries each corresponding to a set S of interface methods that are implemented by objects of the given class. An IMT

Affiliated with

Also associated with

Rating

Method and apparatus for efficient interface method dispatch 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 efficient interface method dispatch, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficient interface method dispatch will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3123965