views:

533

answers:

9

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!

+1  A: 

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.

Paul Dixon
1. People running on different machines, or using different javas, will see different results. What's fastest on one machine won't be the same on another.2. I'd like the competition to be like code golf: everyone can see, on their own machine, what their speed is. That's not possible if we hide the live contest input.
Chip Uni
Why use average and not minimum?
notnoop
@Chip: people will still be able to compare the relative performance of other entries, which is presumably what you want. Then people can "self judge" their own performance. Ultimately, you need judge the times of each entry on the same machine, as just counting the JVM instructions isn't accurate - not all instructions are equal.
Paul Dixon
I would suggest the average rather than the minimum as using a minimum gives the time which managed to obtain the best possible window of opportunity among any other processes running on the machine. By averaging out several runs, it should level the playing field.
Paul Dixon
@Paul -- to make a competition fair, at some point, we need to specify what we're measuring. Clock-time is one measurement. But it's very dependent on the underlying hardware and the choice of virtual machine. Though not all JVM instructions are equal, they make a hardware-independent, machine-independent way to measure how much work an algorithm did; that's why I prefer them. But thank you so much for your thoughts!
Chip Uni
@Chip: That's fine, and as long as contestants are aware they win by using fewest instructions. But it is entirely possible the fastest entry will not win. For example, consider an entry which makes inefficient use of the filesystem, or one which eats so much memory that paging effects come into play. Such an entry might use fewer instructions, but could be outperformed by a significant margin with an entry that used more instructions.
Paul Dixon
Chip: use a different internal input to prevent output forgery, and just run the submitted code through the internal and sample outputs. Then you can show in the scoreboard both times, so teams could compare their times to the other teams and compare their home times with the server times.
Spidey
+1  A: 

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.

Thomas
What I'm trying to avoid is complaints that "Even though the server says your code is faster, my code runs faster on XXXXX than yours!" I understand, and accept, that JVM instructions is an artificial benchmark.
Chip Uni
Complaints about programs running faster on local computers are generally missing the point of the contest. The only case where this impacts performance is if the processor has a different feature set (e.g. handles or doesn't handle 64-bit instructions), and that's not an issue if you mention it upfront. Besides, programmers should expect variations in target hardware as well.
Raymond Martineau
A: 

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.

Jim Zajkowski
+5  A: 

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.

Peter Lawrey
Are you saying that fewest number of JVM instructions is not a fair comparison? And the point of the competition would be to find good, general algorithms -- not to emphasize a particular implementation of the JVM. I strongly suppose that relative clock speed would depend on the machine and JVM implementation.
Chip Uni
What is fair? Some algorithms are more cache-friendly than others. Those will have lower running time than algorithms that perform lots of random accesses.
Yuliy
Good, general algorithms need to deal with cache. If you want to make a practical implementation run fast, you need to pay attention to cache coherency. There are even theoretical metrics (comparable to O() notation) which determine how effectively an algorithm can use the cache (albeit in simplified, theoretical form).
comingstorm
You can use fewer instruction by making more use of library calls, often at the expense of performance. i.e. a smaller program can be slower, not faster!
Peter Lawrey
Aha. NOW I'm understanding what people are saying wrong. I'm going to edit my question once more. Thank you!
Chip Uni
So you see that size has little to do with fastest. You should be clear about which one you mean.
Peter Lawrey
@Peter Lawrey - like your hack with the secret answers :-)
Ridcully
Try this recursive version: public static long recursive_fib(int n, long acc1, long acc2) { if (n < 2) { return acc2; } else { return recursive_fib(n - 1, acc2, acc1 + acc2); } } // kidding!
Juliet
+1  A: 

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.

crowne
A good suggestion, if there's no way to count the number of JVM instructions that were executed.
Chip Uni
A: 

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.

Robert Obryk
That's what everyone else seems to think, too. Thanks!
Chip Uni
A: 

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.

cjrh
Thank you for the suggestion!
Chip Uni
The FastCode project was truly awesome.
cjrh
A: 

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.

ChronoFish
Thank you for the suggestion. (I still think that counting the number of JVM instructions executed makes for a good competition, but everyone else seems to disagree...)
Chip Uni
Well it is *Your* competition! Maybe make it a "Fewest JVM Instructions Algorithm" contest - as long as you specify what makes it "the best" the contestants can either choose to play by the (your) rules or pack up and go home!Good luck!
ChronoFish
A: 

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.

Georg
Glad that you agree that counting the number of instructions seems like a good idea. And even if JVM instructions are very powerful, they're equally powerful for everyone. Do you know of a simple way to count the number of JVM instructions a program takes to run?
Chip Uni
@Chip Uni: No, I've never really used Java before. If the JVM instructions are that powerful, users who understand the JVM have an advantage. This would lead to people optimizing their code specially for the JVM.
Georg