Asembler w Linuksie - optymalizowanie kodu
Asembler jest językiem łączącym ogromne możliwości programistyczne z małą wygodą użycia. Wielu programistów unika go ze względu na nieprzenośność, nieczytelność oraz inne wady programowania niskopoziomowego. Prędzej czy później jednak, tworząc profesjonalne oprogramowanie wymagające maksymalnej wydajności można go odkryć jako idealne narzędzie do optymalizacji krytycznych, ze względu na koszt czasowy, fragmentów programu. Asembler wykorzystywany jest w nietypowych operacjach graficznych, których nie udostępniają nam najbardziej wyszukane biblioteki, przy transferze i przetwarzaniu bardzo dużych ilości danych, ale także w innych operacjach, które są wykonywane na tyle często, by stanowić istotny koszt czasowy.
Jak
Asembler w Linuksie jest na tyle mało popularny, że warto wspomnieć o jego szczególnych cechach, różniących go od innych, typowych asemblerów. W przeciwieństwie do dominującej konwencji opracowanej przez firmę Intel, w Linuksie mamy przeważnie do czynienia z alternatywną konwencją, według mnie, nieco mniej wygodną. Oto główne cechy składni, wykorzystywanej między innymi w inline asemblerze w GCC, które na pewno będą sprawiać z początku kłopoty osobom przyzwyczajonym do Asemblera w DOS / Windows :
· do mnemoniku instrukcji dołączamy przyrostek oznaczający rozmiar danych, np.
"movb" - kopiuj bajt
"movw" - kopiuj słowo (2 bajty)
"movl" - kopiuj długie słowo (4 bajty)
· nazwy rejestrów procesora poprzedamy przedrostkiem "%%", np. "%%ebx".
· obowiązuje porządek <rozkaz> <źródło>,<przeznaczenie>
· instrukcja "addw %%ax, %%cx" oznacza polecenie cx += ax.
· stałe poprzedzamy symbolem "$", np. "cmpb $5, %%bl".
· przy skokach wstecz do etykiet dodajemy przyrostek "b",
przy skokach naprzód przyrostek "f", np. "jne 5f".
(przykładowy skok warunkowy do etykiety oznaczonej przez "5" był wykonywany naprzód )
· wskaźniki zapisujemy w nawiasach okrągłych : "movl (%%edi), %%eax".
· indeksy zapisujemy przed bazą : "movl 5(%%edi), %%eax".
[Od redakcji: z kolei osoby mające doświadczenie w programowaniu procesorów Motoroli, oraz ci, którzy przyzwyczaili się już do programowania w środowisku DJGPP, będą czuć się jak ryby w wodzie. Dla tych, którym składnia AT&T sprawia kłopoty, stworzono proste programy dokonujące konwersji między oboma standardami]
Gdzie
Optymalizacje, które chciałbym opisać dotyczą przede wszystkim osób posiadających maszyny z procesorami serii Pentium, lub kompatybilnymi, myślę jednak, że obecnie procesory te są już od dłuższego czasu standardem. Jedną ze specyficznych możliwości Pentium jest wbudowany licznik cykli procesora, zliczający je od momentu rozpoczęcia pracy komputera, z prędkością odpowiadającą prędkości taktowania zegara w naszym procesorze. Pentium udostępnia nieudokumentowany (dlaczego ?) rozkaz "rdtsc" o kodzie [0F-31] wczytujący 64-bitową zawartość licznika do pary EDX:EAX. Skupiłem się na tym ze względu na użyteczność wspomnianego licznika przy optymalizacji, bowiem za jego pomocą możemy mierzyć prędkość napisanych przez nas fragmentów kodu.
Programując Pentium powinniśmy również poznać zastosowaną w nim architekturę dwukanałowej obsługi rozkazów. Teoria jest taka : jeżeli dwa następujące po sobie w kolejce rozkazów polecenia spełniają pewne specjalne warunki, to wykonywane są one jednocześnie. W ten sposób, z punktu widzenia programisty koszt wykonania drugiego rozkazu jest zerowy. Mówimy, że rozkazy te łączą się w parę lub "skalują się". Na listingu 2 przedstawione są podstawowe zasady łączenia instrukcji :rozkazy dające się skalować to:
· adc, add, and, cmp, dec, inc, lea,
· mov, nop, or, sbb, sub, test, xor.
· a także operacje kładzenia i zdejmowania rejestrów ze stosu, wszystkie bliskie skoki ( w tym "call" ) i w większości przypadków obroty i przesunięcia bitowe.
* NIE skalują się instrukcje o argumentach <stała>,<pamięć> gdzie pamięć jest adresem zawierającym indeks, np. "movl $4, 5(%%edi)"
* zalezność odczyt-po-zapisie uniemożliwia skalowanie, tzn. druga instrukcja nie może czytać z rejestru do którego pisała poprzednia. Ta zasada jest dosyć logiczna i oczywista. Wyjątkami od niej są tylko rejestr znaczników i rejestr stosu. Przykładowo :
"movl %%eax,%%ebx
movl %%ebx,%%ecx" nie łączą się (odczyt ebx po zapisie), ale
"pushl %%eax
pushl %%ebx" łączą się mimo, że obie czytają i piszą do rejestru
stosu.
"cmpl %%ebx,%%ebx
ja 2b" łączą się mimo, że czytamy rejestr znaczników po
zapisie.
Możliwości skalowania rozkazów nie sposób przecenić. Podobny fragment kodu napisany tak, by Pentium mógł połączyć instrukcje w pary może mieć dwukrotnie niższy koszt czasowy. Dobrze jest także wiedzieć, że na procesorze Pentium zwykle nie opłaca się używać złożonych rozkazów np.:
"lodsl" - trwa 2 cykle, zaś
"movl (%%esi), %%eax
addl $4, %%esi" - wykonują się równolegle i trwają 1 cykl
Tworzenie funkcji w Asemblerze
Dalej skupię się na wspomnianym asemblerze wbudowanym w (inline assembler) GCC, który mimo wszystko będzie chyba najwygodniejszym sposobem używania asemblera w połączeniu z kodem w C. Zasada tworzenia funkcji Asemblerowych w C jest niezbyt oczywista i początkowo dosyć uciążliwa.
Najłatwiej zilustrować ją na przykładzie :
int asm_sum(int arg1, int arg2, int arg3)
{
register int wynik;
__asm__("addl %%ebx,%%eax\n"
"addl %%ecx,%%eax"
: "=a" (wynik)
: "a" (arg1), "b" (arg2), "c" (arg3)
: "ax","bx","cx");
return wynik;
}
Deklaracja asm ma postać __asm__(code : output : input : changes): "code" jest to łańcuch (string) zawierający kod, czyli listę rozkazów, zaś "input" to lista danych wejściowych. W tym przykładzie argumenty arg1, arg2 i arg3 są wczytywane odpowiednio do rejestrów eax, ebx i ecx symbolizowanych przez "a", "b" i "c". (Pozostałe oznaczenia: "d" - edx, "S" - esi, "D" - edi, "B" - ebp) "output" to lista danych wyjściowych. W naszym wypadku wynik otrzymany w rejestrze eax ma zostać zapisany do zmiennej "wynik", której wartość zwraca funkcja.
Linijka "=a" (wynik) oznacza "wynik = eax", zaś "changes" to opcjonalne pole będące informacją dla kompilatora o zmianach jakie mogły zajść w wyniku działania funkcji. W tym wypadku informujemy, że ulegają zmianie rejestry ax, bx i cx. Kompilator będzie wiedział, że musi zachować ich stare wartości, jeżeli mają one znaczenie dla programu. W tym polu może zostać na przykład umieszczone słowo "memory". Jeżeli tak zrobimy, będzie to informacja, że kompilator nie powinien wprowadzać optymalizacji polegającej na trzymaniu zmiennych w rejestrach, bo zawartość pamięci może ulec zmianie i zrobi się bałagan.
W dalszych przykładach pole "output" nie będzie wykorzystywane. Ma to miejsce wtedy gdy funkcja ma jedynie wykonać określone zadanie i nie ma danych wyjściowych.
Optymalizacja kodu
Zanim przystąpimy do pisania własnych "ulepszonych" funkcji, które z pewnością osiągną wielokrotnie lepszą wydajność od standartowych :), powinniśmy stworzyć sobie proste narzędzie do pomiaru czasu, aby móc badać, która wersja naszej nowej funkcji jest najszybsza.
Odpowiedni kod może wyglądać następująco :
void get_cpu_time(int *clock)
{
__asm__("rdtsc\n"
"movl %%eax,(%%edi)"
: /* nie ma danych wyjsciowych */
: "D" (clock)
: "ax","dx","di");
}
Treść tej funkcji, po przypomnieniu sobie jak działa rozkaz "rdtsc", powinna być zupełnie jasna: get_cpu_clock(int*) wczytuje wskazanie licznika cykli do zadanej zmiennej. Jeżeli wczytamy jego zawartość bezpośrednio przed i po wykonaniu badanego przez nas kodu, a następnie weźmiemy różnicę tych wskazań, to otrzymamy czas trwania tego kodu. Wygląda to ładnie. Jest jednak jeszcze jedna rzecz, o której warto wspomnieć. Wywołanie get_cpu_time też trwa trochę czasu (choć niewiele), dlatego by zachować dokładność musimy przedtem obliczyć ten błąd przez porównanie wyników dwóch get_cpu_time wywołanych jeden po drugim.
I jeszcze jedno: każdą operację, w której liczymy czas wykonania, powinniśmy wykonać wielokrotnie i brać średni czas. Wynika to z niedokładności pomiaru. Na Pentium prędkość kodu zależy od wielu "czynników zewnętrznych" takich jak wykorzystanie pamięci podręcznej, skuteczne przewidywanie rozgałęzien itp. Ponadto, jak wiemy, Linux jest systemem, w którym w tle wykonuje się równolegle wiele procesów, co w ten czy inny sposób może wpłynąć na wynik.
Jeżeli zsumujemy np. 10000 czasów wykonań danej funkcji i wyciągniemy z tego średnią, to powinniśmy otrzymać w miarę wiarygodne wyniki. W szczególności nie musimy się martwić zaburzeniami jeżeli interesuje nas samo porównywanie, który kod jest szybszy.
Prosty przykład
Rozważmy taką funkcję :
void strcpy1(char *dest, char *source)
{
while (source) { dest++ = source++ }
}
Funkcja ta kopiuje łańcuch (string) z "source" do "dest". Oto schemat programu, który oblicza czas jej wykonywania:
...
#define DlugoscDanych 10000;
#define IloscTestow 10000;
char source [DlugoscDanych];
char dest [DlugoscDanych];
...
for (int i = 0; i < DlugoscDanych; source[i++] = 1) // wypelnienie source
source[DlugoscDanych - 1] = 0; // symbol konca lancucha
while (;;)
{
for (int i = 0; i < IloscTestow; i++)
{
get_cpu_time(start);
/* kod pusty */
get_cpu_time(stop);
error += (stop - start); // w zmiennej "error" dostaniemy sredni
} // czas trwania funkcji get_cpu_time
// pomnozony przez IloscTestow (np.
10000)
for (int i = 0; i < IloscTestow; i++)
{
get_cpu_time(start);
strcpy1(dest,source);
get_cpu_time(stop); // analogicznie otrzymamy koszt strcpy1
time += (stop - start); // (ale bedzie trzeba odjac error)
}
[ wyczysc ekran ]
[ wypisz ((time - error) / IloscTestow) ]
}
Zapiszmy wynik i spróbujmy napisać tę samą funkcję w asemblerze:
void strcpy2(char *dest, char *source)
{
__asm__("cld\n"
"1:\n"
"lodsb\n"
"stosb\n"
"testb %%al,%%al\n"
"jne 1b\n"
: /* nie ma danych wyjsciowych */
"S" (src),"D" (dest)
"ax","si","di");
}
Teraz wstawiamy do naszego programu testującego "strcpy2" zamiast "strcpy1" i porównujemy efekty. Możemy także sprawdzić jaki koszt da standardowa funkcja "strcpy".
A oto zoptymalizowana postać funkcji:
void strcpy3(char *dest, char *source)
{
__asm__("1:\n"
"movw (%%esi),%%ax\n"
"addl $2,%%esi\n"
"cmp $0,%%al\n"
"jz 3f\n"
"cmp $0,%%ah\n"
"jz 2f\n"
"movw %%ax,(%%edi)\n"
"addl $2,%%edi\n"
"jmp 1b\n"
"2:\n"
"movb %%ah,1(%%edi)\n"
"3:\n"
"movb %%al,(%%edi)\n"
: /* nie ma danych wyjsciowych */
: "S" (src),"D" (dest),
: "ax","si","di");
}
Ta funkcja kopiuje po dwa znaki na raz. Następnym krokiem byłby transfer po cztery bajty na iterację. Jeżeli Czytelnik będzie chciał napisać własną wersję takiej funkcji, to doradzam także sprawdzenie, czy faktycznie
poprawnie kopiuje ona łańcuchy! Jeżeli ta optymalizacja jest dla niego jasna, to powinien również dać sobie radę z takimi funkcjami jak "strcmp" czy "strlen".
Są to jednak tylko przykłady prostych funkcji, które z resztą rzadko stanowią poważny koszt czasowy w stosunku do reszty programu. Na ogół mamy do czynienia ze specyficznymi dla konkretnego programu funkcjami i to one stanowią największe pole do popisu dla naszego sprytu i umiejętności kombinowania.
Inny przykład
Wyobraźmy sobie, że chcemy zdefiniować w C++ specjalny typ 64-bitowej, lub innej, dużej liczby całkowitej. 64-bitową liczbę możemy przedstawiać jako złożenie dwóch liczb: "int" i "unsigned int". Konieczne będzie zdefiniowanie operatorów, takich jak "+", "-", "*" itp. Jeżeli będziemy używać zmiennych tego nowego typu do długich, żmudnych obliczeń, to koniecznością jest, by operatory były naprawdę zoptymalizowane. Pisanie ich w czystym C wydaje się dosyć karkołomne i niezbyt efektywne. Poniżej fragment proponowanego przeze mnie rozwiązania:
class huge
{
int hi; /* Starsze 32 bity liczby huge */
unsigned int lo; /* Mlodsze 32 bity */
public:
huge() { } /* Trzy konstruktory liczb huge
*/
huge(int l) { if (l < 0) hi = -1; else
hi = 0;
lo = (unsigned)l; }
huge(int h,unsigned int l) { hi = h; lo = l; }
friend huge operator+ (huge , huge);
[ inne deklaracje ]
};
inline huge operator+(huge h1, huge h2)
{
huge wynik;
__asm__("addl %%ebx,%%eax\n" /* W przypadku przepełnienia ustawia CARRY
*/
"adcl %%edx,%%ecx" /* Dodaje z uwzględnieniem CARRY */
: "=a" (wynik.lo), "=c" (wynik.hi)
: "a"(h1.lo), "b"(h2.lo), "c"(h1.hi), "d"(h2.hi)
: "ax", "bx", "cx", "dx");
return wynik;
}
[ inne operatory ]
...
Jak widać implementacja operatora "+" w asemblerze jest trywialna. Mnożenie sprawi niewiele więcej kłopotów, za to dzielenie jest prawdziwym wyzwaniem. Zachęcam do zastanowienia się nad tym problemem.
Podsumowanie
Jak widzimy, istnieją sytuacje, w których zastosowanie wstawki Asemblerowej nie tylko przyśpiesza kod, ale i ułatwia jego implementację (tak było np. przy dodawaniu liczb 64b). Istnieją wszakże sytuacje, w których w ogóle trudno obejść się bez asemblera. A oto przykład dla osób, które interesują się grafiką: wyobraźmy sobie, że zainicjalizowaliśmy paletę RGB składającą się z bloków po osiem odcieni danego koloru. Oznacza to, że trzy ostatnie bity odpowiadają za jasność, a pozostałe za barwę. Potrzebujemy procedury która "rzuca" na ekran koło światła, tzn. wszystkie punkty tego koła są rozjaśniane, co osiągniemy przez ustawienie trzech ostatnich bitów każdego punktu.
W asemblerze sprawa jest prosta: jeżeli umiemy napisać procedurę rysującą zwykłe koło o danym kolorze, to wystarczy w tej procedurze zamienić
mov "pixel", "kolor"
na
or "pixel", 7.
A jak by to wyglądało w czystym C ?