Kod C ++ do testowania hipotezy Collatza szybciej niż zestaw odręczny - dlaczego?

832

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

jeffer syn
źródło
232
Czy sprawdziłeś kod asemblera generowany przez GCC dla twojego programu C ++?
ruakh
69
Skompiluj z, -Saby uzyskać zestaw wygenerowany przez kompilator. Kompilator jest wystarczająco inteligentny, aby zdać sobie sprawę, że moduł wykonuje podział w tym samym czasie.
user3386109,
267
Myślę, że twoje opcje to 1. Twoja technika pomiaru jest wadliwa, 2. Kompilator pisze lepszy zestaw niż ty lub 3. Kompilator używa magii.
Galik
17
Wygeneruj asm z kodem C + przeplatanymi numerami linii i porównaj notatki.
legends2k
18
@jefferson Kompilator może używać szybszej brutalnej siły. Na przykład może z instrukcjami SSE.
user253751,

Odpowiedzi:

1896

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że 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)

Peter Cordes
źródło
4
Jakiś czas temu wypróbowałem podejście wektoryzowane, nie pomogło (ponieważ możesz zrobić znacznie lepiej w kodzie skalarnym tzcnti jesteś zamknięty na najdłużej działającej sekwencji wśród elementów wektorowych w przypadku wektoryzowanym).
EOF
3
@EOF: nie, miałem na myśli wyrwanie się z wewnętrznej pętli, gdy uderzy jeden z elementów wektora 1, zamiast gdy wszystkie mają (łatwo wykrywalne za pomocą PCMPEQ / PMOVMSK). Następnie używasz kodu PINSRQ i innych rzeczy, aby majstrować przy jednym elemencie, który się zakończył (i jego liczniki) i wskoczyć z powrotem do pętli. Może to łatwo przerodzić się w stratę, gdy zbyt często wychodzisz z wewnętrznej pętli, ale to oznacza, że ​​zawsze dostajesz 2 lub 4 elementy użytecznej pracy wykonanej przy każdej iteracji wewnętrznej pętli. Dobra uwaga na temat zapamiętywania.
Peter Cordes,
4
@jefferson Best I manage to godbolt.org/g/1N70Ib . Miałem nadzieję, że uda mi się zrobić coś mądrzejszego, ale wydaje się, że nie.
Veedrac
87
Rzeczą, która zadziwia mnie niesamowitymi odpowiedziami, takimi jak ta, jest wiedza pokazana z tak szczegółami. Nigdy nie poznam języka ani systemu na tym poziomie i nie wiedziałbym, jak to zrobić. Dobra robota, proszę pana.
camden_kid
8
Legendarna odpowiedź !!
Sumit Jain
104

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.

