Te dwa rozwiązania napisałem dla Project Euler Q14 , w asemblerze i w C ++. Są to te same identyczne metody brutalnej siły do ​​testowania przypuszczeń Collatz . Rozwiązanie montażowe zostało zmontowane

nasm -felf64 p14.asm && gcc p14.o -o p14

C ++ został skompilowany

g++ p14.cpp -o p14

Montaż, p14.asm

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

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

c1:
    inc r10
    cmp rax, 1
    jne l2

    cmp rdi, r10
    cmovl rdi, r10
    cmovl rsi, rcx

    cmp rcx, 2
    jne l1

    mov rdi, fmt
    xor rax, rax
    call printf
    ret

C ++, p14.cpp

#include <iostream>

using namespace std;

int sequence(long n) {
    int count = 1;
    while (n != 1) {
        if (n % 2 == 0)
            n /= 2;
        else
            n = n*3 + 1;

        ++count;
    }

    return count;
}

int main() {
    int max = 0, maxi;
    for (int i = 999999; i > 0; --i) {
        int s = sequence(i);
        if (s > max) {
            max = s;
            maxi = i;
        }
    }

    cout << maxi << endl;
}

Wiem o optymalizacjach kompilatora w celu zwiększenia prędkości i wszystkiego, ale nie widzę wielu sposobów dalszej optymalizacji mojego rozwiązania do montażu (mówiąc programowo, a nie matematycznie).

Kod C ++ ma moduł dla każdego terminu i podział na każdy parzysty termin, gdzie asembler to tylko jeden podział na parzysty termin.

Ale montaż zajmuje średnio 1 sekundę dłużej niż rozwiązanie C ++. Dlaczego to? Pytam głównie z ciekawości.

Czasy wykonania

Mój system: 64-bitowy Linux na 1,4 GHz Intel Celeron 2955U (mikroarchitektura Haswella).

• g++ (niezoptymalizowany): średnio 1272 ms

• g++ -O3 średni 578 ms

• oryginalny asm (div) avg 2650 ms

• Asm (shr) średni 679 ms

• @johnfound asm , zmontowany z nasm avg 501 ms

• @hidefromkgb asm avg 200 ms

• @hidefromkgb asm zoptymalizowany przez @Peter Cordes średnio 145 ms

• @ Veedrac C ++ średnio 81 ms z -O3, 305 ms z-O0

Jeśli uważasz, że 64-bitowa instrukcja DIV jest dobrym sposobem na podzielenie przez dwa, to nic dziwnego, że dane wyjściowe asm kompilatora pobiły Twój ręcznie napisany kod, nawet przy pomocy -O0(szybka kompilacja, bez dodatkowej optymalizacji i przechowywanie / przeładowywanie do pamięci po / przed każdą instrukcją C, aby debugger mógł modyfikować zmienne).

Zobacz przewodnik dotyczący optymalizacji w Agner Fog, aby dowiedzieć się, jak pisać efektywne asm. Ma również tabele instrukcji i przewodnik po mikroarchaach, w którym znajdują się szczegółowe informacje na temat konkretnych procesorów. Zobacz takżex86 otaguj wiki, aby uzyskać więcej linków perf.

Zobacz także to bardziej ogólne pytanie o pokonanie kompilatora przy pomocy odręcznie napisanego asm: Czy wbudowany język asemblera jest wolniejszy niż natywny kod C ++? . TL: DR: tak, jeśli zrobisz to źle (jak to pytanie).

Zwykle pozwalasz kompilatorowi na wykonanie swoich zadań, zwłaszcza jeśli próbujesz napisać C ++, który potrafi się efektywnie kompilować . Zobacz także, czy asembler jest szybszy niż skompilowane języki? . Jedna z odpowiedzi prowadzi do tych schludnych slajdów pokazujących, jak różne kompilatory C optymalizują niektóre naprawdę proste funkcje za pomocą fajnych sztuczek. Rozmowa CppCon2017 Matta Godbolta „ Co ostatnio zrobił dla mnie mój kompilator? Odblokowanie pokrywy kompilatora ”ma podobny charakter.

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

Na Intel Haswell div r64jest 36 uops, z opóźnieniem 32-96 cykli i przepustowością jednego na 21-74 cykli. (Plus 2 ups, aby skonfigurować RBX i zero RDX, ale wykonanie poza kolejnością może uruchomić je wcześniej). Instrukcje o wysokiej liczbie uopów, takie jak DIV, są mikrokodowane, co może również powodować wąskie gardła w interfejsie użytkownika. W tym przypadku opóźnienie jest najistotniejszym czynnikiem, ponieważ jest częścią łańcucha zależności przenoszonego przez pętlę.

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

Dla porównania podział 32-bitowy jest szybszy, ale nadal straszny w porównaniu do zmian. idiv r32wynosi 9 ups, opóźnienie 22-29c i jeden na przepustowość 8-11c w Haswell.

Jak widać z -O0danych wyjściowych asm gcc ( eksplorator kompilatora Godbolt ), używa on tylko instrukcji shift . clang -O0kompiluje się naiwnie, tak jak myślałeś, nawet używając 64-bitowego IDIV dwukrotnie. (Podczas optymalizacji kompilatory używają obu danych wyjściowych IDIV, gdy źródło dokonuje podziału i modułu z tymi samymi operandami, jeśli w ogóle używają IDIV)

GCC nie ma całkowicie naiwnego trybu; zawsze przekształca się w GIMPLE, co oznacza, że ​​niektórych „optymalizacji” nie można wyłączyć . Obejmuje to rozpoznawanie dzielenia przez stałą i stosowanie przesunięć (potęga 2) lub stałej odwrotności multiplikatywnej (brak potęgi 2), aby uniknąć IDIV (patrz div_by_13powyższy link godbolt).

