CN1251076C - Acceleration of method call in virtual machine - Google Patents

Abstract

A system based on a computer platform to increase the speed of code execution by increasing the speed of method calls. A virtual machine includes a loader, an interpreter and a thread manager. The loader builds a hash table using method characteristics, which the interpreter searches to find the location of each method. The interpreter utilizes a method call cache with a pointer to a receiver to increase code execution speed. The thread manager uses a level of depth to increase the speed of lock state transitions.

Description

Computer platform-based systems and methods for increasing execution speed of at least one program

This application claims the benefit of US Provisional Application No. 60/405,266, filed August 22,2002. The disclosures of the above applications are incorporated herein by reference.

technical field

The present invention relates to increasing the speed of code execution, and more particularly to the acceleration of the method invocation mechanism in a virtual machine running in an object-oriented environment like JAVA.

Background technique

Object-oriented languages support inheritance and polymorphism to allow the development of flexible and reusable software. A typical object-oriented program consists of a set of classes. Each of these classes can define a set of data members. Additionally, each class can include a set of methods that act on that set of data members.

Inheritance enables a class to "inherit" or derive the capabilities of a parent class. Thus, because of inheritance, a given method can be shared by both parent and child classes. When calling such a public method, the execution mechanism must determine whether the called method is acting on an object of a superclass or a subclass. Use method characteristics to distinguish methods that work on each object, and these characteristics usually consist of the following parts: method name; parameter number, parameter type, and parameter order (order); and the related class of the object.

The type of a given object is usually determined at runtime. This method of determining the type of an object at runtime is called "dynamic linking". In this regard, the selection of the appropriate method to execute is based on a lookup mechanism, which means that the actual method to execute after an invocation is based on the method receiver's type, class hierarchy, and method inheritance or re- Dynamically determined by the overloading schema. A typical lookup mechanism is described below.

This lookup mechanism determines the actual method to execute when a call occurs. If a class executes a method with the same characteristics as the called method, then the found method is executed. Otherwise, parent classes are checked recursively until the searched method is found. If none of the methods are found, an error signal (MsgNotUnderstood) is emitted. This happens too often and is expensive in terms of execution time and other resources. Therefore, there is a need to increase the speed of the lookup mechanism.

Static techniques precompute part of the lookup, while dynamic techniques use a cache of results from previous lookups, thus avoiding additional lookups. The most important dynamic join algorithm is called Dispatch Table Search (DTS). This DTS is a good approach in terms of space cost, however, the search burden associated with DTS makes this mechanism too slow. There is a need to reduce the overhead associated with DTS. A number of techniques have been proposed to reduce the overhead associated with DTS: static techniques that precompute part of a lookup, and dynamic techniques that cache the results of previous lookups, thus avoiding additional lookups. The above techniques are described below.

A technique called selector table Indexing (STI) is a static method used to speed up the lookup mechanism. This STI technique will be briefly described below. Assuming a class hierarchy of C classes and S selectors, a two-dimensional array of C*S items is built. Assigning consecutive numbers to classes and selectors on each axis, the array is populated by precomputing lookups for each class and selector. An array item containing a reference value for the corresponding method or an error routine. Calculate these tables for a complete system.

STI technology delivers fast and constant time lookups. However, the main disadvantage of STI is that for an ordinary system with limited computing resources such as an embedded system, the space requirement is huge. Many dispatch table compression techniques have been proposed to reduce the overhead of required space, such as selector coloring (selector coloring), row displacement techniques, and so on. However, the implementation of these technologies places an unnecessary burden on limited computing resource environments such as embedded systems. Another disadvantage of this technique is that the compiled code is very sensitive to changes in the class hierarchy. Two-dimensional arrays created by STI are fixed at compile time. But for languages like Java, this set of classes can change dynamically. STI has no control over this situation because it cannot dynamically change the array.

Synchronization techniques improve the functionality of thread managers used to execute multithreaded applications. This synchronization technique used in traditional embedded Java virtual machines (especially those based on Kilobyte virtual machines) is associated with an object state in one of four states: (1) unlocked, (2) simply locked, (3) extend locked, or (4) a state associated with a monitor. Therefore, it is required that the synchronization technique is not associated with any particular locking state.

Therefore, there is a need for a set of techniques that are low in overhead in terms of computational resource processing/execution time, memory, and method search or lookup. This technique should work even when receiving objects change frequently. Additionally, there is a need for a mechanism that can increase the speed of code execution in virtual machines running in resource-constrained computing environments such as embedded systems.

Contents of the invention

A computer-based system for increasing the speed of code execution by increasing the speed of method calls. A virtual machine includes a loader, an interpreter, a thread manager and other modules and/or components. The loader builds a hash-table using the method signature. The interpreter utilizes the constructed hash table to increase the processing speed of the search method. The interpreter builds a method call cache with a pointer and uses it for a receiver to increase code execution speed. The cache memory provides modified guard conditions that enable faster cache operations that result in faster execution. The thread manager employs a depth level to improve the speed of lock state transitions. This level of depth represents the simple lock state and the extended lock state, thus eliminating the need for a separate simple lock state. The smaller the number of lock states, the faster the lock state transitions, and thus the faster code execution. In general, the present invention can be implemented in any virtual machine, such as the Java Virtual Machine (JVM) and Kilobyte Virtual Machine (KVM) environments. In particular, the invention can be implemented in embedded systems with relatively limited computing resources.

Other areas of applicability of the present invention will become apparent from the detailed description provided hereinafter. It should be understood that the detailed description and specific examples, while indicating the preferred embodiment of the invention, are intended for purposes of illustration only and are not intended to limit the scope of the invention.

Description of drawings

A more complete understanding of the invention can be obtained from the detailed description and drawings, in which

Fig. 1 is a block diagram of a virtual machine in one embodiment of the present invention;

Figure 2A shows a typical class hierarchy;

Fig. 2B shows a method hash table used in the lookup acceleration process;

Fig. 3 shows a typical method hash table construction program;

Fig. 4 has described a kind of typical hash search program that is used to search a method in the hash table;

Figure 6 shows a cache entry including a link to the receiver;

Figure 7 shows a first automated process representing a known thread manager;

Figure 8 illustrates an optimal automatic process for increasing the speed of a multi-threaded application;

Figure 9 shows a typical class hierarchy 76 used to represent improvements in inherited method calls;

Figure 10 shows a histogram comparing method call times in one embodiment of the present invention;

Figure 11 shows a pie chart showing jerk/jerk rate in one embodiment of the invention.

Detailed ways

The following description of preferred embodiments is merely exemplary in nature and is in no way intended to limit the invention, its application or uses.

An object-oriented ("00") program consists of classes that contain data members and methods that act on those data members. Thus, a method in an OO program is part of a given class. Objects of the previously denoted/defined classes may be instantiated. Each instance object of a given class has the data members represented in the given class representation/definition. Usually, those methods that are part of a given class act on instantiated objects.

An example shows the typical structure in a 100 program. A typical 00 program can have two classes, which are respectively called class A and class B, where class B inherits from class A, or is derived from class A. Class A can define a method m, and because of this inheritance, class B also has method m as part of it. Objects of class A have method m as part of them, then, due to inheritance, objects of class B also have method m as part of them. The method characteristics are used to distinguish the methods described below.

The 00 environment usually uses some method characteristics to distinguish any two superficially similar methods. These characteristics are formed by using the class name, method name, parameters, and return type. When an execution engine encounters an invocation of a method m on a given object, it uses the characteristics of the called method to find the location in the method table where the method is defined. The search defined by this method is a time-intensive task. The present invention minimizes the time required for method lookup and execution while placing the least demands on the computing resources of any given environment.

