Ho un processo che scorre in due elenchi, uno relativamente grande mentre l'altro è significativamente più piccolo.Perché esiste una differenza di prestazioni tra l'ordine di un ciclo annidato?

Esempio:

larger_list = list(range(15000)) 
smaller_list = list(range(2500)) 

for ll in larger_list: 
    for sl in smaller_list:    
     pass

ho scalato la dimensione verso il basso delle liste per testare le prestazioni, e ho notato c'è una differenza decente tra i quali la lista è in loop attraverso il primo.

import timeit 

larger_list = list(range(150)) 
smaller_list = list(range(25)) 


def large_then_small(): 
    for ll in larger_list: 
     for sl in smaller_list: 
      pass 


def small_then_large(): 
    for sl in smaller_list: 
     for ll in larger_list: 
      pass 


print('Larger -> Smaller: {}'.format(timeit.timeit(large_then_small))) 
print('Smaller -> Larger: {}'.format(timeit.timeit(small_then_large))) 

>>> Larger -> Smaller: 114.884992572 
>>> Smaller -> Larger: 98.7751009799

A prima vista, sembrano identici - tuttavia v'è di 16 seconda differenza tra le due funzioni.

Perché è quello?

fonte

2016-02-29 Wondercricket

Si noti che quella differenza di 16 secondi è di circa 100 e se ci fosse un lavoro effettivo nel ciclo interno, sarebbe 16 secondi al di fuori di un'ora. – user2357112

Interessante. Se contiamo il numero di istruzioni forate eseguite nella funzione large_then_small è 1 + 150 = 151 e in small_then_large è 1 + 25 = 26 (si noti che il numero di loop interni è uguale) - Sto solo parlando sul numero di dichiarazioni for che vengono eseguite). Quindi questo è forse collegato al sovraccarico nella configurazione di for-loops? – Joppe

Ogni volta che si esegue un ciclo 'for', python creerà un nuovo iteratore sulla sequenza. Quindi il più grande e poi più piccolo chiamerà semplicemente il metodo per ottenere un iteratore sulla lista più piccola molte più volte. – Bakuriu

Quando si smonta una delle tue funzioni si ottiene:

>>> dis.dis(small_then_large) 
    2   0 SETUP_LOOP    31 (to 34) 
       3 LOAD_GLOBAL    0 (smaller_list) 
       6 GET_ITER 
     >> 7 FOR_ITER    23 (to 33) 
      10 STORE_FAST    0 (sl) 

    3   13 SETUP_LOOP    14 (to 30) 
      16 LOAD_GLOBAL    1 (larger_list) 
      19 GET_ITER 
     >> 20 FOR_ITER     6 (to 29) 
      23 STORE_FAST    1 (ll) 

    4   26 JUMP_ABSOLUTE   20 
     >> 29 POP_BLOCK 
     >> 30 JUMP_ABSOLUTE   7 
     >> 33 POP_BLOCK 
     >> 34 LOAD_CONST    0 (None) 
      37 RETURN_VALUE 
>>>

Guardando indirizzo 29 & 30, sembra che questi eseguirà ogni volta che il ciclo interno finisce. I due loop sembrano sostanzialmente uguali, ma queste due istruzioni vengono eseguite ogni volta che si chiude il ciclo interno. Avere il numero più piccolo all'interno causerebbe che questi venissero eseguiti più spesso, quindi aumentando il tempo (rispetto al numero più grande sul loop interno).

fonte

2016-02-29 22:11:10 Gerrat

Ottima risposta! +1 da me – CodeLikeBeaker

Wow, ho bisogno di usare il modulo DIS più spesso. – Wondercricket

@Wondercricket: Suppongo che sia utile per le micro-ottimizzazioni come questa, ma di certo non è qualcosa che normalmente guarderei. La tua domanda intrigante lo ha comunque garantito. – Gerrat

Questo stesso fenomeno era in discussione nel duplicato this e mi ha fatto interessare a ciò che accade nella terra C di CPython. pitone Costruito con:

% ./configure --enable-profiling 
% make coverage

Test

% ./python -c "larger_list = list(range(15000)) 
smaller_list = list(range(2500)) 
for sl in smaller_list: 
    for ll in larger_list: 
     pass" 
% mv gmon.out soflgmon.out 

