2015-06-07 2 views
8

Napotkałem dziwny problem wydajności podczas dodawania do klasy klasy str w python 2.7.3. Wiem, że dostęp do zmiennych lokalnych jest szybszy, jednak w poniższym problemie istnieje ponad 100-krotna różnica prędkości między dwiema pętlami. Ten, który uzyskuje dostęp do a.accum_, uruchamia się szybko, ale zwalnia, tak jakby str iadd jest O (n^2) o długości str.Python członek str wydajność zbyt wolny

Czy ktoś zna przyczynę?

# Fast (< 1sec): 
accum = str() 
for ii in range(1000000): 
    if (ii % 10000) == 0: 
     print 'fast cnt', ii 
    accum += 'zzzzz\n' 

# Much slower (> 5 mins): 
class Foo: 
    pass 
a = Foo() 
a.accum_ = str() 
for ii in range(1000000): 
    if (ii % 10000) == 0: 
     print 'slow cnt', ii 
    a.accum_ += 'zzzzz\n' 
+0

Jest to z pewnością dlatego, że w pierwszym podejściu pierwsze podejście łańcuch będzie miał tylko jedno odniesienie podczas jego trwania i CPython może zoptymalizować ten przypadek, stąd czas O (N). W drugim przypadku liczba referencyjna z pewnością wzrosła z 1 (ale gdzie dokładnie?), Stąd czas kwadratowy. –

+0

@AshwiniChaudhary: Licznik referencji jest taki sam w obu przypadkach, ale jak wskazuje odpowiedź, istnieje specyficzna optymalizacja w stosunku do pierwszego przypadku, ale nie w stosunku do drugiego, i dlatego drugi przypadek wymaga czasu kwadratowego. – doublep

+0

@doublep Nie jestem pewien, jak próbujesz policzyć odniesienia, ale sprawdź refcount przed '+ =' i ** podczas ** '+ ='. Powinien wzrosnąć co najmniej 1. –

Odpowiedz

3

Python ciągi są niezmienne i tak nie może mieć metodę __iadd__. To, czego jesteś świadkiem w pierwszym przykładzie, to mikrooptymalizacja interpretera CPythona. W pierwszym przykładzie tłumacz zauważył, że ma zmienną lokalną, która ma licznik referencyjny równy 1. W ten sposób tłumacz może bezmyślnie uciec zmieniając ciąg w miejscu. Nawet jeśli narusza to umowę z str, w żadnym momencie podczas realizacji programu nie będzie oczywiste, że umowa ta została krótko naruszona.

W tym ostatnim przykładzie ta mikrooptymalizacja nie jest wdrażana, dlatego jest tak powolna. Wygląda na to, że można zastosować optymalizację, więc nie jestem pewien, dlaczego nie jest ona stosowana.

Generalnie, jeśli budujesz ciąg, zestawiaj podciągi na liście, a następnie używaj str.join do tworzenia produktu końcowego.

+1

Odpowiednią optymalizację stanowi 'string_concatenate()' w pliku 'ceval.c'. Oczywiście jest to istotne dla CPython. – doublep

5

Dla pierwszego przykładu jest całkiem jasne, że ma to miejsce w przypadku pojedynczej optymalizacji referencyjnej (istnieją dwa odnośniki: jeden od samego obiektu i jeden LOAD_FAST; unicode_concatenate spróbuje zmniejszyć go do 1 przed przekazaniem kontroli do PyUnicode_Append) wykonane przez CPython użyciu tego unicode_modifiable funkcję:

static int 
unicode_modifiable(PyObject *unicode) 
{ 
    assert(_PyUnicode_CHECK(unicode)); 
    if (Py_REFCNT(unicode) != 1) 
     return 0; 
    if (_PyUnicode_HASH(unicode) != -1) 
     return 0; 
    if (PyUnicode_CHECK_INTERNED(unicode)) 
     return 0; 
    if (!PyUnicode_CheckExact(unicode)) 
     return 0; 
#ifdef Py_DEBUG 
    /* singleton refcount is greater than 1 */ 
    assert(!unicode_is_singleton(unicode)); 
#endif 
    return 1; 
} 

jednak w tym drugim przypadku jako przykład dane są przechowywane w Pythonie dict zamiast zwykłej zmiennej, więc robi się trochę inaczej.

a.accum_ += 'foo' 

rzeczywiście wymaga preselekcji wartość a.accum_ i przechowywanie go na stosie. Tak więc teraz ciąg ma co najmniej trzy referencje: jedną ze słownika instancji, jedną z DUP_TOP i jedną z PyObject_GetAttr używaną przez LOAD_ATTR. W związku z tym Python nie może zoptymalizować tego przypadku, ponieważ modyfikowanie jednego z nich na miejscu wpłynie również na inne odniesienia.

>>> class A: 
    pass 
... 
>>> a = A() 
>>> def func(): 
    a.str = 'spam' 
    print a.str 
    return '_from_func' 
... 
>>> a.str = 'foo' 
>>> a.str += func() 
spam 

Można by oczekiwać, że wyjście, żeby być 'spam_from_func', ale będzie inny, ponieważ oryginalna wartość a.str przechowywano przez Python przed func() nazwano.

>>> a.str 
'foo_from_func' 

Byte Code:

>>> import dis 
>>> def func_class(): 
     a = Foo() 
     a.accum = '' 
     a.accum += 'zzzzz\n' 
... 
>>> dis.dis(func_class) 
    2   0 LOAD_GLOBAL    0 (Foo) 
       3 CALL_FUNCTION   0 (0 positional, 0 keyword pair) 
       6 STORE_FAST    0 (a) 

    3   9 LOAD_CONST    1 ('') 
      12 LOAD_FAST    0 (a) 
      15 STORE_ATTR    1 (accum) 

    4   18 LOAD_FAST    0 (a) 
      21 DUP_TOP 
      22 LOAD_ATTR    1 (accum) 
      25 LOAD_CONST    2 ('zzzzz\n') 
      28 INPLACE_ADD 
      29 ROT_TWO 
      30 STORE_ATTR    1 (accum) 
      33 LOAD_CONST    0 (None) 
      36 RETURN_VALUE 

Zauważ, że ta optymalizacja została wykonana w around 2004 (CPython 2.4), aby uniemożliwić użytkownikom zwolnienie się z powolne z a += b lub a = a + b, więc jest głównie przeznaczona dla prostych zmiennych i działa tylko wtedy, gdy następna instrukcja jest STORE_FAST (zmienna lokalna), STORE_DEREF (zamknięcia) i STORE_NAME. To nie jest ogólne rozwiązanie, the best way to do this in Python is to create a list and join its items using str.join.

CPython realizacja detal: Jeśli s i t są zarówno ciągi, niektóre implementacje Python takich jak CPython można zwykle wykonać optymalizacji w miejscu dla przypisania postaci s = s + t lub s += t. Po zastosowaniu tej optymalizacji czterokrotny czas wykonania jest prawdopodobnie znacznie mniejszy, . Ta optymalizacja jest zależna zarówno od wersji, jak i od implementacji . W przypadku kodu wrażliwego na wydajność zalecane jest użycie metody zapewniającej stałą wydajność liniową konkatenacji w różnych wersjach i implementacjach.