00 languages such as JAVA use a frequent dynamic sending mechanism to search for the definition of a called method. This method can be defined in more than one class. The search for appropriate method definitions is done dynamically. This results in a considerable execution time for auxiliary operations. Usually, the existing static and dynamic technologies are not suitable for embedded platforms like embedded JAVA which run under relatively strict resource constraints. In particular, these techniques are memory-intensive, which is not a desirable characteristic for common embedded systems with limited memory resources.

The present invention relates to a dynamic, flexible and efficient technique for accelerating the method invocation mechanism in the 00 environment. For illustration, this method call acceleration mechanism is discussed in the context of a virtual machine using JAVA in an embedded system application. Those skilled in the art will understand that the embedded system using JAVA is for illustration only and not for limitation. The present invention can be run and/or applied in any object-oriented environment. The acceleration technique of the present invention covers multiple aspects of the method invocation process, such as lookup methods, cache methods, and synchronized methods. A virtual machine is described below as a platform for applying the technology of the present invention to an embodiment of the present invention.

FIG. 1 is a block diagram of a virtual machine 10 in one embodiment of the present invention. The virtual machine 10 works closely with an operating system 12 . A loader (loader) 14 loads the code to be executed into the virtual machine 10 . Loader 14 includes hash management modules such as hash builder 16 and hash lookup table 18 . A verifier 20 verifies loaded classes and codes for possible errors. Loader 14 also loads any programs and/or classes from language class library 18 and native class library 24.

Interpreter 26 interprets and executes code loaded by loader 14 . Cache memory 28 and cache information handler 30 are part of interpreter 26 and are used to cache method call commands. The stack management and garbage collection module 32 is used by the interpreter 26 to create and destroy objects on the stack. Interpreter 26 uses thread manager 34 to control the threading operations of the code being executed. As various threads compete to access objects during code execution, thread manager 34 performs locking and unlocking operations on objects. In addition, thread manager 34 also manages thread switching.

The above description about the virtual machine 10 relates to a common virtual machine. A specific example of such a common virtual machine 10 is the Java Virtual Machine (JVM). As another example, a KVM (kilobyte virtual machine) is mentioned. KVM is typically used in embedded system application environments that require a JVM with a small footprint. In KVM or JVM, the loader 14 works as a class file loader, which loads system and user defined classes. In addition, the loader 14 builds a constant pool and class file structure, and interacts with a class and code verifier 20, which in this example will verify the schema of the loaded bytecode Safety (type safety). Interpreter 26 is used to interpret the bytecode of a loaded class file. The thread manager 34 manages application threads. Those skilled in the art will appreciate that the above descriptions of JVM and KVM are for explanation, and they are helpful for understanding the present invention, but not for limitation. The speedup for method lookup is described below.

Figure 2A shows a typical class hierarchy 36. Class A38 includes method 'm'. Class B40 is a subclass of parent class A38. Class B40 includes methods m, m1 and m2. Class B40 inherits method m from class A38. A hash table based lookup of such a typical class hierarchy 36 is described below.

Figure 2B shows the method hash table 42 used in the lookup acceleration process. The loader 14 of the virtual machine (see FIG. 1 ) builds a hash table 42 for each virtual method table of the above class hierarchy. Speed up method table lookups through direct access techniques like hashing. It is implemented using appropriate hashing techniques and an efficient hashing function:

Method features (not shown in the figure) can be constructed in various ways. For example, a method signature can be constructed with the name of the method and the number and types of its formal parameters. Each index of the hash table 42 corresponds to a result obtained by applying a hash function to the method feature. The size of the hash table 42 should be chosen carefully so that its footprint is small while minimizing collisions between method features, resulting in a more efficient and flexible lookup mechanism. Efficiency can be achieved due to the direct access to the provided method table by means of hash method access. Flexibility is enabled because the hash table 42 can be sized to optimize the ratio of speedup to footprint.