gcc -Os(optymalizacja dla rozmiaru) robi use IDIV dla non-power-of-2 Liga, niestety nawet w przypadkach, gdy multyplikatywną kod odwrotna jest tylko nieco większy, ale znacznie szybciej.

Pomaganie kompilatorowi

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

Po pierwsze, interesujące jest tylko zoptymalizowanie wyjścia kompilatora. ( -O3). -O0prędkość jest w zasadzie bez znaczenia.

Spójrz na swoje wyjście asm (na Godbolt, lub zobacz Jak usunąć „szum” z wyjścia zespołu GCC / clang? ). Kiedy kompilator nie tworzy optymalnego kodu: Pisanie źródła C / C ++ w sposób, który prowadzi kompilator do tworzenia lepszego kodu jest zazwyczaj najlepszym podejściem . Musisz znać asm i wiedzieć, co jest skuteczne, ale stosujesz tę wiedzę pośrednio. Kompilatory są również dobrym źródłem pomysłów: czasami brzęk zrobi coś fajnego i możesz przytrzymać gcc, aby zrobić to samo: zobacz tę odpowiedź i to, co zrobiłem z nierozwiniętą pętlą w kodzie @ Veedrac poniżej).

To podejście jest przenośne i za 20 lat jakiś przyszły kompilator może skompilować go na cokolwiek, co będzie wydajne na przyszłym sprzęcie (x86 lub nie), być może przy użyciu nowego rozszerzenia ISA lub auto-wektoryzacji. Ręcznie napisany x86-64 asm sprzed 15 lat zwykle nie był optymalnie dostrojony do Skylake. np. porównywanie i rozgałęzianie makr fuzji jeszcze wtedy nie istniało. To, co jest teraz optymalne dla ręcznie wykonanego asm dla jednej mikroarchitektury, może nie być optymalne dla innych obecnych i przyszłych procesorów. Komentarze do odpowiedzi @ johnfound omawiają 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=bdver3i g++ -O3 -march=skylakezrobi to, co należy. (Lub -march=native.) Lub -mtune=...po prostu dostroić, bez korzystania z instrukcji, które inne procesory mogą nie obsługiwać.

Mam wrażenie, że prowadzenie kompilatora do asm, który jest dobry dla bieżącego procesora, na którym ci zależy, nie powinno stanowić problemu dla przyszłych kompilatorów. Miejmy nadzieję, że są lepsze niż obecne kompilatory w poszukiwaniu sposobów na transformację kodu i mogą znaleźć sposób, który będzie działał dla przyszłych procesorów. Niezależnie od tego, przyszłe x86 prawdopodobnie nie będzie straszne w niczym, co jest dobre na obecnym x86, a przyszły kompilator pozwoli uniknąć pułapek specyficznych dla asmów podczas implementacji czegoś takiego jak przenoszenie danych ze źródła C, jeśli nie zobaczy czegoś lepszego.

Odręcznie napisany asm jest czarną skrzynką dla optymalizatora, więc stała propagacja nie działa, gdy inlining powoduje, że dane wejściowe są stałe w czasie kompilacji. Wpływa to również na inne optymalizacje. Przeczytaj https://gcc.gnu.org/wiki/DontUseInlineAsm przed użyciem asm. (I unikaj wbudowanego asm w stylu MSVC: wejścia / wyjścia muszą przechodzić przez pamięć, co powoduje dodatkowe obciążenie ).

