Running a fastest-algorithm competition

Question

I'd like to run competitions like code golf competitions, but the winner would have the fastest algorithm, not the smallest code.

• One fair way to measure speed of an algorithm is to use a neutral virtual machine, like Java's JVM. Is there an easy way to know the total number of JVM instructions executed? (If the entry uses multiple threads, then the total number of JVM instructions would be summed across all threads.)

For example, the code

public class simple {
    public static int main(String argc[]) {
        int i;

        i = 3;
        while (i > 0) {
            i--;
        }

    return 0;
    }
}

generates the JVM code

0:  iconst_3
1:  istore_1
2:  iload_1
3:  ifle    12
6:  iinc    1, -1
9:  goto    2
12: iconst_0
13: ireturn

and it takes (if I've counted correctly) 18 JVM instructions to run.

• I would like people to be able to run their entries at home, and to see what the judges would see. Obviously, if I give the input to the program, the fastest solution would be to spit out the memoized, pre-computed answers. Is there any way to objectively both let people run programs at home and not see memoized answers?

• What other issues prevent an informal "fastest code competition" from happening?

Thanks!

Answer 1

The only fair comparison is the shortest completion time on a common piece of hardware. The time to complete a program is entirely hardware dependent otherwise what would be the point of spending money on more power machines?

The closest you can get to reproducible results is report a relative speed, e.g. provide a sample program and report in term of the users program running in say 50% of the time. A program which is twice as fast on one PC will likely to be twice as fast on another.

At uni, we would submit assignments which would run against "secret" inputs, however we could submit more than once to correct errors. My first submission didn't work at all but would log all the inputs. ;)

EDIT: A longer answer.

Consider the following program

public class FibMain {
    public static void main(String... args) {
        {
            long start = System.nanoTime();
            System.out.println(iteration_fib(Integer.parseInt(args[0])));
            long time = System.nanoTime() - start;
            System.out.printf("Iteration took %,d us%n", time /  1000);
        }
        {
            long start = System.nanoTime();
            System.out.println(recursive_fib(Integer.parseInt(args[0])));
            long time = System.nanoTime() - start;
            System.out.printf("Recursion took %,d us%n", time /  1000);
        }
    }

    public static long iteration_fib(int n) {
        long t1 = 1;
        long t2 = 1;
        while (n-- > 2) {
            long t = t2;
            t2 += t1;
            t1 = t;
        }
        return t2;
    }

    public static long recursive_fib(int n) {
        if (n <= 2) return 1;
        return recursive_fib(n - 1) + recursive_fib(n - 2);
    }
}

If you look at the generated byte code with javap -c you see

public static long iteration_fib(int);
  Code:
   0:   lconst_1
   1:   lstore_1
   2:   lconst_1
   3:   lstore_3
   4:   iload_0
   5:   iinc    0, -1
   8:   iconst_2
   9:   if_icmple       25
   12:  lload_3
   13:  lstore  5
   15:  lload_3
   16:  lload_1
   17:  ladd
   18:  lstore_3
   19:  lload   5
   21:  lstore_1
   22:  goto    4
   25:  lload_3
   26:  lreturn

public static long recursive_fib(int);
  Code:
   0:   iload_0
   1:   iconst_2
   2:   if_icmpgt       7
   5:   lconst_1
   6:   lreturn
   7:   iload_0
   8:   iconst_1
   9:   isub
   10:  invokestatic    #13; //Method recursive_fib:(I)J
   13:  iload_0
   14:  iconst_2
   15:  isub
   16:  invokestatic    #13; //Method recursive_fib:(I)J
   19:  ladd
   20:  lreturn

So the first example is longer that the second so you might suspect the first one takes longer. However, you would be incorrect for cases where 'n' is an interesting size.

I ran FibMain 44 on my machine and got the following result.

701408733
Iteration took 495 us
701408733
Recursion took 19,174,036 us

This is because the time taken to perform iteration is proportional to n (in this case 44) ad it grows linearly however the time taken for recursion is proportional to the result (in this case 701408733) and that grows exponentially.

If you try 50 as input the first completes in a blink, the second takes so long I got bored of waiting.