johnfound
źródło
6
Huh, to sprytne. SHR ustawia ZF tylko wtedy, gdy EAX wynosił 1 (lub 0). Brakowało mi tego podczas optymalizacji -O3wyjścia gcc , ale zauważyłem wszystkie inne optymalizacje, które wprowadziłeś w wewnętrznej pętli. (Ale dlaczego używasz LEA do przyrostu licznika zamiast INC? Można w tym momencie zablokować flagi i doprowadzić do spowolnienia czegokolwiek oprócz P4 (fałszywa zależność od starych flag dla INC i SHR). LEA może t działa na tylu portach i może prowadzić do konfliktów zasobów częściej opóźniających ścieżkę krytyczną.)
Peter Cordes,
4
Och, właściwie Bulldozer może ograniczać przepustowość przy wyjściu kompilatora. Ma mniej opóźnień CMOV i 3-komponentowy LEA niż Haswell (co rozważałem), więc łańcuch deponowany w pętli ma tylko 3 cykle w twoim kodzie. Nie ma też instrukcji MOV o zerowej latencji dla rejestrów liczb całkowitych, więc zmarnowane instrukcje MOV g ++ faktycznie zwiększają opóźnienie ścieżki krytycznej i są dużą sprawą dla Bulldozera. Tak, optymalizacja dłoni naprawdę pokonuje kompilator w znaczący sposób dla procesorów, które nie są wystarczająco nowoczesne, aby przeżuwać bezużyteczne instrukcje.
Peter Cordes,
95
Twierdzenie, że kompilator C ++ jest lepszy, jest bardzo błędną pomyłką. A szczególnie w tym przypadku. Człowiek zawsze może poprawić kod, a ten konkretny problem jest dobrą ilustracją tego roszczenia. ” Możesz go odwrócić i byłby równie ważny . „ Twierdzenie, że człowiek jest lepszy, jest bardzo błędną pomyłką. A szczególnie w tym przypadku. Człowiek zawsze może pogorszyć kod , a to i to konkretne pytanie jest dobrą ilustracją tego twierdzenia. ” Nie sądzę więc, abyś miał rację tutaj , takie uogólnienia są błędne.
luk32
5
@ luk32 - Ale autor pytania nie może być żadnym argumentem, ponieważ jego znajomość języka asemblerowego jest bliska zeru. Wszystkie argumenty na temat człowieka kontra kompilatora domyślnie zakładają, że człowiek posiada przynajmniej pewien średni poziom wiedzy asm. Więcej: Twierdzenie „Ludzki kod napisany zawsze będzie lepszy lub taki sam jak kod generowany przez kompilator” jest bardzo łatwy do formalnego udowodnienia.
johnfound
30
@ luk32: Doświadczony człowiek może (i zwykle powinien) zacząć od wyjścia kompilatora. Tak długo, jak porównujesz swoje próby upewnienia się, że faktycznie są one szybsze (na docelowym sprzęcie, do którego stroisz), nie możesz zrobić gorszego niż kompilator. Ale tak, muszę się zgodzić, że to trochę mocne stwierdzenie. Kompilatory zwykle radzą sobie znacznie lepiej niż nowi koderzy asm. Ale zwykle możliwe jest zapisanie instrukcji lub dwóch w porównaniu z tym, co wymyślą kompilatory. (Nie zawsze jednak na ścieżce krytycznej, w zależności od uarch). Są bardzo przydatnymi częściami skomplikowanych maszyn, ale nie są „inteligentne”.
Peter Cordes,
24

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.

gnasher729
źródło
2
Lub utwórz tabele wyszukiwania danych dla mnożenia i dodaj stałe zamiast przełącznika. Indeksowanie dwóch 256-wejściowych tabel jest szybsze niż tabela skoków, a kompilatory prawdopodobnie nie szukają takiej transformacji.
Peter Cordes,
1
Hmm, przez chwilę myślałem, że ta obserwacja może potwierdzić hipotezę Collatza, ale nie, oczywiście, że nie. Dla każdego możliwego końcowego 8 bitów istnieje skończona liczba kroków, aż wszystkie znikną. Ale niektóre z tych 8-bitowych wzorców wydłużą resztę łańcucha bitów o więcej niż 8, więc nie można wykluczyć nieograniczonego wzrostu lub powtarzającego się cyklu.
Peter Cordes,
Aby zaktualizować count, potrzebujesz trzeciej tablicy, prawda? adders[]nie mówi ci, ile wykonano przesunięć w prawo.
Peter Cordes,
W przypadku większych tabel warto byłoby użyć węższych typów, aby zwiększyć gęstość pamięci podręcznej. W większości architektur obciążenie rozciągające się od zera uint16_tjest bardzo tanie. Na x86 jest tak samo tani jak rozszerzanie zera z wersji 32-bitowej unsigned intna uint64_t. (MOVZX z pamięci na procesorach firmy Intel wymaga jedynie UOP obciążenia portu, ale AMD procesory potrzebują ALU jak również.) Oh BTW, dlaczego używasz size_tdo lastBits? Jest to 32-bitowy typ z -m32, a nawet -mx32(tryb długi z 32-bitowymi wskaźnikami). To zdecydowanie niewłaściwy typ n. Po prostu użyj unsigned.
Peter Cordes,
20

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!)

hidefromkgb
źródło
2
Nie ma Qtakiej całki 12 = 3Q + 1. Twój pierwszy punkt jest niewłaściwy, uważa.
Veedrac
1
@ Veedrac: bawiłem się tym: można go wdrożyć z lepszym asmem niż implementacja w tej odpowiedzi, używając ROR / TEST i tylko jednego CMOV. Ten kod asm nieskończone pętle na moim procesorze, ponieważ najwyraźniej opiera się na OF, który jest niezdefiniowany po SHRD lub ROR z licznikiem> 1. Również bardzo się stara, aby tego uniknąć mov reg, imm32, najwyraźniej aby zaoszczędzić bajty, ale potem używa 64-bitowa wersja rejestru wszędzie, nawet dla xor rax, rax, więc ma wiele niepotrzebnych prefiksów REX. Oczywiście potrzebujemy tylko REX na regach trzymających nw wewnętrznej pętli, aby uniknąć przepełnienia.
Peter Cordes,
1
Wyniki pomiaru czasu (z Core2Duo E6600: Merom 2,4 GHz. Complex-LEA = opóźnienie 1c, CMOV = 2c) . Najlepsza implementacja pętli wewnętrznej asm w jednym kroku (od Johnfound): 111ms na przebieg tej pętli @main. Dane wyjściowe kompilatora z mojej zaciemnionej wersji tego C (z niektórymi wersjami tmp): clang3.8 -O3 -march=core2: 96ms. gcc5.2: 108ms. Z mojej ulepszonej wersji wewnętrznej pętli asmowej clanga: 92ms (powinno to zobaczyć znacznie większą poprawę w rodzinie SnB, gdzie złożona LEA to 3c, a nie 1c). Z mojej ulepszonej + działającej wersji tej pętli asmowej (używając ROR + TEST, a nie SHRD): 87ms. Mierzone 5 powtórzeniami przed drukowaniem
Peter Cordes,
2
Oto pierwszych 66 rekordów (A006877 w OEIS); Te parzyste zaznaczyłem pogrubioną czcionką: 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799, 1117065, 1501353 1723519, 2298025, 3064033, 3542887, 3732423, 5649499, 6649279, 8400511, 11200681, 14934241, 15733191, 31466382, 36791535, 63728127, 127456254, 169941673, 226588897, 268549803, 537099606, 670617279, 1341234558
ShreevatsaR
1
@hidefromkgb Świetnie! Teraz doceniam także twój drugi punkt: 4k + 2 → 2k + 1 → 6k + 4 = (4k + 2) + (2k + 1) + 1 i 2k + 1 → 6k + 4 → 3k + 2 = ( 2k + 1) + (k) + 1. Dobra obserwacja!
ShreevatsaR
6

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.
Mangu Singh Rajpurohit
źródło
Tak, nie przeprowadziłem żadnego formalnego profilowania, ale uruchomiłem je oba razy i jestem w stanie powiedzieć 2 sekundy z 3 sekund. W każdym razie dzięki za odpowiedź.
Zebrałem
9
Prawdopodobnie nie jest to tylko błąd pomiaru, ręcznie pisany kod asm używa 64-bitowej instrukcji DIV zamiast przesunięcia w prawo. Zobacz moją odpowiedź. Ale tak, prawidłowe pomiary również są ważne.
Peter Cordes,
7
Punktory mają bardziej odpowiednie formatowanie niż blok kodu. Przestań wstawiać tekst do bloku kodu, ponieważ nie jest on kodem i nie korzysta z czcionki o stałej szerokości.
Peter Cordes,
16
Naprawdę nie rozumiem, jak to odpowiada na pytanie. Nie jest to niejasne pytanie, czy kod asemblera lub kod C ++ może być szybszy --- to bardzo konkretne pytanie o rzeczywisty kod , który jest pomocny w samym pytaniu. Twoja odpowiedź nawet nie wspomina o żadnym z tych kodów ani nie dokonuje żadnego porównania. Jasne, twoje wskazówki dotyczące testów porównawczych są w zasadzie poprawne, ale niewystarczające, aby udzielić prawdziwej odpowiedzi.
Cody Gray
6

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))
Emanuel Landeholm
źródło
1
Odpowiedź gnashera pokazuje, że możesz zrobić znacznie więcej niż tylko buforować ogony: wysokie bity nie wpływają na to, co stanie się dalej, a dodawanie / mul tylko propaguje przeniesienie w lewo, więc wysokie bity nie wpływają na to, co dzieje się z niskimi bitami. tzn. możesz użyć odnośników LUT, aby przejść 8 (lub dowolną liczbę) bitów jednocześnie, z mnożeniem i dodawaniem stałych w celu zastosowania do reszty bitów. zapamiętywanie ogonów jest z pewnością pomocne w wielu takich problemach, a dla tego problemu, gdy nie pomyślałeś jeszcze o lepszym podejściu lub nie udowodniłeś, że jest poprawny.
Peter Cordes,
2
Jeśli dobrze rozumiem powyższy pomysł zgrzytacza, uważam, że zapamiętywanie ogona jest optymalizacją ortogonalną. Więc możesz zrobić jedno i drugie. Interesujące byłoby zbadanie, ile można zyskać dzięki dodaniu zapamiętywania do algorytmu zgrabiarki.
Emanuel Landeholm
2
Być może możemy uczynić zapamiętywanie tańszym, przechowując tylko gęstą część wyników. Ustaw górny limit na N, a powyżej, nawet nie sprawdzaj pamięci. Poniżej użyj funkcji skrótu (N) -> N jako funkcji skrótu, więc klucz = pozycja w tablicy i nie trzeba jej przechowywać. Wpis 0środków jeszcze nieobecny. Możemy dalej optymalizować, przechowując tylko nieparzyste N w tabeli, więc funkcja skrótu polega na n>>1odrzuceniu 1. Napisz kod kroku, aby zawsze kończył się znakiem a n>>tzcnt(n)lub czymś, aby upewnić się, że jest nieparzysty.
Peter Cordes,
1
Opiera się to na moim (nieprzetestowanym) pomyśle, że bardzo duże wartości N w środku sekwencji są mniej prawdopodobne, że będą wspólne dla wielu sekwencji, więc nie tracimy zbyt wiele z zapominania o nich. Również, że rozsądnej wielkości N będzie częścią wielu długich sekwencji, nawet tych, które zaczynają się od bardzo dużej N. (To może być myślenie życzeniowe; jeśli jest błędne, tylko buforowanie gęstego zakresu kolejnych N może stracić vs. tabela, w której można przechowywać dowolne klucze.) Czy wykonałeś już jakieś testy trafień, aby sprawdzić, czy początkowy N w pobliżu ma jakieś podobieństwo w swoich wartościach sekwencji?
Peter Cordes,
2
Możesz po prostu zapisać wcześniej obliczone wyniki dla wszystkich n <N, dla niektórych dużych N. Więc nie potrzebujesz narzutu tabeli skrótów. Dane w tej tabeli zostaną ostatecznie wykorzystane dla każdej wartości początkowej. Jeśli chcesz tylko potwierdzić, że sekwencja Collatz zawsze kończy się na (1, 4, 2, 1, 4, 2, ...): Można to udowodnić jako równoważne z udowodnieniem, że dla n> 1, sekwencja ostatecznie być mniejszy niż oryginalny n. I do tego ogony buforowania nie pomogą.
gnasher729,
5

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ć).

Ped7g
źródło
„przepełniona liczba najprawdopodobniej zbliży się do 1 bez kolejnego przepełnienia”: kod nigdy się nie zatrzymuje. (To przypuszczenie, ponieważ nie mogę się doczekać końca czasów, aby się upewnić ...)
Yves Daoust
@ YvesDaoust, oh, ale tak jest? ... na przykład 27seria z obcięciem 8b wygląda następująco: 82 41 124 62 31 94 47 142 71 214 107 66 (obcięta) 33 100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 (reszta działa bez obcięcia). Przepraszam, nie rozumiem cię. Nigdy by się nie zatrzymało, gdyby skrócona wartość była równa części wcześniej osiągniętej w obecnie trwających seriach, i nie mogę znaleźć żadnej takiej wartości w porównaniu do skrótu k-bitowego (ale ja też nie mogę zrozumieć teorii matematyki, dlaczego wstrzymuje się to do obcięcia 8/16/32/64 bitów, intuicyjnie myślę, że to działa).
Ped7g,
1
Powinienem był wcześniej sprawdzić oryginalny opis problemu: „Chociaż nie zostało to jeszcze udowodnione (problem Collatz), uważa się, że wszystkie liczby początkowe kończą się na 1”. ... ok, nic dziwnego, że nie może dostać znajomość z moim ograniczony mglistej wiedzy Math ...: D A z moich doświadczeń z blachy Mogę was zapewnić, że są zbieżne dla każdego 2- 255liczby, albo bez obcinania (do 1), lub z 8-bitowym skróceniem (do oczekiwanego 1lub do 0trzech liczb).
Ped7g,
Hem, kiedy mówię, że nigdy się nie kończy, mam na myśli ... że się nie kończy. Podany kod działa wiecznie, jeśli wolisz.
Yves Daoust,
1
Wybrany do analizy tego, co dzieje się w przypadku przepełnienia. Pętla oparta na CMP mogłaby użyć cmp rax,1 / jna(tj. do{}while(n>1)) Również do zakończenia na zero. Pomyślałem o stworzeniu instrumentalnej wersji pętli, która rejestrowałaby maksimum n, aby dać wyobrażenie o tym, jak blisko jesteśmy do przepełnienia.
Peter Cordes,
5

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.

Damon
źródło
1
Rozgałęzienie ma pewien wzór; np. po liczbie nieparzystej zawsze następuje liczba parzysta. Ale czasami 3n + 1 pozostawia wiele końcowych zerowych bitów, i wtedy to źle zrozumie. Zacząłem pisać o podziale w swojej odpowiedzi i nie odniosłem się do tej innej dużej czerwonej flagi w kodzie OP. (Należy również zauważyć, że stosowanie warunku parzystości jest naprawdę dziwne, w porównaniu do tylko JZ lub CMOVZ. Jest to również gorsze dla procesora, ponieważ procesory Intel mogą makrozłączać TEST / JZ, ale nie TEST / JPE. Agner Fog twierdzi, że AMD może połączyć dowolny TEST / CMP z dowolnym JCC, więc w takim przypadku jest to tylko gorsze dla ludzkich czytelników)
Peter Cordes
5

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;
}
Dmitrij Rubanowicz
źródło
4
Dzielenie liczb całkowitych nie jest w rzeczywistości szybsze niż dzielenie FP na współczesnych procesorach x86. Myślę, że jest to spowodowane tym, że Intel / AMD wydają więcej tranzystorów na dzielniki FP, ponieważ jest to ważniejsza operacja. (Dzielenie liczb całkowitych przez stałe można zoptymalizować do przemnożenia przez odwrotność modułową). Sprawdź tabele wewnętrzne Agner Fog i porównaj DIVSD (liczba zmiennoprzecinkowa podwójnej precyzji) z DIV r32(32-bitowa liczba całkowita bez znaku) lub DIV r64(znacznie wolniejsza 64-bitowa liczba całkowita bez znaku). Zwłaszcza w przypadku przepustowości podział FP jest znacznie szybszy (pojedynczy UOP zamiast mikrokodowany i częściowo potokowy), ale opóźnienie jest również lepsze.
Peter Cordes,
1
np. na procesorze Haswell OP: DIVSD ma 1 impuls, 10-20 cykli opóźnienia, jeden na przepustowość 8-14c. div r64wynosi 36 ups, opóźnienie 32-96c i jeden na przepustowość 21-74c. Skylake ma jeszcze szybszą przepustowość podziału FP (potokowo jeden na 4c z niewiele lepszym opóźnieniem), ale niewiele szybszy div liczby całkowitej. Podobnie jest w przypadku rodziny buldożerów AMD: DIVSD ma operację 1M, opóźnienie 9-27c, jeden na przepustowość 4,5-11c. div r64jest 16M-ops, opóźnienie 16-75c, jeden na przepustowość 16-75c.
Peter Cordes,
1
Czy podział FP nie jest w zasadzie taki sam jak wykładniki liczb całkowitych odejmowanych, mantysja dzieląca liczby całkowite, wykrywa denormale? Te 3 kroki można wykonać równolegle.
MSalters
2
@MSalters: tak, to brzmi dobrze, ale z krokiem normalizacji na końcu przesunięcia bitów między wykładnikiem a modliszką. doublema 53-bitową mantysę, ale nadal jest znacznie wolniejszy niż div r32na Haswell. Zdecydowanie jest to tylko kwestia tego, ile sprzętu Intel / AMD rzuca na problem, ponieważ nie używają tych samych tranzystorów dla dzielników liczb całkowitych i fp. Liczba całkowita jest skalarna (nie ma podziału na liczbę całkowitą-SIMD), a wektor obsługuje wektory 128b (nie 256b jak inne ALU wektorów). Najważniejsze jest to, że liczba całkowita div ma wiele zalet, duży wpływ na otaczający kod.
Peter Cordes,
Err, nie przesuwaj bitów między mantysą a wykładnikiem, ale znormalizuj mantysę za pomocą przesunięcia i dodaj wielkość przesunięcia do wykładnika.
Peter Cordes,
4

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.

gnasher729
źródło
2
Całkowicie się z tym zgadzam. gcc -O3stworzył kod, który mieścił się w zakresie 20% wartości optymalnej dla Haswell, dla tego dokładnego algorytmu. (Uzyskiwanie tych przyspieszeń było głównym celem mojej odpowiedzi tylko dlatego, że o to pytano i ma interesującą odpowiedź, a nie dlatego, że jest to właściwe podejście.) Znacznie większe przyspieszenia uzyskano z transformacji, których kompilator nie szukałby bardzo , np. odraczanie właściwych zmian lub wykonywanie 2 kroków naraz. Znacznie większe przyspieszenia niż te można uzyskać z tabel notatek / wyszukiwania. Wciąż wyczerpujące testy, ale nie czysta brutalna siła.
Peter Cordes,
2
Mimo to prosta implementacja, która jest oczywiście poprawna, jest niezwykle przydatna do testowania innych implementacji. Chciałbym tylko spojrzeć na dane wyjściowe asm, aby sprawdzić, czy gcc zrobił to bez rozgałęzień, jak się spodziewałem (głównie z ciekawości), a następnie przejść do ulepszeń algorytmicznych.
Peter Cordes,
-2

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.

Tyler Durden
źródło
4
1): dodanie 3 razy byłoby głupie w porównaniu do LEA. Również mul rbxna procesorze Haswell OP jest 2 ups z opóźnieniem 3c (i 1 na przepustowość zegara). imul rcx, rbx, 3wynosi tylko 1 impuls, przy tym samym opóźnieniu 3c. Dwie instrukcje ADD będą 2 upops z opóźnieniem 2c.
Peter Cordes,
5
2) ADD 1 jest tutaj prawdopodobnie szybszy niż INC . Nie, OP nie używa Pentium4 . Twój punkt 3) jest jedyną poprawną częścią tej odpowiedzi.
Peter Cordes,
5
4) brzmi jak totalny nonsens. 64-bitowy kod może być wolniejszy w przypadku struktur danych o dużym wskaźniku, ponieważ większe wskaźniki oznaczają większy rozmiar pamięci podręcznej. Ale ten kod działa tylko w rejestrach, a problemy z wyrównaniem kodu są takie same w trybie 32- i 64-bitowym. (Podobnie są problemy z wyrównaniem danych, nie ma pojęcia, o czym mówisz, ponieważ wyrównanie jest większym problemem dla x86-64). W każdym razie kod nawet nie dotyka pamięci w pętli.
Peter Cordes,
Komentator nie ma pojęcia o czym mówi. Wykonanie MOV + MUL na 64-bitowym procesorze będzie około trzykrotnie wolniejsze niż dwukrotne dodanie rejestru. Jego pozostałe uwagi są równie błędne.
Tyler Durden,
6
Cóż, MOV + MUL jest zdecydowanie głupi, ale MOV + ADD + ADD jest nadal głupiutki (właściwie ADD RBX, RBXdwukrotne wykonanie pomnożyłoby przez 4, a nie 3). Zdecydowanie najlepszy sposób to lea rax, [rbx + rbx*2]. Lub, kosztem uczynienia go 3-komponentowym LEA, wykonaj również +1 z lea rax, [rbx + rbx*2 + 1] (opóźnienie 3c na HSW zamiast 1, jak wyjaśniłem w mojej odpowiedzi). Chodziło mi o to, że mnożenie 64-bitowe nie jest bardzo drogie na najnowsze procesory Intela, ponieważ mają niesamowicie szybkie jednostki mnożenia liczb całkowitych (nawet w porównaniu z AMD, gdzie to samo MUL r64ma opóźnienie 6c, z jedną przepustowością na 4c: nawet nie w pełni potokowe.
Peter Cordes,