🚀 go-pugleaf

wild wrote:
>   movups   xmm0, [edi]
>   movups   xmm1, [esi]
>   add      edi,  16
>   add      esi,  16
>   movaps   xmm3, xmm0
>   movaps   xmm4, xmm1
>   pcmpeqb  xmm0, xmm1
>   pcmpeqb  xmm3, xmm7
>   pmovmskb edx,  xmm0
>   pcmpeqb  xmm4, xmm7
>    pmovmskb ecx,  xmm3
>   pmovmskb ebx,  xmm4
>   cmp      ecx,  0
>   jnz      ending_package
>   cmp   ebx,  0
>   jnz      ending_package
>   cmp      edx,  0xFFFF
>   jnz      compare_not_eq
>   jmp      compare_next_pack

Tu jest wersja MMX (łatwo przerobić na SSE),
nieco prostsza niż Twoja:
http://republika.pl/wmula/articles/string.h.asm.html#id5

w.

wild napisał(a):
> pisze pewien program (algorytmy genetyczne, generowanie serii produkcji itp)
> po zprofilowaniu wyszlo ze bardzo duzo czasu program spedza w strcmp
> (porownywanie miedzy soba produkcji reprezentowanych przez zakonczone zerem 
> lancuchy znakow)
> z punku widzenia algorymow niewiele juz moge zrobic zeby zredukowac ilosc 
> tych porownan
> sprobowalem napisac wlasna wesje strcmp
> potrzebuje wiedziec tylko czy 2 lancuchy sa rowne (0) czy rozne (1)
> kod ponizej, ... jest szybciej o jakies 30%
> czy macie moze jakies komentarze do tego kodu, co mozna by tam jeszcze 
> przyspieszyc ?
> nic wiecej nie przychodzi mi juz do glowy (poza aligmentem do 16 danych, ale 
> to komplikuje pare spraw
> a dalszy zysk jest mizerny, ok 3%)
> dodam ze charakterystyka porownywanych ciagow jest taka ze zwykle pierwsze 
> 32 - 40 pierwsze znaki sa takie same
> roznice sa dopiero potem.
> uprzedzajac pytania: liczenie crc32 (czy innego skrotu) i porownywanie tego 
> zamiast stringow nie jest rozwiazaniem
> gdyz ciagi zmieniaja sie zbyt czesto.

 Poczytaj strony o optymalizacji:

http://www.amd.com/us-en/Processors/DevelopWithAMD/0,,30_2252_739_7044,00.html
(w jednym z manuali są przykłady - co najmniej memcpy).

http://www.emboss.co.nz/pentopt/freeinfo.html

http://www.agner.org/assem/

http://www.df.lth.se/~john_e/gems.html

http://graphics.stanford.edu/~seander/bithacks.html

http://www.mark.masmcode.com/

Może coś się przyda.

