8
\$\begingroup\$

Is there a "best" way to do this? I imagine one could write a bash script that would print the time, execute the program, and then print the time again, but perhaps there are pitfalls with this.

Is there a consensus on how times should be measured for challenges?

\$\endgroup\$
  • 1
    \$\begingroup\$ Better than the Bash script would be to just use the time command. For example, the shell command time python3 script.py executes the script and prints the elapsed real and CPU time after is finishes. Also, if there's a lot of output, you should pipe to a file, and if there's a lot of output, to /dev/null. \$\endgroup\$ – Dennis Feb 23 '16 at 21:35
  • 3
    \$\begingroup\$ I've always been a fan of the script timing itself, as it prevents timing on input/output processing, and times the algorithm itself. \$\endgroup\$ – Nathan Merrill Feb 23 '16 at 21:38
3
\$\begingroup\$

I doubt there could be a best way, but the following could help consistency:

  • Use the time command, as @Dennis suggested
  • Execute the programs with as little background memory and CPU usage as possible (you could use a minimal linux distro, if you wanted the least noise).
  • Time each execution several times and average, to reduce noise
  • If the execution time is fast enough, you could consider counting cpu cycles with valgrind. The biggest downside is that, in my experience, it's several times slower.
  • Instead of requiring that the full result be printed, consider outputting an abbreviated result or return 0 if it passes the given test cases (i.e. check inside the answer), to prevent differences due to IO
  • If an answer is compiled, use options specified by the answer
  • Consider normalizing the times or fitting them to a curve and comparing coefficients
  • If the answers take IO input, you could write a script to generate input and time execution for more data points

This boils down to the need for a script that uses more or less simple statistical methods and input generation to get best times. I would be happy to write a simple version in Haskell or Python if given an example challenge and several languages to support (It could also check cpu/memory load and return an error if out of acceptable ranges).

\$\endgroup\$
  • \$\begingroup\$ Python has a builtin timing module: timeit. \$\endgroup\$ – Mego Feb 23 '16 at 23:29
  • \$\begingroup\$ @Mego I believe that's best fit for microbenchmarks? Still would need to call bash, extract averages, etc. \$\endgroup\$ – Michael Klein Feb 23 '16 at 23:57
  • \$\begingroup\$ If you ran all submissions through subprocesses, the overhead for each would be roughly equivalent. \$\endgroup\$ – Mego Feb 24 '16 at 0:53
  • \$\begingroup\$ @Mego Ok. That's assuming little background differences? \$\endgroup\$ – Michael Klein Feb 24 '16 at 0:57
  • \$\begingroup\$ Yep, since there's not really a way to get exactly the same conditions each time. \$\endgroup\$ – Mego Feb 24 '16 at 1:01
  • \$\begingroup\$ @Mego Just for fun, what about a unikernel in a profiling emulator? \$\endgroup\$ – Michael Klein Feb 24 '16 at 1:03
  • \$\begingroup\$ Depending on the approaches permitted by the challenge, you may want to record the minimum time after several executions, rather than the mean time (eliminating background interference, rather than averaging it). This may give a better idea of the real time taken for a deterministic algorithm. For a stochastic algorithm you may be better with a mean, since the minimum could reflect luck rather than a lack of background interference. Ideally the challenge should specify clearly whether solutions will be measured on best time, worst time or some kind of average. \$\endgroup\$ – trichoplax Feb 25 '16 at 12:09
  • 1
    \$\begingroup\$ With respect to the point about differences due to I/O, running once to verify correctness and then a second time redirecting stdout to /dev/null for timing should be fairly effective at eliminating those differences which are actually due to I/O without eliminating differences which are due to formatting the output to meet the spec. \$\endgroup\$ – Peter Taylor Mar 2 '16 at 10:32
  • \$\begingroup\$ I think this fails to take into account languages like java that have a warm up time while the JIT is compiling, and therefore eliminating some languages from competing. In addition using the time command (as far as I know) doesn't take into account the startup time of a runtime. \$\endgroup\$ – J Atkin Mar 5 '16 at 17:24
2
\$\begingroup\$

I recently posted a challenge in which I was responsible for timing the entries. The method I used (based off comments/answers from this post as well as chat messages):

  • use the time function in bash.

  • for better results, if the entry is fast (<1s), it is worthwhile to time a loop that executes the entry many (100s/1000s) times and then divide the result by the number of times it was looped.

  • the time command outputs to stderr. To send this to a file, use 2 >> <path/to/file> or exec 2 >> <path/to/file> in a script.

  • close all other applications while timing.

  • After verifying test cases, send output (stdout) to /dev/null with some version of 2>/dev/null