In the course of loading a class, hash builder 16 builds a table of hashing methods. Computes a hash based on method characteristics. Each entry in hash table 42 consists of two parts. The first part is a flag that indicates whether the class contains a method with such a definition. In this example, first portions 44 ₁ - 44 ₅ are shown. The presence of a flag "1" in the first parts ₄₄₁ and ₄₄₄ indicates that, for those methods whose method signatures are hashed on the hash index of the first first part ₄₄₁ and ₄₄₄ , the link to the method definition is useful.

The second part is a pointer to the method definition. In case of a conflict, the second part is a pointer to the method definition list. Here, the second part 46 ₁ is a single method definition for the second method m2, since no other method characteristics hash to the hash position of the first part 44 ₁ . However, the second part of the first part ₄₄₄ of hash locations is a collision list, since the two method signatures of methods m and m1 each hash to the same first location ₄₄₄ . Thus, the conflicting lists of method definitions for method m and m1 are denoted as second parts 46 ₂ and 46 ₃ , respectively.

Fig. 3 shows a typical method hash table construction procedure. Loader 14 (see FIG. 1 ) may cause a built-in hash builder 16 (see FIG. 1 ) to build hash table 42 (see FIG. 2B ), or the hash builder 16 may be an externally callable program. Those skilled in the art will appreciate that the location of the hash building program, internal or external to loader 14, does not limit the invention in any way. The construction of the hash table 42 and the operation of the hash generator 16 are explained in detail below.

Hash builder 16 processes classes loaded by loader 14 . For each method in a given loaded class, hash builder 16 computes a hash based on the characteristics of that method. Using the generated hash, hash generator 16 obtains the element at the hash index in hash table 42 . In the event that a method definition already exists at the accessed hash location, as determined by the flag at that hash index, then a conflict entry is created for the new method. But if the flag bit at the hash index is “OFF”, indicating that there is no method entry, then the method is recorded in the hash table 42 at the calculated hash index.

Figure 4 depicts a typical hash lookup procedure used to search for a method in a hash table. The hash lookup table 18 (see FIG. 1 ) employs a hash value obtained by applying a hash function to the method characteristics of the corresponding entry/index in the hash table 42 (see FIG. 2B ). Using this hash value, the hash look-up table 18 determines the value of the flag bit at the accessed hash index/entry. If the flag associated with the entry is ON (shown as '1' in Figure 2B), then it accesses the method definition because of the second part of the entry. The OFF state of flag bit (shown in ' 0' among Fig. 2B) represents that this class does not carry out such a method, and search points to a superclass.

The hash-based approach to defining access makes search times faster compared to simple table-based searches. The speedup of this lookup method depends on the size of the hash table. Larger hash table sizes require larger storage space, but minimize collisions. On the other hand, larger hash table sizes may cause additional overhead in storage management (allocation, garbage collection, compaction, etc.).

Those skilled in the art will appreciate that the present invention can be practiced in various ways. For example, in one embodiment, virtual machine 10 may be constructed to include the necessary hash-based lookup elements. Alternatively, a conventional virtual machine can be modified to provide hash-based lookups as described below.

The above search acceleration can be implemented in a traditional embedded JAVA virtual machine, for example, in the following KVM (kilobyte virtual machine). The method lookup mechanism in normal KVM is linear, i.e., it uses a sequential access approach. Hash based lookups have better performance on top of linear approach lookups used in normal KVM. The implementation of such a mechanism will affect two parts of virtual machine 10 (see FIG. 1 ): loader 14 and interpreter 26 . The loader is modified to build a hash table 42 for each loaded class. The interpreter is modified to utilize the hash table 42 to perform fast and direct access lookups.

Dynamic techniques exist in the cached results of previous lookups. Using cache memory technology eliminates the need to create large dispatch tables, which reduces storage overhead and table creation time. Full cache technology stores previous lookup results. In a global cache table, each entry consists of triplets (receiver class, selector, and method address). Receiver classes and selectors are used to compute an index in the cache. If the current class and method names match those in the cache entry at the computed index, then the code at the method address is executed. Thus, method lookup is avoided. Otherwise, a default dispatch technique (usually DTS) is used, and at the end of the search, a new triplet is added to the cache table, transferring control to the method found. The amount of run-time storage required for such an algorithm is small, usually a fixed amount of cache memory and the overhead of the DTS technique. Frequent changes in the receiving class can slow down execution.

Figure 5 shows an existing cache layout for storing method call commands. Cache entry 48 is shown in a representative format, the contents of which are described below. The content link 50 is a pointer to the called method. CodeLoc 52 is a pointer to the instruction that called the method. The original parameter 54 represents the parameter with which the method was initially called. Raw instruction 56 points to the instruction used to invoke the method. In conventional inline caching technology (such as the technology implemented in KVM), only pointers to method definitions are stored in the cache entry 48 . The modified cache entry structure and cache processing mechanism are described below.

Figure 6 shows a cache entry 58 including a link to a receiver. An object involved in invoking a method is called a 'receiver' because it receives method call requests from other objects. Receiver pointer 60 points to the receiver. The other members of cache entry 58 are similar to cache entry 48 described above. Cache entry 48 caches links or pointers to receivers in addition to caching the method call details as described. When a method is called, the receiver's class is compared to the class of the called method. If the two classes are equal, then the method definition is retrieved due to the cache entry. If not, a dynamic lookup is performed to search for the method definition in the class hierarchy. This modification of the cache layout improves the speed of the method lookup process as described below.

A cache method can be used to improve the method calling speed. An inline cache technique can significantly increase program execution speed using a modified cache memory layout. This inline caching technique is to cache the previously searched result (method address) in the code at each calling location. The inline cache changes the call instruction by overwriting the call instruction with a method direct call operation found by the default method lookup. Inline caching assumes that the receiver's class changes frequently, but when this is not the case, inline caching techniques can provide slow execution times.

This inline caching technique can be significantly improved by avoiding many dynamic lookup operations when there is a mismatch between the receiver's class and the called method's class. In the event of such a mismatch, the method definition can be retrieved from the cache if the cache processor 30 can check that the receiver has not changed. This can be done by adding a pointer to the receiver in the cache structure; modifying the condition of the guard cache restore.

Addition of the receive pointer 60 in the cache entry 58 has been described above. The guard condition of the cache can be modified to take advantage of the presence of the receive pointer 60 . When calling a method, the cache processor 30 checks the following guard conditions.

The first guard condition is whether the class of the receiver in a given cache entry 58 is equal to the class of the called method. The second and further guard condition is whether the current receiver is equal to the receiver of the cache pointed to by the receive pointer 60, ie whether the receiver is still unchanged. If any of these guard conditions are met, cache processor 30 retrieves the cache entry 58, thereby accessing the method definition without having to undergo a method table lookup or search. Those skilled in the art will understand that this further guard condition of checking whether the receiver has not been changed makes the cache recovery process more flexible. This other guard condition requires that the receive pointer 60 be set in the modified cache entry 58 .

An example of cache operation in an embodiment of the present invention is described below. In this example, consider a pair of typical classes X and Y (not shown in the figure). Class Y inherits a non-static method m from class X. In an OOP program code using classes X and Y, there exists a loop of instructions which will be executed frequently. In such an instruction loop, method m is invoked on an object _OB , where _OB is an instance of class Y. After the first call to method m, cache handler 18 will store receive pointer 60 to object _OB and also store other call-related entries in cache entry 58. For subsequent calls to method m, the class that receives the pointer 60, ie, class Y, is different from the class that became the called method of class X. The first guard condition, ie whether the receiver's class (class Y) in the cache entry 58 is equal to the called method's class (class Y) will be invalidated and no cache restore operation will be performed. However, the second guard condition, ie whether the current receiver is equal to the receiver of the cache pointed to by the receive pointer, will be satisfied since they both point to the same object _OB . Thus, the second guard condition facilitates faster lookup of cached method calls using the receive pointer in cache entry 58 .

