🚀 go-pugleaf

Wojciech Muła pisze:
> Hej, kontynuacja wątku założonego przez Andrzeja.
> U mnie niestety starsze posty wyparowały, więc nie mam
> gdzie się podczepić.
> 
> Przetestowałem właśnie kilka metod:
> * "bajty"  - naiwny algorytm zamiany bajt po bajcie
> * BSWAP    - zmiana 4 bajtów na iterację (1 x BSWAP)
> * 2xBSWAP  - zmiana 8 bajtów na iterację (2 x BSWAP)
> * PSHUFB   - zmiana 16 bajtów na iterację (1 x PSHUFB)
> * 2xPSHUFB - zmiana 32 bajtów na iterację (2 x PSHUFB)
> 
> Rozmiary tablic są wielokrotnością 32 bajtów, więc wszystkie
> dostępy do pamięci były wyrównane. Procesor Core 2 Duo E8400.
> W tabelce są czasy wykonywania kilku-kilkuset tysięcy iteracji.
> Mój wniosek nie jest odkrywczy: najbardziej ograniczają nas
> czasy dostępu do pamięci.
> 
> +-------------+-----------+----------------+----------------+----------------+----------------+
> |  rozmiar    |   bajty   |      BSWAP     |    2xBSWAP     |     PSHUFB     |    2xPSHUFB    |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |   64 B      |  759 ms   | 292 ms | 2.6 x | 267 ms | 2.8 x | 240 ms | 3.1 x | 138 ms | 5.5 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |  128 B      |  740 ms   | 264 ms | 2.8 x | 218 ms | 3.4 x | 108 ms | 6.8 x | 107 ms | 6.9 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |  256 B      |  808 ms   | 303 ms | 2.6 x | 243 ms | 3.3 x |  81 ms | 9.9 x |  72 ms |11.2 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |  512 B      | 1026 ms   | 394 ms | 2.6 x | 305 ms | 3.3 x |  91 ms |11.2 x |  84 ms |12.2 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |    1 kB     | 1000 ms   | 404 ms | 2.4 x | 298 ms | 3.3 x |  81 ms |12.3 x |  69 ms |14.5 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |    4 kB     |  786 ms   | 312 ms | 2.5 x | 235 ms | 3.3 x |  64 ms |12.0 x |  50 ms |15.7 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |    8 kB     |  793 ms   | 310 ms | 2.5 x | 235 ms | 3.4 x |  61 ms |13.0 x |  51 ms |15.5 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |   16 kB     | 1582 ms   | 617 ms | 2.6 x | 467 ms | 3.4 x | 120 ms |13.2 x | 100 ms |15.8 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> 
> w.
> 

Jak pamiętasz, zadałem na początku pytanie: czy przy odwracaniu 
kolejności bajtów BSWAP może się do czegoś przydać?

Jaki wniosek?

Wojciech Muła pisze:
> Hej, kontynuacja wątku założonego przez Andrzeja.
> U mnie niestety starsze posty wyparowały, więc nie mam
> gdzie się podczepić.
> 
> Przetestowałem właśnie kilka metod:
> * "bajty"  - naiwny algorytm zamiany bajt po bajcie
> * BSWAP    - zmiana 4 bajtów na iterację (1 x BSWAP)
> * 2xBSWAP  - zmiana 8 bajtów na iterację (2 x BSWAP)
> * PSHUFB   - zmiana 16 bajtów na iterację (1 x PSHUFB)
> * 2xPSHUFB - zmiana 32 bajtów na iterację (2 x PSHUFB)
> 
> Rozmiary tablic są wielokrotnością 32 bajtów, więc wszystkie
> dostępy do pamięci były wyrównane. Procesor Core 2 Duo E8400.
> W tabelce są czasy wykonywania kilku-kilkuset tysięcy iteracji.
> Mój wniosek nie jest odkrywczy: najbardziej ograniczają nas
> czasy dostępu do pamięci.
> 
> +-------------+-----------+----------------+----------------+----------------+----------------+
> |  rozmiar    |   bajty   |      BSWAP     |    2xBSWAP     |     PSHUFB     |    2xPSHUFB    |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |   64 B      |  759 ms   | 292 ms | 2.6 x | 267 ms | 2.8 x | 240 ms | 3.1 x | 138 ms | 5.5 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |  128 B      |  740 ms   | 264 ms | 2.8 x | 218 ms | 3.4 x | 108 ms | 6.8 x | 107 ms | 6.9 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |  256 B      |  808 ms   | 303 ms | 2.6 x | 243 ms | 3.3 x |  81 ms | 9.9 x |  72 ms |11.2 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |  512 B      | 1026 ms   | 394 ms | 2.6 x | 305 ms | 3.3 x |  91 ms |11.2 x |  84 ms |12.2 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |    1 kB     | 1000 ms   | 404 ms | 2.4 x | 298 ms | 3.3 x |  81 ms |12.3 x |  69 ms |14.5 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |    4 kB     |  786 ms   | 312 ms | 2.5 x | 235 ms | 3.3 x |  64 ms |12.0 x |  50 ms |15.7 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |    8 kB     |  793 ms   | 310 ms | 2.5 x | 235 ms | 3.4 x |  61 ms |13.0 x |  51 ms |15.5 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> |   16 kB     | 1582 ms   | 617 ms | 2.6 x | 467 ms | 3.4 x | 120 ms |13.2 x | 100 ms |15.8 x |
> +-------------+-----------+--------+-------+--------+-------+--------+-------+--------+-------+
> 
> w.
> 

