In-Depth

Dynamic Java Program Corpus Analysis, Part 2: The Control Pattern Analysis

• By Chung-Chien Hwang, Deng-Jyi Chen, Shih-Kun Huang, Min-Shong Lin
• June 1, 2001

In order to see if any particular behaviors exist in typical Java programs, we collected a suite of Java programs to analyze. These programs were first executed on the modified Java Virtual Machine (JVM)^4,5,6 to get the runtime invocation sequence, and then analyzed to obtain various statistics. The benchmark programs and results are discussed in this article.

The Program Corpus: Benchmark Programs
We collected 18 Java programs for our analyzer. Most of these programs came from two sources—the sample programs included in the JDK, and the winners of the Java Cup's program contest held by Sun Microsystems in 1996. The Javac program is included in the JDK API. LinpackJava⁷ can be downloaded on the World Wide Web. We hope these programs represent the application domains of Java programs and will exhibit typical Java program behavior.

Table 1. Overview of the benchmark programs.

Table 1 shows the overview and descriptions of our benchmark programs. In the "# of Classes" field, the number in parentheses is the number of classes that exist in the program, while the number outside the parentheses is the number of classes actually used in the program's runtime execution. Most of these programs are user-intervention programs. In other words, the program needs a user to terminate the execution of these programs. We always terminate programs after the execution behaviors have reached a steady state, or after finishing some meaningful work. For example, in the animation program, we kept the program running until the animation was repeated two or three times. In the WebDraw program, we drew a Mickey Mouse face and saved it before exiting the program. These benchmark programs can be classified into the following eight categories:

1. Text Processing
   
   • Javac: This program compiles the Animation program found in the Image Processing category.
2. Image Processing
   
   • Animation: An animator program that shows a sequence of pictures circularly.
   • MoleculeViewer: The program draws 3-D molecule models. The mouse navigates the 3-D model to different viewpoints.
   • ScrollText: A sentence is shown on the screen that can be scrolled around.
   • Blink: Several words are shown on the screen and their location and color randomly change.
   • Fractal: Calculates and draws the fractal graph on the screen.
   • DitherTest: The DitherTest gradually mixes two chosen colors and shows the results.
3. Games
   
   • TicTacToe: A little game program.
   • Tubes: A puzzle game program.
4. Multithread Program
   
   • BackgroundThread: Two threads run simultaneously and communicate with each other, exchanging computed data.
   • ThreadX: Three threads are in the program, and users control when to start or stop the running of any of the three threads.
5. Interactive Program
   
   • CardTest: A graphical user interface (GUI) demonstration program. Users can choose a layout and the program will give a demonstration.
   • MapInfo: A simple geographical information system. The map of the University of British Columbia is shown on the screen. Users can get detailed information about any particular building by clicking on it.
6. Simulation
   
   • TrafficSim: The program simulates the effect of traffic flow and lights using graphics.
   • TuringMachine: The program simulates the operations of the Turing machine. Sample programs can be loaded into the simulator and the execution process will be shown.
7. System
   
   • WebDraw: A graphics editor. Users can draw graphics, as well as save or load them to or from the files.
   • DigSim: A digital circuit editor and simulator. Users can choose the built-in digital circuit components, connect them, and simulate how they operate.
8. CPU-Intensive program
   
   • LinpackJava: An artificial benchmark that can test CPU performance.

Figure 1. Average method size.

Figure 2 illustrates the average method size distribution of our benchmark programs. The number of methods was measured in 20 byte increments. For example, the bar at 20 on the X-axis shows the number of methods whose size is between 20 bytes and 40 bytes. We also observe from Figure 2 that method size in most Java programs is small, with nearly half being between zero and 20 bytes in size. This is one of the features of OO programming: It is recommended to access object variables through methods. Methods for accessing object variables usually contain only one return statement. Moreover, methods in OO programs are not very complicated. Complicated methods are usually divided into several simple methods. This is why most methods are very small in our benchmark programs.

Figure 2. Average method size distribution.

Too many small methods induce frequent control transfers during program execution. A control transfer is very expansive when compared to sequential execution.⁸ It needs to search the destination address and prepare the context of the target method's execution. Thus, small method sizes are inefficient in program execution.

Native Method
Although the JVM can be implemented on a chip, it does not contain any I/O instructions. Therefore, when implementing JVM software on a platform, all I/O operations must be executed by the native codes of that platform. Some of the methods of the JDK API are written in the C language and compiled into native codes rather than Java bytecodes.

