Jaki jest efektywny sposób liczenia ustawionych bitów na pozycji lub niższej?

Ten C++ dostaje g++ do emisji bardzo dobrego ASM x86 (eksplorator kompilatora godbolt). Spodziewam się, że skompiluje się wydajnie również na innych architekturach 64-bitowych (jeśli istnieje licznik popcount HW dla std::bitset::count używać, w przeciwnym razie zawsze będzie to powolna część; np. koniecznie użyj g++ -march=nehalem lub nowszy lub -mpopcnt jeśli nie chcesz włączać niczego innego, jeśli możesz ograniczyć swój kod do działania tylko na procesorach obsługujących tę instrukcję x86):

#include <bitset>

int popcount_subset(std::bitset<64> A, int pos) {
  int high_bits_to_eliminate = 63 - pos;
  A <<= (high_bits_to_eliminate & 63);  // puts A[pos] at A[63].

  return (A[63]? ~0ULL : 0) & A.count();  // most efficient way: great code with gcc and clang
  // see the godbolt link for some #ifdefs with other ways to do the check, like
    // return A[BSET_SIZE-1] ? A.count() : 0;
}

Prawdopodobnie nie jest to optymalne na architekturach 32-bitowych, więc porównaj inne alternatywy, jeśli potrzebujesz zbudować wersję 32-bitową.

To zadziała dla innych rozmiarów bitsetu , o ile zrobisz coś z zakodowanym na stałe 63 s i zmień & 63 maska ​​na zmianę liczyć do bardziej ogólnego sprawdzenia zakresu. Aby uzyskać optymalną wydajność z zestawami bitów o dziwnym rozmiarze, utwórz funkcję szablonu ze specjalizacją dla size <= register width maszyny docelowej. W takim przypadku wyodrębnij zestaw bitów do unsigned wpisz odpowiednią szerokość i przesuń na górę rejestru zamiast na górę zestawu bitów.

Można by oczekiwać, że wygeneruje to również idealny kod dla bitset<32> , ale nie do końca. gcc/clang nadal używa 64-bitowych rejestrów na x86-64.

W przypadku dużych zestawów bitów przesunięcie całości będzie wolniejsze niż zwykłe liczenie słów poniżej tego zawierającego pos i używając tego na tym słowie. (Tutaj wektoryzowany popcount naprawdę świeci na x86, jeśli możesz założyć SSSE3, ale nie popcnt obsługa sprzętu insn lub dla celów 32-bitowych. AVX2 256bit pshufb to najszybszy sposób na masowe popcounty, ale myślę, że bez AVX2 64-bitowy popcnt jest bardzo zbliżony do 128-bitowego pshufb realizacja. Zobacz komentarze, aby uzyskać więcej dyskusji.)

Jeśli masz tablicę elementów 64-bitowych i chcesz liczyć bity poniżej określonej pozycji w każdym z nich osobno, zdecydowanie powinieneś użyć SIMD . Przesunięcie części tego algorytmu wektoryzuje, a nie tylko część popcnt. Użyj psadbw w stosunku do rejestru całkowicie zerowego do bajtów o sumie poziomej w 64-bitowych porcjach po pshufb oparty na popcnt, który generuje liczniki dla bitów w każdym bajcie oddzielnie. SSE/AVX nie ma 64-bitowego arytmetycznego przesunięcia w prawo, ale możesz użyć innej techniki, aby zmieszać najwyższy bit każdego elementu.

Jak to wymyśliłem:

Instrukcje asm, które chcesz zmusić kompilator do wyświetlenia, będą:

1. usuń niechciane bity z wartości 64-bitowej
2. przetestuj najwyższy z poszukiwanych bitów.
3. policz to.
4. zwróć 0 lub popcount, w zależności od wyniku testu. (Implementacje bezgałęziowe lub z rozgałęzieniami mają zalety. Jeśli gałąź jest przewidywalna, implementacja bezgałęziowa jest zwykle wolniejsza.)

Oczywisty sposób na zrobienie 1 jest wygenerowanie maski ((1<<(pos+1)) -1 ) i & to. Bardziej wydajnym sposobem jest przesunięcie w lewo o 63-pos , pozostawiając bity, które chcesz spakować na górze rejestru.

Ma to również interesujący efekt uboczny polegający na umieszczeniu bitu, który chcesz przetestować, jako górnego bitu w rejestrze. Testowanie bitu znaku, a nie jakiegokolwiek innego bitu arbitralnego, wymaga nieco mniej instrukcji. Arytmetyczne przesunięcie w prawo może rozesłać bit znaku do reszty rejestru, umożliwiając bardziej wydajny niż zwykle kod bez rozgałęzień.

Robienie popcount to szeroko dyskutowany problem, ale w rzeczywistości jest to trudniejsza część układanki. Na x86 istnieje niezwykle wydajna obsługa sprzętu, ale tylko na najnowszym sprzęcie. W procesorach Intel popcnt instrukcja jest dostępna tylko w Nehalem i nowszych. Zapomniałem, kiedy AMD dodało wsparcie.

Aby używać go bezpiecznie, musisz albo wykonać rozsyłanie procesora z rezerwą, która nie używa popcnt . Lub utwórz oddzielne pliki binarne, które zależą/nie zależą od niektórych funkcji procesora.

popcount bez popcnt instrukcję można wykonać na kilka sposobów. Jeden używa SSSE3 pshufb zaimplementować 4-bitową tablicę LUT. Jest to jednak najskuteczniejsze, gdy jest używane na całej tablicy, a nie na pojedynczym 64b na raz. Skalarne bithacky mogą być tutaj najlepsze i nie wymagałyby SSSE3 (a więc byłyby kompatybilne ze starymi procesorami AMD, które mają 64-bitowe, ale nie pshufb).

Bitbroadcast:

(A[63]? ~0ULL : 0) prosi kompilator o rozesłanie wysokiego bitu do wszystkich innych pozycji bitowych, pozwalając na użycie go jako maski AND do zera (lub nie) wyniku licznika pop. Zauważ, że nawet w przypadku dużych rozmiarów bitsetów nadal maskuje tylko wyjście popcnt , a nie sam zestaw bitów, więc ~0ULL jest w porządku Użyłem ULL, aby upewnić się, że nigdy nie prosiłem kompilatora o rozgłaszanie bitu tylko do najniższego 32b rejestru (z UL na przykład w systemie Windows).

Ta transmisja może być wykonana z arytmetycznym przesunięciem w prawo o 63, które przesuwa się w kopiach starszego bitu.

clang wygenerował ten kod z oryginalnej wersji. Po kilku słowach Glenna o różnych implementacjach dla 4 , zdałem sobie sprawę, że mogę poprowadzić gcc w kierunku optymalnego rozwiązania clang, pisząc kod źródłowy bardziej podobny do ASM, którego chcę. Oczywiste ((int64_t)something) >> 63 bardziej bezpośrednie żądanie arytmetycznego przesunięcia w prawo nie byłoby ściśle przenośne, ponieważ podpisane przesunięcia w prawo są zdefiniowane w implementacji jako arytmetyczne lub logiczne. Norma nie zapewnia żadnego przenośnego operatora arytmetycznego przesunięcia w prawo. (Nie jest to jednak niezdefiniowane zachowanie.) W każdym razie, na szczęście kompilatory są wystarczająco inteligentne:gcc widzi najlepszy sposób, gdy dasz mu wystarczającą wskazówkę.

To źródło tworzy świetny kod na x86-64 i ARM64 z gcc i clang. Oba po prostu używają arytmetycznego przesunięcia w prawo na wejściu do popcnt (więc przesunięcie może działać równolegle z popcnt). Świetnie się też kompiluje na 32-bitowym x86 z gcc, ponieważ maskowanie dzieje się tylko na 32-bitowej zmiennej (po dodaniu wielu wyników popcnt). To reszta funkcji jest paskudna na 32-bitach (kiedy zestaw bitów jest większy niż rejestr).

Oryginalna wersja operatora trójargumentowego z gcc

Skompilowany z gcc 5.3.0 -O3 -march=nehalem -mtune=haswell (starsze gcc, takie jak 4.9.2, również nadal emituje to):

