What is the best way to actually time an answer for fastest-code challenges

Question

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 fastest-code challenges?

Answer 1

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

Answer 2

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.

Answer 3

I recently posted a fastest-code 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