% ./python -c "larger_list = list(range(15000)) 
smaller_list = list(range(2500)) 
for ll in larger_list: 
    for sl in smaller_list: 
     pass" 
% mv gmon.out lofsgmon.out

Risultati

Breve elenco delle lunghe liste (tempo totale per una singola corsa 1.60):

% gprof python soflgmon.out|head -n40 
Flat profile: 

Each sample counts as 0.01 seconds. 
    % cumulative self    self  total   
time seconds seconds calls s/call s/call name  
46.25  0.74  0.74  3346  0.00  0.00 PyEval_EvalFrameEx 
25.62  1.15  0.41 37518735  0.00  0.00 insertdict 
14.38  1.38  0.23 37555121  0.00  0.00 lookdict_unicode_nodummy 
    7.81  1.50  0.12 37506675  0.00  0.00 listiter_next 
    4.06  1.57  0.07 37516233  0.00  0.00 PyDict_SetItem 
    0.62  1.58  0.01  2095  0.00  0.00 _PyEval_EvalCodeWithName 
    0.62  1.59  0.01  3  0.00  0.00 untrack_dicts 
    0.31  1.59  0.01        _PyDict_SetItem_KnownHash 
    0.31  1.60  0.01        listiter_len 
    0.00  1.60  0.00 87268  0.00  0.00 visit_decref 
    0.00  1.60  0.00 73592  0.00  0.00 visit_reachable 
    0.00  1.60  0.00 71261  0.00  0.00 _PyThreadState_UncheckedGet 
    0.00  1.60  0.00 49742  0.00  0.00 _PyObject_Alloc 
    0.00  1.60  0.00 48922  0.00  0.00 PyObject_Malloc 
    0.00  1.60  0.00 48922  0.00  0.00 _PyObject_Malloc 
    0.00  1.60  0.00 47487  0.00  0.00 PyDict_GetItem 
    0.00  1.60  0.00 44246  0.00  0.00 _PyObject_Free 
    0.00  1.60  0.00 43637  0.00  0.00 PyObject_Free 
    0.00  1.60  0.00 30034  0.00  0.00 slotptr 
    0.00  1.60  0.00 24892  0.00  0.00 type_is_gc 
    0.00  1.60  0.00 24170  0.00  0.00 r_byte 
    0.00  1.60  0.00 23774  0.00  0.00 PyErr_Occurred 
    0.00  1.60  0.00 20371  0.00  0.00 _PyType_Lookup 
    0.00  1.60  0.00 19930  0.00  0.00 PyLong_FromLong 
    0.00  1.60  0.00 19758  0.00  0.00 r_string 
    0.00  1.60  0.00 19080  0.00  0.00 _PyLong_New 
    0.00  1.60  0.00 18887  0.00  0.00 lookdict_unicode 
    0.00  1.60  0.00 18878  0.00  0.00 long_dealloc 
    0.00  1.60  0.00 17639  0.00  0.00 PyUnicode_InternInPlace 
    0.00  1.60  0.00 17502  0.00  0.00 rangeiter_next 
    0.00  1.60  0.00 14776  0.00  0.00 PyObject_GC_UnTrack 
    0.00  1.60  0.00 14578  0.00  0.00 descr_traverse 
    0.00  1.60  0.00 13520  0.00  0.00 r_long 
    0.00  1.60  0.00 13058  0.00  0.00 PyUnicode_New 
    0.00  1.60  0.00 12298  0.00  0.00 _Py_CheckFunctionResult 
    ...

Lungo elenco di breve elenchi (tempo totale per una singola esecuzione 1,64):

gprof python lofsgmon.out|head -n40 
Flat profile: 

Each sample counts as 0.01 seconds. 
    % cumulative self    self  total   
