Analiza porównawcza w języku Python: Dlaczego mój kod działa wolniej z powtórzeniem?

Question

Mam proste Sieve of Eratosthanes realizację następująco:

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

jestem analizy porównawczej ten kod poprzez wielokrotne generowanie liczb pierwszych pod 10M:

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

Jestem zdezorientowany, ponieważ czas potrzebny na test wzrostem przebiegu znacznie :

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 

jednak zmienia każde wystąpienie range do xrange eliminuje problem:

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 

Dlaczego tak się dzieje? Czy to naprawdę wszystko narzut GC? 3x spowolnienie po 20 biegach wydaje się dużo ...

Answer 1

To nie jest (jeszcze) odpowiedź, tylko zbiór zorganizowanych eksperymentów.

To naprawdę fascynujące. Wygląda na to, że jest coś bardzo wątpliwego w przypadku alokatora pamięci Pythona.

Oto moja próba zmniejszenia 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)) 

Zauważ, że jeśli usunąć if s[i] sprawiają, że wewnętrzny range się xrange sprawiają, że wartość zwracana prądnica lub pass w wewnętrznej for pętli (lub zrobić to s[j] = True), zachowanie znika, a czasy są płaskie.

Zużycie pamięci w Pythonie wzrasta równomiernie w miarę działania funkcji, ostatecznie osiągając plateau (w tym momencie czas pracy również zaczyna się plateau, w około 250% wartości początkowych).

Moja hipoteza jest taka, że ​​duża liczba wewnętrznych range s (zmniejszającego się rozmiaru) oraz ostatnia tablica powodują fragmentację najgorszego przypadku, utrudniającą dalsze przydzielanie obiektów.

Moja rekomendacja to zmniejszenie liczby przypadków testowych i zgłoszenie go jako błędu w programach Pythona (bugs.python.org).