Timing operation with increasing list size - unexpected behaviour

Question

Problem: How long does it take to generate a Python list of prime numbers from 1 to N? Plot a graph of time taken against N.

I used SymPy to generate the list of primes. I expected the time to increase monotonically. But why is there a dip?

import numpy as np
import matplotlib.pyplot as plt
from time import perf_counter as timer
from sympy import sieve

T = []
tic=timer()

N= np.logspace(1,8,30)
for Nup in N:
    tic = timer()
    A=list(sieve.primerange(1,Nup))
    toc = timer()
    T.append(toc-tic)
    
plt.loglog(N,T,'x-')
plt.grid()
plt.show()

Time taken to generate primes up to N

Answer 1

The sieve itself requires an exponential amount of time to compute ever larger numbers of primes, so plotting the pure runtime of a sieve should come out to roughly a straight line for large numbers.

In your copy of the plot, it looks like it's actually getting a bit worse over time, but when I run your script it's not perfectly straight, but close to a straight line on the log scale towards the end. However, there is a bit of a bend at the start, as with your result.

This makes sense because the sieve caches previous results, but initially it gets little benefit from that and there's the small overhead of setting up the cache and increasing its size which goes down over time, and more importantly there's the overhead of the actual call to the sieve routine. Also, this type of performance measurement is very sensitive to anything else going on on your system, including whatever Python and your IDE are doing

Here's your code with some added code to loop over various initial runs, warming the cache of the sieve before every run - it shows pretty clearly what the effect is:

import numpy as np
import matplotlib.pyplot as plt
from time import perf_counter as timer, sleep
from sympy import sieve

for warmup_step in range(0, 5):
    warmup = 100 ** warmup_step
    sieve._reset()  # this resets the internal cache of the sieve
    _ = list(sieve.primerange(1, warmup))  # warming the sieve's cache

    _ = timer()  # avoid initial delays from other elements of the code
    sleep(3)
    print('Start')

    times = []
    tic = timer()

    numbers = np.logspace(1, 8, 30)
    for n in numbers:
        tic = timer()
        _ = list(sieve.primerange(1, n))
        toc = timer()
        times.append(toc - tic)
        print(toc, n)  # provide some visual feedback of speed

    plt.loglog(numbers, times, 'x-')
    plt.title(f'Warmup: {warmup}')
    plt.ylim(1e-6, 1e+1)  # fix the y-axis, so the charts are easily comparable
    plt.grid()
    plt.show()

The lesson to be learned here is that you need to consider overhead. Of your own code and the libraries you use, but also the entire system that sits around it: the Python VM, your IDE, whatever is running on your workstation, the OS that runs it, the hardware.

The test above is better, but if you want really nice results, run the whole thing a dozen times and average out the results over runs.

Results: