21

I have two scripts that each compute the factorial of a number. I would like to know which is faster. The time command gives me milliseconds and the result is different from time to time:

piousbox@piousbox-laptop:~/projects/trash$ time ruby fac2.rb
30414093201713378043612608166064768844377641568960512000000000000

real    0m0.089s
user    0m0.052s
sys 0m0.028s
piousbox@piousbox-laptop:~/projects/trash$ time ruby fac1.rb
30414093201713378043612608166064768844377641568960512000000000000

real    0m0.091s
user    0m0.048s
sys 0m0.036s
piousbox@piousbox-laptop:~/projects/trash$ time ruby fac1.rb
30414093201713378043612608166064768844377641568960512000000000000

real    0m0.088s
user    0m0.048s
sys 0m0.040s
piousbox@piousbox-laptop:~/projects/trash$ time ruby fac2.rb
30414093201713378043612608166064768844377641568960512000000000000

real    0m0.088s
user    0m0.048s
sys 0m0.028s
piousbox@piousbox-laptop:~/projects/trash$ time ruby fac1.rb
30414093201713378043612608166064768844377641568960512000000000000

real    0m0.087s
user    0m0.064s
sys 0m0.028s
piousbox@piousbox-laptop:~/projects/trash$ time ruby fac2.rb
30414093201713378043612608166064768844377641568960512000000000000

real    0m0.089s
user    0m0.068s
sys 0m0.016s
piousbox@piousbox-laptop:~/projects/trash$ 

How do I take the average time it take to run the script? I could parse and average out the output of a 100 time's but I imagine there is a better solution?

4

No, your idea of averaging is correct.

Script execution depends on lots of factors, and however it is to be split up between setup time (loading interpreter in memory, setting up, and possibly compiling code to bytecode or machine code) and true execution time.

To better focus on inner execution time, you do the loop in the script itself (i.e. instead of calculating one factorial, you calculate it 100 times within one execution of the script. The script will be setup once, and the inner routine will execute 100 times).

To focus on total time, you execute the script one hundred times and average the results. Ideally, you should separate those executions enough that the system returns in a "reference state" (or a script-unrelated state) every time. For example, the interpreter itself will be cached in memory, so that the very first execution of the script will be appreciably slower than the subsequent ones.

To get a better insight on the algorithm, I think the best way is something like this (on an otherwise idle machine):

  • wrap the algorithm in one single function.
  • in the controlling application:
    • call the function once
    • get the system ("wall clock") time and add 10 (or a reasonable N) seconds
    • enter the loop and start counting iterations
    • after each call to the function, increment the counter
    • if the system time is below the saved time, do another loop
    • get exact N, possibly floating point, from current wall clock time
    • display the counter divided by N: that's the number of iterations/second.

The application only runs once, all setup and priming is done by the first untimed iteration, so this should minimize the overheads (except maybe for the time call).

If the function receives an input, you'd do well to supply it a random sequence of inputs using a PRNG seeded with a fixed value, to ensure both versions of the function being tested receive the same values. This avoids one function performing apparently better due to "lucky numbers" (e.g. I remember a variation of the Hillsort algorithm that performed measurably better if the number of items to be sorted was in the form 2k-1 with small ks).

  • Right, thanks. I noticed that the subsequent calls where getting shorter. I run the loop inside the scripts now, and found that one algorithm is definitely faster than the other. – Victor Piousbox Jun 5 '13 at 7:29
38

You can run iterations of the program in a loop; and divide the total time by the number of iterations:

time for i in {1..10}; do sleep 1; done
real    0m10.052s
user    0m0.005s
sys 0m0.018s
  • 2
    Super simple, love it. I also never saw {1..10} before and am baffled that it works, can't find it in the bash manual. Only sad thing is that you don't know the spread of your results (min and max time). – w00t Oct 12 '14 at 20:22
  • @w00t: man -P 'less +/Brace\ Expansion' bash – user2683246 Sep 10 '15 at 1:24
  • Thanks @user2683246! I then also found it at gnu.org/software/bash/manual/bash.html#Brace-Expansion - nice use of less btw. Now I'm also curious about when this appeared in bash… – w00t Sep 10 '15 at 5:23
  • 1
    Aha, version 3, 10 years after I started using bash :) tldp.org/LDP/abs/html/bashver3.html – w00t Sep 10 '15 at 5:27
  • 2
    If this isn't working for arriving Googlers, it may be because you're not running bash. Try running /bin/bash before this. – Cory Klein Oct 21 '15 at 21:24
10
python -m timeit -n 1 -r 100 -s 'import os' 'os.system("ruby fac1.rb")'

For -n, -r and other options see https://docs.python.org/2/library/timeit.html#command-line-interface

10

there is a tool called multitime that does exactly this: running a command several times, measuring how long it takes (real/user/system with mean, min/max and median time automatically computed)

For instance, for measuring a similar script 100 times:

multitime -q -n 100 "fact1.sh"
===> multitime results
1: -q fact1.sh
            Mean        Std.Dev.    Min         Median      Max
real        0.122       0.032       0.086       0.116       0.171       
user        0.148       0.044       0.096       0.137       0.223       
sys         0.023       0.019       0.000       0.014       0.061 
8

This is old but it came up so high on google when I was looking for a command I used previously but couldn't find. Anyways, my preferred way of doing this is:

perf stat -r 10 -B sleep 1

This gives quite a bit of details including average execution time right at the end:

1.002248382 seconds time elapsed                   ( +-  0.01% )

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.