PCMPxSTRy (Packed Compare ... Length String, Return ...) to zestaw instrukcji służących do operacji (ad "jakich operacji" - o tym za chwilę) na stringach po 8-16 znaków naraz (rejestry XMM się kłaniają). Pisze zestaw, gdyż w zasadzie są to cztery instrukcje plus jedna 7-bitowa stała flagowa która definiuje dokładne zachowanie instrukcji.
Jeśli chodzi o instrukcje, to mamy:
PCMPESTRI xmm1, xmm2/m128, imm8
PCMPESTRM xmm1, xmm2/m128, imm8
PCMPISTRI xmm1, xmm2/m128, imm8
PCMPISTRM xmm1, xmm2/m128, imm8
Literki "E" oraz "I" na pierwszej pozycji mówią o tym, czy stringi na których operujemy mają znaną długość, podaną w rejestrze EAX/RAX i EDX/RDX (Explicit), czy też ich długość nie jest znana, ale są null-terminated, tak jak typowe C-stringi (Implicit).
Natomiast literki "I" oraz "M" na drugiej pozycji, mówią o tym, czy funkcja ma zwracać Index pierwszego/ostatniego znaku który spełnia jakieś założenia, czy może Maskę bitową (lub bajtową) z zaznaczonymi bajtami [nie]spełniającymi założenia.
Jeśli chodzi o parametry, to xmm1 oraz xmm2/m128 są 16-bajtowymi (czyli 128-bitowymi) fragmentami stringów, w których każdy znak jest signed lub unsigned char lub wchar (16-bitów per znak). Oczywiście, rejestr może być tylko częściowo wypełniony stringiem (jeśli dany fragment stringa ma np. 10 a nie 16 charów).
Natomiast imm8 jest tym 7-bitową (8smy bit jest nieużywany) stałą flagową która definiuje co tak naprawdę dana instrukcja robi.
Najważniejszą (moim zdaniem) rzeczą w owej stałej jest wybór operacji (bity 3 oraz 2, licząc od 0). Do wyboru są 4:
00b - Equal any, czyli true na n-tej pozycji jeśli na n-tej pozycji ciągu xmm2/m128 znajduje się dowolny znak z ciągu xmm1 (takie lepsze strchr lub strrchr; lepsze, bo można naraz do 16 różnych znaków wyszukiwać).
01b - Ranges, czyli jak wyżej, tylko zamiast różnych znaków podajemy przedziały [sic! tak, to nadal aseembly], np. AZ09 w xmm1 oznacza "znajdź duże litery ASCII i cyfry ASCII".
10b - Equal each, po prostu porównanie stringów (jak strcmp czy memcmp).
11b - Equal ordered, wyszukiwanie podciągu (patrz strstr).
Poza tym, jak wspomniałem wcześniej, na bitach 0 i 1 możemy ustawić format danych (unsigned/signed, byte/word). Dalej, na bitach 5 i 4 można ustawić jak ma być ustawiana maska zwracana (tj. np. ma być true na danej pozycji jeśli warunek jest spełniony czy może jak jest niespełniony? oraz, czy ma być true czy false jeśli dany znak nie należy do stringu (aka wystepuje po terminatorze)).
Na bicie nr 6 natomiast wybiera się, czy (w przypadku instrukcji ... Return Index) ma być zwrócony w ECX index pierwszego czy ostatniego znaku który spełnił warunek, lub (w przypadku instrukcji ... Return Mask) czy ma to być maska bitowa (bit per pozycja) czy bajtowa (bajt ustawiany na 0xFF lub 0 per pozycja).
Dodatkowo, instrukcja ustawia również flagi. Np. flagi SF i ZF mówią o tym czy napotkano koniec ciągu xmm1 i xmm2 (strlen gratis ;>), etc.
Zainteresowanych szczegółami odsyłam do manuali Intela, konkretniej 2B na samym początku ma całą sekcję poświęconą zachowaniu tychże instrukcji.
OK, a teraz czas na przykładowy programik, testy etc.
Zdecydowałem się przetestować wariant Ranges zwracający maskę, ponieważ moim zdaniem jest to stosunkowo najciekawsze zachowanie ww. instrukcji.
Czyli, dla podanego ciągu (dowolnej długości) oraz przedziałów (w dowolnej ilości) funkcja ma zwracać wypełnioną tablicę z ustawionym true w miejscu gdzie znak na danej pozycji wpadł w któryś z przedziałów, lub false jeśli jest to znak spoza podanych przedziałów.
Przykładowo (true oznaczę asteriskiem *, a false kropką .):
Ranges: AZ..
String: Ala ma kota. Kot ma ale.
Result: *..........*.*.........*
Funkcję napisałem w dwóch wersjach:
1. W assembly (64-bity, konwencja wywołań Linux 64-bit fastcall, GNU Assembler), korzystając z PCMPISTRM.
2. Dla porównania w C, najbardziej straight-forward jak się dało.
Dodam, że nie optymalizowałem kodu manualnie w żaden sposób (a jest jeszcze trochę miejsca na takową optymalizację), po prostu chciałem zobaczyć ile da samo wykorzystanie SSE 4.2 w kwestii szybkości działania.
Kod programu testującego jest dostępny tutaj (sam plik .c) lub tutaj (całość razem).
Kod funkcji w C/C++:
int find_range(char *dst, const char *str, const char *ranges)
{
while(*str)
{
const char *r = ranges;
char res = 0;
while(*r)
{
if(*str >= r[0] && *str <= r[1])
res = 0xff;
r += 2;
}
*dst = res;
str++;
dst++;
}
return 0;
}Kod funkcji w assembly:
# 64-bit, SSE 4.2, Linux, GNU Assembly
.intel_syntax noprefix
.text
.globl find_range
.type find_range, @function
find_range:
push rbp
mov rbp, rsp
# args are in:
# RDI - pointer to out table
# RSI - pointer to in table
# RDX - pointer to in range
next_data_packet:
mov r8, rdx
movdqu xmm1, [rsi]
pxor xmm3, xmm3
next_mask:
movdqu xmm2, [r8]
# unsigned byte, range, pos. polarity, byte mask
pcmpistrm xmm2, xmm1, (0 | (1 << 2) | (0 << 4) | (1 << 6))
por xmm3, xmm0
# ZF set == end of table
# SF set == end of range
js end_of_mask
add r8, 0x10
jmp next_mask
end_of_mask:
movdqu [rdi], xmm3
jz end_of_table
add rsi, 0x10
add rdi, 0x10
jmp next_data_packet
end_of_table:
xor eax, eax
leave
retPrzeprowadziłem cztery testy, mierząc czas w cyklach (RDTSC).
Test 1: krótki range (az) oraz krótki tekst (24 znaki)
Test 2: krótki range (az) oraz długi teskt (972 znaki)
Test 3: długi range (aabbcc...zz) oraz krótki tekst (24 znaki)
Test 4: długi range (aabbcc...zz) oraz długi tekst (972 znaki)
Każdy z powyższych testów został uruchomiony (kolejno) dla wersji w assembly oraz wersji w C (skompilowanej -O3).
Wyniki przedstawiają się następująco (w ilości cykli, czym mniej tym lepiej):
Test 1: SSE4.2: 432 cykli, C: 998 cykli
Test 2: SSE4.2: 1158 cykli, C: 28736 cykli
Test 3: SSE4.2: 528 cykli, C: 6504 cykli
Test 4: SSE4.2: 2313 cykli, C: 269000 cykliNo cóż, wyniki są w zasadzie jednoznaczne. W najkrótszym teście PCMPISTRM okazało się ponad 2 razy szybszę, a w najdłuższym ponad 100 razy (huh).
Pełne wyniki można zobaczyć tutaj.
OK, i na koniec kilka dwa linki:
SSE4: instrukcje działające na łańcuchach - by Wojciech Muła (szkoda, że znalazłem tą stronę pod koniec pisania postu, zaoszczędziła by mi trochę "ślęczenia").
Implementing strcmp, strlen, and strstr using SSE 4.2 instructions - by Peter Kankowski.
I tyle,
P.S. W trybie VEX (AVX, rejestry 256-bitowe ymmN, etc) instrukcja niestety i tak działa tylko na 128-bitowych fragmentach danych (chociaż czytając opis jak ta instrukcja jest zaimplementowana, trudno byłoby się spodziewać czegoś innego - patrz manual 2B).
UPDATE: Miałem drobny błąd w kodzie w wersji C, już naprawiony. Wyniki testu się nie zmieniły (tj. błąd powodował zmianę w granicy błędu pomiaru).
Comments:
a zeby Ci nie bylo smutno, ze czepiam sie literowek ;p - ciekawy art, mam tylko jedno pytanko - czy kompilatory jezykow wyzszego poziomu obsluguja takie specyficzne instrukcje?
Kropka po nr? Jaka kropka? To badpixel :D
Ad kompilatory - nie sadze zeby jakis kompilator tej konkretnej instrukcji uzyl, jest po prostu zbyt wysokopoziomowa. Natomiast mozliwe jest, ze standardowa biblioteka jakiegos jezyka (np. C i strstr, strlen, strcmp, etc) bedzie korzystac z tego.
Z punktu widzenia programisty natomiast, kompilatory C/C++ etc udostepniaja intrinsics tych instrukcji (czyli funkcje ktore bezposrednio kompiluja sie do tych instrukcji; cos jak inline assembly), np. _mm_cmpistrm w GCC / Intel C/C++ i kompilatorach MS (http://msdn.microsoft.com/en-us/library/bb531425.aspx) i bodajze llvm.x86.sse42.pcmpestri128 w LDC.
Mam nadzieję, że ARM albo inny ciekawy RISC wygryzie monopol X86 w desktopach.
po prostu powstaja instrukcje przydatne do najczestszych zastosowan, trudno poprawic wydajnosc obecnych procesorow poprzez zwiekszanie zegara, innej drogi ku temu jakos nie widze, ARMy maja szanse powodzenia jedynie na polu zastosowan mobilnych, gdzie w gre wchodzi zuzycie energii.
@anonim: Coraz więcej instrukcji (w tym takich wymyślnych) powoduje, że same układy stają się bardziej skomplikowane, kompilatory w większości i tak z tych instrukcji nie korzystają (a nawet jeśli by je obsługiwały, to większość programów i tak kompiluje się z tak, aby działały również na starszym sprzęcie. No chyba, że kompiluje się samemu pod swoją maszynę, ale to co innego).
Dla RISCowych procesorów na pewno łatwiej tworzy się kompilatory (nie spotkałem się z durną zasadą, że mnożenie daje wynik do jednego jedynego rejestru, albo grupy rejestrów (rdx|rax)), no i sam układ jest mniej skomplikowany (KISS).
Poza tym Intel już od dawna dekoduje instrukcje x86 na serie RISCowych "mikroinstrukcji".
Niestety, z uwagi na wsteczną kompatybilność, mało który system korzysta sam z siebie z dobrodziejstw kolejnych SSE. Przy czym tu tez jest kilka rzeczy które trzeba zauważyć:
1. W systemach open source można skompilować większość rzeczy samemu, i poprosić kompilator aby użył SSE1/2/3/4/5/6... (czy to zrobi, to inna sprawa). Również, dość prosto można "upgradnąć" funkcje tak aby korzystały z SSE.
2. Apple w 32-bitowym OSX korzysta bodajże z SSE do wersji 3 włącznie - może sobie na to pozwolić, ponieważ dostarcza również sprzęt pod owy system.
3. 64-bitowe systemy korzystają z kilku SSE, ponieważ można założyć, że jeśli procek ma tryb 64-bitowy, to również ma kilka wersji SSE (chociaż nie pamiętam które dokładnie SSE można założyć, ale stawiam na SSE 1 i 2).
4. W sumie w systemach z binarnym distro przy odrobinie RE też można podmienić kilka funkcji w standardowych bibliotekach, i tym samym przyspieszyć system. (chociaż to wydaje się stosunkowo słabym pomysłem, chyba że nie ma się co robić z czasem)
Ot taki kolejny przypadek, gdzie przez wsteczną kompatybilność nie można rozwinąć skrzydeł.
Hmm, w sumie x86 to CISC on RISC... fajnie by było mieć dostęp do microkodu procesora, i np. móc składać własne instrukcje (chociaż raczej się na to nie zanosi). Ciekawi mnie też sprawa FPGA w Intel Atom.
No i na koniec... te wszystkie SSE 5,6,7 mogą być mało używane, ponieważ obliczenia przeniosły się na karty graficzne (i historia ponownie zatoczyła koło - patrz Amiga 1200 i np. karta Blizzard PPC).
Chociaż fakt faktem, OSy się raczej nie wybierają na GPU, tj. przynajmniej ich core/kernel (chociaż afair był jakiś eksperymentalny OS który miał korzystać w równiej mierze z GPU jak i z CPU).
Tak więc.. we shall see. Ale i tak będzie ciekawie ;)
Ad mnożenie i wynik w EDX:EAX. No cóż, imo jest to uzasadnione - w końcu mnożąc dwie liczby 32-bitowe można dostać max liczbę 64-bitową. Zresztą, afair IMUL w wersji trzy-operandowej zapisuje wynik tylko w jednym rejestrze.
Natomiast fakt faktem, tworzenie zarówno kompilatorów jak i dekompilatorów na x86 nie jest przyjemne. Zresztą, z disassemblerami to samo.
Powiedzmy, że pozwoliłem sobie na naciągnięcie znaczenia "wysokopoziomowości". Oczywiście chodziło mi o to, że ich działanie (np. w przypadku PCMPISTRM z Ranges) jest dużo skomplikowane/złożone niż np. instrukcji OR czy ADD.
Wydawało mi się, że zdradzisz się szerzej choć trochę w komentarzu do poprzedniego wpisu, gdzie pojawiło się przedstawicielstwo lamentów niezadowolonych czytelników, którzy nie mają co czytać. Najwidoczniej suspens nie służy publicity i trzeba było coś tam skrobnąć.
Dobrze kombinuję, Gyn? :>
Ad rem. Po pierwsze, zacznijmy od tego, że asm x86 prawie od początku był uber, że się tak wyrażę. Prosty świat to na pewno więc nie był, co nie znaczy, że programista C musiał od razu czuć się tu komfortowo (choć właściwie w pewnym stopniu powinien; ja np. poznałem C wiele lat po asm-ie, omijając podobno istotny problem w ogarnięciu wskaźników). Samo określenie CISC mówi za siebie - _complex_ instruction set computing. Wygoda w operowaniu bezpośrednio na pamięci (z pominięciem typowego RISC-owego load-store), złożone tryby adresowania czy "nadmiarowe" instrukcje (tj. realizowalne w kilku krokach za pomocą innych) były tym co powodowało, że ten asm nie był tak straszny od strony programowej, choć bez wątpienia komplikował nieco sprawę sprzętową, a niestała długość instrukcji była i jest tu istotnym elementem układanki (przy okazji polecam lekturę Agnerowego postu "Stop the instruction set war": http://www.agner.org/optimize/blog/read.php?i=25). To co nam wyewoluowało z x86 to CISC duchem (patrz kolejne zestawy SSE), choć sercem są to w zasadzie superskalarne RISC-owe jednostki wykonujące mikro-operacje, a to wszystko opakowane w zaawansowaną logikę. Puryści przyczepią się do mówienia tutaj o RISC-ach i mają rację, bo w zasadzie granica CISC-RISC mocno się skurczyła i do tego rozmazała na przestrzeni lat.
BTW Sukces x86 był możliwy w dużej mierzę dzięki ogromnym funduszom intela. "Utopili" w tym sporo kasy, ale i z efektami. Przewaga intela ostatnimi czasy pochodziła m.in. z pobicia bariery 3 IPC, osiągając zawrotną liczbę 4 instrukcji wykonywanych w trakcie jednego cyklu procesora Core 2. Agner też ciepło wypowiedział się nt. Sandy Bridge ("Test results for Intel's Sandy Bridge processor": http://agner.org/optimize/blog/read.php?i=142), konkludując "It has struck me that the new Sandy Bridge design is actually under-hyped. I would expect a new processor design with so many improvements to be advertised aggressively, but the new design doesn't even have an official brand name."
Ad rem. Po drugie, czy pamiętałeś drogi Gynie o serializacji w kontekście używania RDTSC? (Wybacz, że nie sprawdziłem linków.) Przyznam, że ja np. całkiem niedawno dowiedziałem się, że począwszy od Core i7 jest dostępna instrukcja RDTSCP, która pozwala nam zrezygnować z zabaw z CPUID.
Po trzecie, zapomniałem. Autentycznie...
Przechodząc do komentarzy.
GCC (począwszy od 4.3) nie ma problemu z używaniem tych instrukcji, -msse4.2 i wio.
Co do dalszego rozwoju x86. IMO możnaby pozbyć się balastu 16-bitowego. Mamy w końcu DosBoxy, VirtualBoxy i inne uruchamiane na całkiem niezłych boxach. Byłoby to w pewnym sensie komplementarne do wyrzucenia zbędnego syfu z BIOS-ów jak to nastąpiło np. w coreboot (dawny LinuxBIOS). Zwykłe 32-bity w dalszej przyszłości też możnaby wyrzucić, tzn. całe Legacy Mode (helper: http://developer.amd.com/SiteCollectionImages/Articles/7663.gif). Chyba mało kto wie, że są ciekawe przykłady użycia compatibility mode, jak LinuxPAE64 ("Running 64 bit applications in a 32 bit kernel using 32 bit device drivers and ...", http://www.linuxpae64.org/), przez co tego akurat bym w najbliższych 10-20 latach się nie wyzbywał. Gorzej jest ze stricte usuwaniem instrukcji, bo o ile normalne kompilatory z niektórych zwyczajnie nie korzystają, to te egzotyczne wypadki wpadają czasem do zabezpieczeń, są używane do obfuskacji, etc. W raytracing w 2020 nie wierzę, ale kryptografia krzywych eliptycznych powinna już do tego czasu poważnie zagościć w naszych przyszłych prockach. Chociaż może i na to za wcześnie. W ogóle jakieś sensowne wsparcie dla faktoryzacji i logarytmów dyskretnych byłoby mile widziane, ale z pewnością Stany zawsze będą blokować różnego rodzaju poważne wspomagacze w masowo produkowanych prockach.
Co by nie mówić, nie można odmówić swoistego piękna instrukcjom typu CRC32 (Nehalem) czy POPCNT (Barcelona). Bo prawdą jest, że zwykły Kowalski kompilując tych instrukcji nie otrzyma, ale w bibliotekach, w których wydajność jest kluczowa, zawsze będzie wiele implementacji tych samych funkcji wykorzystujących maksymalnie możliwości udostępniane przez różne procki, magicznie wybieranych poprzez CPU dispatcher. (BTW zbów polecam lekturę postu Agnera, "Intel's "cripple AMD" function": http://www.agner.org/optimize/blog/read.php?i=49, łącznie z odpowiedziami, także tymi po 14 miesiącach :>)
Co do założeń o dostępności SSE w związku z 64-bitami, to łatwo zapamiętać, że jest to co najmniej SSE2, gdyż sqrt na double'u w gcc przy optymalizacji (-O wystarczy) nie pluje się o brak -lm i korzysta z SQRTSD, które dodano właśnie w Pentium 4 wraz z SSE2. Szybki rzut oka na Agnerowe tabelki obsługi zestawów instrukcji sugeruje, że jest to też co najwyżej SSE2, gdyż wyższe mogłyby trafić na Athlony 64 pozbawione ich obsługi.
Pełny dostęp do mikrokodu? Marzenie ściętej głowy. :)
Fuzja (przynajmniej do pewnego stopnia) CPU i GPU to może być przyszłość. AMD ma Fusion, które z czasem może wyewoluować w naprawdę poważny kawałek krzemu. Intel chyba nie ma nic póki co, ale z pewnością będą chcieli to zmienić. Aż boję się myśleć o jednoczeniu sił Intela z nVidią...
Już nie piszę więcej, bo wyjdzie mi komentarz dłuższy od artykułu. :>
Add a comment: