czy kiedy chce zawartość tablicy zwiększyć o 1.
to czy przypisanie do każdej zmiennej po prostu ręcznie będzie szybsze niż w pętli ?
bo nie trzeba sprawdzać warunku żeby przerwać pętlę ?
wydaje mi się że jest to kompromis pomiędzy mniejszą ilością obliczeń a zarezerwowaną pamięcią na instrukcjie.
Pytasz o mikro optymalizację. Przy takich pytaniach warto podać język, rodzaj struktury (jest n rodzajów tablic) i przykładowy kod.
Nie ma na to odpowiedzi uniwersalnej pasującej do każdego języka.
Takimi rzeczami zajmuje się kompilator/interpreter.
int t[4];
for(int i=0i<4;i++){
t[i]++;
}
czy
t[0]++;t[1]++;t[2]++;t[3]++;
Tak naprawdę to bez znaczenia, jeśli chodzi o szybkość. A jeśli chodzi o czytelność to 1.
Nic ci to nie da. Na x86, Wykonanie instrukcji loop
to czas nieporównywalnie mały z 2 instrukcjami mov
pamięć-rejestr (i odwrotnie). Poza tym, w dzisiejszych czasach, kompilator ci to zoptymalizuje. Jak się uczysz programować, to już w ogóle zmykaj na jakiś nowoczesny język programowania. :)
nie rozumiem jak nic nie da. pierwszy przykład . pętla for może się nie wykonać ani razu bo jest sprawdzany warunek a on nie pochłania 0 czasu procesora. bez for tego nie było by warunku.
kamil kowalski napisał(a):
nie rozumiem jak nic nie da. pierwszy przykład . pętla for może się nie wykonać ani razu bo jest sprawdzany warunek a on nie pochłania 0 czasu procesora. bez for tego nie było by warunku.
No to zobacz co ci wygeneruje kompilator i porównaj obydwa rozwiązania - ile taktów procesora potrzeb do wykonania tej instrukcji. Zobacz jakie zegary mają aktualnie procesory i czy ma to sens?
// Type your code here, or load an example.
void square(int num) {
int t[4];
t[0]++;
t[1]++;
t[2]++;
t[3]++;
}
square(int):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-20], edi
mov eax, DWORD PTR [rbp-16]
add eax, 1
mov DWORD PTR [rbp-16], eax
mov eax, DWORD PTR [rbp-12]
add eax, 1
mov DWORD PTR [rbp-12], eax
mov eax, DWORD PTR [rbp-8]
add eax, 1
mov DWORD PTR [rbp-8], eax
mov eax, DWORD PTR [rbp-4]
add eax, 1
mov DWORD PTR [rbp-4], eax
nop
pop rbp
ret
// Type your code here, or load an example.
void square(int num) {
int t[4];
for(int i=0;i<4;i++){
t[i]++;
}
}
square(int):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-36], edi
mov DWORD PTR [rbp-4], 0
jmp .L2
.L3:
mov eax, DWORD PTR [rbp-4]
cdqe
mov eax, DWORD PTR [rbp-32+rax4]
lea edx, [rax+1]
mov eax, DWORD PTR [rbp-4]
cdqe
mov DWORD PTR [rbp-32+rax4], edx
add DWORD PTR [rbp-4], 1
.L2:
cmp DWORD PTR [rbp-4], 3
jle .L3
nop
nop
pop rbp
ret
Dla krótkich pętli kompilatory potrafią same rozwijać pętle. GCC ma nawet specjalną opcje -funroll_loops
do tego.
Jeśli to C/C++ to lepiej to zostaw kompilatorowi.
Jeśli naprawdę chcesz to optymalizować ręcznie to raczej musisz mieć ustalony rozmiar tablicy (stały).
I tablica musi być wielkości setek lub tysięcy elementów.
Kilka rozwiązań:
- SIMD intrisinc: https://stackoverflow.com/a/41087832
- openmp:
#pragma omp simd
- intel: #pragma vector always
W dzisiejszym czasach dobrą drogą jest korzystać z tego co udostępnia język. np. iteratorów i tutaj map.
Coraz częściej w kompilatorach zawarte są optymalizacje dotyczących właśnie takich operacji związanych z wektorami. Stosowana jest architektura SIMD https://en.wikipedia.org/wiki/SIMD
Warto poznać co dany język oferuje w tym temacie, bo sporo obliczeń zaczyna być wykonywanych na wektorach.
Z tego co pamiętam w Rust jest to już optymalizowane. w którejś Javie już jest lub będzie i zapewne w innych językach też.
W przypadku pętli - zależnie od kompilatora i sytuacji zysk może być albo zerowy, albo pomijalnie mały. W przypadku iteratorów może to mieć znaczenie ma.
Natomiast jeśli nie jest to problem czysto teoretyczny, a informacja, która według ciebie przyda ci się w rzeczywistości - to źle szukasz.
@kamil kowalski:
testujesz wydajność https://en.wikipedia.org/wiki/Dead_code
kamil kowalski napisał(a):
// Type your code here, or load an example.
void square(int num) {
int t[4];
t[0]++;
t[1]++;
t[2]++;
t[3]++;
}square(int):
push rbp
mov rbp, rsp
mov DWORD PTR [rbp-20], edi
mov eax, DWORD PTR [rbp-16]
(...)
weź włącz jakiekolwiek optymalizacje
z flagą -O1 (najprostsze optymalizacje):
void square(int num) {
int t[4];
t[0]++;
t[1]++;
t[2]++;
t[3]++;
}
daje po kompilacji
square(int):
ret
a
void square(int num) {
int t[4];
for(int i=0;i<4;i++){
t[i]++;
}
}
daje po kompilacji
square(int):
ret
nawet kompilować nie potrafisz
aktualizacja:
tak się włącza podstawowe optymalizacje (-O1
), ale tryb release to -O2
albo -O3
(albo może i więcej, np: -Ofast
albo jakieś dodatkowe flagi)
Robert Karpiński napisał(a):
Warto poznać co dany język oferuje w tym temacie, bo sporo obliczeń zaczyna być wykonywanych na wektorach.
Z tego co pamiętam w Rust jest to już optymalizowane. w którejś Javie już jest lub będzie i zapewne w innych językach też.
W zasadzie wszystkie popularne języki kompilowane (zarówno AOT jak i JIT) mają autowektoryzację, czyli taki implicit SIMD. Oprócz tego jest explicit SIMD, czyli np. compiler intrinsics (np. w C++, C#, Ruście, itd) albo jakieś specjalne API do jawnego SIMDa (np. Vector API z https://openjdk.java.net/projects/panama/ albo nieco bardziej niskopoziomowe SIMD API dla innych języków, np. C++ https://github.com/vectorclass , Rust https://github.com/rust-lang/portable-simd , itp itd)
Żeby zyskać na SIMDach to najpierw trzeba ogarnąć podstawowe mechanizmy optymalizacyjne kompilatora i procesora. Inaczej to błądzenie po omacku i setki egzystencjalnych pytań, których można by uniknąć pochylając się nad podstawami.
zrobiłem przykład bez martwego kodu.
bez pętli:
void quad_inc(int * t) {
t[0]++;
t[1]++;
t[2]++;
t[3]++;
}
po kompilacji z -O2
quad_inc(int*):
add DWORD PTR [rdi], 1
add DWORD PTR [rdi+4], 1
add DWORD PTR [rdi+8], 1
add DWORD PTR [rdi+12], 1
ret
po kompilacji z -O3
quad_inc(int*):
movdqu xmm0, XMMWORD PTR [rdi]
paddd xmm0, XMMWORD PTR .LC0[rip]
movups XMMWORD PTR [rdi], xmm0
ret
.LC0:
.long 1
.long 1
.long 1
.long 1
z pętlą:
void quad_inc(int * t) {
for(int i=0;i<4;i++){
t[i]++;
}
}
po kompilacji z -O2
quad_inc(int*):
lea rax, [rdi+16]
.L2:
add DWORD PTR [rdi], 1
add rdi, 4
cmp rdi, rax
jne .L2
ret
po kompilacji z -O3
quad_inc(int*):
movdqu xmm0, XMMWORD PTR [rdi]
paddd xmm0, XMMWORD PTR .LC0[rip]
movups XMMWORD PTR [rdi], xmm0
ret
.LC0:
.long 1
.long 1
.long 1
.long 1
przy użyciu -O3
oba kody wejściowe (z pętlą i bez) dają identyczne kody wynikowe.
bo jest sprawdzany warunek a on nie pochłania 0 czasu procesora.
no ok, ale czy tutaj nie wpadnie branch prediction i ugra na wydajności?
WeiXiao napisał(a):
bo jest sprawdzany warunek a on nie pochłania 0 czasu procesora.
no ok, ale czy tutaj nie wpadnie branch prediction i ugra na wydajności?
niby ugra, ale i tak przykładowe kody w tym wątku są tak prostackie, że nie ma sensu wyciągać z nich daleko idących wniosków
na nowoczesnym procesorze ta pętelka będzie prawdopodobnie tylko ciut wolniejsza od 4-ech instrukcji mov
, ale to niewiele dowodzi
dla laika, najlepszym sposobem na oszacowanie wydajności jest odpalenie kodu w specjalnych środowiskach testowych do mikrobenchmarków:
- dla javy to https://openjdk.java.net/projects/code-tools/jmh/
- dla c++ to nie wiem jaki jest najlepszy czy najczęściej używany, ale znalazłem np. https://github.com/google/benchmark