2017-01-24 13 views
20

Zawsze uważałem, że porównania były najszybszą operacją, jaką może wykonać komputer. Pamiętam, że słyszałem to na prezentacji D. Knutha, gdzie napisał pętle w porządku malejącym ", ponieważ porównanie z 0 jest szybkie". Czytałem również, że multiplikacje powinny być wolniejsze niż dodatki here.Dlaczego dodawanie i mnożenie są szybsze niż porównania?

Jestem zaskoczony widząc, że zarówno w Pythonie 2, jak i 3, testy zarówno pod kontrolą Linuksa, jak i Maca, porównania wydają się znacznie wolniejsze niż operacje arytmetyczne.

Czy ktoś może wyjaśnić, dlaczego?

%timeit 2 > 0 
10000000 loops, best of 3: 41.5 ns per loop 

%timeit 2 * 2 
10000000 loops, best of 3: 27 ns per loop 

%timeit 2 * 0 
10000000 loops, best of 3: 27.7 ns per loop 

%timeit True != False 
10000000 loops, best of 3: 75 ns per loop 

%timeit True and False 
10000000 loops, best of 3: 58.8 ns per loop 

A pod python 3:

$ ipython3 
Python 3.5.2 | packaged by conda-forge | (default, Sep 8 2016, 14:36:38) 
Type "copyright", "credits" or "license" for more information. 

IPython 5.1.0 -- An enhanced Interactive Python. 
?   -> Introduction and overview of IPython's features. 
%quickref -> Quick reference. 
help  -> Python's own help system. 
object? -> Details about 'object', use 'object??' for extra details. 

In [1]: %timeit 2 + 2 
10000000 loops, best of 3: 22.9 ns per loop 

In [2]: %timeit 2 * 2 
10000000 loops, best of 3: 23.7 ns per loop 

In [3]: %timeit 2 > 2 
10000000 loops, best of 3: 45.5 ns per loop 

In [4]: %timeit True and False 
10000000 loops, best of 3: 62.8 ns per loop 

In [5]: %timeit True != False 
10000000 loops, best of 3: 92.9 ns per loop 
+3

Spodziewałem się wszystkich tych przykładów być nieustannie fałdowane na drodze do zostania kodowaniem bajtowym. Być może czas przeszkadza w tym. –

+5

bardziej ogólnie, "ponieważ porównanie z 0 jest szybkie" jest bardzo istotne, jeśli programujemy Z80 lub coś podobnego ... inaczej to prawdopodobnie wcale nie jest, i jest to dokładnie to, o czym mówi pewna o wiele bardziej znana wypowiedź Knutha . Mogę się domyślać, że Knuth mówił tutaj o surowym języku asemblerowym, a jeśli tak, to próbując zastosować to do skompilowanego/interpretowanego języka, jest prawie całkowity non sequitur. –

+2

