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.
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.
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.
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
Table 2: Java(TM) 2 Runtime Environment, Standard Edition 1.5.0_08-b03 Results