Tại sao có sự khác biệt hiệu suất giữa thứ tự của vòng lặp lồng nhau?

Question

Tôi có một quy trình lặp qua hai danh sách, một danh sách tương đối lớn trong khi danh sách còn lại nhỏ hơn đáng kể.

Ví dụ:

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

for ll in larger_list: 
    for sl in smaller_list:    
     pass 

Tôi trèo lên kích thước xuống của danh sách để kiểm tra hiệu suất, và tôi nhận thấy có sự khác biệt khá giữa mà danh sách được looped qua đầu tiên.

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 

Thoạt nhìn, chúng trông giống hệt nhau - tuy nhiên có sự khác biệt 16 giây giữa hai hàm.

Tại sao lại như vậy?

Answer 1

Khi bạn tháo rời một trong những chức năng của bạn, bạn nhận được:

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

Nhìn vào địa chỉ 29 & 30, nó trông như thế này sẽ thực hiện mỗi lần vòng lặp bên trong kết thúc. Hai vòng lặp về cơ bản giống nhau, nhưng hai lệnh này được thực thi mỗi khi vòng lặp bên trong thoát ra. Việc có số nhỏ hơn ở bên trong sẽ khiến các số này được thực hiện thường xuyên hơn, do đó tăng thời gian (so với số lớn hơn trên vòng lặp bên trong).

Answer 2

Hiện tượng tương tự này đang được thảo luận trong this trùng lặp và khiến tôi quan tâm đến những gì diễn ra trong đất C của CPython. Xây dựng python với:

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

thử nghiệm

% ./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 

Kết quả

danh sách ngắn các danh sách dài (tổng thời gian cho một hoạt động đơn lẻ 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 
    ... 

danh sách dài ngắn danh sách (tổng thời gian cho một lần chạy 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 
    ... 

Sự khác biệt là biên (2,4%) và hồ sơ thêm vào thời gian chạy, vì vậy rất khó để nói số tiền thực sự sẽ là bao nhiêu. Tổng thời gian cũng bao gồm việc tạo danh sách kiểm tra, để ẩn đi sự khác biệt thực sự hơn nữa.

Lý do cho sự khác biệt 16 trong thử nghiệm ban đầu là timeit.timeit chạy tuyên bố hoặc hàm đã cho number=1000000 lần theo mặc định, để có thể tăng lên tới 40.000 trong trường hợp này. Đừng báo giá trị đó mặc dù, vì nó là một tạo tác của profiling. Với mã kiểm tra ban đầu của bạn và python3 profiling phi trên máy tính này tôi nhận được:

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

đó có nghĩa là một sự khác biệt của

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

mỗi lần chạy đơn (7.2μs), 18% trong tổng số.

Vì vậy, như đã nêu trong former answer, POP_BLOCK được thực hiện hơn, nhưng nó không chỉ là thế, nhưng toàn bộ thiết lập vòng trong:

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 

So với danh sách ngắn các danh sách dài:

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 

Điều đó có tác động không đáng kể.