Tło:
Podczas optymalizacji kodu Pascal za pomocą wbudowanego języka asemblera zauważyłem niepotrzebną MOVinstrukcję i usunąłem ją.
Ku mojemu zaskoczeniu usunięcie niepotrzebnych instrukcji spowodowało spowolnienie programu .
Przekonałem się, że dodanie arbitralnych, bezużytecznych MOVinstrukcji jeszcze bardziej zwiększyło wydajność .
Efekt jest zmienny, a zmiany oparte na kolejności wykonywania: te same niepotrzebne instrukcje transponowane w górę lub w dół o jedną linię powodują spowolnienie .
Rozumiem, że procesor wykonuje wszelkiego rodzaju optymalizacje i usprawnienia, ale wydaje się, że to bardziej czarna magia.
Dane:
Wersja mojego kodu warunkowo kompiluje trzy niepotrzebne operacje w środku pętli, która działa 2**20==1048576razy. (Program otaczający oblicza tylko skróty SHA-256 ).
Wyniki na moim raczej starym komputerze (Intel (R) Core (TM) 2 CPU 6400 @ 2,13 GHz):
avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without: 1836.44 msProgramy były uruchamiane 25 razy w pętli, a kolejność uruchamiania zmieniała się losowo za każdym razem.
Fragment:
{$asmmode intel}
procedure example_junkop_in_sha256;
var s1, t2 : uint32;
begin
// Here are parts of the SHA-256 algorithm, in Pascal:
// s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
// s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
// Here is how I translated them (side by side to show symmetry):
asm
MOV r8d, a ; MOV r9d, e
ROR r8d, 2 ; ROR r9d, 6
MOV r10d, r8d ; MOV r11d, r9d
ROR r8d, 11 {13 total} ; ROR r9d, 5 {11 total}
XOR r10d, r8d ; XOR r11d, r9d
ROR r8d, 9 {22 total} ; ROR r9d, 14 {25 total}
XOR r10d, r8d ; XOR r11d, r9d
// Here is the extraneous operation that I removed, causing a speedup
// s1 is the uint32 variable declared at the start of the Pascal code.
//
// I had cleaned up the code, so I no longer needed this variable, and
// could just leave the value sitting in the r11d register until I needed
// it again later.
//
// Since copying to RAM seemed like a waste, I removed the instruction,
// only to discover that the code ran slower without it.
{$IFDEF JUNKOPS}
MOV s1, r11d
{$ENDIF}
// The next part of the code just moves on to another part of SHA-256,
// maj { r12d } := (a and b) xor (a and c) xor (b and c)
mov r8d, a
mov r9d, b
mov r13d, r9d // Set aside a copy of b
and r9d, r8d
mov r12d, c
and r8d, r12d { a and c }
xor r9d, r8d
and r12d, r13d { c and b }
xor r12d, r9d
// Copying the calculated value to the same s1 variable is another speedup.
// As far as I can tell, it doesn't actually matter what register is copied,
// but moving this line up or down makes a huge difference.
{$IFDEF JUNKOPS}
MOV s1, r9d // after mov r12d, c
{$ENDIF}
// And here is where the two calculated values above are actually used:
// T2 {r12d} := S0 {r10d} + Maj {r12d};
ADD r12d, r10d
MOV T2, r12d
end
end;Spróbuj sam:
Kod jest dostępny online na GitHub, jeśli chcesz go wypróbować samodzielnie.
Moje pytania:
- Dlaczego bezużyteczne kopiowanie zawartości rejestru do pamięci RAM zwiększałoby wydajność?
- Dlaczego ta sama bezużyteczna instrukcja zapewnia przyspieszenie na niektórych liniach, a spowolnienie na innych?
- Czy to zachowanie może być wykorzystane przez kompilator w sposób przewidywalny?
źródło
Odpowiedzi:
Najbardziej prawdopodobną przyczyną poprawy prędkości jest to, że:
Twój Core2 nie prowadzi osobnego rejestru historii dla każdego skoku warunkowego. Zamiast tego zachowuje wspólną historię wszystkich skoków warunkowych. Jedną wadą prognoz globalnych oddziałów jest to, że historia jest rozcieńczana przez nieistotne informacje, jeśli różne skoki warunkowe są nieskorelowane.
Ten samouczek prognozowania gałęzi pokazuje, jak działają bufory predykcji gałęzi. Bufor pamięci podręcznej jest indeksowany przez dolną część adresu instrukcji rozgałęzienia. Działa to dobrze, chyba że dwie ważne nieskorelowane gałęzie mają te same niższe bity. W takim przypadku kończy się aliasing, który powoduje wiele nieprzewidzianych gałęzi (co blokuje potok instrukcji i spowalnia program).
Jeśli chcesz zrozumieć, w jaki sposób nieprzewidywalne oddziały wpływają na wydajność, spójrz na tę doskonałą odpowiedź: https://stackoverflow.com/a/11227902/1001643
Kompilatory zwykle nie mają wystarczającej ilości informacji, aby wiedzieć, które gałęzie będą miały alias i czy te aliasy będą znaczące. Informacje te można jednak ustalić w czasie wykonywania za pomocą narzędzi takich jak Cachegrind i VTune .
źródło
Możesz przeczytać http://research.google.com/pubs/pub37077.html
TL; DR: losowe wstawianie instrukcji nop do programów może łatwo zwiększyć wydajność o 5% lub więcej i nie, kompilatory nie mogą tego łatwo wykorzystać. Zwykle jest to połączenie predykcji rozgałęzienia i zachowania pamięci podręcznej, ale równie dobrze może to być np. Przeciągnięcie stacji rezerwacji (nawet w przypadku braku przerwanych łańcuchów zależności lub oczywistej nadmiernej subskrypcji zasobów).
źródło
Wierzę, że w nowoczesnych procesorach instrukcje montażu są ostatnią widoczną warstwą dla programisty, która udostępnia instrukcje wykonania procesorowi, w rzeczywistości jest to kilka warstw od faktycznego wykonania przez procesor.
Współczesne procesory to hybrydy RISC / CISC, które tłumaczą instrukcje CISC x86 na instrukcje wewnętrzne bardziej zachowujące się w RISC. Dodatkowo dostępne są analizatory wykonania poza kolejnością, predyktory branżowe, „fuzja mikrooperacji” Intela, które próbują grupować instrukcje w większe partie równoczesnej pracy (coś w rodzaju VLIW / Itanium titanic). Istnieją nawet granice pamięci podręcznej, które mogą sprawić, że kod będzie działał szybciej, bo Bóg wie, dlaczego, jeśli jest większy (być może kontroler pamięci podręcznej dostosowuje go inteligentniej lub utrzymuje go dłużej).
CISC zawsze miał warstwę translacji od zestawu do mikrokodu, ale chodzi o to, że w nowoczesnych procesorach sprawy są znacznie bardziej skomplikowane. Dzięki wszystkim dodatkowym nieruchomościom tranzystorowym w nowoczesnych fabrykach półprzewodników procesory prawdopodobnie prawdopodobnie zastosują kilka metod optymalizacji równolegle, a następnie wybiorą tę na końcu, która zapewnia najlepsze przyspieszenie. Dodatkowe instrukcje mogą zachęcać procesor do korzystania z jednej ścieżki optymalizacji, która jest lepsza niż inne.
Wpływ dodatkowych instrukcji prawdopodobnie zależy od modelu procesora / generacji / producenta i prawdopodobnie nie będzie przewidywalny. Optymalizacja języka asemblera w ten sposób wymagałaby wykonania na wielu generacjach architektury procesora, być może przy użyciu specyficznych dla CPU ścieżek wykonania, i byłaby pożądana tylko dla naprawdę bardzo ważnych sekcji kodu, chociaż jeśli robisz asembler, prawdopodobnie już o tym wiesz.
źródło
Przygotowywanie pamięci podręcznej
Operacje przenoszenia do pamięci mogą przygotować pamięć podręczną i przyspieszyć kolejne operacje przenoszenia. Procesor zwykle ma dwie jednostki obciążenia i jedną jednostkę pamięci. Jednostka ładująca może czytać z pamięci do rejestru (jeden odczyt na cykl), jednostka pamięci przechowuje z rejestru do pamięci. Istnieją również inne jednostki, które wykonują operacje między rejestrami. Wszystkie jednostki pracują równolegle. Tak więc w każdym cyklu możemy wykonać kilka operacji jednocześnie, ale nie więcej niż dwa obciążenia, jeden sklep i kilka operacji rejestru. Zwykle są to 4 proste operacje z rejestrami zwykłymi, do 3 prostych operacji z rejestrami XMM / YMM i 1-2 złożone operacje z dowolnymi rejestrami. Twój kod ma wiele operacji z rejestrami, więc jedna sztuczna pamięć operacyjna jest bezpłatna (ponieważ i tak jest więcej niż 4 operacje rejestrów), ale przygotowuje pamięć podręczną do kolejnej operacji przechowywania. Aby dowiedzieć się, jak działają magazyny pamięci, zapoznaj się zPodręcznik informacyjny dotyczący optymalizacji architektury Intel 64 i IA-32 .
Przełamywanie fałszywych zależności
Chociaż nie odnosi się to dokładnie do twojego przypadku, czasami używa się 32-bitowych operacji mov w 64-bitowym procesorze (jak w twoim przypadku), aby wyczyścić wyższe bity (32-63) i przerwać łańcuch zależności.
Dobrze wiadomo, że pod x86-64 użycie 32-bitowych argumentów kasuje wyższe bity 64-bitowego rejestru. Zarzuty przeczytaj odpowiednią część - 3.4.1.1 - Instrukcji programisty oprogramowania Intel® 64 i IA-32 Architectures, tom 1 :
Tak więc instrukcje mov, które na pierwszy rzut oka mogą wydawać się bezużyteczne, usuwają wyższe bity odpowiednich rejestrów. Co nam daje? Łamie łańcuchy zależności i pozwala na wykonywanie instrukcji równolegle, w losowej kolejności, za pomocą algorytmu Out-of-Order zaimplementowanego wewnętrznie przez procesory od Pentium Pro w 1995 roku.
Cytat z podręcznika optymalizacji architektury Intel® 64 i IA-32 , rozdział 3.5.1.8:
MOVZX i MOV z 32-bitowymi argumentami dla x64 są równoważne - wszystkie przerywają łańcuchy zależności.
Dlatego twój kod działa szybciej. Jeśli nie ma zależności, CPU może wewnętrznie zmienić nazwę rejestrów, nawet jeśli na pierwszy rzut oka może się wydawać, że druga instrukcja modyfikuje rejestr wykorzystywany przez pierwszą instrukcję, a obie nie mogą wykonywać się równolegle. Ale ze względu na zmianę nazwy rejestru mogą.
Zmiana nazwy rejestru jest techniką stosowaną wewnętrznie przez CPU, która eliminuje fałszywe zależności danych wynikające z ponownego wykorzystania rejestrów przez kolejne instrukcje, które nie mają żadnych rzeczywistych zależności między nimi.
Myślę, że teraz widzisz, że to zbyt oczywiste.
źródło