Method and Apparatus for Benchmarking Byte Code Sequences

The present invention relates to data processing systems in general, and in particular, to interpreted languages for programming data processing systems.

Rapid growth of the "Internet," a worldwide communications network of computers, has stimulated the interest in distributed data processing. In a distributed data processing environment, a server can download an application to a client, and the client then executes the application. An even greater degree of sophistication in distributed processing is manifested in distributed data processing systems that allow a local data processing device to invoke methods on a remote host just as if they were implemented locally. In order for distributed data processing to function in an open network environment such as the Internet, it is necessary that the distributed applications be platform neutral. In other words, there is no way in such a networking environment for the server to know the computing platform with which it is communicating. Applications transmitted for remote execution must be able to function independent of the computing platform to which they are targeted.

Java is a programming language designed to be platform neutral. For this reason, it has rapidly become a popular programming language for distributed data processing.

Java source code is compiled to run on a Java Virtual Machine ("Java VM"). Any platform from which a Java VM has been implemented can execute Java applications. The Java VM interfaces the platform independent compiled Java source code to the platform on which the application is being executed. The Java VM is a software engine running on top of the hardware and operating system of the target platform.

Platform independency is achieved by the compilation of Java source code into a set of one byte digits called "byte code." A byte code may be viewed as a machine code for the Java VM, wherein each byte code corresponds to a Java VM instruction. The Java VM instructions are defined in the specifications for the Java VM. The byte code is platform independent. The Java VM then acts as an interpreter between the Java byte code and the specific system on which the Java program is executing.

Although platform independence is an advantage of Java, it is acquired at a price. Because Java is an interpreted programming language, Java applications execute more slowly than a similar program produced using a compiled language, such as C or C++, would execute. The Java Virtual Machine steps through the compiled Java program, typically referred to as a Java class file, byte code-by-byte code translating each into native instruction sequences on the fly. This process is slower in executing applications than are languages compiled and then loaded as a set of native machine instructions. In order to improve performance of Java applications, it is becoming more common now for Java interpreters to include "Just In Time" ("JIT") compilers. JIT compilers translate certain Java byte code segments into machine code for the particular hardware platform on which the Java VM is implemented. This translation occurs at one time and the block of compiled code is then stored for later execution.

Different Java VM implementations handle byte code interpretation in a variety of ways. Therefore, there can be a significant variation in performance among different Java VM implementations. The ability of the JIT within a particular Java VM implementation to optimally compile for the most commonly occurring sequences of byte codes is critical to the performance of that Java VM implementation. In order to improve the performance of the JIT, and its Java VM implementation, there is a need in the art for a method and apparatus of detecting, articulating and accurately measuring such commonly occurring byte code sequences.

The aforementioned need is addressed by the present invention which identifies frequently occurring byte code sequences and obtains performance measures thereof. The invention first identifies frequently appearing byte code sequences within a byte code trace. The frequently occurring sequences are then abstracted for stand alone execution, in which they are formulated into a byte code assembly program. This assembly program is then assembled and injected into a Java benchmark driver program.

Byte code trace analysis identifies sequences of byte codes that appear with some frequency in the byte code image of an application of interest. The byte code trace is simply the record of a specific sequence of byte codes encountered by the Java VM in executing an application of interest. A byte code trace of any particular application may include several million byte codes. Byte code sequences of interest, such as those that are frequently occurring, may have variable length from a single byte code to a preselected maximum length of about 30 byte codes. Byte code analysis identifies those sequences that occur with a frequency exceeding a preselected value, reports those sequences, and the frequency of occurrence.

Selected frequently occurring byte code sequences are then formulated into a byte code assembly program. A particular byte code sequence may have an associated environmental dependency which must be reproduced for the extracted byte code sequence. The Java VM instructions establishing the linkages to these environmental dependencies along with the Java VM instructions corresponding to the byte code sequence to be benchmarked from the binary byte code assembly program are formed.

The binary byte code program is injected into a benchmark executable. The benchmark executable is a Java skeleton that includes methods implementing measurement tools to obtain accurate timings and other hardware metrics for the byte code sequence being benchmarked. Execution of the target executable with the injected byte code binary program then generates the required benchmarking statistics.

These, and other features and advantages, will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings. It is important to note the drawings are not intended to represent the only form of the invention.