While analyzing our benchmark programs, we have found that, in most cases, the execution percentages of the native methods do not exceed 20% (see Figure 3). However, the native method execution percentages of TrafficSim and TuringMachine are 25% and 32%, respectively, which is higher than other programs. The reason is that the two programs contain a lot of I/O operations. Because the DitherTest and LinpackJava programs involve many arithmetic operations, the native method execution percentages are relatively very low.

Figure 3. Percentages of native method during execution.

We believe that if a Java program executes more native methods, then the execution speed of that program will increase. But executing more native methods contradicts the design philosophy of JVM, which is designed for a platform-independent execution. If execution depends heavily on native methods, then the Java program will no longer be platform-independent.

Method Invocation Localities
In Figure 4, two values are drawn for each program. The left bar represents the receiver class locality, while the right bar represents the method class locality. These values are around 0.1 or less. This means that during program execution, over a short period of time the access to classes is confined to a small subset, rather than all of the program classes.

Figure 4. Receiver-class locality and method-class locality.

A very interesting phenomenon is that receiver class localities are always smaller than method class localities. This is because a message to an object may cause the object to execute methods of its super classes. In Figure 5, there are two classes A and B, where Class B is a subclass of A. m1 is a method of Class A, and m2 is a method of Class B. The middle column of Figure 5 is a program segment, where b is an object of class B, while m1 and m2 messages are sent to object b three times. The right column of Figure 5 is the method invocation sequence of the program segment. In this sequence, the receiver class is always B; however, the method classes are A and B, alternatively. This example illustrates why receiver class localities are always smaller than method class localities.

Figure 5. An example of receiver-class locality vs. method-class locality.

Figure 6 shows the method localities of our benchmark programs. All of these method localities are smaller than 0.07, which is slightly better than the values for the receiver and method class localities.

Figure 6. Method locality.

The receiver and method classes, along with method localities of the DitherTest program, are much smaller than other programs. That is why there is a large loop that involves intensive computations. Only several methods are involved in that loop. Consequently, the DitherTest program localities are much smaller.

By analyzing method invocation localities during program execution over a period of time, the method invocation behaviors are confined to a small set of classes or methods. Java Runtime System (OO runtime system) utilizes this feature to support runtime method invocation prediction. With accurate prediction, program performance can be improved.

Consecutive Patterns
Figure 7 shows the percentages of receiver and method class consecutive patterns in our benchmark programs. The left bar of each program represents the percentage of receiver class consecutive patterns, while the right bar represents the percentage of method class consecutive patterns.

Figure 7. Percentages of receiver/method class consecutive patterns.

The percentages of these two patterns vary between different programs. The percentages of DitherTest and LinpackJava programs are very high when compared to other programs. They are computation-intensive programs. The code for intensive computations is in one or several methods of a particular class. As a result, the dynamic execution behavior focuses on these methods or classes, and produces higher percentages of consecutive patterns.

Figure 8 shows the percentages of method consecutive patterns of the benchmark programs. Compared with the percentages of class consecutive patterns, the percentages of method consecutive patterns are very low. DitherTest, LinpackJava and DigSim have high percentages of method consecutive patterns. The DigSim program uses a lot of Vector objects to store circuit information. When simulating the circuits, these Vector objects' sizes must be retrieved for simulation. As a result, a lot of the method consecutive patterns are from invoking the Vector.size() method.

Figure 8. Percentages of method consecutive pattern.

Except for the ThreadX program, the percentages of receiver class consecutive patterns are always higher than the percentages of method class consecutive patterns. The reason is the same as with receiver class localities that are always smaller than the method class localities. Figure 9 points out why the ThreadX program is abnormal.

Figure 9. An abnormal example.

In Figure 9, there are three classes: A, B, and C. Classes B and C are subclasses of A, while m1 and m2 are methods defined in class A. The third column of Figure 9 is a program segment. In this program segment, object b and object c both invoke the methods in class A, though they are not the same classes. As a result, the correspondent method invocation sequence (Figure 10) is a method class consecutive pattern, but not a receiver class consecutive pattern. In the ThreadX program, this situation occurs very often, so its percentage of method class consecutive patterns is higher than its percentage of receiver class consecutive patterns.

Figure 10. Method invocation sequence of abnormal example.

