Perché sta prendendo la mod di un numero in python più veloce con gli esponenti?

Question

Stavo cercando di ottimizzare un programma con cui sto armeggiando, quando ho notato che fare value = i % 65536 sembrava rallentare, quindi fare value = i % (2**16).

Per verificare ciò, ho eseguito il seguente programma:

import cProfile 
import pstats 

AMOUNT = 100000000 

def test1(): 
    for i in xrange(AMOUNT): 
     value = i % 65536 
    return 

def test2(): 
    for i in xrange(AMOUNT): 
     value = i % (256**2) 
    return 

def test3(): 
    for i in xrange(AMOUNT): 
     value = i % (16**4) 
    return 

def test4(): 
    for i in xrange(AMOUNT): 
     value = i % (4**8) 
    return 

def test5(): 
    for i in xrange(AMOUNT): 
     value = i % (2**16) 
    return 

def run_tests(): 
    test1() 
    test2() 
    test3() 
    test4() 
    test5() 
    return 

if __name__ == '__main__': 
    cProfile.run('run_tests()', 'results') 
    stats = pstats.Stats('results') 
    stats.sort_stats('calls', 'nfl') 
    stats.print_stats() 

... che ha prodotto il seguente risultato:

Fri May 11 15:11:59 2012 results 

     8 function calls in 40.473 seconds 

    Ordered by: call count, name/file/line 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
     1 0.000 0.000 40.473 40.473 <string>:1(<module>) 
     1 0.000 0.000 40.473 40.473 test.py:31(run_tests) 
     1 10.466 10.466 10.466 10.466 test.py:6(test1) 
     1 7.475 7.475 7.475 7.475 test.py:11(test2) 
     1 7.485 7.485 7.485 7.485 test.py:16(test3) 
     1 7.539 7.539 7.539 7.539 test.py:21(test4) 
     1 7.508 7.508 7.508 7.508 test.py:26(test5) 

Utilizzando 65536 era il più lento a 10.466 secondi, mentre si fa 256**2 era il più veloce a 7.475 secondi (con gli altri possibili valori di esponente in mezzo). Certo, questa differenza di velocità è evidente solo in presenza di elevate quantità di ripetizioni, ma sono ancora curioso di sapere perché questo si verifica.

Perché il numero di un numero di 65536 è più lento, quindi il mod viene utilizzato dagli esponenti? Dovrebbero valutare lo stesso numero e avrei pensato che ci sarebbe voluto più tempo prima che l'interprete python valutasse completamente gli esponenti prima di prendere il mod.

Per estensione, è generalmente più efficiente utilizzare le potenze di due in espressioni python piuttosto che digitare completamente il numero in uscita? E questo modello vale per le operazioni oltre al modulo o per altri numeri oltre allo 2?

(btw, sto usando Python 2.7.2 (32 bit), e ho eseguito quanto sopra su un laptop Windows 7 a 64 bit).

EDIT:
così ho provato invertendo l'ordine delle funzioni che io chiamo, e ora è vero il contrario. Sembra che qualunque sia la prima funzione in run_tests sarà sempre un po 'più lenta quando si usa cProfile, che è strano. Quindi, lezione appresa, immagino - i profiler sono strani: D

Answer 1

Non c'è differenza nel codice byte generato, perché il compilatore fa bene il suo lavoro e ottimizza l'espressione aritmetica costante. Ciò significa che i risultati del test sono solo una coincidenza (prova a cronometrare le funzioni in un ordine diverso!).

>>> import dis 
>>> dis.dis(test1) 
    2   0 SETUP_LOOP    30 (to 33) 
       3 LOAD_GLOBAL    0 (xrange) 
       6 LOAD_GLOBAL    1 (AMOUNT) 
       9 CALL_FUNCTION   1 
      12 GET_ITER    
     >> 13 FOR_ITER    16 (to 32) 
      16 STORE_FAST    0 (i) 

    3   19 LOAD_FAST    0 (i) 
      22 LOAD_CONST    1 (65536) 
      25 BINARY_MODULO  
      26 STORE_FAST    1 (value) 
      29 JUMP_ABSOLUTE   13 
     >> 32 POP_BLOCK   

    4  >> 33 LOAD_CONST    0 (None) 
      36 RETURN_VALUE   
>>> dis.dis(test5) 
    2   0 SETUP_LOOP    30 (to 33) 
       3 LOAD_GLOBAL    0 (xrange) 
       6 LOAD_GLOBAL    1 (AMOUNT) 
       9 CALL_FUNCTION   1 
      12 GET_ITER    
     >> 13 FOR_ITER    16 (to 32) 
      16 STORE_FAST    0 (i) 

    3   19 LOAD_FAST    0 (i) 
      22 LOAD_CONST    3 (65536) 
      25 BINARY_MODULO  
      26 STORE_FAST    1 (value) 
      29 JUMP_ABSOLUTE   13 
     >> 32 POP_BLOCK   

    4  >> 33 LOAD_CONST    0 (None) 
      36 RETURN_VALUE   

