Benchmarking in Python: Perché il mio codice funziona più lentamente con la ripetizione?

Question

Ho un semplice Sieve of Eratosthanes implementazione come segue:

# 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] ] 

sto benchmarking questo codice generando ripetutamente numeri primi in 10M:

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

Sono confuso, come il tempo impiegato per aumenti di funzionamento di prova marcatamente :

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 

Tuttavia, cambiando ogni istanza di range-xrange elimina il 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 

Perché è questo il caso? È davvero tutto il sovraccarico di GC? 3x rallenta dopo 20 corse sembra un bel po '...

Answer 1

Questa non è (ancora) una risposta, ma solo una raccolta di esperimenti organizzati.

Questo è affascinante, davvero. Sembra che ci sia qualcosa di molto dubbio in corso con l'allocatore di memoria di Python.

Ecco il mio tentativo di ridurre il TestCase:

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)) 

Nota che se tolgo if s[i], rendono l'interno range un xrange, rendono il valore di ritorno di un generatore, o pass nel interna for loop (o fare it s[j] = True), il comportamento scompare e i tempi sono piatti.

L'utilizzo della memoria di Python aumenta costantemente man mano che la funzione viene eseguita, raggiungendo infine un plateau (a questo punto i tempi di esecuzione iniziano anche a plateau, a circa il 250% dei valori iniziali).

mia ipotesi è che il gran numero di interiori range s (di dimensioni decrescenti), più la matrice finale, provocano una sorta di caso peggiore mucchio frammentazione che rende molto difficile continuare ripartizione oggetti.

La mia raccomandazione sarebbe quella di creare un caso di test ridotto e archiviarlo come un bug con gli sviluppatori Python (bugs.python.org).