No cóż, nie jesteśmy już amatorami i przyszła pora, aby przyjrzeć się temu, w czym asembler
wprost błyszczy: algorytmy intensywne obliczeniowo. Specjalnie na potrzeby tego kursu
napisałem następujący programik. Zaprezentuję w nim kilka sztuczek i pokażę, do jakich rozmiarów
(tutaj: 2 instrukcje) można ścisnąć główną pętlę programu.
Oto ten programik:
; Program liczący sumę liczb od 1 do liczby wpisanej z klawiatury ; ; Autor: Bogdan D. ; ; kompilacja NASM: ; nasm -O999 -o ciag_ar.obj -f obj ciag_ar.asm ; alink ciag_ar.obj bibl\lib\bibldos.lib -c- -oEXE -m- ; kompilacja FASM (stary format biblioteki - OMF): ; fasm ciag_ar.asm ciag_ar.obj ; alink ciag_ar.obj bibl\lib\bibldos.lib -c- -entry _start -oEXE -m- ; kompilacja FASM (nowy format biblioteki - COFF): ; fasm ciag_ar.asm ciag_ar.obj ; ld -s -o ciag_ar.exe ciag_ar.obj bibl\lib\bibldos.a %include "bibl\incl\dosbios\nasm\std_bibl.inc" %include "bibl\incl\dosbios\nasm\do_nasma.inc" .stack 400h section .text ; FASM (stary format biblioteki - OMF): ; format coff ; include "bibl\incl\dosbios\fasm\std_bibl.inc" ; use16 ; public start ; public _start ; FASM (nowy format biblioteki - COFF): ; format coff ; include "bibl\incl\dosbios\fasm32\std_bibl.inc" ; public start ; public _start start: _start: ..start: pisz db "Program liczy sume liczb od 1 do podanej liczby.",cr,lf db "Podaj liczbe calkowita: ",0 we32e ; pobieramy z klawiatury liczbę do rejestru EAX jnc liczba_ok ; flaga CF=1 oznacza błąd blad: pisz db cr, lf, "Zla liczba!",0 wyjscie 1 ; mov ax, 4c01h / int 21h liczba_ok: test eax, eax ; jeśli EAX=0, to też błąd jz blad mov ebx, eax ; zachowaj liczbę. EBX=n xor edx, edx ; EDX = nasza suma mov ecx, 1 petla: add edx, eax ; dodaj liczbę do sumy sub eax, ecx ; odejmij 1 od liczby jnz petla ; liczba różna od zera? ; to jeszcze raz dodajemy pisz db cr, lf, "Wynik z sumowania 1+2+3+...+n= ",0 mov eax, edx ; EAX = wynik pisz32e ; wypisz EAX mov eax, ebx ; przywrócenie liczby add eax, 1 ; EAX = n+1 mul ebx ; EDX:EAX = EAX*EBX = n*(n+1) shr edx, 1 rcr eax, 1 ; EDX:EAX = EDX:EAX/2 pisz db cr, lf, "Wynik ze wzoru: n(n+1)/2= ",0 pisz64 ; wypisuje na ekranie 64-bitową liczbę całkowitą ; z EDX:EAX wyjscie 0 ; mov ax, 4c00h / int 21h
Jak widać, nie jest on ogromny, a jednak spełnia swoje zadanie. Teraz przeanalizujemy ten krótki programik:
Mówi, co program robi oraz kto jest jego autorem. Może zawierać informacje o wersji programu, o niestandardowym sposobie kompilacji/uruchomienia i wiele innych szczegółów.
To są makra uruchamiające procedury z mojej biblioteki. Używam ich, bo są sprawdzone i nie muszę ciągle umieszczać kodu tych procedur w programie.
wyjsciezawiera w sobie kod wyjścia z programu, napisany obok.
test rej, rej / jz ... / jnz ...
Instrukcja TEST jest szybsza niż CMP rej, 0 i nie zmienia zawartości rejestru, w
przeciwieństwie do OR. Jest to najszybszy sposób na sprawdzenie,
czy wartość rejestru wynosi 0.
Jak widać, najpierw do sumy dodajemy n, potem n-1, potem n-2, i na końcu 1. Umożliwiło to
znaczne skrócenie kodu pętli, a więc zwiększenie jej szybkości. Napisanie SUB EAX, ECX
zamiast SUB EAX, 1 skraca rozmiar instrukcji i powoduje jej przyspieszenie,
gdyż dzięki temu w samej pętli procesor operuje już tylko na rejestrach.
SHR EDX, 1 / RCR EAX, 1
Wynik musimy podzielić przez 2, zgodnie ze wzorem.
Niestety, nie ma instrukcji SHR dla 64 bitów. Więc trzeba ten brak jakoś obejść.
Najpierw, SHR EDX, 1 dzieli EDX przez 2, a bit 0 ląduje we fladze CF. Teraz,
RCR EAX, 1 (rotate THROUGH CARRY)
wartość CF (czyli stary bit 0 EDX) umieści w bicie 31 EAX. I o to chodziło!
Poniższy programik też napisałem dla tego kursu. Ma on pokazać złożone sposoby adresowania oraz
instrukcje warunkowego przesunięcia (CMOV..):
; Program wczytuje od użytkownika macierz 3x3, po czym znajduje ; element największy i najmniejszy ; ; Autor: Bogdan D. ; ; kompilacja: ; nasm -O999 -o macierze.obj -f obj macierze.asm ; alink macierze.obj bibl\lib\bibldos.lib -c- -oEXE -m- ; kompilacja FASM (stary format biblioteki - OMF): ; fasm macierze.asm macierze.obj ; alink macierze.obj bibl\lib\bibldos.lib -c- -entry _start -oEXE -m- ; kompilacja FASM (nowy format biblioteki - COFF): ; fasm macierze.asm macierze.obj ; ld -s -o macierze.exe macierze.obj bibl\lib\bibldos.a %include "bibl\incl\dosbios\nasm\std_bibl.inc" %include "bibl\incl\dosbios\nasm\do_nasma.inc" %define rozmiar 3 .stack 400h section .text ; FASM (stary format biblioteki - OMF): ; format coff ; include "bibl\incl\dosbios\fasm\std_bibl.inc" ; use16 ; rozmiar = 3 ; public start ; public _start ; FASM (nowy format biblioteki - COFF): ; format coff ; include "bibl\incl\dosbios\fasm32\std_bibl.inc" ; rozmiar = 3 ; public start ; public _start start: _start: ..start: ; wyłączyć dwie poniższe linie w przypadku FASMa z nowym formatem ; biblioteki (32-bitowy COFF nie pozwala na manipulację segmentami) mov ax, cs mov ds, ax ; DS musi być = CS, bo inaczej zapisywalibyśmy ; nie tam, gdzie trzeba, a macierz jest w ; segmencie kodu. pisz db "Prosze podac 9 elementow macierzy," db cr,lf," a ja znajde najwiekszy i najmniejszy.",0 xor edx, edx ; ECX = 0 mov ebx, macierz petla_wczyt: pisz db cr, lf, "Prosze podac element nr ", 0 mov eax, edx add eax, 1 pisz32e ; wypisz numer elementu mov ax, (0eh << 8) | ":" ; wypisz dwukropek ; FASM: ; mov ax, (0eh shl 8) or ":" int 10h mov al, spc ; wypisz spację int 10h we32e ; wczytaj element jc blad mov [ebx+4*edx], eax ; umieść w macierzy add edx, 1 ; zwiększ licznik elementów ; i równocześnie pozycję w macierzy cmp edx, rozmiar*rozmiar jb petla_wczyt jmp wczyt_gotowe blad: pisz db cr, lf, "Zla liczba!",0 wyjscie 1 wczyt_gotowe: ; EBP = max, EDI = min mov ebp, [ebx] mov edi, [ebx] ; pierwszy element mov edx, 1 mov eax, 1 mov esi, rozmiar*rozmiar znajdz_max_min: mov ecx, [ ebx + 4*edx ] cmp ebp, ecx ; EBP < macierz[edx] ? cmovb ebp, ecx ; jeśli tak, to EBP = macierz[edx] cmp edi, ecx ; EDI > macierz[edx] ? cmova edi, ecx ; jeśli tak, to EDI = macierz[edx] add edx, eax cmp edx, esi jb znajdz_max_min pisz db cr, lf, "Najwiekszy element: ",0 mov eax, ebp pisz32e pisz db cr, lf, "Najmniejszy element: ",0 mov eax, edi pisz32e wyjscie 0 macierz: times rozmiar*rozmiar dd 0
Przypatrzmy się teraz miejscom, gdzie można zwątpić w swoje umiejętności:
mov ax, (0eh << 8) | ":"
Znaki <<
odpowiadają instrukcji SHL, a znak |
odpowiada instrukcji OR. Mamy więc: 0eh shl 8,
czyli 0e00h. Robimy OR z dwukropkiem (3ah) i mamy AX=0e3ah. Uruchamiając przerwanie 10h,
na ekranie otrzymujemy dwukropek.
mov [ebx+4*edx], eax
EBX = adres macierzy. EDX = 0, 1, 2, ..., rozmiar*rozmiar=9. Elementy macierzy mają rozmiar po 4 bajty każdy, stąd EDX mnożymy przez 4. Innymi słowy, pierwszy EAX idzie do [ebx+4*0]=[ebx], drugi do [ebx+4] (na 2 miejsce macierzy), trzeci do [ebx+8] itd.
mov ecx, [ ebx + 4*edx ] cmp ebp, ecx ; EBP < macierz[edx] ? cmovb ebp, ecx ; jeśli tak, to EBP = macierz[edx] cmp edi, ecx ; EDI > macierz[edx] ? cmova edi, ecx ; jeśli tak, to EDI = macierz[edx] add edx, eax cmp edx, esi jb znajdz_max_min
Najpierw, do ECX idzie aktualny element. Potem porównujemy EBX z tym elementem i, gdy EBP < ECX,
kopiujemy ECX do EBP. Do tego właśnie służy instrukcja CMOVB
(Conditional MOVe if Below).
Instrukcje z rodziny (F)CMOV umożliwiają pozbywanie się skoków warunkowych,
które obniżają wydajność kodu.
Podobnie, porównujemy EDI=min z ECX.
Potem zwiększamy EDX o 1 i sprawdzamy, czy nie przeszliśmy przez każdy element macierzy.
Powyższy program trudno nazwać intensywnym obliczeniowo
, bo ograniczyłem rozmiar macierzy do
3x3. Ale to był tylko przykład. Prawdziwe programy mogą operować na macierzach zawierających
miliony elementów. Podobny program napisany w HLLu jak C czy Pascal po prostu zaliczyłby się na
śmierć.
Teraz pokażę program, który ewoluował od nieoptymalnej formy (zawierającej na przykład więcej skoków warunkowych w głównej pętli oraz inne nieoptymalne instrukcje) do czegoś takiego:
; L_mag.asm ; ; Program wyszukuje liczby, które są sumą swoich dzielników ; ; Autor: Bogdan D. ; kontakt: bogdandr (at) op (dot) pl ; ; nasm -O999 -o l_mag.com -f bin l_mag.asm ; fasm l_mag.asm l_mag.com org 100h start: mov ax,cs mov ebx,1 ; liczba początkowa mov ebp,1 mov ds,ax align 16 start2: mov esi,ebx ; ESI = liczba mov ecx,ebp ; EBP = 1 shr esi,1 ; zachowanie połowy liczby xor edi,edi ; suma dzielników=0 align 16 petla: xor edx,edx ; dla dzielenia nop cmp ecx,esi ; czy ECX (dzielnik)>liczba/2? mov eax,ebx ; przywrócenie liczby do dzielenia nop ja dalej2 ; Jeśli ECX > ESI, to koniec ; dzielenia tej liczby nop div ecx ; EAX = EDX:EAX / ECX, EDX=reszta nop nop add ecx,ebp ; zwiększamy dzielnik o 1 nop test edx,edx ; czy ECX jest dzielnikiem? ; (czy EDX=reszta=0?) nop nop jnz petla ; nie? Dzielimy przez następną liczbę ; tak? lea edi,[edi+ecx-1] ; dodajemy dzielnik do sumy, nie ; sprawdzamy na przepełnienie. ; ECX-1 bo dodaliśmy EBP=1 do ; ECX po DIV. jmp short petla ; dzielimy przez kolejną liczbę ud2 align 16 dalej2: cmp ebx,edi ; czy to ta liczba? ; (czy liczba=suma dzielników) mov ah,9 mov edx,jest jne nie ; nie int 21h ; tak - napis "znaleziono " mov eax,ebx call pl ; wypisujemy liczbę align 16 nie: mov ah,1 int 16h nop jnz klaw cmp ebx,0ffffffffh ; czy już koniec zakresu? nop je koniec ; tak add ebx,ebp ; nie, zwiększamy liczbę badaną o ; jeden i od początku nop jmp short start2 ud2 align 16 klaw: xor ah,ah int 16h koniec: mov ah,9 mov edx,meta nop int 21h ; napis "koniec " mov eax,ebx call pl ; wypisujemy ostatnią sprawdzoną liczbę spr: ; czekamy na klawisz mov ah,1 nop int 16h jz spr xor ah,ah int 16h mov ax,4c00h int 21h ud2 align 16 pc: ; wypisuje cyfrę w AL mov ah,0eh push ebp or al,30h int 10h pop ebp ret ud2 align 16 pl: ; wypisuje liczbę dziesięciocyfrową w EAX mov ecx,1000000000 xor edx,edx div ecx call pc mov eax,edx mov ecx,100000000 xor edx,edx div ecx call pc mov eax,edx mov ecx,10000000 xor edx,edx div ecx call pc mov eax,edx mov ecx,1000000 xor edx,edx div ecx call pc mov eax,edx mov ecx,100000 xor edx,edx div ecx call pc mov eax,edx mov ecx,10000 xor edx,edx div ecx call pc mov eax,edx xor edx,edx mov ecx,1000 div ecx call pc mov eax,edx mov cl,100 div cl mov ch,ah call pc mov al,ch xor ah,ah mov cl,10 div cl mov ch,ah call pc mov al,ch call pc ret ud2 align 4 jest db 10,13,"Znaleziono: $" meta db 10,13,"Koniec. ostatnia liczba: $"
Dziel EBX przez kolejne przypuszczalne dzielniki. Jeśli trafisz na prawdziwy dzielnik
(reszta=EDX=0), to dodaj go do sumy, która jest w EDI.
Unikałem ustawiania obok siebie takich instrukcji, które zależą od siebie, jak na przykład
CMP / JA czy DIV / ADD
NOPów?
Nie. Zamiast czekać na wynik poprzednich instrukcji, procesor zajmuje się... robieniem niczego. Ale jednak się zajmuje. Współczesne procesory potrafią wykonywać wiele niezależnych instrukcji praktycznie równolegle. Więc w czasie, jak procesor czeka na wykonanie poprzednich instrukcji, może równolegle wykonywać NOPy. Zwiększa to przepustowość, utrzymuje układy dekodujące w ciągłej pracy, kolejka instrukcji oczekujących na wykonanie nie jest pusta.
lea edi,[edi+ecx-1] ?
LEA - Load Effective Address. Do rejestru EDI załaduj ADRES (elementu, którego) ADRES wynosi EDI+ECX-1. Czyli, w paskalowej składni: EDI := EDI+ECX-1. Do EDI dodajemy znaleziony dzielnik. Musimy odjąć 1, bo wcześniej (po dzieleniu) zwiększyliśmy ECX o 1.
UD2 i czemu jest umieszczona po instrukcjach JMP ?
Ta instrukcja (UnDefined opcode 2) wywołuje wyjątek wykonania nieprawidłowej
instrukcji przez procesor. Umieściłem ją w takich miejscach, żeby nigdy nie była
wykonana.
Po co ona w ogóle jest w tym programie w takich miejscach?
Ma ona interesującą właściwość: powstrzymuje jednostki dekodujące instrukcje od dalszej
pracy. Po co dekodować instrukcje, które i tak nie będą wykonane (bo były po skoku
bezwarunkowym) ? Strata czasu.
align 16 ?
Te dyrektywy są tylko przed etykietami, które są celem skoku. Ustawianie kodu od adresu, który dzieli się przez 16 może ułatwić procesorowi umieszczenie go w całej jednej linii pamięci podręcznej (cache). Mniej instrukcji musi być pobieranych z pamięci (bo te, które są najczęściej wykonywane już są w cache), więc szybkość dekodowania wzrasta. Układania kodu i danych zwiększa ogólną wydajność programu
O tych wszystkich sztuczkach, które tu zastosowałem, można przeczytać w podręcznikach dotyczących
optymalizacji programów, wydanych zarówno przez Intel, jak i AMD (u AMD są też wymienione
sztuczki, których można użyć do optymalizacji programów napisanych w języku C).
Podaję adresy (te same co zwykle):
AMD,
Intel.
Życzę ciekawej lektury i miłej zabawy.