How to compare runtimes of two algorithms in a reproducible way

Question

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?

Answer 1

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
taskset -c 0-3 ./a.out

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)