Jak pamiętasz, zadałem na początku pytanie: czy przy odwracaniu
kolejności bajtów BSWAP może się do czegoś przydać?

Jaki wniosek?

Co prawda w ogólnym przypadku długość pola nie jest wielokrotnością 4, 
ale zaprezentowany przeze mnie algorytm po wykonaniu serii instrukcji 
BSWAP wykonuje jeszcze CO NAJWYŻEJ DWIE ZAMIANY, czyli dodatkowy koszt 
jest stały i niewielki. W ogólnym przypadku pola ładowane/zapisywane 
do/z rejestrów EAX i EDX nie są wyrównane do DWORD, co też może wydłużać 
czasy podane powyżej (a propos: czy rozmiar tablicy będący 
wielokrotnością 32 gwarantuje, że cała tablica będzie wyrównana na 
adresie podzielnym przez 32? Chyba jednak nie...).

Skoro już wziąłeś się za pomiary, to spróbuje porównać moją procedurę z 
naiwnym przestawianiem bajtów.



     PUSH EBX
     PUSH ESI
     PUSH EDI

     CLD

     LEA EDI,[ESI+ECX-4]

     MOV EBX,ECX

     ADD ECX,4
     SHR ECX,3
     JZ  @@Partial

@@Loop:
     LODSD
     MOV EDX,[EDI]
     BSWAP EAX
     BSWAP EDX
     STOSD
     MOV [ESI-4],EDX
     SUB EDI,8
     LOOP @@Loop

@@Partial:

     ; być może ten kawałek można lepiej zrobić
     AND EBX,7
     JZ  @@Done
     TEST EBX,4
     JNZ @@Done
;---------------------------
     LEA  EDI,[ESI+EBX-1]
     MOV  AL,[EDI]
     MOVSB
     MOV [ESI-1],AL

@@Done:

     POP EDI
     POP ESI
     POP EBX

Andrzej Grażyński <grazynsk@petex.com.pl> wrote:

> Jak pamiętasz, zadałem na początku pytanie: czy przy odwracaniu
> kolejności bajtów BSWAP może się do czegoś przydać?
> 
> Jaki wniosek?

Wniosek jest taki, że się bardzo przydaje. Bez wielkiego wysiłku
mamy przyspieszenie 2 razy, przy rozwinięciu pętli ponad 3 razy
(w stosunku do wersji bajt po bajcie).

> Co prawda w ogólnym przypadku długość pola nie jest wielokrotnością 4, 
> ale zaprezentowany przeze mnie algorytm po wykonaniu serii instrukcji 
> BSWAP wykonuje jeszcze CO NAJWYŻEJ DWIE ZAMIANY, czyli dodatkowy koszt 
> jest stały i niewielki. W ogólnym przypadku pola ładowane/zapisywane 
> do/z rejestrów EAX i EDX nie są wyrównane do DWORD, co też może wydłużać 
> czasy podane powyżej

Będę jeszcze jutro albo pojutrze testował więcej i wtedy przygotuję jakiś
nadający się do wglądu program. Na razie wstępnie zaobserwowałem, że
niewyrównane dane dają spowolnienie 2-3 krotne (dla BSWAP mniejsze,
dla rozkazów SSE większe).

