Jeśli uważasz, że 64-bitowa Instrukcja DIV jest dobrym sposobem na dzielenie przez dwa, to nic dziwnego, że wyjście ASM kompilatora bije Twój ręcznie napisany kod, nawet z -O0 (Szybka kompilacja, bez dodatkowej optymalizacji i przechowywanie / przeładowanie do pamięci po / przed każdą instrukcją C, aby debugger mógł modyfikować zmienne).

Zobacz także bardziej ogólne Pytanie o pokonanie kompilatora z ręcznie pisanym asm: czy język asemblera jest wolniejszy niż natywny kod C++?. TL: DR: tak, jeśli robisz to źle(jak to pytanie).

Zazwyczaj pozwalasz kompilatorowi robić swoje, szczególnie jeśli próbujesz napisać C++, który potrafi kompilować efektywnie . Zobacz też czy assembly jest szybszy niż skompilowane języki?. Jeden z odpowiedzi linki do te schludne slajdy pokazujące, jak różne kompilatory C optymalizują niektóre naprawdę proste funkcje za pomocą fajnych sztuczek. Matt Godbolt ' s CppCon2017 talk "co mój kompilator zrobił dla mnie ostatnio? W podobny sposób można rozpinać pokrywę kompilatora.

even:
    mov rbx, 2
    xor rdx, rdx
    div rbx

Na Intel Haswell, div r64 jest to 36 uops, z opóźnieniem 32-96 cykli, a przepustowość jednego na 21-74 cykle. (Plus 2 uops do Ustawienia RBX i zero RDX, ale out-of-order execution może uruchomić te wcześniej). instrukcje o wysokiej liczbie uop, takie jak DIV, są mikrokodowane, co może również powodować wąskie gardła w interfejsie. w tym przypadku opóźnienie jest najistotniejszym czynnikiem, ponieważ jest częścią łańcucha zależności przenoszonego w pętli.

shr rax, 1 wykonuje ten sam niepodpisany podział: jest to 1 uop, z opóźnieniem 1c i może działać 2 na cykl zegara.

Dla porównania, podział 32-bitowy jest szybszy, ale nadal straszny vs.przesunięcia. idiv r32 is 9 uops, 22-29C opóźnienie, i jeden na przepustowość 8-11c na Haswell.

Jak widać patrząc na wyjście gcc -O0 asm (Godbolt compiler explorer), używa on tylko instrukcji przesunięcia. clang -O0 kompiluje naiwnie, tak jak myślałeś, nawet używając 64-bitowego IDIV dwa razy. (Podczas optymalizacji Kompilatory używają obu wyjść IDV, gdy źródło wykonuje podział i moduł z tymi samymi operandami, jeśli w ogóle używają IDV)

GCC nie ma całkowicie naiwnego trybu; zawsze transformuje się przez GIMPLE, co oznacza, że niektóre "optymalizacje" nie mogą być wyłączone. W celu uniknięcia IDIV (zobacz div_by_13w powyższym linku godbolt), należy używać przesunięć (potęga 2) lub mnożnika o stałym punkcie (Nie potęga 2).

gcc -Os (optimize for size) czy używa IDIV dla podziału nie-power-of-2, niestety nawet w przypadkach, gdy multiplikatywny kod odwrotny jest tylko nieco większy, ale znacznie szybciej.

Pomoc kompilator

(Streszczenie dla tego przypadku: użyj uint64_t n)

Po pierwsze, interesujące jest tylko spojrzenie na zoptymalizowane wyjście kompilatora. (-O3). -O0 prędkość jest w zasadzie bez znaczenia.

Spójrz na wyjście asm (na Godbolt, lub zobacz jak usunąć "szum" z wyjścia montażowego GCC/clang?). Gdy kompilator nie tworzy optymalnego kodu: pisanie źródła C / C++ w taki sposób, że prowadzi kompilator do tworzenia lepszego kodu jest zwykle najlepszym podejściem . Musisz znać asm i wiedzieć, co jest skuteczne, ale wykorzystujesz tę wiedzę pośrednio. Kompilatory są również dobrym źródłem pomysłów: czasami clang zrobi coś fajnego i możesz trzymać gcc ręcznie, aby zrobić to samo: zobacz tę odpowiedź i to, co zrobiłem z nie rozwijaną pętlą w kodzie @ Veedrac poniżej.)

To podejście jest przenośne i za 20 lat jakiś przyszły kompilator może je skompilować do tego, co jest wydajne na przyszłym sprzęcie (x86 lub nie), może używając nowego rozszerzenia ISA lub auto-wektoryzacji. Ręcznie napisany x86-64 asm sprzed 15 lat zazwyczaj nie byłby optymalnie dostrojony do Skylake. np. compare&branch makro-Fusion wtedy nie istniało. to, co jest teraz optymalne dla ręcznie tworzonego asm dla jednej mikroarchitektury, może nie być optymalne dla innych obecnych i przyszłych procesorów. komentarze do odpowiedzi @ johnfound omów główne różnice między AMD Bulldozer i Intel Haswell, które mają duży wpływ na ten kod. Ale teoretycznie, g++ -O3 -march=bdver3 i g++ -O3 -march=skylake postąpią słusznie. (Lub -march=native.) Lub -mtune=... po prostu dostroić, bez użycia instrukcji, których inne procesory mogą nie obsługiwać.

Mam wrażenie, że kierowanie kompilatora do asm, który jest dobry dla obecnego procesora, na którym ci zależy, nie powinno być problemem dla przyszłych kompilatorów. Mają nadzieję, że są lepsi od obecnych kompilatorów w znajdowaniu sposobów na transformację kodu i mogą znaleźć sposób, który działa na przyszłe Procesory. Niezależnie od tego, przyszły x86 prawdopodobnie nie będzie straszny w niczym, co jest dobre na obecnym x86, a przyszły kompilator uniknie żadnych pułapek specyficznych dla asm podczas implementacji czegoś takiego jak ruch danych ze źródła C, jeśli nie zobaczy czegoś lepszego.

Ręcznie napisany asm jest czarną skrzynką dla optymalizatora, więc propagacja stała nie działa, gdy inlining sprawia, że wejście staje się stałą kompilacji. Dotyczy to również innych optymalizacji. Czytaj https://gcc.gnu.org/wiki/DontUseInlineAsm przed użyciem asm. (I unikaj wbudowanego asm W Stylu MSVC: wejścia/wyjścia muszą przejść przez pamięć , która dodaje napowietrzne.)

W tym przypadku: Twój n mA typ signed, a gcc używa sekwencji SAR/SHR / ADD, która daje prawidłowe zaokrąglenie. (IDIV i arytmetyka-przesunięcie "okrągłe" inaczej dla ujemnych wejść, patrz SAR insn set ref manual entry ). (IDK jeśli gcc próbował i nie udowodnił, że n nie może być negatywna. Signed-overflow jest niezdefiniowanym zachowaniem, więc powinno być w stanie.)

Powinieneś użyć uint64_t n, więc może po prostu SHR. Jest więc przenośny do systemów, w których long jest tylko 32-bitowy (np. Windows x86-64).

BTW, GCC ' s optimized ASM output looks pretty good (using unsigned long n): pętla wewnętrzna, do której wkracza main(), robi to:

 # from gcc5.4 -O3  plus my comments

 # edx= count=1
 # rax= uint64_t n

.L9:                   # do{
    lea    rcx, [rax+1+rax*2]   # rcx = 3*n + 1
    mov    rdi, rax
    shr    rdi         # rdi = n>>1;
    test   al, 1       # set flags based on n%2 (aka n&1)
    mov    rax, rcx
    cmove  rax, rdi    # n= (n%2) ? 3*n+1 : n/2;
    add    edx, 1      # ++count;
    cmp    rax, 1
    jne   .L9          #}while(n!=1)

  cmp/branch to update max and maxi, and then do the next n

Pętla wewnętrzna jest bezgałęziowa, a ścieżka krytyczna pętli-niesiona łańcuch zależności To:

• 3-składowa LEA (3 cykle)
• cmov (2 cykle na Haswella, 1C na Broadwella lub później).

Łącznie: 5 cykli na iterację, wąskie gardło opóźnienia . Out-of-order execution zajmuje się wszystkim innym równolegle z tym (w teorii: nie testowałem z licznikami perf, aby sprawdzić, czy naprawdę działa w 5c / iter).

Wejście FLAGS z cmov (produkowane przez TEST) jest szybsze do wytworzenia niż wejście RAX (z Lea->MOV), więc nie jest na ścieżce krytycznej.

Podobnie MOV - > SHR, który wytwarza wejście RDI CMOV, jest poza ścieżką krytyczną, ponieważ jest również szybszy niż LEA. MOV na IvyBridge i Później ma zerowe opóźnienie(obsługiwane w czasie register-rename). (Nadal wymaga uop i gniazda w potoku, więc nie jest wolny, tylko zerowe opóźnienie). Dodatkowy MOV w łańcuchu Lea dep jest częścią wąskiego gardła na innych procesorach.

Cmp / jne nie jest również częścią ścieżki krytycznej: nie jest przenoszona w pętli, ponieważ zależności kontrolne są obsługiwane za pomocą Branch prediction + speculative execution, w przeciwieństwie do zależności danych na ścieżce krytycznej.

Pokonanie kompilatora

GCC odwaliło kawał dobrej roboty. Może zapisać jeden bajt kodu za pomocą inc edx zamiast add edx, 1, ponieważ nikt nie dba o P4 i jego fałszywe zależności Dla instrukcji częściowej modyfikacji flagi.

Może również zapisać wszystkie instrukcje MOV, a TEST: SHR ustawia CF= przesunięty bit out, więc możemy użyć cmovc zamiast test / cmovz.

 ### Hand-optimized version of what gcc does
.L9:                       #do{
    lea     rcx, [rax+1+rax*2] # rcx = 3*n + 1
    shr     rax, 1         # n>>=1;    CF = n&1 = n%2
    cmovc   rax, rcx       # n= (n&1) ? 3*n+1 : n/2;
    inc     edx            # ++count;
    cmp     rax, 1
    jne     .L9            #}while(n!=1)

Zobacz odpowiedź @ johnfound na kolejny sprytny trik: Usuń CMP przez rozgałęzianie na wyniku flagi SHR, a także użycie go dla CMOV: zero tylko jeśli N było 1 (lub 0) Na początek. (Ciekawostka: SHR z hrabią != 1 Na Nehalem lub wcześniej powoduje stall, jeśli odczytasz wyniki flagi . W ten sposób powstał single-uop. Kodowanie specjalne shift-by-1 jest jednak w porządku.)

Unikanie MOV nie pomaga w opóźnienie w ogóle na Haswell (czy MOV x86 naprawdę może być "wolny"? Dlaczego nie mogę tego odtworzyć?). To pomaga znacząco na procesorach takich jak Intel pre-IvB i AMD Bulldozer-family, gdzie MOV nie ma zerowego opóźnienia. Zmarnowane instrukcje MOV kompilatora wpływają na ścieżkę krytyczną. Złożone BD - Lea I CMOV mają mniejsze opóźnienie (odpowiednio 2C i 1C), więc jest to większy ułamek opóźnienia. Problemem stają się również wąskie gardła przepustowości, ponieważ mają one tylko dwa rury integer ALU. Zobacz odpowiedź @johnfound , gdzie ma Wyniki pomiaru czasu z procesora AMD.

Nawet w przypadku Haswella, ta wersja może nieco pomóc, unikając sporadycznych opóźnień, gdy niekrytyczny uop kradnie Port wykonania od jednego na ścieżce krytycznej, opóźniając wykonanie o 1 cykl. (Nazywa się to konfliktem zasobów). Zapisuje również rejestr, który może pomóc podczas wykonywania wielu wartości n równolegle w pętli interleaved (patrz poniżej).

LEA ' s opóźnienie zależy od trybu adresowania w procesorach z rodziny Intel SnB. 3C dla 3 składowych ([base+idx+const], co wymaga dwóch oddzielnych dodań), ale tylko 1c z 2 lub mniej składowymi (jeden add). Niektóre procesory (jak Core2) wykonują nawet 3-komponentowe LEA w jednym cyklu, ale rodzina SnB tego nie robi. co gorsza, Intel SnB-family standaryzuje opóźnienia, więc nie ma 2c UOPs , w przeciwnym razie 3-komponentowa LEA byłaby tylko 2C jak Bulldozer. (3-komponentowy LEA jest wolniejszy również na AMD, tylko nie przez dużo).

Więc lea rcx, [rax + rax*2] / inc rcx jest tylko opóźnieniem 2C, szybszym niż lea rcx, [rax + rax*2 + 1], na procesorach Intel SnB-family, takich jak Haswell. Break-even na BD, a gorzej na Core2. To kosztuje dodatkowy uop, co zwykle nie jest tego warte, aby zaoszczędzić opóźnienie 1c, ale opóźnienie jest głównym wąskim gardłem tutaj i Haswell ma wystarczająco szeroki rurociąg, aby obsłużyć dodatkową przepustowość uop.

W 1997 roku, w wyniku połączenia z SHR, firma została przekształcona w spółkę akcyjną. Głupie Kompilatory. : P są wielkie kawałki skomplikowanej maszyny, ale mądry człowiek często może pokonać je na małą skalę problemów. (Podane tysiące do milionów razy dłużej, aby myśleć o tym, oczywiście! Kompilatory nie używają wyczerpujących algorytmów do szukania każdego możliwego sposobu działania, ponieważ zajmowałoby to zbyt dużo czasu przy optymalizacji kodu inlined, co jest tym, co robią najlepiej. Nie są one również modelowane rurociągiem w docelowej mikroarchitekturze, przynajmniej nie w tych samych szczegółach coIACA lub inne narzędzia analizy statycznej; używają tylko heurystyki.)

Proste rozwijanie pętli nie pomoże; to wąskie gardła pętli na opóźnienie łańcucha zależności przenoszonego przez pętlę, a nie na napowietrzność / przepustowość pętli. Oznacza to, że poradziłby sobie z hyperthreading (lub innym rodzajem SMT), ponieważ procesor ma dużo czasu na przeplatanie instrukcji z dwóch wątków. Oznacza to równoległe połączenie pętli w main, ale jest to w porządku, ponieważ każdy wątek może po prostu sprawdzić zakres n wartości i w wyniku tego powstaje para liczb całkowitych.

Przeplatanie ręcznie w jednym wątku może być również opłacalne . Może obliczyć sekwencję dla pary liczb równolegle, ponieważ każdy z nich zajmuje tylko kilka rejestrów i wszystkie mogą aktualizować to samo max / maxi. To tworzy więcej równoległości na poziomie instrukcji .

Sztuką jest podjęcie decyzji, czy poczekać, aż wszystkie wartości n osiągną 1, zanim otrzymamy kolejną parę począwszy od wartości n, lub czy przełamać i uzyskać nowy punkt początkowy dla tylko jednego, który osiągnął warunek końcowy, bez dotykania rejestrów dla drugiej sekwencji. Prawdopodobnie najlepiej jest, aby każdy łańcuch działał na użytecznych danych, w przeciwnym razie musiałbyś warunkowo zwiększyć jego licznik.

Możesz to zrobić nawet z SSE packed-porównaj rzeczy, aby warunkowo zwiększyć licznik dla elementów wektorowych, gdzie n Nie osiągnął jeszcze 1. A potem ukryć nawet dłuższe opóźnienie implementacji warunkowego przyrostu SIMD, trzeba by trzymać więcej wektorów n wartości w powietrzu. Może warto tylko z wektorem 256b (4x uint64_t).

Myślę, że najlepszą strategią, aby wykryć 1 "lepki" jest zamaskowanie wektora wszystkich tych, które dodajesz, aby zwiększyć licznik. W przypadku, gdy wektor Przyrostowy ma wartość zero, a + = 0 jest liczbą zerową.]}

Nieprzetestowany pomysł na podręcznik wektoryzacja

# starting with YMM0 = [ n_d, n_c, n_b, n_a ]  (64-bit elements)
# ymm4 = _mm256_set1_epi64x(1):  increment vector
# ymm5 = all-zeros:  count vector

.inner_loop:
    vpaddq    ymm1, ymm0, xmm0
    vpaddq    ymm1, ymm1, xmm0
    vpaddq    ymm1, ymm1, set1_epi64(1)     # ymm1= 3*n + 1.  Maybe could do this more efficiently?

    vprllq    ymm3, ymm0, 63                # shift bit 1 to the sign bit

    vpsrlq    ymm0, ymm0, 1                 # n /= 2

    # FP blend between integer insns may cost extra bypass latency, but integer blends don't have 1 bit controlling a whole qword.
    vpblendvpd ymm0, ymm0, ymm1, ymm3       # variable blend controlled by the sign bit of each 64-bit element.  I might have the source operands backwards, I always have to look this up.

    # ymm0 = updated n  in each element.

    vpcmpeqq ymm1, ymm0, set1_epi64(1)
    vpandn   ymm4, ymm1, ymm4         # zero out elements of ymm4 where the compare was true

    vpaddq   ymm5, ymm5, ymm4         # count++ in elements where n has never been == 1

    vptest   ymm4, ymm4
    jnz  .inner_loop
    # Fall through when all the n values have reached 1 at some point, and our increment vector is all-zero

    vextracti128 ymm0, ymm5, 1
    vpmaxq .... crap this doesn't exist
    # Actually just delay doing a horizontal max until the very very end.  But you need some way to record max and maxi.

Możesz i powinieneś zaimplementować to z wewnętrznymi, zamiast ręcznie pisanego asm.

Algorytmiczne / usprawnienie implementacji:

Poza implementacją tej samej logiki z bardziej wydajnym asm, poszukaj sposobów na uproszczenie logiki lub uniknięcie zbędnej pracy. np. memoize w celu wykrycia wspólnych zakończeń sekwencji. W przeciwieństwie do poprzednich wersji, nie jest to możliwe.]}

@EOF zwraca uwagę, że tzcnt (lub bsf) może być służy do wykonywania wielu iteracji n/=2 w jednym kroku. To chyba lepsze niż wektoryzacja SIMD; żadna Instrukcja SSE czy AVX tego nie potrafi. Jest jednak nadal kompatybilny z wykonywaniem wielu skalarów ns równolegle w różnych rejestrach całkowitych.

Więc pętla może wyglądać tak:

goto loop_entry;  // C++ structured like the asm, for illustration only
do {
   n = n*3 + 1;
  loop_entry:
   shift = _tzcnt_u64(n);
   n >>= shift;
   count += shift;
} while(n != 1);

Może to zrobić znacznie mniej iteracji, ale zmiany liczby zmiennych są powolne w procesorach Intel SnB z rodziny bez BMI2. 3 uops, 2C latency. (Mają zależność od FLAG ponieważ count = 0 oznacza, że flagi są niezmodyfikowane. Obsługują to jako zależność od danych i pobierają wiele uops, ponieważ uop może mieć tylko 2 wejścia (Pre-HSW/BDW anyway)). O tym właśnie mówią ludzie narzekający na szaloną konstrukcję x86. To sprawia, że procesory x86 są wolniejsze niż gdyby ISA został zaprojektowany od podstaw dzisiaj, nawet w bardzo podobny sposób. (tj. jest to część "podatku x86", który kosztuje prędkość / moc.) SHRX / SHLX / SARX (BMI2) to duża wygrana (1 uop / 1c latencji).

Stawia również tzcnt (3C na Haswella i później) na ścieżce krytycznej, dzięki czemu znacznie wydłuża całkowite opóźnienie łańcucha zależności przenoszonego pętlą. Nie wymaga jednak użycia CMOV, ani przygotowania rejestru [54]}. @Veedrac ' s answer pokonuje to wszystko przez odroczenie tzcnt / shift dla wielu iteracji, co jest bardzo skuteczne(patrz poniżej).

Możemy bezpiecznie używać BSF lub TZCNT zamiennie, ponieważ n nigdy nie może być zero w tym momencie. Kod maszynowy TSCNT dekoduje się jako BSF na procesorach, które nie obsługują BMI1. (Bezsensowne prefiksy są ignorowane, więc REP BSF działa jako BSF).

TZCNT działa znacznie lepiej niż BSF na procesorach AMD, które go obsługują, więc dobrym pomysłem może być użycie REP BSF, nawet jeśli nie zależy ci na ustawieniu ZF, jeśli wejście jest zerowe, a nie wyjście. Niektóre Kompilatory robią to, gdy używasz __builtin_ctzll nawet z -mno-bmi.

Wykonują to samo na procesorach Intela, więc po prostu zapisz bajt, jeśli tylko to się liczy. TSCNT na Intel (pre-Skylake) nadal ma fałszywą zależność od rzekomo tylko do zapisu operandu wyjściowego, podobnie jak BSF, aby wspierać nieudokumentowane zachowanie, które BSF z input = 0 pozostawia swoje miejsce docelowe niezmodyfikowane. Więc musisz obejść to, chyba że optymalizacja tylko dla Skylake, więc nie ma nic do zyskania z dodatkowego bajtu REP. (Intel często wychodzi poza to, czego wymaga podręcznik x86 ISA, aby uniknąć łamania powszechnie używanego kodu, który zależy od coś, czego nie powinno, lub co jest z mocą wsteczną niedozwolone. na przykład System Windows 9x nie zakłada spekulacyjnego prefetchingu wpisów TLB, co było bezpieczne, gdy kod został napisany, zanim Intel zaktualizował reguły zarządzania TLB.)

W każdym razie, LZCNT/TZCNT na Haswell mają ten sam fałszywy dep co POPCNT: zobacz to pytanie i odpowiedź . To dlatego w wyjściu GCC asm dla kodu @ Veedrac, widzisz to łamanie łańcucha dep za pomocą zerowania xor w rejestrze. używa jako miejsca docelowego TZCNT, gdy nie używa DST = src. Ponieważ TSCNT / LZCNT / POPCNT nigdy nie zostawia miejsca docelowego niezdefiniowanego lub niezmodyfikowanego, ta fałszywa zależność od wyjścia procesorów Intel jest błędem / ograniczeniem wydajności. Prawdopodobnie warto mieć kilka tranzystorów / mocy, aby zachowywały się jak inne UOP, które idą do tej samej jednostki wykonawczej. Jedynym plusem perf jest interakcja z innym ograniczeniem uarch: mogą mikro-fuse operand pamięci z trybem adresowania indeksowanego na Haswell, ale na Skylake gdzie Intel usunął fałszywy dep dla LZCNT / TZCNT oni "un-laminate" indeksowane tryby adresowania, podczas gdy POPCNT może nadal mikro-fuse dowolny tryb addr.

Ulepszenia pomysłów / kodu z innych odpowiedzi:

@odpowiedź hidefromkgb ma miłą obserwację, że masz gwarancję, że będziesz w stanie zrobić jedną prawą zmianę po 3N+1. Można to obliczyć bardziej efektywnie niż pominięcie kontroli między krokami. Wdrożenie asm w tej odpowiedzi jest jednak złamana (zależy od OF, która jest niezdefiniowana po SHRD z liczbą > 1), i powolna: ROR rdi,2 jest szybsza niż SHRD rdi,rdi,2, a użycie dwóch instrukcji CMOV na ścieżce krytycznej jest wolniejsze niż dodatkowy TEST, który może działać równolegle.

Umieściłem tidied / improved C (który prowadzi kompilator do tworzenia lepszego asm), i przetestowałem + działa szybciej asm (w komentarzach pod C) na Godbolt: zobacz link w @hidefromkgb odpowiedź . (Ta odpowiedź trafia w limit 30K char z dużych adresów Godbolt, ale shortlinki mogą gnić i były zbyt długie na goo.gl w każdym razie.)

Poprawiono również drukowanie wyjściowe, aby przekonwertować na ciąg znaków i utworzyć jeden write() zamiast zapisywać jeden znak na raz. To minimalizuje wpływ na czas całego programu za pomocą perf stat ./collatz (aby rejestrować liczniki wydajności), a ja usunąłem niektóre niekrytyczne asm.

@Kod Veedraca

Mam małe przyspieszenie od prawej zmiany biegów tak samo jak my know needs doing, and checking to continue the loop. Od 7,5 s dla limitu=1E8 do 7,275 s, na Core2Duo (Merom), przy współczynniku rozwinięcia 16.

Code + comments on Godbolt . Nie używaj tej wersji z clang; robi coś głupiego z defer-loop. Użycie licznika tmp k, a następnie dodanie go do {[64] } później zmienia to, co robi clang, ale to nieco rani gcc.

Zobacz dyskusję w komentarzach: Kod Veedraca jest excellent na procesorach z BMI1 (tzn. nie Celeron/Pentium)