Zamiast spekulować na temat tego, co może się zdarzyć, a co nie, spójrzmy, prawda? Będę musiał użyć C ++, ponieważ nie mam przydatnego kompilatora C # (chociaż zobacz przykład C # z VisualMelon ), ale jestem pewien, że te same zasady obowiązują niezależnie.
Uwzględnimy dwie alternatywy napotkane w wywiadzie. Uwzględnimy również wersję, która używa abszgodnie z sugestiami niektórych odpowiedzi.
#include <cstdlib>
bool IsSumInRangeWithVar(int a, int b)
{
int s = a + b;
if (s > 1000 || s < -1000) return false;
else return true;
}
bool IsSumInRangeWithoutVar(int a, int b)
{
if (a + b > 1000 || a + b < -1000) return false;
else return true;
}
bool IsSumInRangeSuperOptimized(int a, int b) {
return (abs(a + b) < 1000);
}
Teraz skompiluj go bez jakiejkolwiek optymalizacji: g++ -c -o test.o test.cpp
Teraz możemy dokładnie zobaczyć, co to generuje: objdump -d test.o
0000000000000000 <_Z19IsSumInRangeWithVarii>:
0: 55 push %rbp # begin a call frame
1: 48 89 e5 mov %rsp,%rbp
4: 89 7d ec mov %edi,-0x14(%rbp) # save first argument (a) on stack
7: 89 75 e8 mov %esi,-0x18(%rbp) # save b on stack
a: 8b 55 ec mov -0x14(%rbp),%edx # load a and b into edx
d: 8b 45 e8 mov -0x18(%rbp),%eax # load b into eax
10: 01 d0 add %edx,%eax # add a and b
12: 89 45 fc mov %eax,-0x4(%rbp) # save result as s on stack
15: 81 7d fc e8 03 00 00 cmpl $0x3e8,-0x4(%rbp) # compare s to 1000
1c: 7f 09 jg 27 # jump to 27 if it's greater
1e: 81 7d fc 18 fc ff ff cmpl $0xfffffc18,-0x4(%rbp) # compare s to -1000
25: 7d 07 jge 2e # jump to 2e if it's greater or equal
27: b8 00 00 00 00 mov $0x0,%eax # put 0 (false) in eax, which will be the return value
2c: eb 05 jmp 33 <_Z19IsSumInRangeWithVarii+0x33>
2e: b8 01 00 00 00 mov $0x1,%eax # put 1 (true) in eax
33: 5d pop %rbp
34: c3 retq
0000000000000035 <_Z22IsSumInRangeWithoutVarii>:
35: 55 push %rbp
36: 48 89 e5 mov %rsp,%rbp
39: 89 7d fc mov %edi,-0x4(%rbp)
3c: 89 75 f8 mov %esi,-0x8(%rbp)
3f: 8b 55 fc mov -0x4(%rbp),%edx
42: 8b 45 f8 mov -0x8(%rbp),%eax # same as before
45: 01 d0 add %edx,%eax
# note: unlike other implementation, result is not saved
47: 3d e8 03 00 00 cmp $0x3e8,%eax # compare to 1000
4c: 7f 0f jg 5d <_Z22IsSumInRangeWithoutVarii+0x28>
4e: 8b 55 fc mov -0x4(%rbp),%edx # since s wasn't saved, load a and b from the stack again
51: 8b 45 f8 mov -0x8(%rbp),%eax
54: 01 d0 add %edx,%eax
56: 3d 18 fc ff ff cmp $0xfffffc18,%eax # compare to -1000
5b: 7d 07 jge 64 <_Z22IsSumInRangeWithoutVarii+0x2f>
5d: b8 00 00 00 00 mov $0x0,%eax
62: eb 05 jmp 69 <_Z22IsSumInRangeWithoutVarii+0x34>
64: b8 01 00 00 00 mov $0x1,%eax
69: 5d pop %rbp
6a: c3 retq
000000000000006b <_Z26IsSumInRangeSuperOptimizedii>:
6b: 55 push %rbp
6c: 48 89 e5 mov %rsp,%rbp
6f: 89 7d fc mov %edi,-0x4(%rbp)
72: 89 75 f8 mov %esi,-0x8(%rbp)
75: 8b 55 fc mov -0x4(%rbp),%edx
78: 8b 45 f8 mov -0x8(%rbp),%eax
7b: 01 d0 add %edx,%eax
7d: 3d 18 fc ff ff cmp $0xfffffc18,%eax
82: 7c 16 jl 9a <_Z26IsSumInRangeSuperOptimizedii+0x2f>
84: 8b 55 fc mov -0x4(%rbp),%edx
87: 8b 45 f8 mov -0x8(%rbp),%eax
8a: 01 d0 add %edx,%eax
8c: 3d e8 03 00 00 cmp $0x3e8,%eax
91: 7f 07 jg 9a <_Z26IsSumInRangeSuperOptimizedii+0x2f>
93: b8 01 00 00 00 mov $0x1,%eax
98: eb 05 jmp 9f <_Z26IsSumInRangeSuperOptimizedii+0x34>
9a: b8 00 00 00 00 mov $0x0,%eax
9f: 5d pop %rbp
a0: c3 retq
Widzimy na podstawie adresów stosu (na przykład -0x4in mov %edi,-0x4(%rbp)versus -0x14in mov %edi,-0x14(%rbp)), który IsSumInRangeWithVar()wykorzystuje 16 dodatkowych bajtów na stosie.
Ponieważ IsSumInRangeWithoutVar()nie przydziela miejsca na stosie do przechowywania wartości pośredniej s, musi go ponownie obliczyć, co powoduje, że ta implementacja jest o 2 instrukcje dłuższa.
Zabawne, IsSumInRangeSuperOptimized()wygląda bardzo podobnie IsSumInRangeWithoutVar(), z tym, że najpierw porównuje do -1000 i 1000 sekund.
Teraz skompilować tylko najbardziej podstawowych optymalizacje: g++ -O1 -c -o test.o test.cpp. Wynik:
0000000000000000 <_Z19IsSumInRangeWithVarii>:
0: 8d 84 37 e8 03 00 00 lea 0x3e8(%rdi,%rsi,1),%eax
7: 3d d0 07 00 00 cmp $0x7d0,%eax
c: 0f 96 c0 setbe %al
f: c3 retq
0000000000000010 <_Z22IsSumInRangeWithoutVarii>:
10: 8d 84 37 e8 03 00 00 lea 0x3e8(%rdi,%rsi,1),%eax
17: 3d d0 07 00 00 cmp $0x7d0,%eax
1c: 0f 96 c0 setbe %al
1f: c3 retq
0000000000000020 <_Z26IsSumInRangeSuperOptimizedii>:
20: 8d 84 37 e8 03 00 00 lea 0x3e8(%rdi,%rsi,1),%eax
27: 3d d0 07 00 00 cmp $0x7d0,%eax
2c: 0f 96 c0 setbe %al
2f: c3 retq
Spójrz na to: każdy wariant jest identyczny . Kompilator jest w stanie zrobić coś całkiem sprytnego: abs(a + b) <= 1000jest równoznaczny z a + b + 1000 <= 2000rozważeniem setbewykonania niepodpisanego porównania, więc liczba ujemna staje się bardzo dużą liczbą dodatnią. leaInstrukcja może rzeczywiście wykonać te wszystkie dodatki w jednej instrukcji i wyeliminować wszystkie gałęzie warunkowe.
Aby odpowiedzieć na twoje pytanie, prawie zawsze optymalizacją jest nie pamięć lub szybkość, ale czytelność . Czytanie kodu jest o wiele trudniejsze niż jego pisanie, a czytanie kodu, który został zmodyfikowany w celu „optymalizacji”, jest o wiele trudniejsze niż czytanie kodu, który został napisany dla jasności. Te „optymalizacje” najczęściej są nieistotne lub, jak w tym przypadku, dokładnie zero rzeczywistego wpływu na wydajność.
W odpowiedzi na pytanie, co się zmienia, gdy ten kod jest w języku interpretowanym zamiast kompilowanym? Czy zatem optymalizacja ma znaczenie, czy ma taki sam wynik?
Zmierzmy! Transkrybowałem przykłady do Pythona:
def IsSumInRangeWithVar(a, b):
s = a + b
if s > 1000 or s < -1000:
return False
else:
return True
def IsSumInRangeWithoutVar(a, b):
if a + b > 1000 or a + b < -1000:
return False
else:
return True
def IsSumInRangeSuperOptimized(a, b):
return abs(a + b) <= 1000
from dis import dis
print('IsSumInRangeWithVar')
dis(IsSumInRangeWithVar)
print('\nIsSumInRangeWithoutVar')
dis(IsSumInRangeWithoutVar)
print('\nIsSumInRangeSuperOptimized')
dis(IsSumInRangeSuperOptimized)
print('\nBenchmarking')
import timeit
print('IsSumInRangeWithVar: %fs' % (min(timeit.repeat(lambda: IsSumInRangeWithVar(42, 42), repeat=50, number=100000)),))
print('IsSumInRangeWithoutVar: %fs' % (min(timeit.repeat(lambda: IsSumInRangeWithoutVar(42, 42), repeat=50, number=100000)),))
print('IsSumInRangeSuperOptimized: %fs' % (min(timeit.repeat(lambda: IsSumInRangeSuperOptimized(42, 42), repeat=50, number=100000)),))
Uruchom z Python 3.5.2, to generuje dane wyjściowe:
IsSumInRangeWithVar
2 0 LOAD_FAST 0 (a)
3 LOAD_FAST 1 (b)
6 BINARY_ADD
7 STORE_FAST 2 (s)
3 10 LOAD_FAST 2 (s)
13 LOAD_CONST 1 (1000)
16 COMPARE_OP 4 (>)
19 POP_JUMP_IF_TRUE 34
22 LOAD_FAST 2 (s)
25 LOAD_CONST 4 (-1000)
28 COMPARE_OP 0 (<)
31 POP_JUMP_IF_FALSE 38
4 >> 34 LOAD_CONST 2 (False)
37 RETURN_VALUE
6 >> 38 LOAD_CONST 3 (True)
41 RETURN_VALUE
42 LOAD_CONST 0 (None)
45 RETURN_VALUE
IsSumInRangeWithoutVar
9 0 LOAD_FAST 0 (a)
3 LOAD_FAST 1 (b)
6 BINARY_ADD
7 LOAD_CONST 1 (1000)
10 COMPARE_OP 4 (>)
13 POP_JUMP_IF_TRUE 32
16 LOAD_FAST 0 (a)
19 LOAD_FAST 1 (b)
22 BINARY_ADD
23 LOAD_CONST 4 (-1000)
26 COMPARE_OP 0 (<)
29 POP_JUMP_IF_FALSE 36
10 >> 32 LOAD_CONST 2 (False)
35 RETURN_VALUE
12 >> 36 LOAD_CONST 3 (True)
39 RETURN_VALUE
40 LOAD_CONST 0 (None)
43 RETURN_VALUE
IsSumInRangeSuperOptimized
15 0 LOAD_GLOBAL 0 (abs)
3 LOAD_FAST 0 (a)
6 LOAD_FAST 1 (b)
9 BINARY_ADD
10 CALL_FUNCTION 1 (1 positional, 0 keyword pair)
13 LOAD_CONST 1 (1000)
16 COMPARE_OP 1 (<=)
19 RETURN_VALUE
Benchmarking
IsSumInRangeWithVar: 0.019361s
IsSumInRangeWithoutVar: 0.020917s
IsSumInRangeSuperOptimized: 0.020171s
Dezasemblacja w Pythonie nie jest szczególnie interesująca, ponieważ „kompilator” kodu bajtowego nie robi wiele w zakresie optymalizacji.
Wydajność trzech funkcji jest prawie identyczna. Możemy mieć ochotę iść ze IsSumInRangeWithVar()względu na jego krańcowy wzrost prędkości. Chociaż dodam, że próbowałem różnych parametrów timeit, czasem IsSumInRangeSuperOptimized()wychodziło to szybciej, więc podejrzewam, że mogą to być czynniki zewnętrzne odpowiedzialne za różnicę, a nie jakakolwiek istotna zaleta jakiejkolwiek implementacji.
Jeśli jest to naprawdę kod krytyczny pod względem wydajności, interpretowany język jest po prostu bardzo złym wyborem. Uruchamiając ten sam program z pypy, otrzymuję:
IsSumInRangeWithVar: 0.000180s
IsSumInRangeWithoutVar: 0.001175s
IsSumInRangeSuperOptimized: 0.001306s
Samo użycie pypy, które wykorzystuje kompilację JIT w celu wyeliminowania dużej części obciążenia interpretera, przyniosło poprawę wydajności o 1 lub 2 rzędy wielkości. Byłem bardzo zszokowany, widząc, że IsSumInRangeWithVar()jest o rząd wielkości szybszy od innych. Zmieniłem więc kolejność testów porównawczych i uruchomiłem ponownie:
IsSumInRangeSuperOptimized: 0.000191s
IsSumInRangeWithoutVar: 0.001174s
IsSumInRangeWithVar: 0.001265s
Wygląda więc na to, że tak naprawdę to nie implementacja sprawia, że jest szybka, ale kolejność, w jakiej przeprowadzam testy porównawcze!
Chciałbym się w to zagłębić głębiej, bo szczerze mówiąc nie wiem, dlaczego tak się dzieje. Uważam jednak, że o to chodzi: mikrooptymalizacje, takie jak to, czy zadeklarować wartość pośrednią jako zmienną, czy nie, są rzadko istotne. W przypadku interpretowanego języka lub wysoce zoptymalizowanego kompilatora pierwszym celem jest nadal pisanie czystego kodu.
Jeśli konieczna może być dalsza optymalizacja, test porównawczy . Pamiętaj, że najlepsze optymalizacje nie wynikają z drobnych szczegółów, ale z większego obrazu algorytmicznego: pypy będzie o rząd wielkości szybszy do powtarzanej oceny tej samej funkcji niż cpython, ponieważ używa szybszych algorytmów (kompilator JIT vs interpretacja) do oceny program. Jest też kodowany algorytm, który należy wziąć pod uwagę: przeszukiwanie drzewa B będzie szybsze niż połączona lista.
Po upewnieniu się, że używasz odpowiednich narzędzi i algorytmów do pracy, przygotuj się na głębsze zanurzenie się w szczegóły systemu. Wyniki mogą być bardzo zaskakujące, nawet dla doświadczonych programistów, i dlatego musisz mieć wzorzec do oceny zmian.