Podczas testowania porównawczego należy uważać na [stałe składanie] (https://en.wikipedia.org/wiki/Constant_folding). – Schwern

Odpowiedz

18

Dzieje się tak ze względu na Constant Folding w Peep Holeoptimizer w terminie kompilator Pythona .

Używając modułu dis, jeśli złamiemy każdą z instrukcji, aby sprawdzić, w jaki sposób są one tłumaczone na poziomie maszyny, zauważysz, że wszyscy operatorzy, tacy jak nierówność, równość itd., Są najpierw ładowani do pamięci, a następnie oceniani. Jednak wszystkie wyrażenia, takie jak mnożenie, dodawanie itd. Są obliczane i ładowane jako stała do pamięci.

Ogólnie rzecz biorąc, to prowadzi do mniejszej liczby etapów realizacji, czyniąc kroki szybciej:

>>> import dis 

>>> def m1(): True != False 
>>> dis.dis(m1) 
    1   0 LOAD_GLOBAL    0 (True) 
       3 LOAD_GLOBAL    1 (False) 
       6 COMPARE_OP    3 (!=) 
       9 POP_TOP    
      10 LOAD_CONST    0 (None) 
      13 RETURN_VALUE   

>>> def m2(): 2 *2 
>>> dis.dis(m2) 
    1   0 LOAD_CONST    2 (4) 
       3 POP_TOP    
       4 LOAD_CONST    0 (None) 
       7 RETURN_VALUE   

>>> def m3(): 2*5 
>>> dis.dis(m3) 
    1   0 LOAD_CONST    3 (10) 
       3 POP_TOP    
       4 LOAD_CONST    0 (None) 
       7 RETURN_VALUE   

>>> def m4(): 2 > 0 
>>> dis.dis(m4) 
    1   0 LOAD_CONST    1 (2) 
       3 LOAD_CONST    2 (0) 
       6 COMPARE_OP    4 (>) 
       9 POP_TOP    
      10 LOAD_CONST    0 (None) 
      13 RETURN_VALUE   

>>> def m5(): True and False 
>>> dis.dis(m5) 
    1   0 LOAD_GLOBAL    0 (True) 
       3 JUMP_IF_FALSE_OR_POP  9 
       6 LOAD_GLOBAL    1 (False) 
     >> 9 POP_TOP    
      10 LOAD_CONST    0 (None) 
      13 RETURN_VALUE   
+0

Jestem zaskoczony, że optymalizator wizjera nie zmniejsza znanych warunków, szczególnie biorąc pod uwagę, że pozwoliłoby to na martwe rozgałęzienia. Dobre użycie dis –

+1

@ JonChesterfield jest zaskoczeniem, że optymalizator zwierciadła nie redukuje znanych czynników warunkowych: Cóż, ja też. Ale biorąc pod uwagę, że nierówność i inne tego rodzaju wyrażenia mogą być używane na wszelkiego rodzaju obiektach w świecie Python, być może, zostawiając je kompilator byłby bardziej przydatny w przykładach kodu rzeczywistego. –

+0

To może być warte osobnego pytania. Nie mogę wymyślić przyczyny, dla której 2 <2 nie może zostać statycznie rozwiązane. Być może Python pozwala użytkownikowi zastąpić '__LT__' dla wbudowanych typów, lub może to tylko brakujący przypadek w optymalizatorze. –

4

Szybkie disassambling ujawnia, że ​​porównanie dotyczy więcej operacji. Według this answer, istnieją pewne precalculation zrobione przez "peephole optimiser" (wiki) dla mnożenia, dodawania, etc., ale nie dla operatorów porównania:

>>> import dis 
>>> def a(): 
... return 2*3 
... 
>>> dis.dis(a) 
    2   0 LOAD_CONST    3 (6) 
       3 RETURN_VALUE 
>>> def b(): 
... return 2 < 3 
... 
>>> dis.dis(b) 
    2   0 LOAD_CONST    1 (2) 
       3 LOAD_CONST    2 (3) 
       6 COMPARE_OP    0 (<) 
       9 RETURN_VALUE 
4

Podobnie jak inni pisali - to ze względu na otwór optymalizator peep który wstępnie oblicza wyniki 2 * 3 (6). Jak dis pokazuje

0 LOAD_CONST    3 (6) 

Ale spróbuj tego - będzie wyłączyć optymalizator od wstępnego obliczania wyników

>>> def a(a, b): 
...  return a*b 
... 
>>> dis.dis(a) 
    2   0 LOAD_FAST    0 (a) 
       3 LOAD_FAST    1 (b) 
       6 BINARY_MULTIPLY 
       7 RETURN_VALUE 
>>> def c(a,b): 
...  return a<b 
... 
>>> dis.dis(c) 
    2   0 LOAD_FAST    0 (a) 
       3 LOAD_FAST    1 (b) 
       6 COMPARE_OP    0 (<) 
       9 RETURN_VALUE 
>>> 

Jeśli czas te funkcje powinny być porównanie będzie szybciej.

2

Dla przypadku Pythona powyższe odpowiedzi są poprawne. Kod maszynowy jest nieco bardziej skomplikowany. Zakładam, że mówimy tutaj o operacjach liczb całkowitych, przy użyciu obiektów typu "float" i obiektów złożonych, żadne z poniższych nie będzie miało zastosowania. Zakładamy również, że wartości, które porównujesz, są już załadowane do rejestrów. Jeśli nie są one pobierane z dowolnego miejsca, mogą trwać 100 razy dłużej niż rzeczywiste operacje. Nowoczesne procesory mają wiele sposobów porównywania dwóch liczb. Bardzo popularne robią XOR a, b, jeśli chcesz tylko sprawdzić, czy dwie wartości są równe, czy CMP a, b, jeśli chcesz poznać relację między wartościami (mniej, więcej, równiej, itd.). Operacja CMP to tylko odjęcie z wynikiem odrzuconym, ponieważ interesują nas tylko flagi pooperacyjne.

Obie te operacje mają głębokość 1, więc można je wykonać w jednym cyklu procesora. Jest to tak szybkie, jak tylko możesz. Mnożenie jest formą powtarzających się uzupełnień, więc głębokość operacji jest zwykle równa wielkości twojego rejestru.Istnieją pewne optymalizacje, które można wprowadzić w celu zmniejszenia głębokości, ale ogólnie mnożenie jest jedną z wolniejszych operacji, które może wykonywać procesor.

Jednak pomnożenie przez 0,1 lub dowolną potęgę 2 można zredukować do operacji zmiany. Co jest również głębokością jednej operacji. Więc zajmuje to samo porównanie dwóch liczb. Pomyśl o systemie dziesiętnym, możesz pomnożyć dowolną liczbę przez 10, 100, 1000 przez dodanie zer na końcu numeru. Każdy kompilator optymalizacyjny rozpozna ten typ mnożenia i użyje dla niego najbardziej wydajnej operacji. Nowoczesne procesory są również bardzo zaawansowane, więc mogą wykonać tę samą optymalizację sprzętu, licząc ile bitów jest ustawionych w dowolnym z operandów. A jeśli to tylko jeden bit, operacja zostanie zredukowana do zmiany.

W twoim przypadku pomnożenie przez 2 jest tak szybkie, jak porównywanie dwóch liczb. Jak już wspomniano powyżej, każdy kompilator optymalizujący zobaczy, że mnożysz dwie stałe, więc zastąpi ona tylko zastąpi funkcję zwracając stałą.

8

Jak wyjaśnili inni, dzieje się tak dlatego, że optymalizator okularów Pythona optymalizuje operacje arytmetyczne, ale nie dokonuje porównań.

Po napisaniu własnego optymalizatora wizjera dla podstawowego kompilatora, mogę zapewnić, że optymalizacja stałych porównań jest równie łatwa jak optymalizacja stałych operacji arytmetycznych. Nie ma więc żadnego technicznego powodu, dla którego Python powinien to robić, ale nie ten pierwszy.

Jednak każda taka optymalizacja musi być oddzielnie zaprogramowana i wiąże się z dwoma kosztami: czasem jej zaprogramowania oraz dodatkowym kodem optymalizacyjnym zajmującym miejsce w pliku wykonywalnym Pythona. Więc musisz zrobić kilka triage: która z tych optymalizacji jest dość powszechna, aby opłacić koszty?

Wygląda na to, że osoby wdrażające Python, w miarę możliwości, zdecydowały się najpierw zoptymalizować operacje arytmetyczne. Być może przejdą do porównań w przyszłym wydaniu.

+2

Warto zauważyć, że w Pythonie 2 operacja 'True! = False' i' True and False' nie może być zoptymalizowana w ten sposób, ponieważ zarówno 'True' i' False' mogą zostać zdefiniowane na nowo, więc te globale muszą być podnosił wzrok za każdym razem, gdy był wykonywany. W pythonie 3 słowa "prawda" i "fałsz" są słowami kluczowymi i nie można ich przedefiniować. –

+0

Dzięki @Amanda, nie wiedziałem o tym. Ciekawe, że czasy Pythona 3 w OP pomijają przypadki Prawda i Fałsz. – TonyK

+0

Istnieje również trzeci koszt - czas potrzebny na faktyczne wykonanie optymalizacji za każdym razem, gdy źródło jest kompilowane (co w pewnych okolicznościach może być za każdym razem, gdy program jest uruchamiany). :) – psmears

1

Wow, odpowiedź @mu 無 rozwaliła mój umysł! Jednak ważne jest, aby nie generalizować podczas wyciągania wniosków ... Sprawdzasz czasy dla CONSTANTS nie zmiennych. W przypadku zmiennych mnożenie wydaje się wolniejsze niż porównanie.

Oto bardziej interesująca sprawa, w której numery porównywane są przechowywane w zmiennych rzeczywistych ...

import timeit 
def go(): 
    number=1000000000 
    print 
    print 'a>b, internal:',timeit.timeit(setup="a=1;b=1", stmt="a>b", number=number) 
    print 'a*b, internal:',timeit.timeit(setup="a=1;b=1", stmt="a*b", number=number) 
    print 'a>b, shell :', 
    %%timeit -n 1000000000 "a=1;b=1" "a>b" 
    print 'a*b, shell :', 
    %%timeit -n 1000000000 "a=1;b=1" "a*b" 
go() 

Wynik otrzymujemy:

a>b, internal: 51.9467676445 
a*b, internal: 63.870462403 
a>b, shell :1000000000 loops, best of 3: 19.8 ns per loop 
a>b, shell :1000000000 loops, best of 3: 19.9 ns per loop 

i porządek zostanie przywrócony w wszechświat;)

Dla kompletności, pozwala zobaczyć więcej przypadków ... A jeśli mamy jedną zmienną i jedną stałą?

import timeit 
def go(): 
    print 'a>2, shell :', 
    %%timeit -n 10000000 "a=42" "a>2" 
    print 'a*2, shell :', 
    %%timeit -n 10000000 "a=42" "a*2" 
go() 

a>2, shell :10000000 loops, best of 3: 18.3 ns per loop 
a*2, shell :10000000 loops, best of 3: 19.3 ns per loop 

co dzieje się z boolami?

import timeit 
def go(): 
    print 
    number=1000000000 
    print 'a==b : ', timeit.timeit(setup="a=True;b=False",stmt="a==b",number=number) 
    print 'a and b : ', timeit.timeit(setup="a=True;b=False",stmt="a and b",number=number) 
    print 'boolean ==, shell :', 
    %%timeit -n 1000000000 "a=True;b=False" "a == b" 
    print 'boolean and, shell :', 
    %%timeit -n 1000000000 "a=False;b=False" "a and b" 
go() 

a==b : 70.8013108982 
a and b : 38.0614485665 
boolean ==, shell :1000000000 loops, best of 3: 17.7 ns per loop 
boolean and, shell :1000000000 loops, best of 3: 16.4 ns per loop 

: D Teraz to jest interesujące wydaje logiczną i jest szybszy niż ==. Jednak wszystko to byłoby w porządku, ponieważ Donald Knuth nie straciłby snu, najlepszym sposobem porównania byłoby użycie i ...

W praktyce powinniśmy sprawdzić numpy, co może być jeszcze bardziej znaczące ...

import timeit 
def go(): 
    number=1000000 # change if you are in a hurry/ want to be more certain.... 
    print '==== int ====' 
    print 'a>b : ', timeit.timeit(setup="a=1;b=2",stmt="a>b",number=number*100) 
    print 'a*b : ', timeit.timeit(setup="a=1;b=2",stmt="a*b",number=number*100) 
    setup = "import numpy as np;a=np.arange(0,100);b=np.arange(100,0,-1);" 
    print 'np: a>b : ', timeit.timeit(setup=setup,stmt="a>b",number=number) 
    print 'np: a*b : ', timeit.timeit(setup=setup,stmt="a*b",number=number) 
    print '==== float ====' 
    print 'float a>b : ', timeit.timeit(setup="a=1.1;b=2.3",stmt="a>b",number=number*100) 
    print 'float a*b : ', timeit.timeit(setup="a=1.1;b=2.3",stmt="a*b",number=number*100) 
    setup = "import numpy as np;a=np.arange(0,100,dtype=float);b=np.arange(100,0,-1,dtype=float);" 
    print 'np float a>b : ', timeit.timeit(setup=setup,stmt="a>b",number=number) 
    print 'np float a*b : ', timeit.timeit(setup=setup,stmt="a*b",number=number) 
    print '==== bool ====' 
    print 'a==b : ', timeit.timeit(setup="a=True;b=False",stmt="a==b",number=number*1000) 
    print 'a and b : ', timeit.timeit(setup="a=True;b=False",stmt="a and b",number=number*1000) 
    setup = "import numpy as np;a=np.arange(0,100)>50;b=np.arange(100,0,-1)>50;" 
    print 'np a == b : ', timeit.timeit(setup=setup,stmt="a == b",number=number) 
    print 'np a and b : ', timeit.timeit(setup=setup,stmt="np.logical_and(a,b)",number=number) 
    print 'np a == True : ', timeit.timeit(setup=setup,stmt="a == True",number=number) 
    print 'np a and True : ', timeit.timeit(setup=setup,stmt="np.logical_and(a,True)",number=number) 
go() 

==== int ==== 
a>b : 4.5121130192 
a*b : 5.62955748632 
np: a>b : 0.763992986986 
np: a*b : 0.723006032235 
==== float ==== 
float a>b : 6.39567713272 
float a*b : 5.62149055215 
np float a>b : 0.697037433398 
np float a*b : 0.847941712765 
==== bool ==== 
a==b : 6.91458288689 
a and b : 3.6289697892 
np a == b : 0.789666454087 
np a and b : 0.724517620007 
np a == True : 1.55066706189 
np a and True : 1.44293071804 

Znowu to samo zachowanie ... Więc myślę, można korzystać używając zamiast za == w ogóle,

przynajmniej w 2 Pythona (Python 2.4.1 2.7.11 | Anaconda (64-bitowy) | (domyślnie, 16 lutego 2016, 09:58:36) [MSC v.1500 64-bitowy (AMD64)]), gdzie wypróbowałem wszystkie te ...

Powiązane problemy