There are four values drawn in Figure 11. The percentages of receiver-consecutive patterns and class-consecutive patterns are listed here for comparison with percentages of receiver-hierarchy-consecutive patterns and class-hierarchy-consecutive patterns.

Figure 11. Percentages of receiver/class hierarchy consecutive patterns.

Receiver-hierarchy-consecutive patterns mean that given two consecutive events, if the receiver classes are the same or belong to the same inheritance path, they are then called receiver-hierarchy-consecutive patterns. The percentages of receiver-hierarchy-consecutive patterns and class-hierarchy- consecutive patterns are very close, and they are usually higher than the percentages of class-consecutive patterns. The reason is that the invocation of the constructor will cause the invocation of the superclass constructors. The consecutive invocations of constructors are class-hierarchy-consecutive patterns, but they are not class-consecutive patterns.

By analyzing these consecutive patterns, we found the percentages of consecutive patterns of some programs to be high. The implication of this phenomenon is that the compilers or runtime systems can deploy some tricks to reduce the overhead of method invocation. The overhead of method invocation includes the searching of the destination address of the method, and the preparation of the execution context.

Loop-N Patterns
In Figure 12, four values are drawn for each program. The first value is the percentage of receiver-class-consecutive-patterns listed for comparison with the other three values. The second value is the percentage of receiver-loop-2 patterns, while the third is the percentage of receiver-loop-3 patterns. The fourth value is the percentage of receiver-loop-4 patterns.

Figure 12. Percentages of receiver loop—2, 3, and 4 patterns.

Figure 12 also shows that observed programs with a high percentage of receiver-consecutive-patterns usually have high percentages of receiver-loop-N-patterns. The BackgroundThread program is the only exception. During the execution of the BackgroundThread program, the percentages of receiver-consecutive-patterns, receiver-loop-2 patterns, and receiver-loop-4 patterns are 16%, 12%, and 13%, respectively; however, the percentage of receiver-loop-3 patterns is 75%. From this comparison, we can conclude that during the execution of the BackgroundThread program there are many method invocation destinations that are the same as the following third method invocation destination.

Figure 13 shows the percentages of class-loop-2, class-loop-3, class-loop-4, and class-consecutive patterns. The behaviors and values of the class-loop-N patterns are nearly the same as with the receiver-loop-N patterns.

Figure 13. Percentages of class loop—2, 3, and 4 patterns.

Figure 14 shows the percentages of method-loop-2, 3, and 4 patterns and method-consecutive patterns. Compared to receiver-loop-N and class-loop-N patterns, the percentages of method-loop-N patterns are lower.

Figure 14. Percentages of method loop—2, 3, and 4 patterns.

Generally speaking, the occurrence of the same consecutive method invocation is rare. But the occurrence of the same method invocation every second, third, or fourth situation is more frequent than consecutive situations. Take the Javac program for example—its percentage of method-consecutive patterns is 7%. The percentages of method-loop-2, 3, and 4 are 24%, 13%, and 24%, respectively, which is higher than the percentage of method-consecutive patterns.

Except for the consecutive patterns discussed in the previous section, Loop-N patterns is another kind of control pattern. By our analysis, we have found that these Loop-N patterns do exist during the Java program execution, and that the percentages of these patterns for some Java programs are high. This also provides another opportunity for compilers or runtime systems to optimize the Java programs (OO programs) execution.

Receiver Class vs. Method Class
By our definition, an event has three components: the receiver class, method class, and method. The relationship between the receiver class and the method class has three possibilities. They may be the same, they may belong to the same class hierarchy, or they are not the same and do not belong to the same class hierarchy. The first situation is called thisclass-method invocation. The second situation corresponds to an invocation to the method belonging to the superclass of the receiver class. This kind of invocation is called superclass-method invocation. The third situation is if the event is a static-method invocation; if it is, then the receiver class will be java/lang/Class, and the method class will be the class the static method belongs to.

In Figure 15, the percentages of the above three possibilities are shown for each benchmark program. In Figure 15, it can be easily recognized that in most of our benchmark programs the situation where the receiver class and method class are the same dominates the other two possibilities (especially when the static method invocations occupy only a small portion of the events).

Figure 15. The percentages of static-method, thisclass-method, and superclass-method invocation.

In the ThreadX program, the percentage of the second situation is larger than the first situation. There are three threads in the ThreadX program. To demonstrate the concurrent execution of the three threads, the programmer uses three objects whose class is inherited from java.awt.panel to show the running status of these three threads. Many of the messages are sent to the superclasses of the three objects, rather than the class of these objects. As a result, the percentages of the second situation are larger than the first.

