25/11/2008

In JIT we trust, part 2

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?

  1. for (i = 0; i < array.length; ++i)
  2. 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!

Timing results (all times in seconds)
Loop typeRun 1Run 2Run 3
Naive11.33810.45510.460
Length-hoisted11.78611.51911.299
For-each11.52111.51711.141
Out-hoisted naive11.41911.46511.184
Out-hoisted length-hoisted11.51411.47511.168
Out-hoisted for-each11.73011.51911.512
‘Super hoist’11.61411.53912.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: