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 -O999 -f elf ciag_ar.asm ; ld -s -o ciag_ar ciag_ar.o bibl/lib/libasmio.a ; ; fasm ciag_ar.asm ciag_ar.o ; ld -s -o ciag_ar ciag_ar.o bibl/lib/libasmio.a ; FASM: ; format ELF ; include "bibl/incl/linuxbsd/fasm/std_bibl.inc" ; section ".text" executable ; public _start ; NASM %include "bibl/incl/linuxbsd/nasm/std_bibl.inc" section .text global _start _start: pisz db "Program liczy sume liczb od 1 do podanej liczby.",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 lf, "Zla liczba!",lf,0 wyjscie 1 ; mov ebx, 1 / mov eax, 1 / int 80h 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 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 lf, "Wynik ze wzoru: n(n+1)/2= ",0 pisz64 ; wypisuje na ekranie 64-bitową liczbę całkowitą ; z EDX:EAX nwln wyjscie 0
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.
Makro wyjscie
zawiera 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, 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 -f elf macierze.asm ; ld -s -o macierze macierze.o -Lbibl/lib -lasmio ; ; fasm macierze.asm macierze.o ; ld -s -o macierze macierze.o -Lbibl/lib -lasmio ; FASM: ; format ELF ; include "bibl/incl/linuxbsd/fasm/std_bibl.inc" ; section ".text" executable ; public _start ; rozmiar = 3 ; NASM %include "bibl/incl/linuxbsd/nasm/std_bibl.inc" %define rozmiar 3 section .text global _start _start: pisz db "Prosze podac wszystkie 9 elementow macierzy," db lf, "a ja znajde najwiekszy i najmniejszy.",lf,0 xor edx, edx ; ECX = 0 mov ebx, macierz petla_wczyt: pisz db "Prosze podac element numer ",0 mov eax, edx add eax, 1 pisz32e ; wypisz numer elementu push ebx push edx mov eax, 4 mov ebx, 1 mov ecx, dwukspc mov edx, 2 int 80h ; wypisz dwukropek i spację pop edx pop ebx 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 lf, "Zla liczba!",lf,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 lf, "Najwiekszy element: ",0 mov eax, ebp pisz32e pisz db lf, "Najmniejszy element: ",0 mov eax, edi pisz32e nwln wyjscie 0 ; FASM: section ".data" writeable section .data macierz times rozmiar*rozmiar dd 0 dwukspc db ": "
Przypatrzmy się teraz miejscom, gdzie można zwątpić w swoje umiejętności:
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/tablicach
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 -f elf l_mag.asm
; ld -s -o l_mag l_mag.o
;
; fasm l_mag.asm l_mag
; FASM:
; format ELF executable
; entry _start
; segment readable executable
; lf = 10
; NASM
%define lf 10 ; znak przejścia do nowej linii (Line Feed)
section .text
global _start
_start:
mov ebx,1 ; liczba początkowa
mov ebp,1
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?)
jne nie ; nie
push ebx
mov eax, 4
mov ebx, 1
mov ecx, jest
mov edx, jest_dlugosc
int 80h ; tak - napis "znaleziono"
pop ebx
mov eax,ebx
call pl ; wypisujemy liczbę
align 16
nie:
cmp ebx,0ffffffffh ; czy już koniec zakresu?
nop
je koniec ; tak
add ebx,ebp ; nie, zwiększamy liczbę badaną o 1
nop
jmp start2 ; i idziemy od początku
ud2
align 16
koniec:
push ebx
mov eax, 4
mov ebx, 1
mov ecx, meta
mov edx, meta_dlugosc
int 80h
pop eax
call pl ; wypisujemy ostatnią sprawdzoną liczbę
mov eax, 4
mov ebx, 1
mov ecx, nwln
mov edx, 1
int 80h ; wypisz znak nowej linii
mov eax, 1
xor ebx, ebx
int 80h
ud2
align 16
pc: ; wypisuje cyfrę w AL
push eax
or al, "0"
mov [cyfra], al
push ebx
push ecx
push edx
mov eax, 4
mov ebx, 1
mov ecx, cyfra
mov edx, 1
int 80h
pop edx
pop ecx
pop ebx
pop eax
ret
ud2
align 16
pl: ; wyświetla 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
; FASM: segment readable writeable
section .data align=4
jest db lf,"Znaleziono: "
jest_dlugosc equ $-jest ; FASM: "=" zamiast "equ"
meta db lf,"Koniec. ostatnia liczba: "
meta_dlugosc equ $-meta ; FASM: "=" zamiast "equ"
cyfra db 0
nwln db lf
A oto analiza:
Dziel EBX przez kolejne przypuszczalne dzielniki. Jeśli trafisz na prawdziwy dzielnik
(reszta=EDX=0), to dodaj go do sumy=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.