comparing fastest code

Question

To compare solutions on performance, we should form a kind of template, what to specify or how to specify the question.

I realized, when trying to solve fast line drawing algorithm, that it is not clearly specified:

How are the results compared? What is it, what shall be compared? How fast a line is drawn, but we know, that because of caches and cache-size and cache-misses, a solution which is fast with 10 000 elements might be slow with ten millions.

The size of source (code-golf) can be compared more easily², but if I look at a bunch of c/python/ruby-code I can't estimate how many lines it might draw per second or minute. Not roughly, and not even for languages which I use on a daily basis.

Possible approaches:

• A) Let chaos rule. Every question shall choose its own way.

• B) Let every answer specify machine characteristics and use its own, private timing policy.

  • User A: Pentium III 800 Mhz, 1000 runs / 0.4 s
  • User B: 3 dual-cores @ 3Ghz, 1s: 23 786 000 runs

• C) Let the quizz master fix the settings, for a minimal comparision, and the users have to specify their machine:

  • How many solutions in 30s
  • How many time for 1 Mio. solutions

• D) Let the quizz master fix the settings, for a minimal comparision, and the users have to provide ready-to-run code/applications, not just functions/snippets.

  • Full source code A.cc, B.Java, C.scala
  • How to run it:

  g++ A.cc -lm -o A && time A
javac B.java; java B # internal timing
  scalac C.scala && time scala C 1000000 # specify problem size

• E) Let the users use IDEONE or something similar, to have it executed on the same machine. Specify number of solutions or time to run. Drawback: Not every language is available.

I'm not sure how to handle the problem best, and I know, that most users go online, without discussing their riddle in chat - maybe in a unjustified fear, that somebody else will copy it? However; if we have something in the faq, or it is easy to find on meta, we can often provide links 'how to ask performance tasks' so some people will use it from the beginning.

If you worked on your solution and meanwhile the asker decides, how to compare the resulst, you might have to do doubled work.

I think we should look for a ruleset which will fit 90% of the performance questions, and be fine for as much languages as possible. It should be short and easy to explain.

Pleas argue for one of the ideas A-E, argue for a modification like B' or C'', or introduce your solution F-Z.

---

²) Don't discuss it here: Can C/C++-Users and the like substract their main-boilerplate or not - this might be argued about, but we can at least estimate, what the substraction or addition of a main method would mean in terms of character costs. Or include-files - we know, we know.

Answer 1

I'd go with option F. Here are the rules for option F:

Requirements:

1. Askers MUST provide one or more explicit input test cases to be optimized.
   
   • For example, if the input to the program is x, the question could be specified to optimize for inputs x=5, x=50, and x=500.
2. Each code must compute the average "weight" of their code across all input cases.
   
   • The weight is determined by how many operations occur throughout the course of running of the program with the specified inputs.
   • We'll have to nail down a fair definition of what constitutes an operation in all competing languages.
   • We'll probably have to write a program that produces an average score given the input conditions, the language-type, and the code.

A simple relatively-simple JavaScript example:

Test input cases: x=5, x=50, and x=500

Code:

for(i=0; i<x; i++){
    f(x);
}

function f(x){
    y=x;
}

Scoring:

1. i=0

   • Executed once per loop: multiplier = 1, 1, 1
   • i: 1 point (to use the variable)
   • =: 1point (to use an operator)
   • 0: 1point (to use a number)
   • Score: 3, 3, 3 (same score for each of the 3 runs)

2. i<x

   • Executed once per iteration plus 1 time (when it evaluates to false): multiplier = 6, 51, 501
   • i<x: 3 points (by reasoning in 1)
   • Score: 18, 153, 1503

3. i++

   • Executed once per iteration: multiplier = 5, 50, 500
   • i++: 3 points
   • Score: 15, 150, 1500
4. function f(x){..}
   • function f(x): 0 points (function calls and parameters only count when called)
   • y=x: 3 points
   • function weight: 3 points (could also have been an equation if there was a loop based on x)
   • Score: 0 points (Only figured in when the function is called)
5. f(x)
   • Executed once per iteration: multiplier = 5, 50, 500
   • f: 4 points (1 point for the function call plus 3 points for the function weight from step 4)
   • (x): 1 point (cost of passing the variable into the function)
   • Score: 25, 250, 2500
6. Final Score: 2041 Points = 6123/3 = (61+556+5506)/3

Conclusion

This would be obviously be very difficult to score by hand. However, we could make a program that scores each competing language. This would take a good amount of effort, but with teamwork we could do it. Also, as opposed to code-golf I think this would actually be a valuable metric outside of just gaming, so it might just be a worthwhile venture...

Answer 2

In a distinctive, but similar way to Briguy37's suggestion, for some puzzles, this approach might be sufficient, if the main goal is to find a fine Big-O-algorithm, independent of the speed of the language, machine, compiler/interpreter/vm:

Example:

Say you want to sort some collection in place.

• any modification can only be done via a swap method, which has a build-in swap-counter named swaps.
• any comparision has to be done with a lessThan-method with an equivalent counter named comps
• there is a arbitrary cost function, which weights both counters: cost = 2 * comps + 3 * swaps
• The winning criteria would be to minimize the costs.

Code original:

public static int [] bubbleSorta (int [] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i + 1; j < a.length; j++) {
            if (a[i] > a[j]) {
                int tmp = a[i];
                a[i] = a[j];
                a[j] = tmp;
            }
        }
    }
    return a;
}

replace it with

int cmps = 0;

public boolean gt (int a, int b) 
{
    ++cmps;
    return a > b;   
}

int swaps = 0;

public void swap (int i, int j, int [] arr) {
    ++swaps;
    int tmp = arr [i];
    arr [i] = arr [j];
    arr [j] = tmp;
}

public int [] bubblesorta (int [] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (gt (arr [i], arr [j])) {
                swap (i, j, arr);
            }
        }
    }
    return arr;
}

For iterating, the i < arr.length could be kept, instead of forcing the user to use gt (arr.length, i), but of course this is up to to you, the master of the question.

The challenge is of course not, to replace gt or swap with something else, to circumvent the counter, but to minimize the calls of such methods, to develop a different algorithm.

Of course it must be specified how to handle methods in common libraries, which perform swap or gt inside. And maybe the consequences aren't foreseeable for languages of very different paradigm.

Me, for instance, I don't know, whether the above example can be ported to the CodeGolf-Language or to APL.

Answer 3

I would suggest making the judgement be the minimum number of assembly/JVM commands actually ran to solve it (might be harder to judge, but I'm pretty sure that there has to be a tool out there to judge that). Speed can easily be judged from measuring that.