Do rozpakowywania elementów pętli

Question

Raz, po obejrzeniu samouczka optymalizacji wydajności Mike'a Mullera (myślę, że this one), jedna myśl zaczęła żyć w mojej głowie: jeśli wydajność ma znaczenie, zminimalizuj dostęp do elementów w pętli według indeksu, np. sol. jeśli potrzebujesz kilkakrotnie uzyskać dostęp do x[1] w pętli for x in l - przypisz zmienną do x[1] i użyj jej ponownie w pętli.

Teraz mam ten syntetyczny przykład:

import timeit 

SEQUENCE = zip(range(1000), range(1, 1001)) 

def no_unpacking(): 
    return [item[0] + item[1] for item in SEQUENCE] 


def unpacking():  
    return [a + b for a, b in SEQUENCE] 


print timeit.Timer('no_unpacking()', 'from __main__ import no_unpacking').timeit(10000) 
print timeit.Timer('unpacking()', 'from __main__ import unpacking').timeit(10000) 

unpacking() i no_unpacking() zwracają ten sam wynik. Implementacja jest inna: unpacking() rozpakowuje elementy w a i b w pętli; no_unpacking() pobiera wartości według indeksów.

Dla python27, to pokazuje:

1.25280499458 
0.946601867676 

innymi słowy unpacking() przewyższa no_unpacking() o ~ 25%.

Pytanie brzmi:

• dlaczego dostępu przez indeks spowolnić znacząco (nawet w tym prostym przypadku)?

Bonus pytanie:

• Próbowałem również ten na pypy - nie ma prawie żadnej różnicy między tymi 2 funkcje, wydajność mądry. Dlaczego?

Dzięki za pomoc.

Answer 1

Aby odpowiedzieć na Twoje pytania możemy sprawdzić kodu bajtowego generowane przez dwóch funkcji wykorzystujących moduł dis:

In [5]: def no_unpacking(): 
    ...:  s = [] 
    ...:  for item in SEQUENCE: 
    ...:   s.append(item[0] + item[1]) 
    ...:  return s 
    ...: 
    ...: 
    ...: def unpacking(): 
    ...:  s = [] 
    ...:  for a,b in SEQUENCE: 
    ...:   s.append(a+b) 
    ...:  return s 

^{Mam rozszerzył listę-zrozumieniem bo w python3 byłoby bardziej uciążliwe, by sprawdzić ciekawe bajtodes. Kod jest równoważny, więc nie ma to większego znaczenia dla naszego celu.}

Kod bajtowy dla pierwszej funkcji jest następująca:

In [6]: dis.dis(no_unpacking) 
    2   0 BUILD_LIST    0 
       3 STORE_FAST    0 (s) 

    3   6 SETUP_LOOP    39 (to 48) 
       9 LOAD_GLOBAL    0 (SEQUENCE) 
      12 GET_ITER    
     >> 13 FOR_ITER    31 (to 47) 
      16 STORE_FAST    1 (item) 

    4   19 LOAD_FAST    0 (s) 
      22 LOAD_ATTR    1 (append) 
      25 LOAD_FAST    1 (item) 
      28 LOAD_CONST    1 (0) 
      31 BINARY_SUBSCR   
      32 LOAD_FAST    1 (item) 
      35 LOAD_CONST    2 (1) 
      38 BINARY_SUBSCR   
      39 BINARY_ADD   
      40 CALL_FUNCTION   1 (1 positional, 0 keyword pair) 
      43 POP_TOP    
      44 JUMP_ABSOLUTE   13 
     >> 47 POP_BLOCK    

    5  >> 48 LOAD_FAST    0 (s) 
      51 RETURN_VALUE  

Należy zauważyć, że pętla musi wywołać BINARY_SUBSCR dwukrotnie, aby uzyskać dostęp do dwóch elementów krotki.

Kod bajtowy dla drugiej funkcji jest następująca:

In [7]: dis.dis(unpacking) 
    9   0 BUILD_LIST    0 
       3 STORE_FAST    0 (s) 

10   6 SETUP_LOOP    37 (to 46) 
       9 LOAD_GLOBAL    0 (SEQUENCE) 
      12 GET_ITER    
     >> 13 FOR_ITER    29 (to 45) 
      16 UNPACK_SEQUENCE   2 
      19 STORE_FAST    1 (a) 
      22 STORE_FAST    2 (b) 

11   25 LOAD_FAST    0 (s) 
      28 LOAD_ATTR    1 (append) 
      31 LOAD_FAST    1 (a) 
      34 LOAD_FAST    2 (b) 
      37 BINARY_ADD   
      38 CALL_FUNCTION   1 (1 positional, 0 keyword pair) 
      41 POP_TOP    
      42 JUMP_ABSOLUTE   13 
     >> 45 POP_BLOCK    

12  >> 46 LOAD_FAST    0 (s) 
      49 RETURN_VALUE 

Uwaga jak nie ma BINARY_SUBSCR wykonać.

Więc wydaje się, że UNPACK_SEQUENCE plus jeden STORE_FAST (co jest dodatkowe operacje dodane przez rozpakowywania) są szybciej następnie robi dwa BINARY_SUBSCR. Jest to uzasadnione, ponieważ BINARY_SUBSCR jest pełnowymiarowym wywołaniem metody, natomiast UNPACK_SEQUENCE i STORE_FAST są prostszymi operacjami.

Widać różnicę nawet w prostszych przypadkach:

In [1]: def iter_with_index(s): 
    ...:  for i in range(len(s)): 
    ...:   s[i] 
    ...:   

In [2]: def iter_without_index(s): 
    ...:  for el in s:el 
    ...:  

In [3]: %%timeit s = 'a' * 10000 
    ...: iter_with_index(s) 
    ...: 
1000 loops, best of 3: 583 us per loop 

In [4]: %%timeit s = 'a' * 10000 
    ...: iter_without_index(s) 
    ...: 
1000 loops, best of 3: 206 us per loop 

Jak widać iteracji po sznurku jest około 3 razy wolniej stosując wyraźny indeksowanie. To wszystko z powodu połączeń z numerem BINARY_SUBSCR.

Odnośnie twojego drugiego pytania: pypy ma JIT, który potrafi analizować kod i tworzy zoptymalizowaną wersję, która unika narzutów operacji indeksowania. Kiedy zdaje sobie sprawę, że subskrypcja jest wykonywana na krotkach, prawdopodobnie jest ona w stanie wytworzyć kod, który nie wywołuje metody krotkowej, ale bezpośrednio uzyskuje dostęp do elementów, całkowicie usuwając operacje BINARY_SUBSCR.