Jeśli mam 64-bitową liczbę całkowitą, którą interpretuję jako tablicę spakowanych 8-bitowych liczb całkowitych z 8 elementami. Muszę odjąć stałą 1
od każdej spakowanej liczby całkowitej podczas obsługi przelewu bez wpływu jednego elementu na wynik innego elementu.
Mam ten kod w tej chwili i działa, ale potrzebuję rozwiązania, które odejmuje każdą zapakowaną 8-bitową liczbę całkowitą równolegle i nie zapewnia dostępu do pamięci. Na x86 mogłem używać instrukcji SIMD, takich jak psubb
to, odejmując równolegle zapakowane 8-bitowe liczby całkowite, ale platforma, na której koduję, nie obsługuje instrukcji SIMD. (RISC-V w tym przypadku).
Więc próbuję wykonać SWAR (SIMD w rejestrze), aby ręcznie anulować propagację przenoszenia między bajtami a uint64_t
, robiąc coś równoważnego z tym:
uint64_t sub(uint64_t arg) {
uint8_t* packed = (uint8_t*) &arg;
for (size_t i = 0; i < sizeof(uint64_t); ++i) {
packed[i] -= 1;
}
return arg;
}
Myślę, że można to zrobić za pomocą bitowych operatorów, ale nie jestem pewien. Szukam rozwiązania, które nie korzysta z instrukcji SIMD. Szukam rozwiązania w C lub C ++, które jest dość przenośne, lub po prostu teoria za nim, aby móc wdrożyć własne rozwiązanie.
Odpowiedzi:
Jeśli masz procesor z wydajnymi instrukcjami SIMD, SSE / MMX
paddb
(_mm_add_epi8
) jest również opłacalne. Odpowiedź Petera Cordesa opisuje także składnię wektorową GNU C (gcc / clang) oraz bezpieczeństwo dla UB z dokładnym aliasingiem. Gorąco zachęcam również do przejrzenia tej odpowiedzi.Robienie tego samemu
uint64_t
jest w pełni przenośne, ale nadal wymaga ostrożności, aby uniknąć problemów z wyrównaniem i ścisłego aliasingu UB podczas uzyskiwania dostępu douint8_t
tablicy za pomocąuint64_t*
. Zostawiłeś tę część pytania, zaczynając od danychuint64_t
już w, ale w GNU Cmay_alias
typedef rozwiązuje problem (zobacz odpowiedź Piotra na to lubmemcpy
).W przeciwnym razie możesz przydzielić / zadeklarować swoje dane jako
uint64_t
i uzyskać do nich dostęp,uint8_t*
gdy chcesz mieć poszczególne bajty.unsigned char*
wolno aliasować wszystko, aby uniknąć problemu w konkretnym przypadku elementów 8-bitowych. (Jeśliuint8_t
w ogóle istnieje, prawdopodobnie można bezpiecznie założyć, że jestunsigned char
.)Zauważ, że jest to zmiana w stosunku do wcześniejszego niepoprawnego algorytmu (patrz historia zmian).
Jest to możliwe bez pętli dla arbitralnego odejmowania i staje się bardziej efektywne dla znanej stałej, jak
1
w każdym bajcie. Główną sztuczką jest zapobieganie wykonywaniu każdego bajtu przez ustawienie wysokiego bitu, a następnie poprawianie wyniku odejmowania.Zamierzamy nieznacznie zoptymalizować podaną tutaj technikę odejmowania . Określają:
ze
H
zdefiniowanym jako0x8080808080808080U
(tj. MSB dla każdej spakowanej liczby całkowitej). Dla dekrementacjiy
jest0x0101010101010101U
.Wiemy, że
y
wszystkie MSB są czyste, więc możemy pominąć jeden z kroków maski (tzn.y & ~H
Jest taki sam jaky
w naszym przypadku). Obliczenia przebiegają w następujący sposób:x
na 1, aby pożyczka nie mogła się rozchodzić za MSB do następnego składnika. Nazwij to dostosowanym wejściem.0x01010101010101
od skorygowanego wejścia. Nie powoduje to pożyczek między komponentami dzięki krokowi 1. Nazwij to dostosowaną mocą wyjściową.Operację można zapisać jako:
Najlepiej jest to podkreślone przez kompilator ( aby wymusić to za pomocą dyrektyw kompilatora ), lub wyrażenie jest zapisywane jako część innej funkcji.
Przypadki testowe:
Szczegóły wydajności
Oto zestaw x86_64 dla pojedynczego wywołania funkcji. Aby uzyskać lepszą wydajność, należy podkreślić, że stałe mogą żyć w rejestrze tak długo, jak to możliwe. W ciasnej pętli, w której stałe żyją w rejestrze, faktyczne zmniejszenie wymaga pięciu instrukcji: lub + nie + i + dodaj + xor po optymalizacji. Nie widzę alternatyw, które przeszłyby optymalizację kompilatora.
Z niektórymi testami IACA następującego fragmentu kodu:
możemy pokazać, że na maszynie Skylake wykonywanie dekrementacji, xor i porównaj + skok można wykonać przy prawie 5 cyklach na iterację:
(Oczywiście na x86-64 po prostu ładowałbyś lub
movq
do regułu XMM dlapaddb
, więc bardziej interesujące może być spojrzenie na to, jak się kompiluje dla ISA, takiego jak RISC-V.)źródło
uint8_t
aliasu jest dozwolony dla aliasuuint8_t
danych. Wywołujący twoją funkcję (którzy muszą pobraćuint8_t
dane do auint64_t
) są tymi, którzy muszą się martwić o ścisłe aliasing! Prawdopodobnie więc OP powinien po prostu deklarować / alokować tablice,uint64_t
ponieważchar*
może aliasować cokolwiek w ISO C ++, ale nie odwrotnie.W przypadku RISC-V prawdopodobnie używasz GCC / clang.
Ciekawostka: GCC zna niektóre z tych sztuczek SWAR (pokazanych w innych odpowiedziach) i może ich użyć podczas kompilacji kodu z wektorami natywnymi GNU C dla celów bez instrukcji sprzętowych SIMD. (Ale kliknięcie na RISC-V po prostu naiwnie rozwinie go do operacji skalarnych, więc musisz to zrobić sam, jeśli chcesz dobrej wydajności pomiędzy kompilatorami).
Jedną z zalet natywnej składni wektorowej jest to, że atakując maszynę ze sprzętową kartą SIMD, użyje jej zamiast automatycznie wektoryzacji twojego bithacka lub czegoś okropnego.
Ułatwia pisanie
vector -= scalar
operacji; składnia Just Works, niejawnie transmituje dla ciebie aka splatting skalar.Zauważ też, że
uint64_t*
obciążenie zuint8_t array[]
UB ściśle aliasinguje, więc bądź ostrożny z tym. (Zobacz także Dlaczego strli glibc musi być tak skomplikowane, aby działało szybko? Re: uczynienie binarnych SWAR rygorystycznym aliasingiem bezpiecznym w czystym C). Możesz chcieć, aby coś takiego zadeklarowałouint64_t
, że możesz rzutować wskaźnik, aby uzyskać dostęp do innych obiektów, na przykład jakchar*
działa w ISO C / C ++.użyj tych, aby przenieść dane uint8_t do uint64_t do użycia z innymi odpowiedziami:
Innym sposobem wykonania bezpiecznych dla aliasingu ładunków jest użycie znaku „
memcpy
a”uint64_t
, który również usuwaalignof(uint64_t
wymóg wyrównania. Ale w ISA bez wydajnych nierównomiernych obciążeń, gcc / clang nie inline i optymalizują,memcpy
gdy nie mogą udowodnić, że wskaźnik jest wyrównany, co byłoby katastrofalne dla wydajności.TL: DR: najlepiej jest zadeklarować dane jako ci
uint64_t array[...]
lub przeznaczyć je dynamicznieuint64_t
, a najlepiejalignas(16) uint64_t array[];
, który zapewnia dostosowanie do co najmniej 8 bajtów lub 16 jeśli podaszalignas
.Ponieważ
uint8_t
jest prawie na pewnounsigned char*
bezpieczny dostęp do bajtówuint64_t
viauint8_t*
(ale nie odwrotnie w przypadku tablicy uint8_t). Dlatego w tym szczególnym przypadku, w którym występuje wąski elementunsigned char
, możesz ominąć problem ścisłego aliasingu, ponieważchar
jest on wyjątkowy.Przykład natywnej składni wektorowej GNU C:
GNU C rodzimych wektory są zawsze wolno alias z ich podstawowego typu (np
int __attribute__((vector_size(16)))
może bezpiecznie aliasint
ale niefloat
lubuint8_t
czy cokolwiek innego.W przypadku RISC-V bez żadnego HW SIMD, możesz użyć
vector_size(8)
do wyrażenia tylko szczegółowości, której możesz efektywnie użyć, i zrobić dwa razy więcej mniejszych wektorów.Ale
vector_size(8)
kompiluje się bardzo głupio dla x86 zarówno z GCC, jak i clang: GCC używa bitów SWAR w rejestrach liczb całkowitych GP, clang rozpakowuje się do elementów 2-bajtowych, aby wypełnić 16-bajtowy rejestr XMM, a następnie przepakowuje. (MMX jest tak przestarzały, że GCC / clang nawet nie zawraca sobie nim głowy, przynajmniej nie dla x86-64.)Ale z
vector_size (16)
( Godbolt ) otrzymujemy oczekiwanymovdqa
/paddb
. (Z wektorem wszystkich jedynek wygenerowanym przezpcmpeqd same,same
). W-march=skylake
dalszym ciągu otrzymujemy dwa oddzielne operacje XMM zamiast jednego YMM, więc niestety obecne kompilatory również nie „automatycznie wektorują” operacje wektorowe w szersze wektory: /W przypadku AArch64 korzystanie z niego nie jest takie złe
vector_size(8)
( Godbolt ); ARM / AArch64 może natywnie pracować w 8 lub 16-bajtowych porcjach z rejestramid
lubq
.Prawdopodobnie chcesz
vector_size(16)
się faktycznie skompilować, jeśli chcesz mieć przenośną wydajność w procesorach x86, RISC-V, ARM / AArch64 i POWER . Jednak niektóre inne ISA wykonują SIMD w 64-bitowych rejestrach liczb całkowitych, jak myślę MIPS MSA.vector_size(8)
ułatwia spojrzenie na asm (dane o wartości tylko jednego rejestru): eksplorator kompilatora GodboltMyślę, że to ten sam podstawowy pomysł, co inne nie zapętlone odpowiedzi; zapobiegając przenoszeniu, a następnie ustalając wynik.
To jest 5 instrukcji ALU, gorsze niż najlepsza odpowiedź, jak sądzę. Wygląda jednak na to, że opóźnienie ścieżki krytycznej to tylko 3 cykle, z dwoma łańcuchami po 2 instrukcje prowadzące do XOR. @Reinstate Monica - ζ - odpowiedź kompiluje się do 4-cyklowego łańcucha dep (dla x86). Przepływ w pętli 5-cyklowej jest wąski, ponieważ obejmuje naiwność
sub
na ścieżce krytycznej, a pętla powoduje wąskie gardło w przypadku opóźnienia.Jest to jednak bezużyteczne w przypadku clang. Nawet nie dodaje i nie zapisuje w tej samej kolejności, w jakiej został załadowany, więc nawet nie robi dobrego potoku oprogramowania!
źródło
Zwracam uwagę, że kod, który napisałeś, wektoryzuje, gdy zaczniesz zajmować się więcej niż jednym uint64_t.
https://godbolt.org/z/J9DRzd
źródło
__vector_loop(index, start, past, pad)
konstruktem, który implementacja mogłaby traktować jakofor(index=start; index<past; index++)
[co oznacza, że każda implementacja może przetwarzać kod przy użyciu go, jedynie poprzez zdefiniowanie makra], ale która miałaby luźniejszą semantykę, aby zaprosić kompilator do przetwarzania rzeczy w dowolna potęga wielkości dwóch porcji dopad
, przedłużając początek w dół i kończąc w górę, jeśli nie są one wielokrotnościami wielkości porcji. Skutki uboczne w obrębie każdego kawałka byłyby nieistotne, a jeślibreak
wystąpi w pętli, inne powtórzenia ...restrict
jest pomocny (i byłby bardziej pomocny, gdyby Standard rozpoznał koncepcję „przynajmniej potencjalnie opartą na”, a następnie zdefiniował „oparty na” i „przynajmniej potencjalnie oparty na” bezpośrednio, bez głupich i niewykonalnych przypadków narożnych) moja propozycja pozwoliłaby również kompilatorowi na wykonanie większej liczby pętli niż jest to wymagane - co znacznie uprościłoby wektoryzację, ale dla których Standard nie przewiduje.Możesz upewnić się, że odejmowanie się nie przepełni, a następnie naprawić wysoki bit:
źródło
splat(0x01)
isplat(0x80)
zamiast pobierać jedną z drugiej z przesunięciem. Nawet pisanie go w ten sposób w źródłowym godbolt.org/z/6y9v-u nie powstrzymuje kompilatora przed tworzeniem lepszego kodu; po prostu dokonuje stałej propagacji.Nie jestem pewien, czy tego właśnie chcesz, ale wykonuje 8 odejmowań równolegle względem siebie:
Objaśnienie: Maska bitów zaczyna się od 1 w każdej z 8-bitowych liczb. Popieramy to naszym argumentem. Gdybyśmy mieli 1 w tym miejscu, odjęliśmy 1 i musimy przestać. Odbywa się to poprzez ustawienie odpowiedniego bitu na 0 w new_mask. Gdybyśmy mieli 0, ustawiamy ją na 1 i musimy wykonać przeniesienie, więc bit pozostaje 1 i przesuwamy maskę w lewo. Lepiej sam sprawdź, czy generowanie nowej maski działa zgodnie z planem, tak myślę, ale druga opinia nie byłaby zła.
PS: Właściwie nie jestem pewien, czy sprawdzenie, czy
mask_cp
nie ma wartości zerowej w pętli, może spowolnić program. Bez tego kod nadal byłby poprawny (ponieważ maska 0 po prostu nic nie robi) i kompilatorowi łatwiej byłoby rozwinąć pętlę.źródło
for
nie będzie działać równolegle, czy jesteś mylonyfor_each
?Możesz to zrobić za pomocą operacji bitowych, korzystając z powyższego, i po prostu musisz podzielić liczbę całkowitą na 8 bitów, aby wysłać 8 razy do tej funkcji. Poniższa część została zaczerpnięta z Jak podzielić liczbę 64-bitową na osiem wartości 8-bitowych? ze mną dodając powyższą funkcję
Jest to poprawne C lub C ++, niezależnie od tego, jak ktoś to zauważy
źródło
for_each(std::execution::par_unseq,...
zamiast whilesNie próbując wymyślić kodu, ale dla zmniejszenia o 1 możesz zmniejszyć o grupę 8 1, a następnie sprawdzić, czy LSB wyników „przerzuciły się”. Każdy LSB, który nie przełączył się, wskazuje, że przeniesienie nastąpiło z sąsiednich 8 bitów. Aby to obsłużyć, powinno być możliwe wypracowanie sekwencji AND / ORs / XOR bez żadnych rozgałęzień.
źródło
Skoncentruj pracę na każdym bajcie całkowicie sam, a następnie umieść go z powrotem tam, gdzie był.
źródło