Optymalizacja kodu programu w języku C
Optymalizacja kodu jest procesem, którego celem jest zmiana kodu przy zachowaniu obliczanej funkcji, tak aby przyspieszyć działanie docelowego programu i/lub zmniejszyć jego wielkość. Zwróćmy uwagę, że optymalizacja jest raczej poprawianiem gotowego programu, ponieważ otrzymany kod rzadko jest optymalny. Należy pamiętać, że w optymalizacji powinno uwzględniać się wiele ogólnych warunków. Najważniejszy jest czas działania docelowego programu. Złożony program może pewne fragmenty wykonywać częściej - te powinny być lepiej zoptymalizowane. Zawsze należy szukać rozsądnego kompromisu pomiędzy potrzebą optymalizacji a jej kosztem. Czasami, mimo wszystko, nie warto tworzyć doskonale zoptymalizowanego kodu. To się po prostu nie opłaci.
Propagacja kopii
Instrukcja X = Y jest instrukcją kopiowania. Naturalne jest zastąpienie wystąpień zmiennej X przez Y.
Przykład:
x = y
a = x + y
b = a + x
Zastępujemy przez:
x = y
a = y + y
b = a + y
Po wykonaniu propagacji kopii, instrukcja kopiująca jest martwym kodem. Ostatecznie otrzymamy:
a = y + y
b = a + y
Eliminacja wspólnych podwyrażeń
Wyrażenie E w postaci X op Y jest nazywane wspólnym podwyrażeniem, jeśli występuje ono w kilku miejscach, oraz jeśli wartości zmiennych X i Y użytych w kolejnych wystąpieniach E nie zmieniły się po poprzednim obliczeniu E. W takiej sytuacji można zastąpić kolejne wystąpienia E przez wartość wyliczoną za pierwszym razem.
Przykład:
a = 4 * i
b = 4 * i
c = a + b
Drugie wyliczenie 4 * i można zastąpić przez b. Przekształcony blok:
a = 4 * i
b = a
c = a + b
Eliminację wspólnych podwyrażeń można stosować lokalnie - gdy przeszukujemy jeden blok bazowy, globalnie - dla całego grafu przepływu (trudniejsze z powodu pętli).
Usuwanie martwego kodu
Zmienną nazywamy żywą w danym miejscu programu, jeżeli jej wartość może zostać użyta. Inaczej nazywamy ją w tym miejscu zmienną martwą. Analogicznie definiujemy kod martwy, tj. obliczający wartości bezużyteczne. Na przykład wyliczenie wartości dla zmiennej martwej lub instrukcja postaci
if (false) ... to kod martwy. Oczywiście kod martwy usuwamy.
Zwijanie stałych
Jest to proces upraszczania wyrażeń stałych. Przykład:
x = 30 * 2
można zastąpić przez
x = 60
Zwijanie stałych czasem wykonuje się na wcześniejszych etapach kompilacji.
Propagacja stałych
Jest to proces zastępowania wystąpień stałych przez ich wartości. Przykład
x = 60
y = 3 * x
można zastąpić przez
x = 60
y = 3 * 60
i dalej po zwinięciu wartości w drugim przypisaniu otrzymamy
x = 60
y = 180
W wyniku propagacji stałych instrukcja definiująca stałą staje się martwym kodem, który można usunąć w trakcie eliminacji martwego kodu.
Optymalizacja pętli przez przemieszczanie kodu
Polega na zmniejszeniu ilości kodu w pętli, przez przemieszczenie obliczeń niezmienniczych przed pętle.
Prosty przykład:
i = 0
do {
a = 13
i = i + 1
} while (i < 15)
Wyrażeniem niezmienniczym jest instrukcja przypisania w trzeciej linii. Możemy (a wręcz należy) przemieścić ją przed pętlę.
Wyszukanie zmiennych indukcyjnych
Identyfikacja zmiennych, które zmieniają się w regularny sposób w pętli ułatwia optymalizację pętli. Zmienne o takiej własności nazywany indukcyjnymi. W połączeniu z redukcją mocy (czyli zastępowaniem drogich obliczeń przez tańsze), można w najlepszym przypadku zostawić tylko jedną zmienną indukcyjną. Zmienne indukcyjne w poniższym przykładzie to i, j:
i = 0
do {
j = 4 * i
i = i + 1
} while (i < 20)
Odrębne zagadnienie stanowi sposób identyfikacji zmiennych indukcyjnych, którym tu nie będziemy się zajmować. Po przekształceniu kodu może mieć postać:
i = 0
do {
j = i + i + i + i;
i = i + 1;
} while (i < 20)
Do redukcji mocy działań (zwłaszcza w przypadku mikrokontrolerów) doskonale nadają się operacje przesunięć bitowych. Przypomnijmy, że przesunięcie w prawo o 1 bit odpowiada dzieleniu liczby przez 2, natomiast w lewo – dzieleniu przez 2. W poniższym przykładzie mnożenie przez 10 sprowadzono do kilku prostych operacji arytmetycznych.
a = 10 * a
Można zastąpić przez:
b = a >> 2;
a= a >> 3;
a = a + b;
Redukcja mocy w pętlach
W wypadku, gdy do wyliczania używamy mnożenia, można zastosować inne podejście. Najpierw klasyfikujemy zmienne na kilka rodzajów:
- Zmienna indukcyjna podstawowa - jej definicja występuje dokładnie raz w pętli i jest postaci i = i + C, gdzie C jest niezmiennicze w pętli.
- Zmienna indukcyjna wspólna - jej definicja występuje dokładnie raz w pętli i jej wartość jest funkcją liniową pewnej zmiennej indukcyjnej; czyli i = A op j + B, gdzie A oraz B są niezmiennicze w pętli, op jest operatorem mnożenia lub dzielenia, a j jest zmienną indukcyjną.
Redukcja mocy. Stwórz nową zmienną k. Dodaj przed pętlą k = A * j + B. Za instrukcją j = j + C dodaj k = k + B * C. Zastąp definicję i przez i = k.
Odniesione korzyści to mniejsza liczba operacji mnożenia oraz wyniesione przed pętle obliczenia na wartościach niezmienniczych A, B oraz C.
W analogiczny sposób można redukować moc dla sytuacji, w których zmienna indukcyjna jest wykorzystywana do przypisania z mnożeniem, tzn. w pętli jest instrukcja k = j * A, gdzie A jest niezmiennicze, a j jest zmienną indukcyjną podstawową, której inkrementacja w pętli jest postaci j = j + C. W tej sytuacji zastępujemy przypisanie na k instrukcją k = k + C * A oraz dodajemy przed pętlą odpowiednią inicjalizację wartości k.
Dodaj nowy komentarz