Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-09-22
2002-09-03
Jung, David (Department: 2175)
Data processing: database and file management or data structures
Database design
Data structure types
C709S241000, C709S241000
Reexamination Certificate
active
06446084
ABSTRACT:
COPYRIGHT NOTICE PURSUANT TO 37 C.F.R. § 1.71(E)
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
BACKGROUND
1. Field of the Invention
The present invention relates to platform-independent virtual machines for computer systems. More specifically, the present invention relates to a space-efficient mechanism for improving the speed of lookups of symbolic information related to functions, variables and object-oriented classes on platform-independent virtual machines.
2. Related Art
The recent proliferation of computer networks such as the Internet has lead to the development of computer languages, such as the JAVA™ programming language distributed by Sun Microsystems, Inc. of Palo Alto, Calif. One important feature of the JAVA programming language is the way in which it allows components of a program to be loaded dynamically at runtime. This is accomplished by storing the components of the program as “class files” that can be easily transferred over a network such as the Internet to remote computer nodes. On the remote nodes, a platform-independent virtual machine can execute the program components stored within the class files.
An essential part of a JAVA classfile is the “constant pool,” which is a type of symbol table that stores symbolic information for the associated JAVA class. This allows the JAVA virtual machine (JVM) to dynamically resolve references to functions, variables and other classes at runtime.
Sun, the Sun logo, Sun Microsystems, and Java are trademarks or registered trademarks of Sun Microsystems, Inc. in the United States and other countries.
Unfortunately, constant pool resolution is an expensive, time-consuming operation that occurs very frequently when JAVA programs are run. Most JVMs utilize certain techniques to reduce the need for such constant pool lookups. One commonly used technique is to introduce so-called “quick” bytecodes. This is done by dynamically replacing those JAVA bytecodes that necessitate a constant pool lookup with other “quick” bytecodes that do not require a constant pool lookup, but instead contain a direct pointer to the desired runtime structure. This replacement is performed dynamically when the original bytecode is executed and the associated constant pool references are resolved for the first time. The second time the virtual machine encounters the same code it no longer has to perform the constant pool lookups.
Even simple optimizations such as quick bytecodes usually result in 2-4 times faster execution time. However, these techniques make the virtual machine larger. The code needed to implement quick bytecodes typically increases the size of the virtual machine by at least 5-10 kilobytes, often substantially more if special cache areas are allocated to store the original bytecode sequences. Consequently, these techniques may not be practical for those applications where it is important to have the smallest possible JVM.
Another solution is to provide JVMs with a Just-In-Time (JIT) compiler. This type of system can avoid constant pool lookups by dynamically compiling JAVA bytecodes and the necessary constant pool information into machine code. However, JIT compilers typically require hundreds of kilobytes of additional memory space at the minimum. Consequently, they are completely unsuitable for embedded systems where the virtual machine has to be as small as possible.
What is needed is a space-efficient mechanism for improving the performance of the constant pool lookup process for platform-independent virtual machines.
SUMMARY
One embodiment of the present invention provides a method for increasing performance of code executing on a platform-independent virtual machine. The method operates by receiving a request to resolve an entry in a symbol table at run-time, wherein resolving the entry requires multiple lookups into the symbol table. It next determines if the entry has previously been resolved. If so, the system returns a direct pointer to a runtime structure associated with the entry, which was returned during a previous resolution of the entry. If not, the system resolves the entry through multiple lookups into the symbol table to produce a direct pointer to the runtime structure, and replaces the entry with the direct pointer. In a variation on the above embodiment, the symbol table assumes the form of a constant pool within an object-oriented class file defined within the JAVA programming language. The present invention speeds up constant pool resolution substantially without requiring a significant amount of additional space. Therefore, the present invention is especially valuable for embedded JAVA systems or other applications that have strict size limitations.
REFERENCES:
patent: 5815718 (1998-09-01), Tock
patent: 5920720 (1999-07-01), Toutonghi et al.
patent: 5923878 (1999-07-01), Marsland
patent: 6115719 (2000-09-01), Purdy et al.
patent: 6119125 (2000-09-01), Gloudeman et al.
www. ittc.ukans.edu/~rsarav/jvm-report
ode9.html.*
Publication entitled “The Java Virtual Machine Specification”, Chapters 4-5, http://java.sun.com/docs/books/vmspec/html/classfile.doc.html.
Sun Microsystems, Inc.: “Java Virtual Machine Specification 1.0” http://www.sunsite.ee/java/vmspec.1995, XP002128310 Mountain View, CA 94043-1100, USA paragraph OA.1!.
Venners, Bill: “Inside the Java 2 Virtual Machine (Enterprise Computing)” http://www.artima.com/insidejvm/blurb.html, Dec. 17, 1999, XP002128311 p. 2, line 14-line 33 p. 12, line 35—p. 14, line 11 & Venners, Bill: Inside the Java Virtual Machine (Java Master Series) Dec. 1997, McGraw-Hill, USA.
Shaylor Nik
Taivalsaari Antero K. P.
Jung David
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Optimizing symbol table lookups in platform-independent... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimizing symbol table lookups in platform-independent..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimizing symbol table lookups in platform-independent... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2895518