The foregoing has outlined rather broadly the features and technical advantages of the present invention in order that the detailed description of the invention that follows may be better understood. Additional features and advantages of the invention will be described hereinafter which form the subject of the claims of the invention.

For a more complete understanding of the present invention, and the advantages thereof, reference is now made to the following descriptions taken in conjunction with the accompanying drawings, in which:

FIG. 1 depicts a flow diagram in accordance with a method of an embodiment of the present invention.

FIG. 2A illustrates a flow diagram of a byte code assembly method in accordance with an embodiment of the present invention.

FIG. 2B illustrates a flow diagram of a byte code assembly method in accordance with an embodiment of the present invention.

FIG. 3 illustrates a flow diagram of a byte code assembly method in accordance with an alternative embodiment of the present invention.

FIG. 4 illustrates a flow diagram of a byte code sequence analysis method in accordance with an embodiment of the present invention.

FIG. 5A depicts a first portion of a flow diagram of a byte code sequence analysis method in accordance with an embodiment of the present invention.

FIG. 5B depicts a second portion of a flow diagram of a byte code sequence analysis method in accordance with an embodiment of the present invention.

FIG. 6 schematically illustrates associative array data structures in accordance with an embodiment of the present invention.

FIG. 7 depicts a data processing system configured in accordance with an embodiment of the present invention.

In the following description, numerous descriptive details are set forth to provide a thorough understanding of the present invention. However, it will be obvious to those skilled in the art that the present invention may be practiced without such specific details.

Refer now to the drawings wherein depicted elements are not necessarily shown to scale and wherein like or similar elements are designated by the same reference numeral through the several views.

Refer now to FIG. 1 in which is depicted a flow chart of an embodiment of the present invention. In step 100, the data processing system analyzes a byte code trace to identify frequently occurring byte code sequences. That is, a byte code trace is a list of virtual machine instructions that the Java VM executes in performing an application of interest. An individual byte code is a numerical value that corresponds to an eight bit, or one byte, binary number. Each byte code represents a Java VM instruction. Byte codes are often represented in human readable form in ASCII characters corresponding to their value in hexadecimal, or base-16, notation. By way of illustration, the byte code value seventy-nine is the Java VM instruction for storing a value into an array containing integer values. In ASCII characters, this byte code instruction has the hexadecimal representation "0.times.4F" in accordance with conventional practice in the art. In an embodiment of the present invention, byte code analysis may proceed in a byte code trace in the form of binary values themselves. In an alternative embodiment, a byte code trace in the form of binary values may first be converted to the ASCII representation of the binary values, as just described, on a byte code analysis performed on the byte code trace as represented in ASCII format. An embodiment of the present invention in which the byte code trace analysis process is performed on a byte code trace in ASCII format will be described subsequently. Byte code trace analysis identifies sequences of byte codes that appear frequently in the application of interest. Frequently occurring byte code sequences are those sequences that occur at least a preselected number of times in the byte code trace of the application of interest.

Frequently occurring sequences in the application of interest may then be targeted for benchmarking by incorporating them into a Java benchmarking shell. In order to do this, a byte code binary must be generated corresponding to a byte code sequence to be benchmarked, step 101. In generating the byte code binary, any environmental dependencies associated with the byte code sequence to be benchmarked must also be reproduced or synthesized. That is, the extracted byte code sequence to be benchmarked must be placed in its appropriate context. For example, if the byte code sequence of interest updates an element of an array, then the array must first be created before that byte code sequence is executed.

Refer now to FIGS. 2A and 2B in which alternative embodiments of the present invention for generating byte code binaries are depicted. In an embodiment of the present invention, step 102a corresponds to step 102. In step 102a, Java VM instructions are entered including instructions for synthesizing the environment required by the byte code sequence to be benchmarked (step 200). In step 201, these Java VM instructions are assembled into a byte code binary program. It is understood in the art that Java assembly is the process of replacing Java VM instructions in human readable form with the corresponding byte codes and any operand values representing the operands on which the machine instructions operate. Although the process of assembly may, in principal, be carried out by hand, it is envisioned, in an embodiment of the present invention, that the process of assembly is performed by the data processor.

