Software - Articles

Results for Ubuntu Linux 2.6.17-10-generic

Tim Morrow sent along the following results for Linux. Platform details are as follows:

Linux: Ubuntu Linux 2.6.17-10-generic
Memory: 2GB RAM
Processor: Intel Core Duo 1.83Ghz

Take a look at the results below. There are several interesting points of note in the data.

  1. The "hardcore" iterative method on Linux actually outperforms recursion. This is the behavior I had expected from the beginning, but Sun must have done some insane optimization on the Windows platform, so that even the hardcore implementation couldn't catch the fast recursive one.
  2. The "hardcore" iterative method performs better by ~20% on Java 5 as compared with Java 6. This is a bit of a shocker, and has been reported to Sun.
  3. Interestingly, memory usage under Linux is quite a bit higher than under Windows. As an armchair theorist, the most likely explanation I see is that the javac compiler or java runtime on Widows XP is smart enough to eliminate certain local variables whereas the Linux counterpart is not. For example, in the two lines of code below:
    TreeNode node = toExamine.pop();
    ArrayList children = node.getChildren();
    Since the only reference to "node" in the method is on the subsequent line, a clever compiler or runtime could eliminate the local variable altogether, instead producing code like the following:
    ArrayList children = toExamine.pop();

Table 1: Java(TM) SE Runtime Environment 1.6.0-b105 Results
Solution Time (ns) Heap (bytes)
Elegant Recursion 10,130,420 2,517,024
Fast Recursion 6,696,000 0
Elegant Iterative 17,440,080 2,516,722
Fast Iterative 15,404,880 251,673
Hardcore Iterative 7,029,040 252,064
Table 2: Java(TM) 2 Runtime Environment, Standard Edition 1.5.0_08-b03 Results
Solution Time (ns) Heap (bytes)
Elegant Recursion 9,090,040 2,514,981
Fast Recursion 6,325,320 0
Elegant Iterative 33,069,820 2,518,997
Fast Iterative 34,147,560 251,672
Hardcore Iterative 5,717,600 252,064