; the original ternary-operator version.  See below for the optimal version we can coax gcc into emitting.
popcount_subset(std::bitset<64ul>, int):
    ; input bitset in rdi, input count in esi (SysV ABI)
    mov     ecx, esi    ; x86 variable-count shift requires the count in cl
    xor     edx, edx    ; edx=0 
    xor     eax, eax    ; gcc's workaround for popcnt's false dependency on the old value of dest, on Intel
    not     ecx         ; two's complement bithack for 63-pos (in the low bits of the register)
    sal     rdi, cl     ; rdi << ((63-pos) & 63);  same insn as shl (arithmetic == logical left shift)
    popcnt  rdx, rdi
    test    rdi, rdi    ; sets SF if the high bit is set.
    cmovs   rax, rdx    ; conditional-move on the sign flag
    ret

Zobacz Jak udowodnić, że instrukcje C -x, ~x+1 i ~(x-1) dają takie same wyniki? dla tła na temat używania przez gcc -x == ~x + 1 tożsamość dopełniacza dwójki. (A operacje na liczbach całkowitych uzupełnienia których 2 mogą być użyte bez zerowania wysokich bitów na danych wejściowych, jeśli pożądana jest tylko niska część wyniku? co stycznie wspomina, że ​​shl maskuje liczbę przesunięć, więc potrzebujemy tylko ostatnich 6 bitów ecx trzymać 63 - pos . Przeważnie łącząc to, ponieważ napisałem to niedawno i każdy, kto nadal czyta ten akapit, może go zainteresować.)

Niektóre z tych instrukcji znikną podczas tworzenia wstawek. (np. gcc najpierw wygeneruje liczbę w ecx.)

Z mnożeniem Glenna zamiast operatora potrójnego pomysł (włączony przez USE_mul ), robi to gcc

    shr     rdi, 63
    imul    eax, edi

na końcu zamiast xor / test / cmovs .

Analiza wydajności Haswella, przy użyciu danych mikroarchowych z Agner Fog (wersja Multiply):

• mov r,r :1 połączona domena uop, 0 latencji, brak jednostki wykonawczej
• xor -zerowanie:1 połączona domena uop, brak jednostki wykonawczej
• not :1 uop dla p0/p1/p5/p6, opóźnienie 1c, 1 na przepustowość 0,25c
• shl (aka sal ) z liczbą w cl :3 uops dla p0/p6:opóźnienie 2c, przepustowość 1 na 2c. (Dane Agner Fog wskazują, że IvyBridge zajmuje do tego tylko 2 uops, co dziwne.)
• popcnt :1 uop dla opóźnienia p1, 3c, 1 na przepustowość 1c
• shr r,imm :1 uop dla p0/p6, opóźnienie 1c. 1 na przepustowość 0,5c.
• imul r,r :1uop dla opóźnienia p1, 3c.
• nie licząc ret

Sumy:

• 9 uops połączonych domen, może wydawać w 2,25 cyklu (teoretycznie; efekty uop cache-line zwykle powodują lekkie zawężenie frontendu).
• 4 uops (przesunięcia) dla p0/p6. 2 uops za p1. 1 dowolny port ALU uop. Może wykonać jeden na 2c (nasycając porty zmiany), więc frontend jest najgorszym wąskim gardłem.

Opóźnienie:Ścieżka krytyczna od momentu, gdy zestaw bitów jest gotowy do wyniku:shl (2) -> popcnt (3) -> imul (3). Łącznie 8 cykli . Lub 9c od kiedy pos jest gotowy, ponieważ not to dodatkowe opóźnienie 1c.

Optymalne bitbroadcast wersja zastępuje shr z sar (ta sama wydajność) i imul z and (opóźnienie 1c zamiast 3c, działa na dowolnym porcie). Tak więc jedyną zmianą wydajności jest zmniejszenie opóźnienia ścieżki krytycznej do 6 cykli . Przepustowość nadal jest wąskim gardłem w interfejsie. and możliwość uruchomienia na dowolnym porcie nie ma znaczenia, chyba że mieszasz to z kodem, który ogranicza wąskie gardła na porcie 1 (zamiast patrzeć na przepustowość do uruchomienia tylko tego kod w ciasnej pętli).

wersja cmov (operator potrójny) :11 uops połączonych domen (frontend:jeden na 2,75c ). jednostki wykonawcze:nadal wąskie gardła na portach zmiany (p0/p6) co 1 na 2c. Opóźnienie :7c od bitsetu do wyniku, 8c od pos do wyniku. (cmov to opóźnienie 2c, 2 uops dla dowolnego z p0/p1/p5/p6.)

Klang ma kilka różnych sztuczek w rękawie:Zamiast test /cmovs , generuje maskę samych jedynek lub samych zer za pomocą arytmetycznego przesunięcia w prawo, aby rozgłaszać bit znaku do wszystkich pozycji rejestru. Uwielbiam to:Używam and zamiast cmov jest bardziej wydajny na Intelu. Mimo to nadal ma zależność od danych i wykonuje pracę po obu stronach gałęzi (co jest główną wadą cmov w ogóle). Aktualizacja:z odpowiednim kodem źródłowym gcc również użyje tej metody.

clang 3.7 -O3 -Wall -march=nehalem -mtune=haswell

popcount_subset(std::bitset<64ul>, int):
    mov     ecx, 63
    sub     ecx, esi      ; larger code size, but faster on CPUs without mov-elimination
    shl     rdi, cl       ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi      ; doesn't start a fresh dep chain before this, like gcc does
    sar     rdi, 63       ; broadcast the sign bit
    and     eax, edi      ; eax = 0 or its previous value
    ret

sar / and zastępuje xor / test / cmov i cmov to instrukcja 2 uop na procesorach Intela, więc to naprawdę miłe. (Dla wersji z operatorem trójargumentowym).

Clang nadal wykonuje sar / and sztuczka zamiast rzeczywistego imul podczas korzystania z wersji źródłowej multiply lub wersji źródłowej „bitbroadcast”. Pomagają one gcc bez ranienia klangu. (sar/and jest zdecydowanie lepszy niż shr/imul :2c mniejsze opóźnienie na ścieżce krytycznej.) pow_of_two_sub wersja szkodzi klangowi (patrz pierwszy link do godbolt:pominięto w tej odpowiedzi, aby uniknąć bałaganu z pomysłami, które się nie powiodły).

mov ecx, 63 / sub ecx, esi jest faktycznie szybszy na procesorach bez mov-eliminacji dla ruchów reg,reg (zero latencji i brak portu wykonania, obsługiwane przez zmianę nazwy rejestru). Obejmuje to Intel przed IvyBridge, ale nie nowsze procesory Intel i AMD.

mov imm Clanga / sub metoda umieszcza tylko jeden cykl opóźnienia dla pos na ścieżkę krytyczną (poza bitset->opóźnieniem wyniku), zamiast dwóch dla mov ecx, esi / not ecx na procesorach, gdzie mov r,r ma opóźnienie 1c.

Z BMI2 (Haswell i nowsze), optymalna wersja ASM może zapisać mov do ecx . Wszystko inne działa tak samo, ponieważ shlx maskuje swój rejestr wejściowy licznika zmian do rozmiaru operandu, tak jak shl .

Instrukcje przesunięcia x86 mają szaloną semantykę CISC, gdzie jeśli liczba przesunięć wynosi zero, flagi nie są zmieniane. Tak więc instrukcje przesunięcia o zmiennej liczbie mają (potencjalną) zależność od starej wartości flag. „Normalny” x86 shl r, cl dekoduje do 3 uops na Haswell, ale BMI2 shlx r, r, r to tylko 1. Szkoda, że ​​gcc nadal emituje sal z -march=haswell , zamiast używać shlx (którego używa w niektórych innych przypadkach).

// hand-tuned BMI2 version using the NOT trick and the bitbroadcast
popcount_subset(std::bitset<64ul>, int):
    not     esi           ; The low 6 bits hold 63-pos.  gcc's two-s complement trick
    xor     eax, eax      ; break false dependency on Intel.  maybe not needed when inlined.
    shlx    rdi, rdi, rsi ; rdi << ((63-pos) & 63)
    popcnt  rax, rdi
    sar     rdi, 63       ; broadcast the sign bit: rdi=0 or -1
    and     eax, edi      ; eax = 0 or its previous value
    ret

Analiza wydajności dla Intel Haswell:6 uops połączonych domen (frontend:jeden na 1,5c ). Jednostki wykonawcze:2 uops przesunięcia p0/p6. 1 pkt 1 uop. 2 uops dowolnego portu:(jeden na 1,25c od całkowitego limitu portu wykonania). Opóźnienie ścieżki krytycznej:shlx (1) -> popcnt (3) -> and (1) =5c bitset->wynik. (lub 6c z pos ->wynik).

Zauważ, że podczas inline, człowiek (lub inteligentny kompilator) może uniknąć potrzeby xor eax, eax . Jest tam tylko z powodu popcnt fałszywa zależność od rejestru wyjściowego (na Intelu) i potrzebujemy danych wyjściowych w eax (którego rozmówca mógł ostatnio użyć do długiego łańcucha dep). Z -mtune=bdver2 czy coś, gcc nie wyzeruje rejestru, którego będzie używał dla popcnt wyjście.

Podczas inline, moglibyśmy użyć rejestru wyjściowego, który musi być gotowy co najmniej już w popcnt 's source reg, aby uniknąć problemu. Kompilatory wykonają w miejscu popcnt rdi,rdi gdy źródło nie jest później potrzebne, ale tak nie jest w tym przypadku. Zamiast tego możemy wybrać inny rejestr, który musi być już gotowy przed źródłem. popcnt dane wejściowe zależą od 63-pos , a my możemy to zaatakować, więc popcnt rsi,rdi zależność od rsi nie może tego opóźnić. Lub gdybyśmy mieli 63 w rejestrze moglibyśmy popcnt rsi,rdi / sarx rax, rsi, reg_63 / and eax, esi . Lub 3-argumentowe instrukcje przesunięcia BMI2 również pozwolą nam nie obciążać danych wejściowych, na wypadek gdyby były później potrzebne.

Jest to tak lekkie, że narzut pętli i ustawienie operandów wejściowych / przechowywanie wyników będą głównymi czynnikami. (I 63-pos można zoptymalizować za pomocą stałej czasu kompilacji lub w dowolnym miejscu, z którego pochodzi liczba zmiennych).

Kompilator Intela zabawnie strzela sobie w stopę i nie wykorzystuje faktu, że A[63] jest bitem znaku. shl / bt rdi, 63 / jc . Nawet ustawia gałęzie w naprawdę głupi sposób. Może zero eax, a następnie przeskoczyć przez popcnt lub nie w oparciu o flagę znaku ustawioną przez shl .

Optymalna implementacja rozgałęzień , zaczynając od wyjścia ICC13 z -O3 -march=corei7 na bogu:

   // hand-tuned, not compiler output
        mov       ecx, esi    ; ICC uses neg/add/mov :/
        not       ecx
        xor       eax, eax    ; breaks the false dep, or is the return value in the taken-branch case
        shl       rdi, cl
        jns    .bit_not_set
        popcnt    rax, rdi
.bit_not_set:
        ret

To prawie optymalne:A[pos] == true sprawa ma jedną nie zajętą ​​gałąź. Nie oszczędza to jednak zbyt wiele na metodzie bezgałęziowej.

Jeśli A[pos] == false przypadek jest bardziej powszechny:przeskocz przez ret instrukcji, do popcnt / ret . (Lub po wstawieniu:skocz do bloku na końcu, który wykonuje popcnt i odskakuje).

Moją natychmiastową reakcją byłoby przetestowanie określonego bitu i natychmiastowe zwrócenie 0 z tego, co jest jasne.

Jeśli to miniesz, utwórz maskę bitową z ustawionym bitem (i mniej znaczącymi) i and że z oryginalnym wejściem. Następnie użyj count() funkcja członkowska, aby uzyskać liczbę bitów ustawioną w wyniku.

Co do tworzenia maski:możesz przesunąć 1 w lewo o N miejsc, a następnie odjąć 1.

Zakładając unsigned long lub unsigned long long jest wystarczająco duży, aby pomieścić 64 bity, możesz zadzwonić do bits.to_unlong() (lub bits.to_ullong() ), aby uzyskać dane zestawu bitów jako liczbę całkowitą, zamaskuj bity powyżej X ((1 << X) - 1 ), a następnie policz te bity zgodnie z odpowiedzią na pytanie, do którego prowadzisz link.