In an alternative embodiment, step 102b corresponds to step 102 of FIG. 1. In step 102b, an environmental context may be reproduced in a target executable. In such an alternate embodiment of the present invention, the environmental context is reproduced by introducing it into the target executed source code in step 202. That is, the source code for the Java benchmarking shell is modified to incorporate source code implementing the environmental dependencies required by the byte code sequence to be benchmarked. Compilation of the resulting Java source code then yields a benchmark shell binary that includes the required environmental dependencies. Nevertheless, it is still necessary, when building a byte code binary representing the sequence to be benchmarked, to incorporate within the Java VM instructions representing that sequence, appropriate linkages to the environmental dependencies included in the benchmark shell, as in step 203. In either embodiment of the step of generating a byte code binary, 102a or 102b, the Java VM instructions representing either embodiment are then assembled into a binary byte code program (step 201).

It should be noted that the step of assembling the Java VM instructions into the binary byte code program (step 201) is not always required in some embodiments of the present invention. For example, after a byte code sequencing operation is performed to detect a frequent sequence, that sequence may be reproduced in Java directly in some situations. One such frequent sequence has the form:

dup

sipush<index>

iconst.sub.-- 0

bastore

Such byte code are explained in greater detail in The Java Virtual Machine Specification by Tim Lindholm et al., published by Addison-Wesley in 1997, which is incorporated by reference herein.

This sequence may be produced by the following Java language construct:

byte arr [ ]=[0,0,0,0, . . . 0 ];.

Given that the sequence can be produced using a Java language construct, a benchmark may be easily fabricated by inserting the aforementioned Java construct in the source code for the benchmark driver. Thus, when that benchmark is compiled and executed, the benchmark will then perform the desired sequence.

However, it should be noted that such substitutions do not always result in correctly functioning code. In such situations, byte-code assembly and subsequent injection should still be implemented.

Referring now to FIG. 1, in step 102, the binary byte code program implementing the sequence to be benchmarked is injected into the benchmark driver shell. The injection of the byte code binary into a target executable is the subject of a copending application "SYSTEM AND METHOD FOR DYNAMIC MODIFICATION OF CLASS FILES," heretofore incorporated by reference into this application. The process of byte code assembly for injection into the benchmark shell is a special case of a more general process of byte code injection assembly. Byte code injection assembly may be used for introducing new functionality into any target executable, not necessarily a Java benchmarking shell.

Refer now to FIG. 3 in which a flow chart of the process of byte code injection assembly is illustrated. The target executable is processed to update information about its environment, in step 300. This includes information such as constant pool entries for exported methods (functions), imported methods, and instance variables for classes in the executable are obtained. An embodiment of the data processing program that can provide such information is the Java class file disassembler, "javap." Javap (or its equivalent) is part of every Java VM implementation. Then, in step 301, assembly code corresponding to Java VM instructions implementing the functionality to be added is entered. These assembly code java VM instructions include instructions establishing the required linkages to the target executable environmental dependencies. The assembly code so entered is then assembled into a byte code binary in step 302. The byte code binary thus generated may then be injected into the target executable using the dynamic modification technique that is the subject of the cross-referenced copending application hereinabove incorporated by reference.

The method of byte code sequence analysis will now be described by reference to FIG. 4. FIG. 4 schematically depicts a flow chart of a byte code sequence analysis method in accordance with one embodiment to the present invention. A data processing machine initiates the process in step 400. In step 401 a byte code is entered. Although byte code analysis in accordance with an embodiment of the present invention may be implemented with byte codes being entered "by hand," byte codes from a byte code trace may also be retrieved from a data processing file. When retrieving the byte code trace from a data processing file, the following methodology may be used in one embodiment of the present invention.

In one embodiment of the present invention, the "java.sub.-- g" command in the standard JavaSoft Java Development Kit (JDK) provides for method and byte code tracing. To implement byte code tracing in accordance with one embodiment of the present invention, this mechanism was modified somewhat. First, an output format was modified to be more efficient. A typical byte code trace used for profiling is several megabytes in length. The standard java.sub.-- g mechanism also outputs byte code addresses, operands, and information about operand values. In the modification, the amount of data output for each byte code was limited to the byte code itself (and, in some cases, the operand value). Similarly, the output for method invocations was also modified to contain only the name of the method. Second, the byte code address for each byte code was examined. If a backward branch had been taken because a loop has been detected, a blank byte code was output prior to the byte codes at the target address of that branch. This enabled an aliasing optimization that is subsequently described in the application. Finally, the interpreter loop of the JVM was modified to poll the local file system (every several thousand byte codes) for the presence of a well-known file name (e.g., "trace.sub.-- file"). As long as that file was not present, the interpreter proceeded and no tracing was enabled. When the user created the file, this engaged byte code and method tracing. This latter mechanism was employed to provide control over the start and end of method and byte code tracing, an important factor when collecting traces from very large or long-running applications.

