The relative efficiency of Java programs is much discussed today, particularly in comparison to well-established implementation languages such as C or C++. Java is often considered very slow and memory-intensive. However, most benchmarks compare only a single implementation of a program in, say, C++, to one implementation in Javaneglecting the possibility that alternative implementations might compare differently. In contrast, this article presents a comparison of 40 different implementations of the same program, written by 38 different programmers (there are two double Java implementations). The data compares, for one particular programming task, the average relative performance between languages as well as the performance differences from one programmer to another within a group of programs written in the same language. As noted, these interpersonal program differences are larger than those between the languages.
The 40 program implementations investigated were created by graduate students during the course of a controlled experiment on a different question (L. Prechelt and B. Unger, "A Controlled Experiment on the Effects of PSP training: Detailed Description and Evaluation, (Jan. 1999); ftp.ira.uka.de). There are 24 programs written in Java, 11 in C++, and 5 in C. Each program was written by a single person. These programmers had an average of 8 years of programming experience and estimated that they had previously written an average of 100 KLOC each (median: 20 KLOC).
All programs implement the same functionality, namely a conversion of telephone numbers into word strings. The program first loads a dictionary of 73,113 words into memory from a flat text file (one word per line, 93KB overall). Then it reads "telephone numbers" from another file, converts them one by one, and prints the results. The conversion is defined by a fixed mapping of characters to digits as follows:
e j n q r w x d s y f t a m c i v b k u l o p g h z
0 1 1 1 2 2 2 3 3 3 4 4 5 5 6 6 6 7 7 7 8 8 8 9 9 9
The task of the program is to find a sequence of words such that the sequence of characters in these words exactly corresponds to the sequence of digits in the phone number. All possible solutions must be found and printed. The solutions are created word by word and if no word from the dictionary can be inserted at some point during that process, a single digit from the phone number can appear in the result at that position. Many phone numbers have no solution at all. Here is an example of the program output for the phone number "3586-75," when the dictionary contained the words "Dali," "um," "Sao," "da," "Pik," and 73,108 others:
3586-75: Dali um
3586-75: Sao 6 um
3586-75: da Pik 5
A list of partial solutions needs to be maintained by the program while processing each number, and the dictionary must be embedded in a supporting data structure (such as a 10-ary digit tree) for efficient access. Search functions of this kind might be part of a server in a larger client/server software system.
The programmers were asked to write as reliable a program as they could. Efficiency was less important. However, a runtime limit (not quantified to the programmers in advance) was imposed during the acceptance test and many programs failed to satisfy it on the first attempt and had to be optimized before they were accepted. All 40 programmers found that writing the program took between 3 and 63 work hours (median: 10 hours, mean: 14 hours) and the resulting program had between 107 and 614 lines (median: 244 lines, mean: 277 lines, excluding comments).
All measurements presented were taken on a Sun Ultra 1 Unix workstation with 192MB main memory running the SunOS 5.5.1 (Solaris 2.5) operating system. The C/C++ programs were compiled with the GNU gcc/g++ compiler version 2.7.2, the Java programs ran under Sun's Java development kit (JDK) 1.2 reference implementation with a just-in-time compiler (JIT). The execution of the JIT is embedded in the execution of the program, hence all data presented includes the time or memory consumed by the JIT compilation.
Let's first investigate the memory requirements of the different programs. Figure 1 shows the amount of memory required by the programs after they have loaded the dictionary and processed 1,000 telephone numbers. The memory size reported includes the size of static and dynamic data structures, the program code and libraries used, and the basic process overhead. For Java programs it also contains the size of the Java Virtual Machine, including the JIT compiler.
The following are some observations:
As shown, the Java programs require substantially more memory on average, but the ratio to the C or C++ programs is not larger than the good/bad ratio.
The total CPU time required by the programs (runtime) consists of two parts; one for loading the dictionary (load time) and one for actually processing the 1,000 inputs (processing time). Figure 2 shows the total runtime.
These are the main observations:
The processing time (and hence the total runtime) reflects that part of the programming task that is not straightforward but which requires substantial design considerations by the programmer. The individual differences are huge compared to the differences between languages, even though the latter differences are quite large as well.
The memory, runtime, and processing time data is summarized in Figure 3. From the error bars we can learn another important lesson: Large performance ratios (like many of those presented here) are unstable even if they are estimated from a substantial number of programs. Consequently, performance comparisons based on only a single program pair should be considered highly dubious unless it is guaranteed both programs are equally well designed and appropriate for the language in which they are written.
The results are actually biased against the Java programs: On average, the Java programmers had only half as much programming experience in Java as the C programmers had in C or the C++ programmers had in C++. On the other hand, no clear relationship between the programmer's level of experience and the runtime or memory efficiency of the resulting program could be found in the data. The work time required for writing the program is also quite similar for the Java group versus the C/C++ group, except for three Java outliers who took over 30 hours.
The length of the resulting programs (excluding comments) is similar in all three groups but the Java programmers inserted a significantly larger amount of comments into their programs than the C++ programmers and in particular the C programmers.
I present three important conclusions from this data:
The programming problem investigated here required a non-trivial algorithm and data structure design. However, the data clearly shows that the importance of an efficient technical infrastructure (such as language/compiler, operating system, or even hardware) is often vastly overestimated compared to the importance of a good program design and an economical programming style.
©1999 ACM 0002-0782/99/1000 $5.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 1999 ACM, Inc.
No entries found