ABSTRACT
We present the fast subtype checking implemented in Sun's HotSpot JVM. Subtype checks occur when a program wishes to know if class S implements class T, where S and T are not both known at compile-time. Large Java programs will make millions or even billions of such checks, hence a fast check is essential. In actual benchmark runs our technique performs complete subtype checks in 3 instructions (and only 1 memory reference) essentially all the time. In rare instances it reverts to a slower array scan. Memory usage is moderate (11 words per class) and can be traded off for time. Class loading does not require recomputing any data structures associated with subtype checking.
- B. Alpern, A. Cocchi, and D. Grove. Dynamic Type Checking in Jalapeño. In the 2001 USENIX Java™ Virtual Machine Symposium. Google ScholarDigital Library
- D. F. Bacon and P. F. Sweeney. Fast static analysis of C++ virtual function calls. In Conference on Object Oriented Programming Systems, Languages & Applications (OOPSLA'96). Google ScholarDigital Library
- N.H. Cohen. Type-extension tests can be performed in constant time. ACM Transactions on Programming Languages and Systems, 13(4):626--629, 1991. Google ScholarDigital Library
- E.W. Dijkstra. Recursive Programming. Numer. Programming, (2):312--318, 1960.Google Scholar
- James Gosling, Bill Joy, and Guy Steele. The Java Language Specification. Addison Wesley, 1996. Google ScholarDigital Library
- Tim Lindholm and Frank Yellin. The Java Virtual Machine Specification, Second Edition. Addison Wesley, 1998. Google ScholarDigital Library
- M. Paleczny, C. Click, C. Vick, The Java HotSpot™ Server Compiler. In the 2001 USENIX Java™ Virtual Machine Symposium. Google ScholarDigital Library
- B.H.C. Pfister and J. Templ. Oberon technical notes. Research Report 156, Eidgenossische Techniscle Hochschule Zurich- Departement Informatik, March 1991.Google Scholar
- The Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks. http://www.spec.org/osg/jvm98, 1998.Google Scholar
- The Standard Performance Evaluation Corporation. SPEC JBB2000 Benchmarks. http://www.spec.org/osg/jbb2000, 2000.Google Scholar
- V. Sundaresan, L. Hendren, C. Razafimahefa, R. Vallée-Rai, and P. Lam, E. Gagnon, and C. Godin. Practical virtual method call resolution for Java. In Conference on Object Oriented Programming, Systems, Languages & Applications (OOPSLA'2000). Google ScholarDigital Library
- J. Vitek, A. Krall, and R. N. Horspool. Efficient Type Inclusion Tests. In Conference on Object Oriented Programming Systems, Languages & Applications (OOPSLA'97). Google ScholarDigital Library
Index Terms
- Fast subtype checking in the HotSpot JVM
Recommendations
Compile-time type-checking for custom type qualifiers in Java
OOPSLA '07: Companion to the 22nd ACM SIGPLAN conference on Object-oriented programming systems and applications companionWe have created a system that enables programmers to add custom type qualifiers to the Java language in a backward-compatible way. The system allows programmers to write type qualifiers in their programs and to create compiler plug-ins that enforce the ...
Compile-time type-checking for custom type qualifiers in Java
OOPSLA '07: Companion to the 22nd ACM SIGPLAN conference on Object-oriented programming systems and applications companionWe have created a system that enables programmers to add custom type qualifiers to the Java language in a backward-compatible way. The system allows programmers to write type qualifiers in their programs and to create compiler plug-ins that enforce the ...
Shared subtypes: subtyping recursive parametrized algebraic data types
HASKELL '08A newtype declaration in Haskell introduces a new type renaming an existing type. The two types are viewed by the programmer as semantically different, but share the same runtime representation. When operations on the two semantic views coincide, the ...
Comments