Benchmarking en Python: ¿Por qué mi código se ejecuta más lento con la repetición?

Question

que tienen un simple Sieve of Eratosthanes aplicación de la siguiente manera:

# Generate all primes less than k 
def sieve(k): 
    s = [True] * k 
    s[0] = s[1] = False 
    for i in range(4, k, 2): 
     s[i] = False 

    for i in range(3, int(sqrt(k)) + 2, 2): 
     if s[i]:    
      for j in range(i ** 2, k, i * 2): 
       s[j] = False 

    return [2] + [ i for i in range(3, k, 2) if s[i] ] 

estoy Benchmarking este código al generar repetidamente primos bajo 10M:

st = time() 
for x in range(1000): 
    rt = time() 
    sieve(10000000) 
    print "%3d %.2f %.2f" % (x, time() - rt, (time() - st)/(x + 1)) 

Estoy confundido, como el tiempo que aumenta la ejecución de prueba por marcadamente :

run t avg 
    0 1.49 1.49 
    1 1.79 1.66 
    2 2.23 1.85 
    3 2.72 2.07 
    4 2.67 2.20 
    5 2.87 2.31 
    6 3.05 2.42 
    7 3.57 2.56 
    8 3.38 2.65 
    9 3.48 2.74 
10 3.81 2.84 
11 3.75 2.92 
12 3.85 2.99 
13 4.14 3.07 
14 4.02 3.14 
15 4.05 3.20 
16 4.48 3.28 
17 4.41 3.34 
18 4.19 3.39 
19 4.22 3.43 
20 4.65 3.49 

Sin embargo, el cambio de cada instancia de range-xrange elimina el problema:

run t avg 
    0 1.26 1.26 
    1 1.23 1.28 
    2 1.24 1.27 
    3 1.25 1.26 
    4 1.23 1.26 
    5 1.23 1.25 
    6 1.25 1.25 
    7 1.25 1.25 
    8 1.23 1.25 
    9 1.25 1.25 
10 1.24 1.25 

¿Por qué es este el caso? ¿Es realmente todo sobre GC? 3 veces más lento después de 20 carreras parece mucho ...

Answer 1

Esto no es (todavía) una respuesta, sino solo una colección de experimentos organizados.

Esto es fascinante, de verdad. Parece que hay algo muy dudoso en el asignador de memoria de Python.

Aquí está mi intento de reducir el caso de prueba:

def sieve(k): 
    s = [True] * k 

    for i in xrange(3, int(sqrt(k)) + 2, 2): 
     for j in range(i ** 2, k, i * 2): 
      s[j] = False 

    return [ i for i in range(3, k, 2) if s[i] ] 

st = time() 
for x in range(1000): 
    rt = time() 
    sieve(10000000) 
    print "%3d %.2f %.2f" % (x, time() - rt, (time() - st)/(x + 1)) 

Tenga en cuenta que si quito if s[i], hacen que el interior range un xrange, hacen que el valor de retorno de un generador, o pass en el for bucle interno (o hacer es s[j] = True), el comportamiento desaparece y los tiempos son planos.

El uso de memoria de Python aumenta constantemente a medida que se ejecuta la función, llegando finalmente a una meseta (momento en el que los tiempos de ejecución también comienzan a estabilizarse, alrededor del 250% de sus valores iniciales).

Mi hipótesis es que la gran cantidad de range internos (de tamaño decreciente), más la matriz final, ocasionan algún tipo de fragmentación de montón en el peor de los casos, lo que dificulta la continuación de la asignación de objetos.

Mi recomendación sería hacer un caso de prueba reducido y presentarlo como un error con los desarrolladores de Python (bugs.python.org).