Dlaczego mój program działa tak wolno?

Question

Ktoś postanowił zrobić szybki test, aby zobaczyć, jak natywny klient porównuje javascript pod względem szybkości. Zrobili to, wykonując 10 000 000 obliczeń sqrt i mierząc czas, który zajęli. Wynik z javascript: 0,096 sekundy, a NaCl: 4,241 sekund ... Jak to możliwe? Czy szybkość nie jest jedną z przyczyn używania NaCl w pierwszej kolejności? Czy też brakuje niektórych flag kompilatora lub czegoś podobnego?

Herezje kod, który został uruchomiony:

clock_t t = clock(); 
float result = 0; 
for(int i = 0; i < 10000000; ++i) { 
    result += sqrt(i); 
} 
t = clock() - t;  
float tt = ((float)t)/CLOCKS_PER_SEC; 
pp::Var var_reply = pp::Var(tt); 
PostMessage(var_reply); 

PS: To pytanie jest edytowany wersja czegoś, co pojawiło się w native client mailing list

Answer 1

UWAGA: Ta odpowiedź jest edytowany wersja czegoś, co pojawiło się w Identyfikatory mikrobokacji są trudne: o ile nie wiesz, co robisz BARDZO dobrze, łatwo jest porównywać jabłka z pomarańczami, które nie mają związku z zachowaniem, które chcesz obserwować. rve/środek w ogóle.

Opracuję trochę za pomocą własnego przykładu (będę wykluczać NaCl i trzymać się istniejących, "wypróbowanych i prawdziwych" technologii).

Oto nasz test jako zwykłego programu C:

$ cat test1.c 
#include <math.h> 
#include <time.h> 
#include <stdio.h> 

int main() { 
    clock_t t = clock(); 
    float result = 0; 
    for(int i = 0; i < 1000000000; ++i) { 
     result += sqrt(i); 
    } 
    t = clock() - t; 
    float tt = ((float)t)/CLOCKS_PER_SEC; 
    printf("%g %g\n", result, tt); 

} 
$ gcc -std=c99 -O2 test1.c -lm -o test1 
$ ./test1 
5.49756e+11 25.43 

Ok. Możemy wykonać miliard cykli w 25,43 sekund. Ale zobaczmy, co wymaga czasu: zastąpmy "wynik + = sqrt (i);" z "result + = i;"

$ cat test2.c 
#include <math.h> 
#include <time.h> 
#include <stdio.h> 

int main() { 
    clock_t t = clock(); 
    float result = 0; 
    for(int i = 0; i < 1000000000; ++i) { 
     result += i; 
    } 
    t = clock() - t; 
    float tt = ((float)t)/CLOCKS_PER_SEC; 
    printf("%g %g\n", result, tt); 
} 
$ gcc -std=c99 -O2 test2.c -lm -o test2 
$ ./test2 
1.80144e+16 1.21 

Wow! 95% czasu faktycznie spędził w funkcji sqrt dostarczonej przez CPU, wszystko inne zajęło mniej niż 5%. Ale co, jeśli zmienimy nieco kod: zastąp "printf ("% g% g \ n ", wynik, tt);" z "printf ("% g \ n ", tt);" ?

$ cat test3.c 
#include <math.h> 
#include <time.h> 
#include <stdio.h> 

int main() { 
    clock_t t = clock(); 
    float result = 0; 
    for(int i = 0; i < 1000000000; ++i) { 
     result += sqrt(i); 
    } 
    t = clock() - t; 
    float tt = ((float)t)/CLOCKS_PER_SEC; 
    printf("%g\n", tt); 
} 
$ gcc -std=c99 -O2 test3.c -lm -o test3 
$ ./test 
1.44 

Hmm ... Wygląda na to, że "sqrt" jest prawie tak szybki jak "+". Jak to może być? W jaki sposób printf może mieć wpływ na poprzedni cykl?

Zobaczmy:

$ gcc -std=c99 -O2 test1.c -S -o - 
... 
.L3: 
     cvtsi2sd  %ebp, %xmm1 
     sqrtsd %xmm1, %xmm0 
     ucomisd %xmm0, %xmm0 
     jp  .L7 
     je  .L2 
.L7: 
     movapd %xmm1, %xmm0 
     movss %xmm2, (%rsp) 
     call sqrt 
     movss (%rsp), %xmm2 
.L2: 
     unpcklps  %xmm2, %xmm2 
     addl $1, %ebp 
     cmpl $1000000000, %ebp 
     cvtps2pd  %xmm2, %xmm2 
     addsd %xmm0, %xmm2 
     unpcklpd  %xmm2, %xmm2 
     cvtpd2ps  %xmm2, %xmm2 
     jne  .L3 
... 
$ gcc -std=c99 -O2 test3.c -S -o - 
... 
     xorpd %xmm1, %xmm1 
... 
.L5: 
     cvtsi2sd  %ebp, %xmm0 
     ucomisd %xmm0, %xmm1 
     ja  .L14 
.L10: 
     addl $1, %ebp 
     cmpl $1000000000, %ebp 
     jne  .L5 
... 
.L14: 
     sqrtsd %xmm0, %xmm2 
     ucomisd %xmm2, %xmm2 
     jp  .L12 
     .p2align 4,,2 
     je  .L10 
.L12: 
     movsd %xmm1, (%rsp) 
     .p2align 4,,5 
     call sqrt 
     movsd (%rsp), %xmm1 
     .p2align 4,,4 
     jmp  .L10 