\$\endgroup\$
  • \$\begingroup\$ Point 2: I'd rather discourage [fastest-code] for things that take less than a second. Every now and then you get a freakishly fast answer (glances at Dennis), but for the most part this shouldn't be a big issue imo. \$\endgroup\$ – Geobits Mar 2 '16 at 3:32
  • \$\begingroup\$ @IGoBest I agree. If I had known how fast his would be, I would have added more test cases to bring it up. If more answers had been that fast, I definitely would have added more \$\endgroup\$ – Liam Mar 2 '16 at 3:33
  • \$\begingroup\$ Also: if the task is short, start-up times for interpreter, virtual machines, run time systems, etc. become more and more important. Starting up a VM a hundred times can cost significant time. Sure, that's part of a language, so maybe you actually want to include it. Be aware of what you want to time. \$\endgroup\$ – nimi Mar 2 '16 at 17:12
2
\$\begingroup\$

Ideally, the challenge and its scoring cases should be designed so that executing each scoring case takes a significant amount of time. If that is the case and the desired output is sufficiently short, simply using the time command should do the trick.

Every now and then, that isn't possible. If the solutions that have been posted are a lot faster than anticipated, there are only two possible ways (I can think of) that may still provide usable timings:

  1. Change the scoring cases. That's not always possible without invalidating all answers.

    For example, the input may have been guaranteed to fit in a signed 32-bit integer. But even then, using test cases close to the maximum input should produce more reliable results.

  2. Time the submissions from within.

    Simply timing everything n times for a large value of n may reduce the variance, but if starting a process takes more or less the same time as the actual computation, it won't be enough to compare submissions.

For example, let us take my answer to your latest challenge.

$ a=(1907000000 1337000000 1240000000 660000000 99820000 40550000 24850000 41500)
$ for j in ${a[@]}; do time ./pi2 $j; done 2>&1 | grep real
real    0m0.011s
real    0m0.008s
real    0m0.007s
real    0m0.005s
real    0m0.002s
real    0m0.002s
real    0m0.002s
real    0m0.001s
$ time /bin/true

real    0m0.001s
user    0m0.000s
sys     0m0.001s

Executing the last scoring case is as fast as literally doing nothing. In fact, the last four test cases actively harm the timing process, as their run times are entirely dominated by process creation.

Let us compare running each scoring case 1000 times with running time (the external command, not the shell keyword) an equal amount of times.

$ time for i in {1..1000}; do for j in ${a[@]}; do ./pi $j; done; done > /dev/null

real    0m21.138s
user    0m14.451s
sys     0m2.945s
$ time for i in {1..1000}; do for j in ${a[@]}; do /bin/true $j; done; done >&-

real    0m7.141s
user    0m0.507s
sys     0m1.875s
$ time for i in {1..1000}; do for j in ${a[@]}; do true $j; done; done >&-

real    0m0.084s
user    0m0.088s
sys     0m0.000s

Roughly one third of the measured wall time is spent creating processes. This exhibits a lot of variance. In fact, user + system time only account for 2.382 second of the elapsed 7.141 seconds. The remaining time, the CPU core is idle, waiting for whatever resources need to be ready to create a process.

For comparison, I timed my submission from within the program and computed the average with awk.

$ for i in {1..1000}; do for j in ${a[@]}; do ./pisave $j; done; done > times
$ awk '{ sum += $2; } END { print sum / 1e9; }' times
14.1176

This dropped the average execution time of the combined scoring cases from 0.021 to 0.014 seconds, which is the actual time the CPU spends executing the code.

In addition, the variance is a lot lower.

\$\endgroup\$
  • \$\begingroup\$ I don't necessarily support the idea that any time spent doing initialization, executing global constructors etc. should not be counted as part of the running time. \$\endgroup\$ – feersum Mar 6 '16 at 21:13
  • \$\begingroup\$ Neither do I, but if process creation takes one third of the total run time (with a lot of variance), I think it's the lesser of two evils. \$\endgroup\$ – Dennis Mar 6 '16 at 21:15
  • 2
    \$\begingroup\$ The moral of the story here is "plan ahead better if you're writing a fastest code challenge" \$\endgroup\$ – Liam Mar 6 '16 at 21:17

You must log in to answer this question.

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