| Autor: | Wojciech Muła |
|---|---|
| Dodany: | 13.04.2008 |
Przyznaję, że jest dość problematyczne, czy rzeczywiście użycie rozkazów SIMD może w tej klasie algorytmów pomóc, niemniej ciekawe to zastosowanie. Dopisek 7.04.2008 — owszem pomaga, testy które przeprowdziłem wykazują przyspieszenie 2, 3, 4 i więcej razy w stosunku do standardowej funckji strstr. Zobacz artykuł, tam również dostępne są źródła przetestowanych funkcji.
Skojarzyłem rozkaz MPSADBW z algorytmem Karpa-Rabina, w którym dokładne porównania wzorca i podciągu są wykonywane dopiero wtedy, gdy wartości funkcji haszującej dla wyszukiwanego wzorca i testowanego podciągu są równe.
Co prawda MPSADBW nie liczy żadnej funkcji skrótu, za to pozwala za jednym zamachem stwierdzić, na których pozycjach w zakresie 12 znaków jest zlokalizowany 4-znakowy wzorzec (SAD=0). Dopiero gdy ten fakt stwierdzimy można testować dokładniej, tzn. jeśli ów wzorzec był ledwie prefiksem dłuższego ciągu porównujemy kolejne znaki.
Oczywista wada tego rozwiązania: nie można wyszukiwać wzorców krótszych niż 4 znaki.
Szkic programu:
; edi -> wzorzec
; esi -> przeszukiwany łańcuch znaków
; ecx -> długość
movdqa (edi), %xmm0 ; xmm0 - prefiks wzorca
pxor %xmm7, %xmm7 ; xmm7 = packed_word(0)
0:
movdqu (esi), %xmm1 ; xmm1 - 12-bajtowy fragment łańcucha
movdqa %xmm1, %xmm2
; wyszukanie wystąpień
; xmm0 = [abcd .... .... ....] '.' - nieuwzględniane
; xmm2 = [XYab cdYa bcdX ....] '?' - liczba > 0
mpsadbw $0, %xmm0, %xmm1 ; xmm1 = [??0? ???0] (packed word)
; słowo = 0 -> podciągi równe (odległość między nimi zerowa)
pcmpeqw %xmm7, %xmm1 ; xmm1 = [0010 0001]
; sprawdzenie wyniku
ptest %xmm1, %xmm1 ; ZF := 1, gdy xmm1 = 0, czyli w ogóle nie znaleziono prefiksu
jz 1f ; przeskakujemy testy
; ... tutaj wykorzystujemy wyniki zapisane xmm1, np. tak
; w eax maska bitowa
pmovmskb %xmm1, %eax
; interesują nas wyłącznie bity na pozycjach parzystych
for i:=0 to 16 step 2 do
begin
if %eax[i] = 1 then
if strcmp(%edi + 4, %esi + 4 + i/2) = 0 then
...
end;
1:
addl $8, %esi
subl $8, %ecx
jnz 0b
Można też uwzględniać prefiksy 8-bajtowe, co wymaga 2-krotnego wywołania MPSADBW i zmiany przyrostu ESI z 8 na 12, choć nie wydaje mi się to lepszym rozwiązaniem. Dla porządku jednak kawałek kodu:
; ...
movdqa %xmm1, %xmm2
; wyszukanie wystąpień
; xmm0 = [abcd .... .... ....] '.' - nieuwzględniane
; xmm2 = [XYab cdYa bcde ....] '?' - liczba > 0
mpsadbw $0, %xmm0, %xmm1 ; xmm1 = [??0? ???0] (packed word)
; xmm0 = [.... efgh .... ....] '.' - nieuwzględniane
; xmm2 = [.... cdYa bcde fghZ] '?' - liczba > 0
mpsadbw $6, %xmm0, %xmm2 ; xmm2 = [???? ???0]
paddw %xmm2, %xmm1 ; xmm1 = [???? ???0]
pcmpeqw %xmm7, %xmm1 ; xmm1 = [0000 0001]
; ...
addl $12, %esi
subl $12, %ecx
; ...
Firma Intel dla architektury Enhanced Core 2 podaje, że opóźnienie MPSADBW wynosi 4 cykle, zaś przepustowość 2 cykle. Zatem po 4 cyklach dostępna jest informacja, które z 8 kolejnych 4-bajtowych podciągów zawierają 4 bajtowy wzorzec — to daje pół cykla na porównanie (efektownie, ale czy efektywnie?); następnie wykonywany jest PCMPEQW (1 cykl), PTEST (1 cykl) i ewentualny skok (>= 1 cykl). W sumie 7 cykli.
Moje testy wskazują, że tego rodzaju predykcja nie zmusza do wykonywania dużej liczby dokładnych porównań — jednak kwestia, czy w praktyce będzie rzeczywiście tak różowo, jest otwarta.