... 

Pierwsza wersja faktycznie nazywa sqrt miliard razy, ale drugi nie robi tego w ogóle! Zamiast tego sprawdza, czy liczba jest ujemna i wywołuje sqrt tylko w tym przypadku! Czemu? Co próbują zrobić tutaj kompilator (a raczej autorzy kompilacji)?

Cóż, to proste: skoro nie używaliśmy "wyniku" w tej konkretnej wersji, możemy bezpiecznie pominąć wywołanie "sqrt" ... jeśli wartość nie jest ujemna, to jest! Jeśli jest ujemna, to (w zależności od flag FPU) sqrt może robić różne rzeczy (zwracać nonsensowne wyniki, awarię programu itp.). Dlatego ta wersja jest tuzin razy szybsza - ale w ogóle nie oblicza pierwiastków kwadratowych!

Oto ostatni przykład, który pokazuje, jak źle microbenchmarks może pójść:

$ cat test4.c 
#include <math.h> 
#include <time.h> 
#include <stdio.h> 

int main() { 
    clock_t t = clock(); 
    int result = 0; 
    for(int i = 0; i < 1000000000; ++i) { 
     result += 2; 
    } 
    t = clock() - t; 
    float tt = ((float)t)/CLOCKS_PER_SEC; 
    printf("%d %g\n", result, tt); 
} 
$ gcc -std=c99 -O2 test4.c -lm -o test4 
$ ./test4 
2000000000 0 

czas wykonywania jest ... ZERO? Jak to możliwe? Obliczenia miliardowe za mniej niż mrugnięcie oka? Zobaczmy:

$ gcc -std=c99 -O2 test1.c -S -o - 
... 
     call clock 
     movq %rax, %rbx 
     call clock 
     subq %rbx, %rax 
     movl $2000000000, %edx 
     movl $.LC1, %esi 
     cvtsi2ssq  %rax, %xmm0 
     movl $1, %edi 
     movl $1, %eax 
     divss .LC0(%rip), %xmm0 
     unpcklps  %xmm0, %xmm0 
     cvtps2pd  %xmm0, %xmm0 
... 

Uh, o, cykl jest całkowicie wyeliminowany!Wszystkie obliczenia miały miejsce podczas kompilacji i aby dodać obrażenie do obrażeń, oba "zegary" zostały wykonane przed rozpoczęciem cyklu!

Co zrobić, jeśli wprowadzimy to w oddzielnej funkcji?

$ cat test5.c 
#include <math.h> 
#include <time.h> 
#include <stdio.h> 

int testfunc(int num, int max) { 
    int result = 0; 
    for(int i = 0; i < max; ++i) { 
     result += num; 
    } 
    return result; 
} 

int main() { 
    clock_t t = clock(); 
    int result = testfunc(2, 1000000000); 
    t = clock() - t; 
    float tt = ((float)t)/CLOCKS_PER_SEC; 
    printf("%d %g\n", result, tt); 
} 
$ gcc -std=c99 -O2 test5.c -lm -o test5 
$ ./test5 
2000000000 0 

Wciąż to samo ??? Jak to może być?

$ gcc -std=c99 -O2 test5.c -S -o - 
... 
.globl testfunc 
     .type testfunc, @function 
testfunc: 
.LFB16: 
     .cfi_startproc 
     xorl %eax, %eax 
     testl %esi, %esi 
     jle  .L3 
     movl %esi, %eax 
     imull %edi, %eax 
.L3: 
     rep 
     ret 
     .cfi_endproc 
... 

Uh-oh: kompilator jest wystarczająco inteligentny, aby zastąpić cykl mnożeniem!

Teraz, jeśli dodasz NaCl po jednej stronie i JavaScript po drugiej stronie, dostaniesz tak złożony system, że wyniki są dosłownie nieprzewidywalne.

Problem polega na tym, że dla microbenchmark próbujesz wyizolować fragment kodu, a następnie ocenić jego właściwości, ale wtedy kompilator (bez względu na JIT lub AOT) spróbuje udaremnić twoje wysiłki, ponieważ próbuje usunąć wszystkie bezużyteczne obliczenia ze swojego programu!

Mikrobacele są użyteczne, oczywiście, ale są narzędziem ANALIZY FORENSYCZNEJ, a nie czymś, co chcesz wykorzystać do porównania prędkości dwóch różnych systemów! Do tego potrzebne są niektóre "rzeczywiste" (w pewnym sensie świata: coś, czego nie można zoptymalizować na części przez nadmiernie zużywający się kompilator) obciążenie pracą: w szczególności popularne są algorytmy sortujące.

Wartości wzorcowe, które używają sqrt są szczególnie nieprzyjemne, ponieważ, jak widzieliśmy, zazwyczaj spędzają ponad 90% czasu na wykonaniu jednej instrukcji CPU: sqrtsd (fsqrt, jeśli jest to wersja 32-bitowa), która jest oczywiście identyczna dla JavaScript i NaCl. Te testy porównawcze (jeśli są właściwie zaimplementowane) mogą służyć jako test lakmusowy (jeśli prędkość jakiejś implementacji różni się zbytnio od prostej wersji natywnej, to robisz coś źle), ale są one bezużyteczne jako porównanie prędkości NaCl, JavaScript, C# lub Visual Basic.