Regardless in which manner the byte code trace is obtained, the entered byte code is then stored in step 402. It is also concatenated to all previously stored byte code sequences in step 403. In step 404, the new sequences, thus formed, are tested and any such sequence having a length exceeding a preselected maximum length is discarded. Otherwise, the sequences are stored in step 405. A counter is associated with every sequence formed by the steps of entering, storing in concatenation, steps 401-403. In step 406, the counter associated with each such sequence is incremented whenever associated sequence appears, and the sequence is stored in step 405. If the last byte code has been entered (step 407), byte code sequences and their associated counter values, which are the frequencies of occurrence of the associated sequence, are reported in step 408. The process then terminates at step 409. In an alternative embodiment of the present invention, the reporting of sequences and counter values (step 408) may be delimited by reporting only those sequences whose associated counter values exceed a preselected value. If the last byte code has not been entered, the process returns to step 401 with the entry of the next byte code in the sequence.

Refer now to FIGS. 5A and 5B in which is depicted a flow chart detailing an embodiment of byte code sequence analysis of the present invention. The process begins with a new line of a byte code input file in step 500. An entry from the file is read in step 501, and in step 502 the entry is tested to determine if it is a valid byte code. This testing operation is performed to eliminate aliases of sequences to optimize performance of the present invention. Aliases are sequences that are rotations of the same basic sequence. These aliases would be produced when sequencing code appearing in a loop, if this optimization method were not implemented. If it is not a valid byte code, the file is advanced to the next entry in step 503, and a sequence length tag value is set to zero, step 504. The process then returns to step 501 and continues. If a valid byte code has been read a new length value is set equal to zero, step 505 and a loop counter, in step 506, is set equal to the sequence length tag value plus one. The process then enters the loop at step 507 with the testing of the loop counter. If the loop counter is greater than or equal to one, the current byte code is concatenated with the sequence whose length is equal to the value of the loop counter and that sequence is stored, step 508. In step 509 a counter associated with a current sequence is incremented. In other words, in step 509 the current byte code sequence is compared with all other stored byte code sequences, and if there is a match, a counter associated with that byte code sequence is incremented by one. If the current sequence does not match any other stored sequence, then its associated counter assumes the value one. An embodiment of the present invention in which steps 508 and 509 are realized using associative arrays will be described subsequently. In step 510, the counter associated with the current sequence is tested against a preselected frequency value. If the counter is greater than or equal to the preselected frequency value, then the current byte code sequences are so-called frequently occurring sequences. Then, in step 511, the loop counter is tested against the new length value. If the loop counter value does not exceed the new length value the loop counter is decremented in step 512, and the loop is reentered at step 507. However, if the loop counter value exceeds the new length value, the new length value is set equal to the current value of the loop counter, step 513, and the loop counter is then decremented by unity, step 512 and the loop is reentered at step 507. If the current value of the loop counter is not greater than or equal to one, the new length value is tested against a preselected maximum sequence length in step 514. If the new length value does not exceed the maximum sequence length then the sequence length tag value is set equal to the new length value at step 515, and the process advances to the next entry, step 516. Thus, the sequence length tag value forms a window that moves along the byte code trace after generating the first byte code sequence have a length equal to the preselected maximum sequence length. If, however, the new length exceeds the preselected maximum sequence length and the sequence length value is set equal to the preselected maximum length minus one, in step 517, and the process advances to the next byte code entry at step 516.

Associative arrays are convenient structure for implementing steps 508 and 509 in FIGS. 5A and 5B. An associative array is a collection of pairs: an index and the corresponding array element value. In an associative array, the index does not have to be a positive integer. Any number, or even a string, can be an index. Thus, in step 508, a byte code sequence of length "i-1" is fetched from element number "i-1" of a first associative array in concatenated with the sequence so retrieved. The resulting sequence of length "i" is then stored back into element number "i" of the first associative array. Step 509 is implemented with a second associative array. The second associative array is indexed using the byte code sequence as a string value stored in the first associative array. Each element of the second associative array stores a counter. Every time an element of the second associative array is accessed, the counter value stored therein is incremented by one.