(bene in realtà c'è una differenza: il numero viene conservato a diversi offset della tabella costante non riesco a immaginare che alcuna differenza, però.).

Per completezza, ecco una prova adeguata che utilizza il modulo timeit:

import timeit 

setup = "i = 1337" 

best1 = best2 = float("inf") 
for _ in range(5000): 
    best1 = min(best1, timeit.timeit("i % 65536", setup=setup, number=10000)) 
for _ in range(5000): 
    best2 = min(best2, timeit.timeit("i % (2**16)", setup=setup, number=10000)) 
print best1 
print best2 

Nota che sto misurando il tempo minimo di necessario, piuttosto che la media. Se per qualche motivo richiede più tempo, significa che è stato interrotto più spesso (perché il codice non dipende da nient'altro che dalla potenza della CPU).

Answer 2

Hmmm, utilizzando dis per mostrare i codici python bytes mostra che le funzioni sono identiche. Python ha ottimizzato la costante (come previsto). Quindi sospetto che le differenze di orario siano effetti di memorizzazione nella cache. I tempi sul mio portatile lo confermano (usando Python 2.7.3 a 64 bit su Linux)

Fri May 11 23:37:49 2012 results 

    8 function calls in 38.825 seconds 

Ordered by: call count, name/file/line 

ncalls tottime percall cumtime percall filename:lineno(function) 
    1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
    1 0.000 0.000 38.825 38.825 <string>:1(<module>) 
    1 0.000 0.000 38.825 38.825 z.py:31(run_tests) 
    1 7.880 7.880 7.880 7.880 z.py:6(test1) 
    1 7.658 7.658 7.658 7.658 z.py:11(test2) 
    1 7.806 7.806 7.806 7.806 z.py:16(test3) 
    1 7.784 7.784 7.784 7.784 z.py:21(test4) 
    1 7.697 7.697 7.697 7.697 z.py:26(test5) 

tutti più o meno identico

>>> from dis import dis 
>>> def test1(): 
...  for i in xrange(AMOUNT): 
...   value = i % 65536 
...  return 
... 
>>> def test5(): 
...  for i in xrange(AMOUNT): 
...   value = i % (2**16) 
...  return 
... 
>>> dis(test1) 
    2   0 SETUP_LOOP    30 (to 33) 
       3 LOAD_GLOBAL    0 (xrange) 
       6 LOAD_GLOBAL    1 (AMOUNT) 
       9 CALL_FUNCTION   1 
      12 GET_ITER    
     >> 13 FOR_ITER    16 (to 32) 
      16 STORE_FAST    0 (i) 

    3   19 LOAD_FAST    0 (i) 
      22 LOAD_CONST    1 (65536) 
      25 BINARY_MODULO  
      26 STORE_FAST    1 (value) 
      29 JUMP_ABSOLUTE   13 
     >> 32 POP_BLOCK   

    4  >> 33 LOAD_CONST    0 (None) 
      36 RETURN_VALUE   
>>> dis(test5) 
    2   0 SETUP_LOOP    30 (to 33) 
       3 LOAD_GLOBAL    0 (xrange) 
       6 LOAD_GLOBAL    1 (AMOUNT) 
       9 CALL_FUNCTION   1 
      12 GET_ITER    
     >> 13 FOR_ITER    16 (to 32) 
      16 STORE_FAST    0 (i) 

    3   19 LOAD_FAST    0 (i) 
      22 LOAD_CONST    3 (65536) 
      25 BINARY_MODULO  
      26 STORE_FAST    1 (value) 
      29 JUMP_ABSOLUTE   13 
     >> 32 POP_BLOCK   

    4  >> 33 LOAD_CONST    0 (None) 
      36 RETURN_VALUE   
>>> 

Answer 3

Hai eseguito tutti i test solo una volta. La velocità della tua CPU non è sempre la stessa, all'inizio del test probabilmente stava dormendo ed è per questo che il primo test è stato più lento. Per l'analisi comparativa piccole parti di codice (come mod) utilizzare il modulo timeit:

>>> timeit.timeit('for i in range(10000): i % 65536', number=1000) 
0.8686108589172363 
>>> timeit.timeit('for i in range(10000): i % 256**2', number=1000) 
0.862062931060791 
>>> timeit.timeit('for i in range(10000): i % 4**8', number=1000) 
0.8644928932189941 
>>> timeit.timeit('for i in range(10000): i % 2**16', number=1000) 
0.8643178939819336 
>>> timeit.timeit('for i in range(10000): i % 65536', number=1000) 
0.8640358448028564 

Si può vedere che la media è sempre intorno 0.864.