The comparison of the cache technology under the above conditions shows that the modified cache technology in this embodiment has better search performance. The cache memory (see FIG. 5 ) that does not receive the pointer 60 will perform a dynamic search for each subsequent invocation of the method m, which results in a large amount of auxiliary operations. Such a cache cannot take advantage of the other guard condition of comparing the object pointed to by the receive pointer 60 with the current object because of the absence of the receive pointer. On the other hand, cache handler 30 will simply test whether the current receiver is equal to the one pointed to by receive pointer 60 . Thus, for all subsequent calls to method m, the method definition will be retrieved from the cache without any resource-expensive lookup operations. Thus, the cache structure and cache processing mechanism of the present invention greatly improve the speed.

Polymorphic inline caching is an extension of inline caching technology. The compiler generates a call command to a particular stub program. Each call site goes to a specific stub function (stubfunction). The function is initially a call to a method lookup. Each time the method lookup is called, the stub functionality is expanded. At best, the cost of this technique is spent testing and direct jumps. Also, when the class hierarchy is large and receiving classes change frequently, the executable code can be greatly expanded.

Another embodiment of the present invention implements an asynchronous thread manager that provides lookup acceleration. An asynchronous single-threaded program that does not require any external resources can work freely without managing the state or activity of the currently running thread. In situations where multiple simultaneous threads can access the same resource and run concurrently, the conflicting requirements of the various threads must be managed. Before executing a synchronized method, a thread must acquire the lock associated with the receiving object. This is necessary if two threads attempt to execute the method on the same object. The locked object shows the execution action. A typical thread manager is described below, which uses an object lock table to manage conflicting requests from multiple threads.

Figure 7 shows a first automated process 62 representative of a known thread manager. The first automated process 62 represents object locking states as circles and state transitions as directed line segments connecting the states of the automated process. The first automatic process 62 consists of states A-E, which represent the locking state of a given object. State A64 represents an unlocked state; state B66 represents a simple locked state; state C68 represents an extended state; state D70 represents a monitoring state; state E72 represents an exception state. Transformations are identified by the following letters: 'u', 's', 'e', 'm' and 'x'. In particular, these letters stand for the following operations: u - set_unlocked; s - set_simple_locked; e - set_extended_locked; m - set_monitor; x - raise_exception.

Describe the interaction of transformation operations in context with respect to a given object. Initially, the object is in an unlocked state A64. A set_simple_lock operation is performed when a thread attempts to lock an object to change the lock state of the object to simple lock state B66 for the first time. Additionally, when another thread attempts to lock the same object that is in simple locked state B66, the object locked state changes to extended locked state 'C'68. The object remains in an extended state C68 until any other thread attempts to lock it further. From any given state, a watch state D70 may be created when a second thread attempts to lock an object while another thread already has the lock. A transition from any state to monitor state D70 can be made. Exit from a synchronous method triggers a transition from monitor state D70 or extended state C68.

The only exception to this transition from any given state to any other state is exception state E72. When an exception signal occurs, the object reaches exception state E72. It is also not possible to exit the exceptional state E72 by sending a switching instruction or command to the exceptional state E72. For other states, ie A-D, it is possible to transition to other states or to itself by sending an appropriate transition command or signal.

Figure 8 shows an optimal automatic process for increasing the speed of a multi-threaded application. It improves upon the synchronization techniques used in virtual machine 10 (see FIG. 1). By removing simple locked state B66 from the automatic process shown in FIG. 7, the thread manager avoids transitions to and from simple locked state B66, thus transitioning directly from unlocked state A64 to locked state C68. A depth indicator (not shown) is used to indicate the lock level as described below.