W tym przypadku : twój nma podpisany typ, a gcc używa sekwencji SAR / SHR / ADD, która daje prawidłowe zaokrąglenie. (IDIV i przesunięcie arytmetyczne „zaokrągla” inaczej dla danych ujemnych, patrz SAR wprowadzanie ustawień ręcznych ref . (IDK, jeśli gcc spróbowało i nie udało się udowodnić, że nnie może być negatywne, czy co. Przepełnienie podpisane jest niezdefiniowanym zachowaniem, więc powinno być w stanie.)

Powinieneś był użyć uint64_t n, aby mógł po prostu SHR. Dlatego jest przenośny dla systemów, w których longjest tylko 32-bitowy (np. Windows x86-64).

BTW, zoptymalizowane wyjście asm gcc wygląda całkiem dobrze (przy użyciu )unsigned long n : wewnętrzna pętla, w którą inline main()wykonuje:

 # 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 nie ma rozgałęzień, a ścieżka krytyczna łańcucha zależności przenoszonej przez pętlę to:

• 3-komponentowy LEA (3 cykle)
• cmov (2 cykle na Haswell, 1c na Broadwell lub później).

Łącznie: 5 cykli na iterację, wąskie gardło związane z opóźnieniem . Wykonywanie poza kolejnością zajmuje się wszystkim innym równolegle z tym (teoretycznie: nie testowałem liczników perf, aby sprawdzić, czy naprawdę działa przy 5c / iter).

Wejście FLAGS cmov(produkowane przez TEST) jest szybsze w produkcji 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, znajduje się poza ścieżką krytyczną, ponieważ jest również szybszy niż LEA. MOV na IvyBridge, a później ma zerowe opóźnienie (obsługiwane w czasie zmiany nazwy rejestru). (Nadal wymaga ulepszenia i szczeliny w rurociągu, więc nie jest wolny, tylko zero opóźnień). Dodatkowe MOV w łańcuchu dep LEA jest częścią wąskiego gardła na innych procesorach.

Cmp / jne również nie jest częścią ścieżki krytycznej: nie jest przenoszony w pętli, ponieważ zależności sterujące są obsługiwane za pomocą przewidywania gałęzi + wykonania spekulatywnego, w przeciwieństwie do zależności danych na ścieżce krytycznej.

Pokonanie kompilatora

GCC wykonało tutaj całkiem dobrą robotę. inc edxZamiast tegoadd edx, 1 można zapisać jeden bajt kodu , 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 się przesunął, więc możemy użyć cmovczamiast 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 inną sprytną sztuczkę: usuń CMP przez rozgałęzienie wyniku flagi SHR, a także używając go do CMOV: zero tylko, jeśli n było 1 (lub 0) na początek. (Ciekawostka: SHR z liczbą! = 1 na Nehalem lub wcześniejszym powoduje przeciągnięcie, jeśli czytasz wyniki flagi . W ten sposób zrobili to pojedynczo. Jednak specjalne kodowanie shift-by-1 jest w porządku.)

Unikanie MOV wcale nie pomaga w opóźnieniu na Haswell ( czy MOV x86 naprawdę może być „wolny”? Dlaczego w ogóle nie mogę tego odtworzyć? ). Pomaga to znacznie w procesorach takich jak Intel przed IvB i rodzina buldożerów AMD, w których MOV nie ma zerowego opóźnienia. Zmarnowane instrukcje MOV kompilatora wpływają na ścieżkę krytyczną. Kompleks LEA i CMOV BD mają zarówno niższe 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 całkowite rury ALU. Zobacz odpowiedź @ johnfound , gdzie ma wyniki pomiaru czasu z procesora AMD.

Nawet w Haswell ta wersja może trochę pomóc, unikając sporadycznych opóźnień, w których niekrytyczna funkcja UOP kradnie port wykonania z jednego na ścieżce krytycznej, opóźniając wykonanie o 1 cykl. (Nazywa się to konfliktem zasobów). Zapisuje również rejestr, co może być pomocne przy wykonywaniu wielu nwartości równolegle w pętli z przeplotem (patrz poniżej).

Opóźnienie LEA zależy od trybu adresowania od procesorów z rodziny Intel SnB. 3c dla 3 składników ( [base+idx+const]co wymaga dwóch osobnych dodatków), ale tylko 1c z 2 lub mniejszą liczbą składników (jeden dodatek). Niektóre procesory (jak Core2) wykonują nawet 3-komponentowy LEA w jednym cyklu, ale nie robi tego rodzina SnB. Co gorsza, rodzina Intel SnB standaryzuje opóźnienia, więc nie ma 2c upops , w przeciwnym razie 3-komponentowa LEA byłaby tylko 2c jak Bulldozer. (3-komponentowy LEA jest również wolniejszy na AMD, tylko nie tak bardzo).

Tak więc lea rcx, [rax + rax*2]/ inc rcxma opóźnienie tylko 2c, szybsze niż lea rcx, [rax + rax*2 + 1]w przypadku procesorów Intel SnB z rodziny takich jak Haswell. Próg rentowności na BD i gorzej na Core2. Kosztuje to dodatkowy wzrost, co zwykle nie jest warte oszczędzania opóźnienia 1c, ale opóźnienie jest tutaj głównym wąskim gardłem, a Haswell ma wystarczająco szeroki rurociąg, aby poradzić sobie z dodatkową przepustowością wzrostu.

Ani gcc, icc, ani clang (na godbolt) nie używały danych wyjściowych CF SHR, zawsze używając AND lub TEST . Głupie kompilatory. : P Są świetnymi kawałkami złożonej maszynerii, ale sprytny człowiek często potrafi je pokonać w przypadku drobnych problemów. (Biorąc pod uwagę tysiące do milionów razy dłużej o tym myśleć, oczywiście! Kompilatory nie używają wyczerpujących algorytmów do wyszukiwania każdego możliwego sposobu działania, ponieważ zajęłoby to zbyt dużo czasu podczas optymalizacji dużej ilości wstawionego kodu, co jest tym, co robią najlepiej. Nie modelują również potoku w docelowej mikroarchitekturze, przynajmniej nie tak szczegółowo, jak IACA lub inne narzędzia do analizy statycznej; używają tylko heurystyki).

Proste rozwijanie pętli nie pomoże ; to wąskie gardło pętli opóźnia łańcuch zależności przenoszonej przez pętlę, a nie narzut / przepustowość pętli. Oznacza to, że poradziłby sobie z hyperthreading (lub innym rodzajem SMT), ponieważ CPU ma dużo czasu na przeplatanie instrukcji z dwóch wątków. Oznaczałoby to równoległe ułożenie pętli main, ale to dobrze, ponieważ każdy wątek może po prostu sprawdzić zakres nwartości i w rezultacie wygenerować parę liczb całkowitych.

Możliwe jest również przeplatanie ręczne w jednym wątku . Może obliczyć sekwencję dla pary liczb równolegle, ponieważ każda 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 .

Sztuczka decyduje, czy poczekać, aż wszystkie nwartości osiągną, 1zanim uzyska kolejną parę nwartości początkowych , czy też wyrwać się i uzyskać nowy punkt początkowy tylko dla tej, która osiągnęła 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 trzeba warunkowo zwiększyć jego licznik.

Być może możesz to zrobić z pakietem SSE-porównaj, aby warunkowo zwiększyć licznik elementów wektorowych, do których jeszcze nnie dotarł 1. A następnie, aby ukryć jeszcze dłuższe opóźnienie implementacji warunkowego przyrostu SIMD, będziesz musiał utrzymać więcej wektorów nwartości w powietrzu. Może warto tylko z wektorem 256b (4x uint64_t).

Myślę, że najlepszą strategią wykrycia 1„lepkiego” jest maskowanie wektora wszystkich, które dodajesz w celu zwiększenia licznika. Więc kiedy zobaczysz 1element w, wektor przyrostowy będzie miał zero, a + = 0 to brak operacji.

Niezbadany 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

    # 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 elementami zamiast ręcznie napisanego asm.

Poprawa algorytmu / implementacji:

Oprócz samej implementacji tej samej logiki z bardziej wydajnym asmem, poszukaj sposobów na uproszczenie logiki lub uniknięcie zbędnej pracy. np. zapamiętaj, aby wykryć wspólne zakończenia sekwencji. Albo jeszcze lepiej, spójrz na 8 bitów na raz (odpowiedź zgrzytacza)

@EOF wskazuje, że tzcnt(lub bsf) można wykorzystać do wielokrotnych n/=2iteracji w jednym kroku. To prawdopodobnie lepsze niż wektoryzacja SIMD; żadna instrukcja SSE lub AVX nie może tego zrobić. nJednak nadal jest kompatybilny z wykonywaniem wielu skalarów równolegle w różnych rejestrach liczb całkowitych.

Pętla może więc wyglądać następująco:

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 procesorów o zmiennej liczbie są powolne w procesorach z rodziny Intel SnB bez BMI2. 3 ups, opóźnienie 2c. (Mają zależność wejściową od FLAGS, ponieważ liczba = 0 oznacza, że ​​flagi są niezmodyfikowane. Obsługują to jako zależność danych i przyjmują wiele zmian, ponieważ Uop może mieć tylko 2 dane wejściowe (w każdym razie przed HSW / BDW)). Do tego odnoszą się ludzie narzekający na zwariowany projekt CISC x86. Powoduje to, że procesory x86 są wolniejsze niż byłyby, gdyby ISA został zaprojektowany od zera, 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 (opóźnienie 1 uop / 1c).

Umieszcza także tzcnt (3c na Haswell i późniejszych) na ścieżce krytycznej, dzięki czemu znacznie wydłuża całkowite opóźnienie łańcucha zależności przenoszonego przez pętlę. Eliminuje to jednak potrzebę posiadania CMOV lub przygotowania rejestru n>>1. Odpowiedź @ Veedrac przezwycięża to wszystko poprzez odroczenie tzcnt / shift dla wielu iteracji, co jest wysoce skuteczne (patrz poniżej).

Możemy bezpiecznie używać BSF lub TZCNT zamiennie, ponieważ nw tym momencie nigdy nie może być zero. Kod maszynowy TZCNT dekoduje się jako BSF na procesorach, które nie obsługują BMI1. (Prefiksy bez znaczenia 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 warto go używać REP BSF, nawet jeśli nie obchodzi Cię ustawienie ZF, jeśli wejście jest zerowe, a nie wyjściowe. Niektóre kompilatory robią to, __builtin_ctzllnawet jeśli używasz -mno-bmi.

Działają tak samo na procesorach Intela, więc po prostu zapisz bajt, jeśli to wszystko. TZCNT na platformie Intel (przed Skylake) wciąż ma fałszywą zależność od rzekomo operandu wyjściowego tylko do zapisu, podobnie jak BSF, w celu obsługi nieudokumentowanego zachowania, że ​​BSF z wejściem = 0 pozostawia swój cel niezmodyfikowany. Musisz więc obejść ten problem, chyba że zoptymalizujesz go tylko dla Skylake, więc nie możesz zyskać na dodatkowym bajcie REP. (Intel często wykracza poza to, czego wymaga instrukcja ISA x86, aby uniknąć łamania powszechnie używanego kodu, który zależy od czegoś, czego nie powinien, lub którego nie wolno z mocą wsteczną. Np. Windows 9x nie zakłada spekulacyjnego wstępnego pobierania wpisów TLB , co było bezpieczne kiedy kod został napisany, zanim Intel zaktualizował zasady zarządzania TLB ).

W każdym razie, LZCNT / TZCNT na Haswell mają takie same fałszywe informacje jak POPCNT: zobacz to pytania i odpowiedzi . Właśnie dlatego w wyjściu asm gcc dla kodu @ Veedrac widzisz, jak zrywa łańcuch dep z zerowaniem xor w rejestrze, który ma zamiar użyć jako miejsca docelowego TZCNT, gdy nie używa dst = src. Ponieważ TZCNT / LZCNT / POPCNT nigdy nie pozostawiają miejsca docelowego niezdefiniowanego lub niezmodyfikowanego, ta fałszywa zależność od wydajności procesorów Intela jest błędem / ograniczeniem wydajności. Przypuszczalnie warto, aby niektóre tranzystory / moc zachowywały się tak, jak inne urządzenia działające w tej samej jednostce wykonawczej. Jedyną zaletą jest interakcja z innym ograniczeniem uarch: mogą one operand pamięci z trybem indeksowanego adresowania na Haswell, ale na Skylake, gdzie Intel usunął fałszywą zależność dla LZCNT / TZCNT, „un-laminate” indeksowane tryby adresowania, podczas gdy POPCNT może nadal mikrowzłączać dowolny tryb addr.

Ulepszenia pomysłów / kodu wynikające z innych odpowiedzi:

Odpowiedź @ hidefromkgb zawiera miłą spostrzeżenie, że masz gwarancję, że będziesz w stanie wykonać jedną prawą zmianę po 3n + 1. Możesz to obliczyć jeszcze bardziej efektywnie niż pomijając sprawdzanie między krokami. Implementacja asm w tej odpowiedzi jest jednak zepsuta (zależy od OF, która jest niezdefiniowana po SHRD z liczbą> 1) i powolna: ROR rdi,2jest szybsza niż SHRD rdi,rdi,2, a użycie dwóch instrukcji CMOV na ścieżce krytycznej jest wolniejsze niż dodatkowy TEST które mogą działać równolegle.

Umieściłem uporządkowane / ulepszone C (które prowadzi kompilator do wytwarzania lepszego asm), i przetestowałem + działając szybciej asm (w komentarzach poniżej C) na Godbolt: patrz link w odpowiedzi @ hidefromkgb . (Ta odpowiedź osiągnęła limit 30k znaków z dużych adresów URL Godbolt, ale krótkie linki mogą gnić i były zbyt długie na goo.gl.)

Poprawiono także drukowanie wyjściowe w celu konwersji na ciąg znaków i tworzenia jednego write()zamiast pisania jednego znaku na raz. To minimalizuje wpływ na synchronizację czasową całego programu z perf stat ./collatz(do rejestrowania liczników wydajności), a ja zaciemniłem niektóre niekrytyczne asm.

@ Kod Veedrac

Dostałem niewielkie przyspieszenie od przesunięcia w prawo, o ile wiemy, że trzeba to zrobić, i sprawdzenia, czy mogę kontynuować pętlę. Od 7,5 s dla limitu = 1e8 do 7,275 s na Core2Duo (Merom), przy współczynniku rozwinięcia 16.

kod + komentarze na temat Godbolt . Nie używaj tej wersji z clang; robi coś głupiego z pętlą odroczenia. Użycie licznika tmp, ka następnie dodanie go do countpóźniejszych zmian zmienia działanie clang, ale to trochę boli gcc.

Zobacz dyskusję w komentarzach: kod Veedrac jest doskonały na procesorach z BMI1 (tj. Nie Celeron / Pentium)

Twierdzenie, że kompilator C ++ może generować bardziej optymalny kod niż kompetentny programista w asemblerze, jest bardzo błędnym błędem. A szczególnie w tym przypadku. Człowiek zawsze może uczynić kod lepszym niż kompilator, a ta konkretna sytuacja jest dobrą ilustracją tego twierdzenia.

Różnica w czasie jest widoczna, ponieważ kod asemblera w pytaniu jest bardzo daleki od optymalnego w wewnętrznych pętlach.

(Poniższy kod jest 32-bitowy, ale można go łatwo przekonwertować na 64-bitowy)

Na przykład funkcję sekwencji można zoptymalizować tylko do 5 instrukcji:

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

Cały kod wygląda następująco:

include "%lib%/freshlib.inc"
@BinaryType console, compact
options.DebugMode = 1
include "%lib%/freshlib.asm"

start:
        InitializeAll
        mov ecx, 999999
        xor edi, edi        ; max
        xor ebx, ebx        ; max i

    .main_loop:

        xor     esi, esi
        mov     eax, ecx

    .seq:
        inc     esi                 ; counter
        lea     edx, [3*eax+1]      ; edx = 3*n+1
        shr     eax, 1              ; eax = n/2
        cmovc   eax, edx            ; if CF eax = edx
        jnz     .seq                ; jmp if n<>1

        cmp     edi, esi
        cmovb   edi, esi
        cmovb   ebx, ecx

        dec     ecx
        jnz     .main_loop

        OutputValue "Max sequence: ", edi, 10, -1
        OutputValue "Max index: ", ebx, 10, -1

        FinalizeAll
        stdcall TerminateAll, 0

Aby skompilować ten kod, potrzebny jest FreshLib .

W moich testach (procesor AMD A4-1200 1 GHz) powyższy kod jest około cztery razy szybszy niż kod C ++ z pytania (po kompilacji z -O0: 430 ms vs. 1900 ms) i ponad dwa razy szybszy (430 ms vs. 830 ms) po kompilacji kodu C ++ -O3.

Dane wyjściowe obu programów są takie same: maksymalna sekwencja = 525 na i = 837799.

Dla większej wydajności: prosta zmiana polega na tym, że po n = 3n + 1 n będzie parzyste, więc możesz od razu podzielić przez 2. A n nie będzie wynosić 1, więc nie musisz go testować. Możesz więc zapisać kilka instrukcji if i napisać:

while (n % 2 == 0) n /= 2;
if (n > 1) for (;;) {
    n = (3*n + 1) / 2;
    if (n % 2 == 0) {
        do n /= 2; while (n % 2 == 0);
        if (n == 1) break;
    }
}

Oto wielka wygrana: jeśli spojrzysz na najniższe 8 bitów n, wszystkie kroki aż do podzielenia przez 2 osiem razy są całkowicie określone przez te osiem bitów. Na przykład, jeśli ostatnie osiem bitów ma wartość 0x01, to jest w formacie binarnym, twój numer to ???? 0000 0001, następne kroki to:

3n+1 -> ???? 0000 0100
/ 2  -> ???? ?000 0010
/ 2  -> ???? ??00 0001
3n+1 -> ???? ??00 0100
/ 2  -> ???? ???0 0010
/ 2  -> ???? ???? 0001
3n+1 -> ???? ???? 0100
/ 2  -> ???? ???? ?010
/ 2  -> ???? ???? ??01
3n+1 -> ???? ???? ??00
/ 2  -> ???? ???? ???0
/ 2  -> ???? ???? ????

Tak więc można przewidzieć wszystkie te kroki, a 256k + 1 zostanie zastąpione przez 81k + 1. Coś podobnego stanie się dla wszystkich kombinacji. Aby utworzyć pętlę za pomocą dużej instrukcji switch:

k = n / 256;
m = n % 256;

switch (m) {
    case 0: n = 1 * k + 0; break;
    case 1: n = 81 * k + 1; break; 
    case 2: n = 81 * k + 1; break; 
    ...
    case 155: n = 729 * k + 425; break;
    ...
}

Uruchom pętlę, aż n ≤ 128, ponieważ w tym momencie n może stać się 1 z mniej niż ośmioma podziałami na 2, a wykonanie ośmiu lub więcej kroków naraz sprawi, że przegapisz punkt, w którym osiągniesz 1 po raz pierwszy. Następnie kontynuuj „normalną” pętlę - lub przygotuj tabelę, która powie Ci, ile jeszcze kroków trzeba osiągnąć 1.

PS. Podejrzewam, że sugestia Petera Cordesa uczyniłaby to jeszcze szybszym. Nie będzie żadnych gałęzi warunkowych, z wyjątkiem jednej, i ta będzie poprawnie przewidywana, chyba że pętla faktycznie się zakończy. Więc kod byłby podobny

static const unsigned int multipliers [256] = { ... }
static const unsigned int adders [256] = { ... }

while (n > 128) {
    size_t lastBits = n % 256;
    n = (n >> 8) * multipliers [lastBits] + adders [lastBits];
}

W praktyce mierzyłbyś, czy przetwarzanie ostatnich 9, 10, 11, 12 bitów n jednocześnie byłoby szybsze. Dla każdego bitu liczba wpisów w tabeli podwoiłaby się i spodziewam się spowolnienia, gdy tabele nie będą już pasować do pamięci podręcznej L1.

PPS. Jeśli potrzebujesz liczby operacji: w każdej iteracji wykonujemy dokładnie osiem podziałów na dwa i zmienną liczbę operacji (3n + 1), więc oczywistą metodą zliczania operacji byłaby inna tablica. Ale możemy faktycznie obliczyć liczbę kroków (na podstawie liczby iteracji pętli).

Możemy nieco przedefiniować problem: Zamień n na (3n + 1) / 2, jeśli jest nieparzysty, a n na n / 2, jeśli parzysty. Następnie każda iteracja wykona dokładnie 8 kroków, ale można by pomyśleć o oszustwie :-) Załóżmy, że były operacje r n <- 3n + 1 i operacje s n <- n / 2. Wynik będzie całkiem dokładnie n '= n * 3 ^ r / 2 ^ s, ponieważ n <- 3n + 1 oznacza n <- 3n * (1 + 1 / 3n). Biorąc logarytm, znajdujemy r = (s + log2 (n '/ n)) / log2 (3).

Jeśli wykonamy pętlę, aż n ≤ 1 000 000 i będziemy mieć wstępnie obliczoną tabelę, ile iteracji potrzeba od dowolnego punktu początkowego n ≤ 1 000 000, wówczas obliczenie r jak powyżej, w zaokrągleniu do najbliższej liczby całkowitej, da właściwy wynik, chyba że s jest naprawdę duży.

Z raczej niepowiązanej uwagi: więcej hacków wydajnościowych!

• [pierwsza «przypuszczenie» zostało ostatecznie obalone przez @ShreevatsaR; oddalony]

• Przechodząc przez sekwencję, możemy uzyskać tylko 3 możliwe przypadki w 2 sąsiedztwie bieżącego elementu N(pokazane jako pierwsze):

  1. [nawet dziwne]
  2. [nieparzysty] [parzysty]
  3. [parzysty] [parzysty]

  Skoczyć obok tych elementów 2 środki do obliczania (N >> 1) + N + 1, ((N << 1) + N + 1) >> 1i N >> 2, odpowiednio.

  Let `wykazać, że w obydwu przypadkach (1) i (2), możliwe jest wykorzystanie pierwszego formuły (N >> 1) + N + 1.

  Przypadek (1) jest oczywisty. Przypadek (2) implikuje (N & 1) == 1, więc jeśli założymy (bez utraty ogólności), że N ma długość 2-bitową, a jego bity są baod najbardziej do najmniej znaczącego, a następnie a = 1, co następuje:

  (N << 1) + N + 1:     (N >> 1) + N + 1:
  
          b10                    b1
           b1                     b
         +  1                   + 1
         ----                   ---
         bBb0                   bBb

  gdzie B = !b. Przesunięcie w prawo pierwszego wyniku daje nam dokładnie to, czego chcemy.

  QED: (N & 1) == 1 ⇒ (N >> 1) + N + 1 == ((N << 1) + N + 1) >> 1.

  Jak udowodniono, możemy przechodzić przez sekwencję 2 elementów jednocześnie, za pomocą pojedynczej operacji trójskładnikowej. Kolejna 2-krotna redukcja czasu.

Wynikowy algorytm wygląda następująco:

uint64_t sequence(uint64_t size, uint64_t *path) {
    uint64_t n, i, c, maxi = 0, maxc = 0;

    for (n = i = (size - 1) | 1; i > 2; n = i -= 2) {
        c = 2;
        while ((n = ((n & 3)? (n >> 1) + n + 1 : (n >> 2))) > 2)
            c += 2;
        if (n == 2)
            c++;
        if (c > maxc) {
            maxi = i;
            maxc = c;
        }
    }
    *path = maxc;
    return maxi;
}

int main() {
    uint64_t maxi, maxc;

    maxi = sequence(1000000, &maxc);
    printf("%llu, %llu\n", maxi, maxc);
    return 0;
}

Porównujemy tutaj, n > 2ponieważ proces może zatrzymać się na 2 zamiast 1, jeśli całkowita długość sekwencji jest nieparzysta.

[EDYTOWAĆ:]

Przetłumaczmy to na zbiór!

MOV RCX, 1000000;



DEC RCX;
AND RCX, -2;
XOR RAX, RAX;
MOV RBX, RAX;

@main:
  XOR RSI, RSI;
  LEA RDI, [RCX + 1];

  @loop:
    ADD RSI, 2;
    LEA RDX, [RDI + RDI*2 + 2];
    SHR RDX, 1;
    SHRD RDI, RDI, 2;    ror rdi,2   would do the same thing
    CMOVL RDI, RDX;      Note that SHRD leaves OF = undefined with count>1, and this doesn't work on all CPUs.
    CMOVS RDI, RDX;
    CMP RDI, 2;
  JA @loop;

  LEA RDX, [RSI + 1];
  CMOVE RSI, RDX;

  CMP RAX, RSI;
  CMOVB RAX, RSI;
  CMOVB RBX, RCX;

  SUB RCX, 2;
JA @main;



MOV RDI, RCX;
ADD RCX, 10;
PUSH RDI;
PUSH RCX;

@itoa:
  XOR RDX, RDX;
  DIV RCX;
  ADD RDX, '0';
  PUSH RDX;
  TEST RAX, RAX;
JNE @itoa;

  PUSH RCX;
  LEA RAX, [RBX + 1];
  TEST RBX, RBX;
  MOV RBX, RDI;
JNE @itoa;

POP RCX;
INC RDI;
MOV RDX, RDI;

@outp:
  MOV RSI, RSP;
  MOV RAX, RDI;
  SYSCALL;
  POP RAX;
  TEST RAX, RAX;
JNE @outp;

LEA RAX, [RDI + 59];
DEC RDI;
SYSCALL;

Użyj tych poleceń, aby skompilować:

nasm -f elf64 file.asm
ld -o file file.o

Zobacz C i ulepszoną / poprawioną wersję asm autorstwa Peter Cordes na Godbolt . (uwaga redaktora: przepraszam, że umieściłem moje odpowiedzi w odpowiedzi, ale moja odpowiedź przekroczyła limit 30 000 znaków z linków i tekstu Godbolta!)

Programy C ++ są tłumaczone na programy asemblacyjne podczas generowania kodu maszynowego z kodu źródłowego. Byłoby praktycznie błędem powiedzieć, że asembler jest wolniejszy niż C ++. Ponadto generowany kod binarny różni się w zależności od kompilatora. Tak więc inteligentny kompilator C ++ może generować kod binarny bardziej optymalny i wydajny niż kod głupiego asemblera.

Uważam jednak, że twoja metodologia profilowania ma pewne wady. Poniżej przedstawiono ogólne wytyczne dotyczące profilowania:

1. Upewnij się, że system jest w stanie normalnym / bezczynności. Zatrzymaj wszystkie uruchomione procesy (aplikacje), które uruchomiłeś lub które intensywnie wykorzystują procesor (lub odpytuj przez sieć).
2. Twój rozmiar danych musi być większy.
3. Twój test musi trwać dłużej niż 5-10 sekund.
4. Nie polegaj tylko na jednej próbce. Wykonaj test N razy. Zbierz wyniki i oblicz średnią lub medianę wyniku.

W przypadku problemu Collatz można znacznie zwiększyć wydajność, buforując „ogony”. Jest to kompromis czas / pamięć. Zobacz: memoization ( https://en.wikipedia.org/wiki/Memoization ). Możesz także przyjrzeć się rozwiązaniom dynamicznego programowania dla innych kompromisów czasu / pamięci.

Przykładowa implementacja Pythona:

import sys

inner_loop = 0

def collatz_sequence(N, cache):
    global inner_loop

    l = [ ]
    stop = False
    n = N

    tails = [ ]

    while not stop:
        inner_loop += 1
        tmp = n
        l.append(n)
        if n <= 1:
            stop = True  
        elif n in cache:
            stop = True
        elif n % 2:
            n = 3*n + 1
        else:
            n = n // 2
        tails.append((tmp, len(l)))

    for key, offset in tails:
        if not key in cache:
            cache[key] = l[offset:]

    return l

def gen_sequence(l, cache):
    for elem in l:
        yield elem
        if elem in cache:
            yield from gen_sequence(cache[elem], cache)
            raise StopIteration

if __name__ == "__main__":
    le_cache = {}

    for n in range(1, 4711, 5):
        l = collatz_sequence(n, le_cache)
        print("{}: {}".format(n, len(list(gen_sequence(l, le_cache)))))

    print("inner_loop = {}".format(inner_loop))

Z komentarzy:

Ale ten kod nigdy się nie zatrzymuje (z powodu przepełnienia liczb całkowitych)!?! Yves Daoust

W przypadku wielu liczb nie przepełni się.

Jeśli to będzie przelewać - w jednym z tych pechowców początkowych nasion, liczba przelot ten najprawdopodobniej zbiegają się ku 1 bez innej przepełnienie.

Nadal jest to interesujące pytanie, czy jest jakaś przepełniona cyklicznie liczba nasion?

Jakakolwiek prosta końcowa seria zbieżna zaczyna się od potęgi dwóch wartości (dość oczywistej?).

2 ^ 64 przepełni się do zera, co jest nieokreśloną nieskończoną pętlą zgodnie z algorytmem (kończy się na 1), ale najbardziej optymalne rozwiązanie w odpowiedzi zakończy się z powodu shr raxwytworzenia ZF = 1.

Czy możemy wyprodukować 2 ^ 64? Jeśli liczbą początkową jest 0x5555555555555555, jest to liczba nieparzysta, następna liczba to 3n + 1, czyli 0xFFFFFFFFFFFFFFFF + 1= 0. Teoretycznie w nieokreślonym stanie algorytmu, ale zoptymalizowana odpowiedź johnfound zostanie odzyskana po wyjściu na ZF = 1. Thecmp rax,1 Peter Cordes zakończy się nieskończoną pętlą (wariant 1 QED, „tani” przez nieokreśloną 0liczbę).

Co powiesz na bardziej złożoną liczbę, bez której powstanie cykl 0? Szczerze mówiąc, nie jestem pewien, moja teoria matematyki jest zbyt mglista, aby uzyskać poważny pomysł, jak sobie z tym poradzić na poważnie. Ale intuicyjnie powiedziałbym, że szereg będzie zbieżny do 1 dla każdej liczby: 0 <liczba, ponieważ formuła 3n + 1 powoli zmieni każdy nie-2 czynnik pierwotny liczby pierwotnej (lub pośredniej) w pewną potęgę 2, prędzej czy później . Więc nie musimy się martwić o nieskończoną pętlę dla oryginalnych serii, tylko przepełnienie może nam przeszkodzić.

Po prostu włożyłem kilka liczb do arkusza i przyjrzałem się 8-bitowym obciętym liczbom.

Istnieją trzy wartości przepełnione się 0: 227, 170i 85( 85przechodząc bezpośrednio do 0, pozostałe dwa postępuje w kierunku85 ).

Ale nie ma wartości, która tworzy cykliczne ziarno przepełnienia.

Co zabawne, zrobiłem sprawdzian, który jest pierwszym numerem, który cierpi na 8-bitowe obcięcie, i już 27ma to wpływ! Osiąga wartość 9232w odpowiedniej nieciętej serii (pierwsza obcięta wartość jest 322w 12 kroku), a maksymalna wartość osiągnięta dla dowolnej z 2-255 liczb wejściowych w nie obciętej postaci to 13120(dla 255siebie) maksymalna liczba kroków konwergencja 1to około 128(+ -2, nie jestem pewien, czy „1” ma się liczyć itp.).

Co ciekawe (dla mnie) liczba 9232jest maksymalna dla wielu innych numerów źródłowych, co jest w tym takiego wyjątkowego? : -O 9232= 0x2410... hmmm .. nie mam pojęcia.

Niestety nie mogę dokładnie zrozumieć tej serii, dlaczego się zbiega i jakie są implikacje obcięcia ich do k bitów, ale z cmp number,1warunkiem zakończenia z pewnością możliwe jest umieszczenie algorytmu w nieskończonej pętli z określoną wartością wejściową kończącą się na0 po obcięcie.

Ale wartość 27przepełnienia dla przypadku 8-bitowego jest swego rodzaju ostrzeżeniem, wygląda to tak, że jeśli policzysz liczbę kroków do osiągnięcia wartości 1, otrzymujesz błędny wynik dla większości liczb z całkowitego zestawu k-bitowych liczb całkowitych. W przypadku 8-bitowych liczb całkowitych 146 na 256 liczb miało wpływ na serię przez obcięcie (niektóre z nich mogą nadal przypadkowo osiągnąć odpowiednią liczbę kroków, być może jestem zbyt leniwy, aby to sprawdzić).

Nie opublikowałeś kodu wygenerowanego przez kompilator, więc jest tu trochę zgadywania, ale nawet bez jego obejrzenia można powiedzieć, że:

test rax, 1
jpe even

... ma 50% szansy na błędne przewidzenie branży, a to będzie kosztowne.

Kompilator prawie na pewno wykonuje oba obliczenia (które kosztują niewiarygodnie więcej, ponieważ div / mod ma dość długie opóźnienie, więc wielokrotne dodawanie jest „darmowe”) i kontynuuje CMOV. Co oczywiście ma zerową szansę na błędne przewidywanie.

Nawet bez patrzenia na montaż, najbardziej oczywistym powodem jest to, że /= 2prawdopodobnie jest zoptymalizowany jako>>=1 wiele procesorów ma bardzo szybką zmianę. Ale nawet jeśli procesor nie ma operacji przesunięcia, dzielenie liczb całkowitych jest szybsze niż dzielenie zmiennoprzecinkowe.

Edycja: Twój przebieg może się różnić w zależności od powyższej instrukcji „dzielenie liczb całkowitych jest szybsze niż dzielenie zmiennoprzecinkowe”. Poniższe komentarze pokazują, że w nowoczesnych procesorach priorytetem jest optymalizacja podziału fp zamiast podziału na liczby całkowite. Więc jeśli ktoś szukaliśmy najbardziej prawdopodobny powód SpeedUp których kwestia tego wątku prosi o, a następnie kompilatora /=2jak >>=1byłby najlepszy 1. miejsce na wygląd.

W przypadku niepowiązanej nuty , jeśli njest nieparzyste, wyrażenie n*3+1zawsze będzie parzyste. Nie trzeba więc sprawdzać. Możesz zmienić tę gałąź na

{
   n = (n*3+1) >> 1;
   count += 2;
}

Tak więc byłoby to całe stwierdzenie

if (n & 1)
{
    n = (n*3 + 1) >> 1;
    count += 2;
}
else
{
    n >>= 1;
    ++count;
}

Jako ogólna odpowiedź, nie ukierunkowana konkretnie na to zadanie: W wielu przypadkach można znacznie przyspieszyć dowolny program, wprowadzając ulepszenia na wysokim poziomie. Jak obliczanie danych raz, a nie wiele razy, całkowite unikanie niepotrzebnej pracy, najlepsze użycie pamięci podręcznej i tak dalej. Te rzeczy są znacznie łatwiejsze do zrobienia w języku wysokiego poziomu.

Możliwe jest pisanie kodu asemblera poprawić działanie kompilatora optymalizującego, ale jest to ciężka praca. A kiedy to zrobisz, twój kod jest znacznie trudniejszy do zmodyfikowania, więc znacznie trudniej jest dodać ulepszenia algorytmiczne. Czasami procesor ma funkcjonalność, której nie można używać z języka wysokiego poziomu, asemblacja wbudowana jest często przydatna w takich przypadkach i nadal pozwala na używanie języka wysokiego poziomu.

W problemach Eulera przez większość czasu udaje Ci się zbudować coś, dowiedzieć się, dlaczego jest on wolny, zbudować coś lepszego, dowiedzieć się, dlaczego jest wolny, i tak dalej. To bardzo, bardzo trudne przy użyciu asemblera. Lepszy algorytm przy połowie możliwej prędkości zwykle pokonuje gorszy algorytm przy pełnej prędkości, a uzyskanie pełnej prędkości w asemblerze nie jest trywialne.

Prosta odpowiedź:

• robienie MOV RBX, 3 i MUL RBX jest kosztowne; po prostu DODAJ RBX, RBX dwa razy

• ADD 1 jest prawdopodobnie szybszy niż INC tutaj

• MOV 2 i DIV są bardzo drogie; po prostu przesuń w prawo

• Kod 64-bitowy jest zwykle zauważalnie wolniejszy niż kod 32-bitowy, a problemy z wyrównaniem są bardziej skomplikowane; przy takich małych programach trzeba je spakować, aby wykonywać obliczenia równoległe, aby mieć szansę na szybsze działanie niż kod 32-bitowy

Jeśli wygenerujesz listę zestawów dla swojego programu C ++, możesz zobaczyć, jak różni się ona od zestawu.