# How to compare runtimes of two algorithms in a reproducible way

I am solving one relatively simple problem with two different algorithm: one which uses brute force while the other is optimized. For a variety of reasons I actually cannot show the codes here but I do not think this is of importance.

Here is how I am currently comparing the two algorithms (I use Fortran):

CALL CPU_TIME(t1)
DO pp = 1,10000
**Algorithm_1**
END DO
CALL CPU_TIME(t2)

CALL CPU_TIME(t3)
DO pp = 1,10000
**Algorithm_2**
END DO
CALL CPU_TIME(t4)

PRINT*, "Algorithm 1 time = ", (t2-t1)/(pp-1)
PRINT*, "Algorithm 2 time = ", (t4-t3)/(pp-1)


This gives me a rough idea of the speed up factor. But my problem is that it only gives a rough idea.

For one case, the average speedup factor is about 460. Sometimes I get 534, other times 380. And that is obtained by running the same executable multiple times in a row. This is the most extreme case; I usually get a range of $\pm$ 5 %, which still bothers me.

Is there a robust way to compare two algorithms? Or are discrepancies in the results expected?

To make more robust comparisons (on linux), you can :

1) On Intel CPUs the turbo overclocks your CPU. This is controlled by the temperature of the CPU, so it can behave differently from one run to the other. On Linux, you can block the frequency of the CPU as follows. For example, for 2.4GHz:

  echo 1 > /sys/module/processor/parameters/ignore_ppc

for x in /sys/devices/system/cpu/cpu[0-3]/cpufreq/;do
echo 2400000 > \$x/scaling_max_freq
done


2) As long as there is free memory, linux caches your last I/Os. If your program needs to allocate a lot of memory, the first allocation will take time as it will empty the I/O caches to provide some free memory. To make your allocation times more predictable, empty your I/O caches

echo 3 > /proc/sys/vm/drop_caches


3) Your processes can migrate from one CPU core to another. At each migration, you lose the L1 and L2 caches, so you will experience more cache misses. Also, the migration takes some time. To remove this overhead, bind your process to CPU cores:

export OMP_PROC_BIND=true


4) Before measuring the CPU time, make a little bit of warm up

5) Maybe that algorithm 1 runs faster when it is preceded by algorithm 2, or vice versa. To avoid such a bias, you can interleave measurements of algorithms 1 and 2.

  ! DO ALL POSSIBLE INITIALIZATION HERE

NREP=10000
NLOOP=100

time1 = 0.d0
time2 = 0.d0

DO k=1,NLOOP

! WARM UP
DO pp = 1,NREP/10
**Algorithm_1**
END DO

!MEASURE 1
CALL CPU_TIME(t1)
DO pp = 1,NREP
**Algorithm_1**
END DO
CALL CPU_TIME(t2)

time1 = time1 + t2-t1

! WARM UP
DO pp = 1,NREP/10
**Algorithm_2**
END DO

! MEASURE 2
CALL CPU_TIME(t3)
DO pp = 1,NREP
**Algorithm_2**
END DO
CALL CPU_TIME(t4)

time2 = time2 + t4-t3

ENDDO

PRINT*, "Algorithm 1 time = ", time1/(dble(NREP)*dble(NLOOP))
PRINT*, "Algorithm 2 time = ", time2/(dble(NREP)*dble(NLOOP))


6) Make sure you are the only user on the machine

7) Close all other background applications if you are on a desktop computer (firefox, etc)

8) Turn off the network

9) For Multi-threaded applications, make sure your threads are bound to different physical CPU cores (check in /proc/cpuinfo)

• I have been using your approach even though I do not understand everything about it. Can you provide a brief explanation or references concerning points 1, 2 and 3? Feb 21 '16 at 12:51
• I edited the answer to be more explicit on these points. Feb 21 '16 at 19:33
• Thanks for the edit! On another note, is there a introductory HPC book you would recommend? @AnthonyScemama Feb 21 '16 at 19:52
• I would recommend "Introduction to High Performance Computing for Scientists and Engineers" (Chapman & Hall/CRC Computational Science) by Georg Hager and Gerhard Wellein. There is also, "The Software Optimization Cookbook: High Performance Recipes for IA-32 Platforms" by Richard Gerber, Aart J. C. Bik, Kevin Smith, and Xinmin Tian which is a bit old (2005) but not outdated. You can also look at the web site of Agner fog : agner.org/optimize Feb 22 '16 at 12:15