When a thread attempts to lock an object for the first time, the object transitions from the unlocked state A64 to the simply locked state B66 (see FIG. 7). In this case, set the depth (the number of times the object is locked) to one. As described above, an object transitions from simple locked state B66 to extended locked state C68. When a thread attempts to lock the object a second time, the depth increases to two, indicating a transition to the extended locked state C68. The extended locked state C68 may be considered a state in which the depth level may be greater than or equal to one. Thus, with a depth indicator, the need for a simple locked state B66 can be eliminated.

Cancellation of simple lock state improves thread performance because certain parts of code can be avoided from executing. In addition, transitions from simple locking state to extended locking are avoided, making this thread manager more efficient.

Figure 9 shows a typical class hierarchy 76 used to represent improvements in inherited method calls. Here, the base class is class P78. Class Q80 inherits and derives class P78. Class Q80 extends the inherited method m() of class P78. Class R82 derives class Q80, and class S84 further extends class R82. In the main() method of class S84, a new object 'o' of type S() is initialized. Use the inherited method 'm' as an example in the further description to illustrate the results of the speedup. Those skilled in the art will appreciate that the above description of class hierarchy 76 is an example of a typical class hierarchy and does not limit the present invention in any way. Typically, the techniques presented in this invention have been shown to enable up to about 27% speedup in the execution speed of JAVA programs. The following description summarizes the class hierarchy described above to illustrate typical performance enhancements obtained by applying the principles of the present invention.

Figure 10 shows a histogram 86 used to compare the original method call to the optimal method call in one embodiment of the present invention. It is assumed that the original method call 88 is performed under the KVM environment, while the optimal method call 90 is performed with the virtual machine 10 (see FIG. 1 ) of the present invention. The X-axis of the histogram 86 represents hash table size 42 (see FIG. 2B ), while the Y-axis represents execution time. As shown on the x-axis, the hash table size 42 varies from 11 units to 29 units. The best method call of 90 shows improved performance on all hash table sizes of 42. As shown on the Y-axis, the optimal method call 90 takes about 500 milliseconds, while the original method call 88 takes about 800 milliseconds for the same method call. Thus, the optimal method call 90 of the present invention has improved execution time compared to the KVM method call time. Those skilled in the art will understand that the above comparison of method call times is exemplary and representative, but it does not limit the present invention in any way.

Figure 11 shows a pie chart 92 showing acceleration/jerk rate in one embodiment of the present invention. Reference 94 indicates the size of the hash table 42 (see FIG. 2B ), and the resulting acceleration is represented by a corresponding sector 96 . The pie chart 92 reflects the use of profiling techniques for the code snippets shown in FIG. 9 and described above. The pie chart 92 shows that when the size of the hash table 42 is optimal, there can be better execution times. In this example, the optimal size of the hash table is about 29 units, and its corresponding execution time is 27.91 units. This can be contrasted with the case where the size of the hash table 42 is 11, the execution time increases to 35.97. Using the flexible technique of the present invention, the optimal size of the hash table 42 can be chosen so that collisions are minimized and the required memory footprint is reduced. The general features of the present invention are described below.

The invention is preferably used in object-oriented systems implemented in embedded systems where computing resources are limited compared to larger systems. Performance enhancement is ideal in embedded systems since the systems are usually real-time. Additionally, the present invention provides a flexible approach to optimize the resource requirements of performance enhancement techniques. This is another desirable feature in embedded systems since they have limited memory and processing power. Those skilled in the art will understand that the term "embedded system" is used in a general manner covering any system that operates under certain resource constraints. For example, a system running a JVM in an application employing a cell phone or a watch where computing resources are of limited character.

The description of the invention itself is merely exemplary, and therefore, changes that do not depart from the gist of the invention are intended to fall within the scope of the invention. Such changes are not considered to depart from the spirit and scope of the invention.

Claims (20)