> (a propos: czy rozmiar tablicy będący wielokrotnością 32 gwarantuje,
> że cała tablica będzie wyrównana na adresie podzielnym przez 32?
> Chyba jednak nie...).

Procedury zakodowałem jako wstawki asemblerowe w GCC, mam w programie duże
statyczne tablice, które na pewno były wyrównane do granicy 16 bajtów (a może
nawet do granicy strony), bo inaczej by wersje SSE nie zadziałały. :)

> Skoro już wziąłeś się za pomiary, to spróbuje porównać moją procedurę z 
> naiwnym przestawianiem bajtów.
> 
>      PUSH EBX
>      PUSH ESI
>      PUSH EDI
> 
>      CLD
> 
>      LEA EDI,[ESI+ECX-4]
> 
>      MOV EBX,ECX
> 
>      ADD ECX,4
>      SHR ECX,3
>      JZ  @@Partial
> 
> @@Loop:
>      LODSD
>      MOV EDX,[EDI]
>      BSWAP EAX
>      BSWAP EDX
>      STOSD
>      MOV [ESI-4],EDX
>      SUB EDI,8
>      LOOP @@Loop

Zmartwię Cię - na Core 2 to jest dramatycznie wolne, niekiedy wolniejsze
od wersji bajt po bajcie, a jeśli szybsze to nieznacznie tylko. Wszystko
psuje pewnie lods/stos. Mój kod jest natomiast taki:

1:
	mov eax, [esi]
	mov ebx, [edi]
	bswap eax
	bswap ebx
	mov eax, [edi]
	mov ebx, [esi]
	add esi, 4
	sub edi, 4
	cmp esi, edx	; edx = esi + 4*(ecx/2)
	jne 1

I te czasy dla tablic 32-bajtowych wynoszą mniej więcej:
* bajt po bajcie - 400 ms / 100%
* Twoje BSWAP	 - 490 ms / 120%
* moje BSWAP	 - 180 ms /  45%

w.

Wojciech Muła pisze:
> Andrzej Grażyński <grazynsk@petex.com.pl> wrote:
> 
>> Jak pamiętasz, zadałem na początku pytanie: czy przy odwracaniu
>> kolejności bajtów BSWAP może się do czegoś przydać?
>>
>> Jaki wniosek?
> 
> Wniosek jest taki, że się bardzo przydaje. Bez wielkiego wysiłku
> mamy przyspieszenie 2 razy, przy rozwinięciu pętli ponad 3 razy
> (w stosunku do wersji bajt po bajcie).
> 
>> Co prawda w ogólnym przypadku długość pola nie jest wielokrotnością 4, 
>> ale zaprezentowany przeze mnie algorytm po wykonaniu serii instrukcji 
>> BSWAP wykonuje jeszcze CO NAJWYŻEJ DWIE ZAMIANY, czyli dodatkowy koszt 
>> jest stały i niewielki. W ogólnym przypadku pola ładowane/zapisywane 
>> do/z rejestrów EAX i EDX nie są wyrównane do DWORD, co też może wydłużać 
>> czasy podane powyżej
> 
> Będę jeszcze jutro albo pojutrze testował więcej i wtedy przygotuję jakiś
> nadający się do wglądu program. Na razie wstępnie zaobserwowałem, że
> niewyrównane dane dają spowolnienie 2-3 krotne (dla BSWAP mniejsze,
> dla rozkazów SSE większe).
> 
>> (a propos: czy rozmiar tablicy będący wielokrotnością 32 gwarantuje,
>> że cała tablica będzie wyrównana na adresie podzielnym przez 32?
>> Chyba jednak nie...).
> 
> Procedury zakodowałem jako wstawki asemblerowe w GCC, mam w programie duże
> statyczne tablice, które na pewno były wyrównane do granicy 16 bajtów (a może
> nawet do granicy strony), bo inaczej by wersje SSE nie zadziałały. :)
> 
>> Skoro już wziąłeś się za pomiary, to spróbuje porównać moją procedurę z 
>> naiwnym przestawianiem bajtów.
>>
>>      PUSH EBX
>>      PUSH ESI
>>      PUSH EDI
>>
>>      CLD
>>
>>      LEA EDI,[ESI+ECX-4]
>>
>>      MOV EBX,ECX
>>
>>      ADD ECX,4
>>      SHR ECX,3
>>      JZ  @@Partial
>>
>> @@Loop:
>>      LODSD
>>      MOV EDX,[EDI]
>>      BSWAP EAX
>>      BSWAP EDX
>>      STOSD
>>      MOV [ESI-4],EDX
>>      SUB EDI,8
>>      LOOP @@Loop
> 
> Zmartwię Cię - na Core 2 to jest dramatycznie wolne, niekiedy wolniejsze
> od wersji bajt po bajcie, a jeśli szybsze to nieznacznie tylko. Wszystko
> psuje pewnie lods/stos. Mój kod jest natomiast taki:
> 
> 1:
> 	mov eax, [esi]
> 	mov ebx, [edi]
> 	bswap eax
> 	bswap ebx
> 	mov eax, [edi]
> 	mov ebx, [esi]
> 	add esi, 4
> 	sub edi, 4
> 	cmp esi, edx	; edx = esi + 4*(ecx/2)
> 	jne 1
> 
> I te czasy dla tablic 32-bajtowych wynoszą mniej więcej:
> * bajt po bajcie - 400 ms / 100%
> * Twoje BSWAP	 - 490 ms / 120%
> * moje BSWAP	 - 180 ms /  45%
> 
> w.

