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 linkuje do tych schludnych slajdów pokazujących, jak różne kompilatory C optymalizują niektóre naprawdę proste funkcje za pomocą fajnych sztuczek.

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, aby skonfigurować 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ć front-end wąskie gardła. 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. [[8]} to 9 uops, opóźnienie 22-29C i jedna na przepustowość 8-11c w systemie Haswell.

Jak widać patrząc na wyjście gcc -O0 asm (Godbolt compiler explorer ), używa 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 przekształca się przez GIMPLE, co oznacza, że niektóre "optymalizacje" nie mogą być wyłączone. Obejmuje to rozpoznawanie podział przez stałą i wykorzystanie przesunięć (potęga 2) lub mnożnika stałego (Nie potęga 2), aby uniknąć IDIV(zobacz div_by_13 w powyższym linku godbolt).

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 szybszy.

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 sposób, który prowadzi kompilatora do tworzenia lepszego kodu jest zwykle najlepszym podejściem . Musisz znać asm i wiedzieć, co jest wydajny, 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 skompilować je 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ówcie 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 pułapek specyficznych dla asm podczas wdrażania czegoś takiego jak ruch danych ze źródła C, jeśli nie widzi 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óry dodaje overhead .)

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ć negatywny, czy co. 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

• 3-składowa LEA (3 cykle)
• cmov (2 cykle na Haswell, 1C na Broadwell 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 wyprodukowania niż wejście RAX (z Lea - > MOV), więc nie znajduje się na ścieżce krytycznej.

Podobnie MOV - > SHR, który wytwarza wejście RDI CMOV, jest poza ścieżką krytyczną, bo jest też 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 również nie jest 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 od ścieżka krytyczna.

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= bit przesunięty na zewnątrz, 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 trick: 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 z opóźnieniem w ogóle na Haswell (czy MOV x86 naprawdę może być "wolny"? Dlaczego nie mogę tego odtworzyć?). Tak. pomoc 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ż ma tylko dwie rury 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).

Opóźnienie LEA zależy od trybu adresowania , w procesorach z rodziny Intel SnB. 3c dla 3 składników ([base+idx+const], co zajmuje dwa osobne dodatki), ale tylko 1c z 2 lub mniej składnikami (jeden dodatek). 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 aż tak bardzo).

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 on 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 to wielkie kawałki skomplikowanych maszyn, ale mądry człowiek często może ich pokonać w małych problemach. (Podane tysiące do milionów razy dłużej, aby o tym pomyśleć, 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 modelują również potoku w docelowej mikroarchitekturze, przynajmniej nie w tym samym detalu co IACA lub inne narzędzia do analizy statycznej; po prostu używają heurystyki.)

Proste rozwijanie pętli nie pomoże ; ta pętla wąskie gardła opóźnień ł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łoby to równoległość pętli w main, ale jest to w porządku, ponieważ każdy wątek może po prostu sprawdzić zakres wartości n i w rezultacie wytworzyć parę liczb całkowitych.

Przeplatanie ręcznie w obrębie jednego wątku może być również realne . 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 przed otrzymaniem kolejnej pary wartości początkowych n, czy też czy przełamać się i uzyskać nowy punkt startowy dla tylko jednego, który osiągnął stan końcowy, bez dotykając 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, aby ukryć jeszcze dłuższe opóźnienie implementacji warunkowego przyrostu SIMD, trzeba trzymać więcej wektorów n wartości w górę powietrze. 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ą.]}

Niesprawdzony pomysł na ręczną wektoryzację

# 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

    # There may be a better way to do this blend, avoiding the bypass delay for an FP blend between integer insns, not sure.  Probably worth it
    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.

Algorytmiczny / poprawa 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 wskazuje, że tzcnt (lub bsf) może być użyty do wykonania wielu iteracji n/=2 w jednym kroku. To chyba lepsze niż wektoryzacja SIMD, bo ż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. (Są zależne od FLAG, ponieważ count = 0 oznacza, że flagi są niezmodyfikowane. Obsługują to jako zależność od danych i pobierają wiele UOP, ponieważ UOP może mieć tylko 2 wejścia (pre-HSW/BDW)). 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 latency).

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ńcuch zależności przenoszony przez 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 punkcie. 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.

Działają tak samo na procesorach Intela, więc zachowaj bajt, jeśli tylko to się liczy. TSCNT na Intel (pre-Skylake) nadal ma fałszywą zależność od rzekomo tylko do zapisu operand, podobnie jak BSF, 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 wykracza poza to, czego wymaga podręcznik x86 ISA, aby uniknąć łamania powszechnie używanego kodu, który zależy od czegoś, czego nie powinien, lub który jest wstecznie zabroniony. np. Windows 9x nie zakłada spekulacyjnego prefetchingu TLB wpisy , które były bezpieczne podczas pisania kodu, 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 asm gcc dla kodu @Veedrac widzisz, że łamie łańcuch dep za pomocą zerowania xor w rejestrze, który ma być używany jako miejsce docelowe TZCNT, gdy nie używa DST=src. Ponieważ TSCNT / LZCNT / POPCNT nigdy nie opuszczają miejsca docelowego niezmodyfikowana, ta fałszywa zależność od wyjścia procesorów Intela jest wyłącznie 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. Na Haswella, ale na Skylake, gdzie Intel usunął fałszywą zależność dla LZCNT/TZCNT, udało im się uzyskać dostęp do danych, które nie były w pełni kompatybilne z innymi procesorami, np. z Windows XP, Windows Vista, Windows Vista, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, Windows 7, "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. Implementacja asm w tej odpowiedzi jest jednak zepsuta (zależy od tego, która jest niezdefiniowana po SHRD z liczbą > 1) i slow: ROR rdi,2 jest szybszy 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ź uderza w limit znaków 30K z dużych adresów Godbolt, ale shortlinki mogą gnić i były too long for 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 bardzo małe przyspieszenie od przesunięcia w prawo tyle, ile wiemy wymaga zrobienia i sprawdzenia, aby kontynuować pętlę. 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 doskonały na procesorach z BMI1 (tzn. nie Celeron/Pentium)