1. A computer platform-based system for increasing the speed of execution of at least one program, the system comprising: A virtual machine, which has a loader for loading a program; The loader includes a hash builder and a hash table lookup module, the hash builder is used to construct at least one hash table corresponding to at least one program class, and the hash table utilizes at least one of the classes at least one hash method characteristic of the method is constructed; The hash look-up module uses a hash function to obtain a hash value for the hash method characteristics of a given method belonging to a given program class, and uses the hash value to search for the given method The hash table. 2. The system according to claim 1, wherein said hash method signature is obtained by applying a hash function to said method signature of said class. 3. The system according to claim 2, wherein said hash table comprises; at least one hash table index corresponding to said hashed method signature; at least one method flag; and At least one pointer for the definition of said method of said class. 4. The system according to claim 3, wherein said hash table further comprises: a collision list for handling a plurality of hashed method signatures corresponding to a common said index of said hash table. 5. The system of claim 4, wherein said loader includes a conflict handler for updating said conflict list. 6. The system of claim 5, wherein said conflict handler is optimized to handle conflict cases where a plurality of hashed method characteristics correspond to a common said index of said hash table. 7. The system according to claim 6, wherein when said hash look-up module cannot find the location of said hash table entry for said given method, said hash look-up module searches said hash table entry for said class. A list of conflicts. 8. according to the system of claim 7, wherein when said hash look-up module can not find the position of said hash table entry corresponding to said given method in said collision list, said hash look-up module Searches for a superclass of said class. 9. The system of claim 1, wherein said virtual machine is a kilobyte virtual machine (KVM) running in a storage environment associated with an electronic device, and said interpreter is a bytecode interpreter. 10. The system of claim 1, wherein said virtual machine is a Java Virtual Machine (JVM). 11. The system according to claim 1, wherein said hash table requires an optimal storage capacity. 12. A computer platform-based virtual machine for executing a program, the program having at least one class, the class having at least one method, the virtual machine comprising: A loader, including a hash compiler and a hash table lookup module, the hash compiler is used to construct at least one hash table corresponding to at least one program class, and the hash table utilizes at least one of the classes at least one hash method characteristic of the method is constructed; The hash look-up module uses a hash function to obtain a hash value for the hash method characteristics of a given method belonging to a given program class, and uses the hash value to search for the given method said hash table; an interpreter for executing methods loaded by said loader, a cache memory associated with said interpreter, said interpreter comprising at least one cache entry storing a previously pointed object and a second link previously pointing to the method; and a cache information handler, associated with said interpreter, for, in the cache, directly passing said second link when a currently pointed object is compared with said previously pointed object through said first link obtaining said method; and A thread manager used by the interpreter, at least two threads of the thread manager act on the object, the thread manager controls the locking of the object with a depth level, wherein a change in the depth level produces at least two Transitions between different locking states. 13. A computer platform-based method for increasing execution speed of at least one program, the method comprising: loading the program into a virtual machine with a loader; constructing at least one hash table corresponding to at least one class of the program; constructing said hash table with at least one hash method signature of at least one method of said class; and The loaded program is interpreted with a hash look-up module to search for at least one given method belonging to a given class of the program. 14. The method according to claim 13, wherein the constructing step further comprises: A hash function is applied to an attribute of said method of said class to obtain at least one hashed method attribute. 15. The method according to claim 13, wherein the interpreting step further comprises: The hashed method table is searched for a hash table entry corresponding to the given method. 16. The method according to claim 13, wherein the constructing step further comprises: A collision list is created for handling hashed method signatures corresponding to a common index of said hash table. 17. The method according to claim 16, wherein the interpreting step further comprises: When the hash table lookup module cannot find the location of an entry in the hash table corresponding to the given method, the conflict list of the class is searched. 18. The method according to claim 17, further comprising: A search of the conflict list is optimized. 19. The method according to claim 17, further comprising: When the hash table lookup module cannot find the position of the hash table entry corresponding to the given method in the conflict list, search a superclass of the class, where the class is the same as the superclass class related. 20. The method according to claim 13, further comprising: Optimize the size of the hash table.

Images