We have classified three kinds of relationships between the receiver class and the method class. When the receiver class and method class are in the same inheritance path, but not the same class, there will be a distance among the inheritance path between the two classes.

In Figure 16, the average distance between the receiver class and method class of each benchmark program is shown (the situation where the receiver class and method class are the same is not included in the calculation of average distance). Most of the average distances are between one and two. This means that more than half of the messages are sent to the receiver's direct superclass, while others are sent to the superclasses of the receiver's direct superclass.

Figure 16. Average distance between receiver class and method class.

Using methods defined in superclasses is a feature of the OO programming paradigm. It allows programmers to reuse programs written by others. But this feature is also a source of runtime overhead. When a method invocation occurs, the runtime system has to upward search the applicable method along the inheritance path. A solution for this overhead is to gather all the applicable methods in a table—then there is no need to upward search the inheritance path. But this solution incurs excessive memory usage.

In our analysis of the relationships between receiver class and method class—as well as their respective percentages during execution—we have found that in most of our benchmark programs, more than half of the method invocations are thisclass-method invocations. For superclass-method invocations, the average upward search level is below two. Analysis of the results hints to us that merging the upward searching method with the table method mentioned in the previous paragraph can improve the performance of method lookup with acceptable increased memory usage.

Conclusion
OO program behavior can be characterized by the method invocation sequence produced during program execution. In this article, Java was chosen as our target programming language, and various runtime information was analyzed. The method invocation sequence of a Java program execution was obtained by running the Java program on the modified JVM software implementation. The JVM software implementation of Sun Microsystems is written in the C language. The major parts of the implementation we modified were the dynamic class loader and the execution engine. We also designed and implemented an analyzer to analyze the runtime information obtained by running Java programs on the modified JVM software implementation.

We collected 18 Java programs as our benchmark programs, consisting of eight application domain categories. We believe these 18 programs can represent typical Java applications. After obtaining the runtime information of these benchmark programs, we used our analyzer to analyze the method sizes, native method percentages, method invocation localities, and control patterns.

Method sizes of Java programs are usually very short. More than 50% of them are less than 20 bytes. This indicates that inline, these short methods will reduce much of the method invocation overhead and improve performance. JVM does not define any I/O instructions, so a JVM software implementation needs native codes to deal with program I/O operations. In our analysis, less than 20% of the method invocations in most Java programs are native method invocations.

In addition, we evaluated whether locality of method invocation exists during Java program execution. Our analysis revealed that over a short period of time, method invocations were confined to a small set of classes and methods. The immediate application of this analysis result is to help the method invocation prediction. With more accurate method invocation prediction during program execution, the performance of object-oriented programs can be improved.

We also defined two control patterns—consecutive patterns and loop-N patterns—and evaluated their percentages in the method invocation sequence of the benchmark programs. Although the percentages of these patterns vary between different programs, they do exist in the method invocation sequence during program execution. The existence of control patterns provides opportunities for users to optimize the runtime behaviors of their OO programs.

A final result of our analysis of the benchmark programs was that most of the method classes of method invocations are the same class as the receiver class, instead of superclasses of the receiver class. We hope this article and its results provide users with directions for improving the execution efficiency of their OO programs.

References

1. Agrawal, Rakesh and Ramakrishnan Srikant. "Mining Sequential Patterns." See http://citeseer.nj.nec.com/189.html.
2. Chen, Ming-Syan. "Data Mining: An Overview from a Database Perspective," IEEE Transactions on Knowledge And Data Engineering, 8(6), Dec. 1996.
3. Hwang, Chung Chien, et. al. "Dynamic Java Program Corpus Analysis: Part 1—The Analyzer," Journal of Object-Oriented Programming, 14(1):26–29, May 2001.
4. Flanagan, David. Java in a Nutshell, O'Reilly & Associates, Inc., Sebastopol, CA,1996.
5. Lindholm,Tim and Frank Yellin. The Java Virtual Machine Specification, Addison–Wesley, Reading, MA, 1997.
6. Meyer, Jon and Troy Downing. Java Virtual Machine, O'Reilly & Associates, Sebastopol, CA, 1997.
7. See http://www.netlib.org/benchmark/linpackjava/.
8. Ungar, David, et. al. "Object, Message, and Performance: How They Coexist in Self," IEEE Computer, 25(10):53–64, 1992.