Method steps 508 and 509 using two associative arrays may be better understood by referring to FIG. 6 in which these associative arrays are schematically depicted. In FIG. 6, for simplicity, byte code values are denoted by single lower case letters. A simplified byte code trace, 600, is illustrated in this array. Byte code sequences of maximum length equal to four are considered. The state of the first associative array after the first four byte codes have been entered are shown at 601. The set of index values 601a are illustrated to be "1", "2", "3", and "4". The set of values stored in the respective array elements, 601b, are byte code sequences "b", "ab", "bab", and "abab". In reaching the displayed state of associative array 601, a set of sequences of having lengths from 1 to 4 have been generated. All unique sequences so generated form the index set 602a of associative array 602. In an alternate embodiment, sequences may be of length 1 to N where N is preselected. The set of array contents 602b contains the number of occurrences of each of the respective byte code sequences comprising the index set 602a . After the next byte code, "c", is entered, first associative array 603 results. The index set 603a of first associative array 603 is unchanged and the content set 603b is as illustrated. Second associative array 604 now has more elements, and its index set 604a includes four additional values: "c", "bc", "abc", and "abac". The contents of 604b of second associative array 604 is as shown with each of the four additional elements all containing the value one, each of the byte code sequences "c", "bc", "abc", and "abac" having occurred for the first time.

An implementation of associative arrays is available in the pattern matching program awk. An example of an awk script which corresponds to the method illustrated in the flow chart of FIGS. 5A and 5B is as follows:

In the foregoing program, it should be noted that the term "as[i]" is a currently active sequence of length i. This currently active sequence is indexed by an integer number. It should be noted that in the program illustrated herein, only sequencing up to a length "LMAX" will be evaluated. Thus, there will only be as[1] through as[LMAX] entries. Each time a new byte code is examined, the values of as[i], for all i will be updated to reflect that a new byte code is part of each current sequence. Furthermore, it should be noted that the term "SCNT[x]" is a number of times that sequence x has been detected.

Furthermore, it should be noted that the first associative array, implementing the step 508 in FIGS. 5A and 5B, appears in line 11 where step 508 is performed. That associative array is denoted "as". The second associative array appears on line 12 as the associative array "SCNT". Note that the associative array SCNT is indexed by the contents of element number "i" of the associative array "as".

It should also be noted that the aforementioned program may be written in programming language other than awk script. Such other languages may include C, C++, and the like.

A representative hardware environment for practicing the present invention is depicted in FIG. 7, which illustrates a typical hardware configuration of workstation 713 in accordance with the subject invention having central processing unit (CPU) 710, such as a conventional microprocessor, and a number of other units interconnected via system bus 712. Workstation 713 includes random access memory (RAM) 714, read only memory (ROM) 716, and input/output (I/O) adapter 718 for connecting peripheral devices such as disk units 720 and tape drives 740 to bus 712, user interface adapter 722 for connecting keyboard 724, mouse 726, speaker 728, microphone 732, and/or other user interface devices such as a touch screen device (not shown) to bus 712, communication adapter 734 for connecting workstation 713 to a data processing network, and display adapter 736 for connecting bus 712 to display device 738. CPU 710 may include other circuitry not shown herein, which will include circuitry commonly found within a microprocessor, e.g., execution unit, bus interface unit, arithmetic logic unit, etc. CPU 710 may also reside on a single integrated circuit.

The foregoing provides a description of alternate embodiments of the present invention. It should be well-known to those with skill in the relevant art that additional embodiments may also be utilized to implement a Java benchmark driver program. Furthermore, it should be noted that because the Java benchmark driver program is written in Java, the present invention is able to perform measurements in a competitive manner as Java's portability allows the Java benchmark driver program to be executed on any platform implementing a Java VM and a JIT compiler.

Although the present invention and its advantages have been described in detail, it should be understood that various changes, substitutions and alterations can be made herein without departing from the spirit and scope of the invention as defined by the appended claims.