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.

Answer 2

You would probably have to use a realtime JVM so that you can fairly control the garbage collector. It would be unfair if one contender showed a longer runtime just because the garbage collector kicked in during their run.

Answer 3

The only sensible measure is time on some real hardware. Compilers optimize for time, not for count of executed instructions, so counting instructions would defeat many optimizations and make some of them pessimizations. Not only instructions take different amounts of time, but also the delays in execution due to e.g. memory access can vary significantly.

Answer 4

Why not take the VJM one step further and implement a full Linux based VM? The clock cycles should be the same (I guess depending on how the VM was implemented).

For instance you could create a VM based on the 8088 with 256K RAM and 5 meg of diskspace running MINUX. Regardless of "how fast" the code executes, wouldn't the number of CPU cycles remain the same (relative to the 8088) whether 8088 was actually implemented on a Pentium Dual Core or some old Power PC.

Once you've established the virtual hardware, the language choice can become part of the solution for the "fastest algorithm" contest.

Answer 5

You could learn a great deal about what is required for this kind of competition by looking at FastCode, especially with respect to managing different hardware configurations, and benchmark & validation procedures.

Answer 6

I also think that counting the numbers of instructions is a good measure.

The only drawback I see is that if the JVM instructions are too powerful. I don't know the JVC, but it would be possible that there's native support for strings. Appending strings could result in only one instruction. (Don't think so.)

I'd just use plain old time command. This measures execution time, not real time which does eliminate almost all influences by background processes.

Answer 7

For (1) why not just time the execution of the process? Engineer the puzzle so that the actual processing is by far the most dominant aspect of the timing rather than process startup, and time it over several iterations to obtain an average.

For (2) provide sample input, but use alternative input for the live contest.

Answer 8

As to (2), the solution normally used in programming contests (where only correctness counts) is to provide a small, limited number of example inputs, but use a more comprehensive test set on the judging system.

As to (3), the number of JVM instructions used is not necessarily a good measure for speed. Some implementations may take longer or shorter for each instruction; and I haven't even started about jitting and other optimizations.

Answer 9

You could implement an autograder-type testing site where people can submit their code and get an e-mail with their performance results, and perhaps an indication of what the top speed result is. They won't get the input but will get the results of what the official JVM will produce. To prevent abuse, fix the class loader to prevent loading any sort of outgoing connection-type stuff, and limit the performance tester to one submission per address per day, or some other strategy.

Answer 10

You can make a competition with several on-line tools like SPOJ (this one is free and support Java). This way you have one reference machine which measure the programs' execution time.