> int __declspec(naked) _fastcall CompareStrings(const char *astr, const char 
> *bstr)
> {
>  __asm
>  {
>   push     edi
>   push     esi
>   push     ebx
>   push     ecx
>   subps    xmm7, xmm7
>   mov      edi,  ecx // astr
>   mov      esi,  edx // bstr

 Pozbądź się tych 2 instrukcji i używaj ECX i EDX jako wskaźników.

> compare_next_pack:
> 
>   movups   xmm0, [edi]
>   movups   xmm1, [esi]
>   add      edi,  16
>   add      esi,  16
>   movaps   xmm3, xmm0
>   movaps   xmm4, xmm1
>   pcmpeqb  xmm0, xmm1
>   pcmpeqb  xmm3, xmm7
>   pmovmskb edx,  xmm0
>   pcmpeqb  xmm4, xmm7
>    pmovmskb ecx,  xmm3
>   pmovmskb ebx,  xmm4
>   cmp      ecx,  0
>   jnz      ending_package
>   cmp   ebx,  0
>   jnz      ending_package
>   cmp      edx,  0xFFFF
>   jnz      compare_not_eq
>   jmp      compare_next_pack

 Po pierwsze - "TEST ECX/EBX, ECX/EBX" zamiast "CMP ECX/EBX, 0".
 Skoro wszystkie łańcuchy znaków reprezentują to samo, więc pewnie są
tej samej długości. Może źle myślę (małe mam doświadczenie w SIMD),
ale pomysł mam taki:

	push		ecx	; jeśli trzeba
	push		edx	; jeśli trzeba

	xor		eax, eax
compare_next_pack:
	cmp		ecx, adres_konca_stringa
	jae		koniec
	movups		xmm0, [ecx]
	movups		xmm1, [edx]
; porównywanie bezpośrednio danych. Stringi muszą być dopełnione
; do wielokrotności 16 bajtów. Ułożenie też by pomogło, nawet jeśli
; to tylko 3%
	pcmpeqb		xmm0, xmm1
	pmovmskb	eax, xmm0
	add		ecx, 16
	add		edx, 16

; EAX != 0 od razu oznacza, że dane były różne.
	test		eax, eax
	jz		compare_next_pack
	mov		eax, 1
koniec:
	pop		edx
	pop		ecx

	ret

 To wprowadza jednak potrzebę kontrolowania długości stringów.
Powyższa pętle, jeśli w ogóle jest prawidłowa, korzysta tylko z 2
rejestrów XMM, można więc ją 4-krotnie rozwinąć, by porównywać 64
bajty w jednym machu.
 Jeśli wartość zwracana dla różnych łańcuchów niekoniecznie musi być 1
(a wystarczy cokolwiek różnego od zera), wyrzucamy linię "mov eax, 1".

-- 
Pozdrawiam, Bogdan                                  (Linux i FreeDOS)
Kurs assemblera x86 (DOS i Linuks): http://rudy.mif.pg.gda.pl/~bogdro
Grupy dyskusyjne o asm:  pl.comp.lang.asm alt.pl.asm alt.pl.asm.win32
Rozmawiaj bezpiecznie: www.JabberPL.org Surfuj anonimowo: tor.eff.org

> Tu jest wersja MMX (łatwo przerobić na SSE),
> nieco prostsza niż Twoja:
> http://republika.pl/wmula/articles/string.h.asm.html#id5

ok, mmxowa wersja jest o 10% szybsza
aaa przy okazji, na stronie jest literowka (w strcmp)
w linijce
// jmp end ; napotkaniu końca A, B, lub różniącego je bajtu

ma byc jnz end a nie jmp !!!!!

Wojciech Muła wrote:

> 
> Tu jest wersja MMX (łatwo przerobić na SSE),
> nieco prostsza niż Twoja:
> http://republika.pl/wmula/articles/string.h.asm.html#id5

Conieco można to uprościć, np.

.compare_mmx:

         movq    mm0, [edi]
	add	edi, 8
         pcmpeqd mm0, [esi] ;
	add	esi, 8

         psrlq   mm0, 1

         movd    eax, mm0   ; 0xffffffff jeśli równe
         inc     eax    ; eax=0 i ZF ustawione jeśli równe
         jnz     .diff

         loop     .compare_mmx

.compare_rest:
mov	eax, ebx
or   eax, eax  ; jeśli nie jest potrzebne dodatkowe porównanie
jz .equal     ; łańcuchy są identyczne

; da się to zrobić bez masek w pamięci, ale zostawmy to przyszłym 
pokoleniom...
movq    mm0, [edi]
pcmpeqb mm0, [esi]
por     mm0, [mask + ebx*8 - 8] ; przypadkowe dane spoza końców
                                 ; łańcuchów są uznawane za identyczne
                                 ; (-8, gdyż ebx=1..7)

pcmpeqd mm0, mm1
psrlq   mm0, 16

movd    eax, mm0
inc     eax    ; eax=0 i ZF ustawione jeśli równe

.equal:
.diff:
mov	ebx, 1
cmovnz	eax, ebx
ret

wild wrote:
> ma byc jnz end a nie jmp !!!!!

Dzięki, już poprawione.  

w.

Bernard wrote:
> Conieco można to uprościć, np.
>
> .compare_mmx:
>
>          movq    mm0, [edi]
> 	add	edi, 8
>          pcmpeqd mm0, [esi] ;
> 	add	esi, 8
>
>          psrlq   mm0, 1
>
>          movd    eax, mm0   ; 0xffffffff jeśli równe
>          inc     eax    ; eax=0 i ZF ustawione jeśli równe
>          jnz     .diff
>
>          loop     .compare_mmx

Zaraz, ale gdzie tutaj sprawdzasz czy nie ma kończącego zera?
Ten loop sugeruje, że z góry znasz maks. długość obu łańcuchów,
a tego zdaje się OP nie zakładał.  (Przy takim założeniu pewnie
byłoby nawet szybciej z użyciem zwykłych instrukcji IA-32).

w.

Wojciech Muła wrote:
> Bernard wrote:
>> Conieco można to uprościć, np.
>>
>> .compare_mmx:
>>
>>          movq    mm0, [edi]
>> 	add	edi, 8
>>          pcmpeqd mm0, [esi] ;
>> 	add	esi, 8
>>
>>          psrlq   mm0, 1
>>
>>          movd    eax, mm0   ; 0xffffffff jeśli równe
>>          inc     eax    ; eax=0 i ZF ustawione jeśli równe
>>          jnz     .diff
>>
>>          loop     .compare_mmx
> 
> Zaraz, ale gdzie tutaj sprawdzasz czy nie ma kończącego zera?
> Ten loop sugeruje, że z góry znasz maks. długość obu łańcuchów,
> a tego zdaje się OP nie zakładał.  (Przy takim założeniu pewnie
> byłoby nawet szybciej z użyciem zwykłych instrukcji IA-32).
> 
> w.

Program robi dokładnie to samo, co wskazany wcześniej przykład, a ten 
miał porównywać łańcuchy o długości zadanej jako argument. Z 
reklamacjami proszę do autora oryginału.

Bernard wrote:
> Program robi dokładnie to samo, co wskazany wcześniej przykład, a ten 
> miał porównywać łańcuchy o długości zadanej jako argument. Z 
> reklamacjami proszę do autora oryginału.

Widać coś przegapiłem, bo zdawało się, że chodziło właśnie o łańuchy
zakończone zerem.

w.

Cześć.

Użytkownik "wild" <spam@no.thx> napisał w wiadomości
news:enqgtc$29d$1@nemesis.news.tpi.pl...
> > Tu jest wersja MMX (łatwo przerobić na SSE),
> > nieco prostsza niż Twoja:
> > http://republika.pl/wmula/articles/string.h.asm.html#id5
>
> ok, mmxowa wersja jest o 10% szybsza

Wreszcie udało mi się znaleźć trochę czasu, procesor z SSE2 i sprawdzić to i
owo. Dziwiło mnie mianowicie to 10%. Bo jeżeli mowa o czasie wykonania
procedury opartej o MMX w porównaniu do SSE2, to mam inne wyniki (testowane
na xeonie dla wyrównanych łańcuchów o długości po ok. 10M):

135   SSE2
200   MMX    // przyrost o 48%
529   STD    // przyrost o 292% do SSE2 i o 164% do MMX

Ciekawe są też rezultaty dla P3:

306   MMX
801   STD    // przyrost o 162%

Pierwsza kolumna to czas wykonania procedury (mniejsza o jednostkę). STD -
to rezultat dla funkcji strcmp (dla pełniejszego obrazu). Testowany kod
(poniżej) jest dość podobny do tego, który podał wcześniej Wojtek. Różni się
przede wszystkim brakiem jednego skoku warunkowego wewnątrz pętli oraz
końcówką - sprawdzeniem ostatecznego wyniku po wyjściu z pętli (nie pobiera
ponownie danych z pamięci). Wydaje mi się, że powinien być przez to nieco
szybszy, co może mieć znaczenie zwłaszcza przy porównywaniu dużej ilości
krótkich łańcuchów. Za to nie zwraca informacji, który łańcuch jest
"większy" tylko czy się równają czy nie. Ale w końcu od takiego założenia
rozpoczął się ten wątek.

int strequSSE2(const char * str1, const char * str2) {
  _ESI = (int)str1;
  _EBX = (int)str2 - _ESI;
  asm pxor xmm7, xmm7;
  do asm {
    movdqa   xmm0, [esi];
    movdqa   xmm1, [esi + ebx];
    movdqa   xmm2, xmm0;
    pcmpeqb  xmm2, xmm1; // xmm2 <- (xmm0 == xmm1)
    pcmpeqb  xmm2, xmm7; // xmm2 <- (xmm0 != xmm1), zanegowanie
    pcmpeqb  xmm0, xmm7; // xmm0 <- (xmm0 zawiera 0x0)
    pcmpeqb  xmm1, xmm7; // xmm1 <- (j.w.)
    por      xmm0, xmm2;
    por      xmm0, xmm1;
    pmovmskb eax, xmm0; // bity, na których łańcuchy różnią się lub kończą
    add      esi, 16;
  } while (!_EAX);
  asm {
    pmovmskb edx, xmm2;// bity, na których łańcuchy się różnią
    lea      esi, [eax - 1];
    lea      ebx, [edx - 1];
    xor      eax, esi;// tylko młodsze bity warunku końca pętli
    xor      edx, ebx;// tylko młodsze bity różnicy w łańcuchach lub -1
    cmp      eax, edx;
    sbb      eax, eax;// zero, jeśli różnica wystąpiła wcześniej lub równo z
0x0
  };
  return _EAX;
};

Kod dla MMX jest analogiczny.
-- 
Pozdrawiam :-)
Bartek