8
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ This is precisely my problem with "fastest" problems, but I don't know how to resolve it. I'm looking forward to other people's thoughts. \$\endgroup\$ Aug 14, 2011 at 2:31
  • \$\begingroup\$ One thing you didn't consider... algorithmic optimization. While rare, I seem to recall at least one question where posters included a Big-O analysis of the individual answers. This could prove problematic however because not all posters have a CS background. \$\endgroup\$
    – arrdem
    Aug 16, 2011 at 0:14

3 Answers 3

2
\$\begingroup\$

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...

\$\endgroup\$
5
  • \$\begingroup\$ The only way to really score this automatically requires writing an interpreter for each language. Not gonna happen. \$\endgroup\$ Aug 26, 2011 at 8:45
  • \$\begingroup\$ @Peter Taylor: Yup :) \$\endgroup\$
    – Briguy37
    Aug 26, 2011 at 13:05
  • \$\begingroup\$ I'm not sure whether I understand the idea. Maybe it is similar to this idea: For a sorting-algorithm, don't use the normal < operation, but a selfmade boolean lt (a, b) method, which protocolls, how often it was called; analog for swap function. Minimize 3*swpCount + ltCount for sorting 500 random elements. \$\endgroup\$ Aug 26, 2011 at 16:30
  • \$\begingroup\$ @user unknown: Yes, that would be one method of doing it. The general goal is to figure out the total sum of the weight of each operation times the number of times that operation was performed for each input case, and average that across all input cases. \$\endgroup\$
    – Briguy37
    Aug 26, 2011 at 18:49
  • \$\begingroup\$ Ah - you like to figure it out. My idea would be, to define it. Because how do you figure it out? For every language? For a rubber-stamp language? \$\endgroup\$ Jan 12, 2012 at 1:35
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The challenge can't be ported to GolfScript, because "in place" doesn't fit its paradigm. \$\endgroup\$ Jan 12, 2012 at 22:45
-1
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ There have been very few times in the history of computing when this would be a working solution. As it is different instructions run in different time under different conditions, and that is even before we talk about different architectures. \$\endgroup\$ Feb 8, 2014 at 3:08
  • \$\begingroup\$ @dmckee True. I initially was going to say clock ticks, but that would potentially run into issues. In terms of JVM code, it would be rather easy to judge using that method. On the other hand, anything else would be hard to judge under any circumstances. \$\endgroup\$
    – Claudia
    Feb 8, 2014 at 3:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .