One of the things I love about dynamic compilation is that it frees me from having to think about the minute details of how some piece of code will be compiled. In fact, the effects of hand-written ‘optimisations’ are less predictable than one might expect!
Take this simple example: which one do you prefer between these two?
for (i = 0; i < array.length; ++i)for (i = 0, len = array.length; i < len; ++i)
I've been guilty, for a long time, of picking the second one, on the premise that if the length operator didn't have to be called all the time, it'd be faster.
That's the biggest pack of lies ever.
The punchline is that both are about the same in terms of performance, counter-intuitive as that may be. I wrote a little test program, which I tested on my system (Java SE 6, update 10, 64-bit server VM). All it does is print all the command-line arguments to System.out, a million times.
My code tests this loop under a number of different execution scenarios: checking the array boundary the ‘naive’ way (i.e., checking the array length at each run); hoisting the array length and checking that; using for-each (aka extended for loops); as well as hoisting System.out for each of those test types. There's also a ‘super hoist’ mode that does all the above hoisting, as well as doing the million-run loop by hand rather than using a range iterator (see below).
To minimise other system effects, I wrote a null output stream (which acts like /dev/null, without actually opening any device), a range iterator (that always returns null, rather than the iteration count, to avoid boxing overhead), and a no-op loop (just to see how much overhead the loop itself is creating). To minimise warm-up effect, the whole suite is run three times.
Here are some test results for a run with 25 empty arguments. I picked empty arguments to minimise any string-copying overhead that may exist; after all, the point here is to test the various array looping techniques, not string copying!
| Loop type | Run 1 | Run 2 | Run 3 |
|---|---|---|---|
| Naive | 11.338 | 10.455 | 10.460 |
| Length-hoisted | 11.786 | 11.519 | 11.299 |
| For-each | 11.521 | 11.517 | 11.141 |
| Out-hoisted naive | 11.419 | 11.465 | 11.184 |
| Out-hoisted length-hoisted | 11.514 | 11.475 | 11.168 |
| Out-hoisted for-each | 11.730 | 11.519 | 11.512 |
| ‘Super hoist’ | 11.614 | 11.539 | 12.045 |
If anything could be considered ‘faster’, I'd have to say it's the naive loop! However, the differences are too minute to be meaningful.
Code listing:
import java.io.OutputStream;
import java.io.PrintStream;
import java.util.Iterator;
import java.util.NoSuchElementException;
public class PrintArgs {
static final int RUNS = 1000000;
public static void main(String[] args) {
System.setOut(new PrintStream(new NullOutputStream()));
runSuite(args);
runSuite(args);
runSuite(args);
}
private static void runSuite(String[] args) {
time(new NoopLoop(args));
time(new NaiveLoop(args));
time(new NoopLoop(args));
time(new LengthHoistedLoop(args));
time(new NoopLoop(args));
time(new ForEachLoop(args));
time(new NoopLoop(args));
time(new OHNaiveLoop(args));
time(new NoopLoop(args));
time(new OHLengthHoistedLoop(args));
time(new NoopLoop(args));
time(new OHForEachLoop(args));
time(new NoopLoop(args));
time(new SuperHoistLoop(args));
System.err.println();
}
private static void time(Runnable runnable) {
long t0 = System.currentTimeMillis();
runnable.run();
long t1 = System.currentTimeMillis();
System.err.printf("%s: %d ms%n", runnable.getClass().getName(),
t1 - t0);
}
static class NullOutputStream extends OutputStream {
public NullOutputStream() {}
@Override
public void write(int b) {}
@Override
public void write(byte[] b) {}
@Override
public void write(byte[] b, int off, int len) {}
}
static class Range implements Iterable<Void> {
private final int start, end;
public Range(int start, int end) {
this.start = start;
this.end = end;
}
public Range(int end) {
this(0, end);
}
@Override
public Iterator<Void> iterator() {
return new RangeIterator(start, end);
}
}
static class RangeIterator implements Iterator<Void> {
private int start;
private final int end;
public RangeIterator(int start, int end) {
if (start > end)
throw new IllegalArgumentException();
this.start = start;
this.end = end;
}
@Override
public boolean hasNext() {
return start != end;
}
@Override
public Void next() {
if (start == end)
throw new NoSuchElementException();
++start;
return null;
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
}
static abstract class MainRunnable implements Runnable {
private final String[] args;
protected MainRunnable(String[] args) {
this.args = args;
}
@Override
public void run() {
for (Object _ : new Range(RUNS))
main(args);
}
protected abstract void main(String[] args);
}
static class NoopLoop extends MainRunnable {
public NoopLoop(String[] args) {
super(args);
}
@Override
public void main(String[] args) {}
}
static class NaiveLoop extends MainRunnable {
public NaiveLoop(String[] args) {
super(args);
}
@Override
public void main(String[] args) {
for (int i = 0; i < args.length; ++i)
System.out.println(args[i]);
}
}
static class LengthHoistedLoop extends MainRunnable {
public LengthHoistedLoop(String[] args) {
super(args);
}
@Override
public void main(String[] args) {
int len = args.length;
for (int i = 0; i < len; ++i)
System.out.println(args[i]);
}
}
static class ForEachLoop extends MainRunnable {
public ForEachLoop(String[] args) {
super(args);
}
@Override
public void main(String[] args) {
for (String arg : args)
System.out.println(arg);
}
}
static class OHNaiveLoop extends MainRunnable {
private final PrintStream out;
public OHNaiveLoop(String[] args) {
super(args);
out = System.out;
}
@Override
public void main(String[] args) {
for (int i = 0; i < args.length; ++i)
out.println(args[i]);
}
}
static class OHLengthHoistedLoop extends MainRunnable {
private final PrintStream out;
public OHLengthHoistedLoop(String[] args) {
super(args);
out = System.out;
}
@Override
public void main(String[] args) {
int len = args.length;
for (int i = 0; i < len; ++i)
out.println(args[i]);
}
}
static class OHForEachLoop extends MainRunnable {
private final PrintStream out;
public OHForEachLoop(String[] args) {
super(args);
out = System.out;
}
@Override
public void main(String[] args) {
for (String arg : args)
out.println(arg);
}
}
static class SuperHoistLoop implements Runnable {
private final String[] args;
public SuperHoistLoop(String[] args) {
this.args = args;
}
@Override
public void run() {
PrintStream out = System.out;
for (int i = 0; i < RUNS; ++i) {
for (String arg : args)
out.println(arg);
}
}
}
}
No comments:
Post a Comment