The Java runtime implements the JVM, providing a bytecode interpreter and a dynamic loader for Java classes. We have produced a working prototype interpreter for our extensions to the JVM. Our design is based upon the Java runtime implementation provided by Sun Microsystems. Our goal in designing the runtime was to avoid duplication of information by the instantiations of a single class, while making the code run quickly. Minimizing the changes to the existing interpreter was also an important goal. Non-parameterized code runs about as fast as in the original interpreter.
Classes are represented in the Java runtime by class objects. Each class points to its constant pool, which stores auxiliary constant values that are used by the Java bytecodes. These constant values include class names, field and method names and signatures. In this paper, constant pool entries are denoted by angle brackets. Figure 6 contains some examples of this notation, such as the field signature: <Field HashBucket[Key,Value].key #0;>
For a parameterized class, some constants differ among the instantiations. For example, the code that is used by the where-clause operations differs among instantiations, and therefore cannot be placed in the constant pool. To resolve this problem, we create a new class object for each instantiation. Each instantiation class object stores instantiation-specific information in its instantiation pool (ipool). Values that are constant for all instantiations are still placed in the constant pool. Ipool indices are constant across all instantiations, but the contents of the corresponding slots differ. An instantiation object is created by cloning the parameterized class object and then installing a fresh ipool. The ipool serves a function similar to the where-routine object of Section 3.1.
For example, the HashMap method lookup from Figure 4
uses the equals operation of Key, so a pointer to the correct
implementation of equals is placed in the ipool of
each instantiation. Other
examples of values in the ipool include references to
classes that are instantiations that use the parameters, addresses
of static (class) variables,
and pointers to ipools of other instantiations.
This design allows us to duplicate very little data. All instantiations share the code of the class, the class method tables, and the constant pool. Only the data that is genuinely different for the instantiations is placed in the ipool, and there is exactly one class object for each instantiation being used in the running system.
The Sun implementation of the JVM includes an optimization that dynamically modifies the code the first time an instruction is executed, replacing some ordinary bytecodes with quick equivalents that do less work [LY96]. These quick instructions are not part of the bytecode specification and are not visible outside of the implementation. The non-quick version of such an instruction performs a one-time initialization, including dynamic type checking, and then turns itself into the quick version. Our implementation makes extensive use of this self-modifying code technique in order to improve performance. A more detailed discussion of the implementation technique is available [BLM96].
The presence of subclasses makes ipools substantially more complicated than implementing parametric polymorphism for languages like CLU or ML [MTH90], which are not object-oriented. Consider a method call: the compiler and dynamic linker cannot tell which piece of code is run, so they cannot determine the corresponding ipool to use, either. The proper ipool to use for the call is not known until the actual call, and must be determined from the object on which the method is being invoked (the method receiver). The object has a pointer to its instantiation class object, which contains the ipool for the methods of that class. Since the method may be inherited from another class, an additional indirection is required to obtain the correct ipool.
Our implementation technique resembles an
earlier approach [DGLM95], but
extended to provide support for static methods, static variables, and dynamic
type discrimination. It requires few changes to the existing Java
interpreter, and is also applicable to compiled machine code
.
Primitive types such as integers can be used as parameter types under the implementation technique described here. Most of the primitive types take up the same space in an object as an object reference. That they are not full-fledged objects is not a problem for invoking where-routines, since where-routines are accessed through the ipool rather than through the object.
Variables whose type is a parameter
are treated in the bytecodes as though they are object references;
for example, the code of Figure 6 will work properly even
when the code is instantiated on Key = int,
although an aload instruction is used in this case to access an integer.
Other bytecodes such as putfield and getfield do not distinguish between
references and primitive values, and do not create a problem.
The same code cannot support instantiation on long and double, since
these data values do not occupy the same space as an object reference.
The best way to handle large primitive
types such as long and double is probably to rewrite instantiated
code when those types are used as actual parameters.
Note that the specialized instantiations might not even have
the same memory layout, since instance variables of type long will take
up more space than other parameter types.
The only problem with this technique is that the specialized
instantiations for double and long would not share code with the
other instantiations of the same class, which would all use the same
bytecodes.