Python - test algorithm performance

In this article, we would like to show how to test algorithms' performance in Python.

Usually, when we compare algorithms that execution times are short, we repeat computations multiple times to get precise results. The number of repeats is selected empirically. The source code that is not an algorithm part shouldn't be measured.

Main concept:

import time

def get_time():
    return round(1000 * time.time())

def test_function(repeats, description, function):
    t1 = get_time()
    i = 0
    while i < repeats:
        function()
        i += 1
    t2 = get_time()
    dt = t2 - t1
    print(description, ': total time is ', dt, ' ms')


# Usage example:

def case_1():
    # source code case 1
    return 0

def case_2():
    # source code case 2
    return 0

def case_3():
    # source code case 3
    return 0

repeats = 1000  # set number of repeats depending on cases complexity

test_function(repeats, 'case 1', case_1)
test_function(repeats, 'case 2', case_2)
test_function(repeats, 'case 3', case_3)

# add more cases here ...

Hint: presented concept describes only a simple way how to test performance - in practice tests made by benchmarks are more complex.

Practical example

In the below example we compare algorithms that computes Fibonacci sequence values.

In the test, we made 1000 repeats on Fibonacci algorithms using Ryzen 9 x5900 processor and Python 3.10 (CPyhyon) under Windows 11 x64.

Test result:

Iterative algorithm : total time is 121 ms
Binet's formula : total time is 12 ms

Conclusion: iterative algorithm is 10 times slower in the tested cases.

Test source code:

import time
import math

def get_time():
    return round(1000 * time.time())

def test_function(repeats, description, function):
    t1 = get_time()
    i = 0
    while i < repeats:
        function()
        i += 1
    t2 = get_time()
    dt = t2 - t1
    print(description, ': total time is', dt, 'ms')


# Tested algorithms:

def fibonacci_1(input):
    if input < 1: return 0;
    if input < 2: return 1;
    return fibonacci_1(input - 2) + fibonacci_1(input - 1);

def fibonacci_2(input):
    a = math.pow(1 + 2.23606797749979, input);
    b = math.pow(1 - 2.23606797749979, input);
    c = 2.23606797749979 * math.pow(2, input);
    return round((a - b) / c);


# Performance tests:

def case_1():
    i = 1
    while i < 10:
        fibonacci_1(i)
        i += 1

def case_2():
    i = 1
    while i < 10:
        fibonacci_2(i)
        i += 1

repeats = 1000  # set number of repeats depending on cases complexity

test_function(repeats, 'Iterative algorithm', case_1)
test_function(repeats, 'Binet\'s formula', case_2)