time seconds seconds calls s/call s/call name  
48.78  0.80  0.80  3346  0.00  0.00 PyEval_EvalFrameEx 
17.99  1.09  0.29 37531168  0.00  0.00 insertdict 
11.59  1.28  0.19 37531675  0.00  0.00 listiter_next 
11.28  1.47  0.18 37580156  0.00  0.00 lookdict_unicode_nodummy 
    6.71  1.58  0.11 37528666  0.00  0.00 PyDict_SetItem 
    1.22  1.60  0.02        _PyDict_SetItem_KnownHash 
    0.61  1.61  0.01  5525  0.00  0.00 update_one_slot 
    0.61  1.62  0.01  120  0.00  0.00 PyDict_Merge 
    0.30  1.62  0.01 18178  0.00  0.00 lookdict_unicode 
    0.30  1.63  0.01 11988  0.00  0.00 insertdict_clean 
    0.30  1.64  0.01        listiter_len 
    0.30  1.64  0.01        listiter_traverse 
    0.00  1.64  0.00 96089  0.00  0.00 _PyThreadState_UncheckedGet 
    0.00  1.64  0.00 87245  0.00  0.00 visit_decref 
    0.00  1.64  0.00 74743  0.00  0.00 visit_reachable 
    0.00  1.64  0.00 62232  0.00  0.00 _PyObject_Alloc 
    0.00  1.64  0.00 61412  0.00  0.00 PyObject_Malloc 
    0.00  1.64  0.00 61412  0.00  0.00 _PyObject_Malloc 
    0.00  1.64  0.00 59815  0.00  0.00 PyDict_GetItem 
    0.00  1.64  0.00 55231  0.00  0.00 _PyObject_Free 
    0.00  1.64  0.00 54622  0.00  0.00 PyObject_Free 
    0.00  1.64  0.00 36274  0.00  0.00 PyErr_Occurred 
    0.00  1.64  0.00 30034  0.00  0.00 slotptr 
    0.00  1.64  0.00 24929  0.00  0.00 type_is_gc 
    0.00  1.64  0.00 24617  0.00  0.00 _PyObject_GC_Alloc 
    0.00  1.64  0.00 24617  0.00  0.00 _PyObject_GC_Malloc 
    0.00  1.64  0.00 24170  0.00  0.00 r_byte 
    0.00  1.64  0.00 20958  0.00  0.00 PyObject_GC_Del 
    0.00  1.64  0.00 20371  0.00  0.00 _PyType_Lookup 
    0.00  1.64  0.00 19918  0.00  0.00 PyLong_FromLong 
    0.00  1.64  0.00 19758  0.00  0.00 r_string 
    0.00  1.64  0.00 19068  0.00  0.00 _PyLong_New 
    0.00  1.64  0.00 18845  0.00  0.00 long_dealloc 
    0.00  1.64  0.00 18507  0.00  0.00 _PyObject_GC_New 
    0.00  1.64  0.00 17639  0.00  0.00 PyUnicode_InternInPlace 
    ...

La differenza è marginale (2,4%) e la profilatura si aggiunge al tempo di esecuzione, quindi è difficile dire quanto effettivamente sarebbe stata. Il tempo totale include anche la creazione degli elenchi di test, in modo da nascondere ulteriormente la vera differenza.

Il motivo della differenza di 16 secondi nel test originale è che timeit.timeit esegue l'istruzione o la funzione data number=1000000 per impostazione predefinita, quindi in questo caso si sommano a ben 40.000. Non citare questo valore, poiché è un artefatto della profilazione. Con il vostro codice di prova originale e python3 non profiling su questa macchina ottengo:

Larger -> Smaller: 40.29234626500056 
Smaller -> Larger: 33.09413992699956

che significherebbe una differenza di

In [1]: (40.29234626500056-33.09413992699956)/1000000 
Out[1]: 7.198206338001e-06

per singola corsa (7.2μs), 18% in totale.

Così come indicato nel former answer, POP_BLOCK Viene eseguito di più, ma non è solo questo, ma l'intero setup ciclo interno:

0.00  1.64  0.00 16521  0.00  0.00 PyFrame_BlockSetup 
    0.00  1.64  0.00 16154  0.00  0.00 PyFrame_BlockPop

Rispetto al breve elenco di lunghi elenchi:

0.00  1.60  0.00  4021  0.00  0.00 PyFrame_BlockSetup 
    0.00  1.60  0.00  3748  0.00  0.00 set_next 
    0.00  1.60  0.00  3654  0.00  0.00 PyFrame_BlockPop

Questo ha comunque un impatto trascurabile.

fonte

2016-04-13 08:14:55

Perché esiste una differenza di prestazioni tra l'ordine di un ciclo annidato?

risposta

Test

Risultati

Problemi correlati