Skoro LODS/STOS tak się nie lubią z tym procesorem, to zróbmy oczywistą 
modyfikację, nieznacznie różniącą się od Twojej wersji:


   @@Loop:
        MOV EAX,[ESI]
        MOV EDX,[EDI]
        BSWAP EAX
        BSWAP EDX
        MOV [EDI],EAX
        MOV [ESI],EDX
        ADD ESI,4
        SUB EDI,4
        LOOP @@Loop

I sprawdź teraz.

a.

Andrzej Grażyński <grazynsk@petex.com.pl> wrote:

> Skoro LODS/STOS tak się nie lubią z tym procesorem, to zróbmy oczywistą 
> modyfikację, nieznacznie różniącą się od Twojej wersji:
> 
> 
>    @@Loop:
>         MOV EAX,[ESI]
>         MOV EDX,[EDI]
>         BSWAP EAX
>         BSWAP EDX
>         MOV [EDI],EAX
>         MOV [ESI],EDX
>         ADD ESI,4
>         SUB EDI,4
>         LOOP @@Loop
> 
> I sprawdź teraz.

Lepiej, ale dalej słabo. Dopiero po zastąpieniu LOOP sekwencją dec ecx/jnz
jest okej. Te wszystkie CISC-owe instrukcje Intel od jakiegoś czasu właściwie
porzucił, nawet nie ma o nich wzmianki w podręczniku optymalizacji. Wyjątkiem
jest REP MOVS, który jest jakoś specjalnie traktowany w niektórych przypadkach.

Właśnie odkryłem, że wyniki pomiarów dla wersji PSHUFB są jakieś dziwne,
nie wiem dlaczego takie mały czasy mi wtedy wyszły. Teraz zmierzyłem 
i przyspieszenie wychodzi dużo mniejsze. Właściwie przyspieszenie rzędu 16
jest zbyt piękne, aby było prawdziwe. :)

w.

Wojciech Muła <wojciech_mula@poczta.null.onet.pl.invalid> wrote:

> Właśnie odkryłem, że wyniki pomiarów dla wersji PSHUFB są jakieś dziwne,
> nie wiem dlaczego takie mały czasy mi wtedy wyszły. Teraz zmierzyłem 
> i przyspieszenie wychodzi dużo mniejsze. Właściwie przyspieszenie rzędu 16
> jest zbyt piękne, aby było prawdziwe. :)

Gupi jestem. Przyspieszenie rzeczywiści wychodzi prawie 16, oczywiście
w pewnych warunkach. Dawno obiecany testowy program i wyniki z moich
dwóch komputerów:

http://wm.ite.pl/notesen.html#note-2010-8

Wniosek jest właściwie jeden - wyrówanienie danych albo wydajność, wybór
zależy od ciebie. :)

w.

ale takie odwracanie bitów to kiedykolwiek Wam było do czegoś potrzebne? 

"identifikator: 20040501" <NOSPAMtestowanije@go2.pl> wrote:

> ale takie odwracanie bitów to kiedykolwiek Wam było do czegoś potrzebne? 

Mnie nigdy. Ale wnioski z eksperymentów są pouczające.

w.