Dziś kolejny wpis o wydajności C#. Od razu chcę podkreślić, że należy traktować post jako ciekawostkę, która w zdecydowanej większości nie ma znaczenia. Stosując podane wskazówki można nieco przyśpieszyć algorytm, ale DUŻO lepsze efekty można uzyskać np. unikając błędnej alokacji obiektów, która ma fatalne efekty na GC.
Warto jednak znać zasady języka, w którym codziennie pisze się aplikacje. W świecie wysokopoziomowych języków, gdzie wszystko jest robione za nas, łatwo zapomnieć o rzeczach, które są oczywiste dla programistów ASM.
Co się dzieje, gdy wykonamy następującą linię kodu?
Wygenerowany kod, sprawdzi najpierw czy indeks nie przekracza dozwolonego zasięgu tzn. musi być >= 0 i < items.Length. Jeśli zasięg jest niedozwolony to zostanie wyrzucony wyjątek. Dzięki temu, nie będzie czytana wartość, która jest poza tablicą. W przypadku, gdy items ma 3 elementów a my chcielibyśmy przeczytać czwarty, bez sprawdzania uzyskalibyśmy dostęp do pamięci, przechowującej kompletnie inne informacje. Próba zapisu mogłaby skończyć się nadpisaniem jakiś innych, cennych informacji.
Oczywiście sprawdzanie warunku powoduje wygenerowanie kilku dodatkowych instrukcji. Programiści wysokopoziomowych języków nie przejmują się tym, ale gdybyśmy mieli korzystać tylko z ASM, zauważylibyśmy jak wiele niepotrzebnego kodu trzeba pisać. Problem pojawia się w przypadku pętli. Jeśli mamy kilka milionów iteracji, wtedy sprawdzanie tego samego warunku nie zawsze ma sens. JIT jest na tyle inteligentny, że często wygeneruje warunek wyłącznie przed pętlą np.:
for (int j = 0; j < data.Length; j++)
{
int item = data[j];
}
Bardzo jednak łatwo napisać kod, który w każdej iteracji będzie sprawdzał indeks. W powyższym przykładzie, JIT ominie warunek w każdej iteracji bo nie ma przecież potrzeby sprawdzania tego za każdym razem – wiadomo, że indeks zawsze będzie miał prawidłową wartość. Spójrzmy na nieco inny przypadek:
const int n = 100000000;
int[] data = new int[n];
const int tests = 10;
for (int i = 0; i < tests; i++)
{
Stopwatch stopwatch = Stopwatch.StartNew();
for (int j = 0; j < data.Length; j++)
{
int item = data[j];
}
Console.WriteLine("1: {0}", stopwatch.ElapsedMilliseconds);
}
for (int i = 0; i < tests; i++)
{
Stopwatch stopwatch = Stopwatch.StartNew();
for (int j = data.Length - 1; j >= 0; j--)
{
int item = data[j];
}
Console.WriteLine("2: {0}", stopwatch.ElapsedMilliseconds);
}
Powyższy kod wyświetli czas potrzebny na przejście pętli. Pierwsza to klasyczna pętla, która zostanie zoptymalizowana. Druga z kolei, będzie przechodzić od końca do początku. Niestety nie zostanie dokonana żadna optymalizacja w drugim przypadku:
Z tego względu, lepiej pisać pętle, które mają porządek rosnący.
A co w przypadku pętli, gdzie zamiast właściwości Length, korzystamy ze stałej?
for (int j = 0; j < n; j++)
{
int item = data[j];
}
Dla x86, warunek będzie sprawdzamy w każdej iteracji. Z kolei w przypadku x64 zostanie dokona optymalizacja.
Inny scenariusz, który nie zostanie zoptymalizowany to dostęp do statycznej tablicy:
private static []_data=new int[n];
//...
for (int j = 0; j < _data.Length; j++)
{
int item = _data[j];
}
Ma to dobre wytłumaczenie ponieważ statyczna zmienna jest globalna i mogłaby być zmodyfikowana z innego wątku.
Można bez problemu ustawić początek i koniec pętli, a mianowicie:
for (int j = 50; j < data.Length-10; j++)
{
int item = data[j];
}
JIT rozpozna taką pętle i zoptymalizuje ją. Nie trzeba zawsze zaczynać od indeksu 0. Kolejny przykład:
for (int j = 0; j < data.Length-1; j++)
{
int item = data[j+1];
}
Pętla nieco inna ale wciąż jest optymalna – zostanie warunek sprawdzony tylko raz.
Powyższe rozważania dotyczą również tablic wielowymiarowych, które m.in. z tego względu są wolniejsze i lepiej korzystać z jagged array. Nawet w podstawowych, prostych pętlach warunek nie jest eliminowany dla tablic wielowymiarowych.
Generalnie bardzo łatwo napisać pętlę, która nie zostanie zoptymalizowana ale w praktyce nie ma to wielkiego znaczenia – czysta ciekawostka.
