#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
int main()
{
srand(time(NULL));
//tworzenie tabicy statycznej (umieszczona na stosie)
int tabs[1000];
for(int i = 0; i < 1000; ++i)
{
tabs[i] = i;
}
//tworzenie tablicy dynamiczenj:
int * tabd = new int[1000];
//przypisujemy wartości tablicy
for(int *i = tabd; i < tabd + 1000; ++i)
{
*i = rand() % 1000;
}
//wypisujemy na ekran zawartość tablicy
for(int *i = tabd; i < tabd + 1000; ++i)
{
cout<<*i<<" ";
}
//zwalniamy zarezerwowany obszar
delete[] tabd;
}
C# przyzwyczaił nas do prostej konwencji w stylu:
int[] tab = new int[1000];
Proste i bez komplikowania sobie życia. Czy jednak ta tablica zostanie umieszczona na stosie i jest tak samo wydajna jak ta w C/C++? Otóż nie. W wersji C# tablica zostanie umieszczona na stercie. Co to oznacza dla nas w praktyce? Stratę wydajności. Pytanie więc brzmi: jak dużo tracimy przy takiej konwencji w porównaniu do tablic tworzonych bezpośrednio na stosie?
Jak wspominałem C# umożliwia używanie wskaźników. Postanowiłem więc sprawdzić jaka jest różnica czasu w tworzeniu i wykonywaniu operacji przy pomocy wersji takiej do jakiej przywykliśmy i tablicy stworzonej za pomocą operatora stackalloc. Jak można przczytać na MSDN: "The stackalloc keyword is used in an unsafe code context to allocate a block of memory on the stack." - a więc operator ten umożliwia zarezerwowanie pamięci na stosie w trybie unsafe.
Aby możliwe było użycie trybu unsafe, w opcjach projektu należy zaznaczyć właściwość Allow unsafe code:
Po zaznaczeniu tej właściwości możemy już kompilować kod zawierający kod niezarządzany. Aplikacja która posłuży to testu jest bardzo prosta, mamy dwie metody. Pierwsza tworzy tablica w zwykłym stylu (bez użycia stackalloc) a druga tworzy je na stosie. Następnie wykonywane są operacje na tych tablicach. Metody wywołujemy tyle razy ile użytkownik zażąda. Kod aplikacji:
private void button1_Click(object sender, EventArgs e)
{
Stopwatch clock = new Stopwatch();
clock.Start();
for (int i = 0; i < int.Parse(textBox1.Text); i++)
{
manageCode();
}
clock.Stop();
label1.Text = clock.ElapsedMilliseconds.ToString();
clock.Reset();
clock.Start();
for (int i = 0; i < int.Parse(textBox1.Text); i++)
{
unmanageCode();
}
clock.Stop();
label2.Text = clock.ElapsedMilliseconds.ToString();
}
private void manageCode()
{
int[] tab1 = new int[1500];
int[] tab2 = new int[1500];
int[] tab3 = new int[1500];
for (int k = 0; k < tab1.Length; k++)
{
tab1[k] = 10 + 10;
}
for (int k = 0; k < tab1.Length; k++)
{
tab2[k] = 10 + 10;
}
for (int k = 0; k < tab1.Length; k++)
{
for (int z = 0; z < tab1.Length; z++)
{
tab3[k] += tab1[k] + tab2[z];
}
}
}
private unsafe void unmanageCode()
{
int* tab1 = stackalloc int[1500];
int* tab2 = stackalloc int[1500];
int* tab3 = stackalloc int[1500];
for (int* k = tab1; k < (tab1 + 1500); k++)
{
*k = 10 + 10;
}
for (int* k = tab2; k < (tab2 + 1500); k++)
{
*k = 10 + 10;
}
for (int* k = tab3; k < (tab3 + 1500); k++)
{
for (int z = 0; z < 1500; z++)
{
*k += *(tab1 + z) + *(tab2 + z);
}
}
}
}
Sama formatka aplikacji jest bardzo prosta: dwa labele, textbox oraz button:
Wyniki testów dla 500 iteracji kodu zarządzanego i niezarządzanego przedstawiają się następująco:
Prawie 5 sekund różnicy. Czy to dużo czy mało? Jeżeli nasza aplikacja mocno wykorzystuje tablice i często je tworzy, warto zastanowić się nad modyfikacją ich do postaci rezerwowanej na stosie.
Przedstawione tutaj przykłady korzystają z tablic jednowymiarowych. Co w takim razie z tablicami wielowymiarowymi?
W C++ tablicę statyczną i dynamiczną wielowymiarową tworzymy w następujący sposób:
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;
int main()
{
srand(time(NULL));
//tworzenie tabicy dwuwymiarowej statycznej (umieszczona na stosie)
int tab[100][100];
for(int i = 0; i < 100; ++i)
{
for(int j = 0; j < 100; ++j)
{
tab[i][j] = rand() % 1000;
}
}
//tworzenie tablicy dwuwymiarowej dynamicznej (na stercie)
int n = 1000;
//przydzielamy pamięć tablicy wskaźników do wskaźników typu int
int **tabd = new int*[n];
//dla każdego wskaźnika w tablicy przydzielamy pamięć na tablicę o n elementach
for(int i = 0; i < n; ++i)
{
tabd[i] = new int[n];
}
//kasowanie w odwrotnej kolejności niż tworzenie - najpierw najbardziej wewnętrzny wymiar
for(int i = 0; i < n; ++i)
{
delete[] tabd[i];
}
//na końcu zewnętrzna tablica wskaźników
delete[] tabd;
//Jagged arrays (o dowolnych wymiarach wierszy)
//tablica będzie przypominała schodki
int **tabj = new int*[n];
for(int i = 1; i < n + 1; ++i)
{
tabj[i - 1] = new int[i];
}
//Kasowanie tablicy jak poprzedni
for(int i = 1; i < n + 1; ++i)
{
delete[] tabj[i - 1];
}
delete[] tabj;
}
Operacje równorzędne dla C# mogłyby wyglądać następująco:
//tablica dwuwymiarowa
int[,] tab = new int[100, 100];
//jagged array
int[][] tabj = new int[100][];
for (int i = 0; i < tabj.Length; i++)
{
tabj[i] = new int[100];
}
Mniej kodu a jak tym razem wygląda sprawa wydajności?
Aby sprawdzić szybkość wykonywania wersji niezarządzanej i zarządzanej skorzystam z operacji mnożenia macierzy. Implementowana metoda to mnożenie Cauchy'ego. Metoda ta wykonuje sporo operacji, tak więc nada się w sam raz na benchmark.
Ciekawą sprawą tego zagadnienia jest fakt, że w C# nie działa następujący kod:
int n = 500;
int** tab1 = stackalloc int*[n];
for (int i = 0; i < n; i++)
{
tab1[i] = stackalloc int[n];
}
Stackalloc nie obsługuje tablic wielowymiarowych. Łatwo jednak osiągnąć wielowymiarowość. Należy od razu zadeklarować tablicę potrzebnych rozmiarów a później odnosić się do elementów mnożąc odpowiednio ilość elementów w wierszu razy żądany wiersz dodając do tego pozycję żądanego elementu w wierszu:
private void button1_Click(object sender, EventArgs e)
{
Stopwatch clock = new Stopwatch();
clock.Start();
for (int i = 0; i < int.Parse(textBox1.Text); i++)
{
manageCode();
}
clock.Stop();
label1.Text = clock.ElapsedMilliseconds.ToString();
clock.Reset();
clock.Start();
for (int i = 0; i < int.Parse(textBox1.Text); i++)
{
unmanageCode();
}
clock.Stop();
label2.Text = clock.ElapsedMilliseconds.ToString();
}
private void manageCode()
{
Random rand = new Random();
int n = 100;
int[,] a = new int[n, n];
int[,] b = new int[n, n];
int[,] c = new int[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
a[i, j] = rand.Next(0, 1000);
b[i, j] = rand.Next(0, 1000);
}
}
int tmp;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
tmp = 0;
for (int r = 0; r < n; r++)
{
tmp += a[i, r] * b[r, j];
}
c[i, j] = tmp;
}
}
}
private unsafe void unmanageCode()
{
Random random = new Random();
int n = 100;
int * a = stackalloc int[n * n];
int * b = stackalloc int[n * n];
int * c = stackalloc int[n * n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
*(a + i * n + j) = random.Next(0, 1000);
*(b + i * n + j) = random.Next(0, 1000);
}
}
int tmp;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
tmp = 0;
for (int r = 0; r < n; r++)
{
tmp += *(a + i * n + r) * *(b + r * n + j);
}
*(c + i * n + j) = tmp;
}
}
}
Jedyny mankament jaki występuje w powyższym sposobie to ilość pamięci stosu. Standardowo stos w aplikacji .NET zajmuje 1 MB tak więc maksymalny rozmiar tablicy intów jaki stworzymy to trochę ponad 260 tys. elementów (powyżej tej wartości otrzymamy wyjątek stackoverflow). Można jeszcze pokusić się o zwiększenie rozmiaru stosu jest to jednak niezalecana operacja.
Wróćmy do testu i zobaczmy na wynik:
Tak więc znów mamy do czynienia z dwukrotnie większą wydajnością niż w przypadku standardowych tablic.
Ważną kwestią która z pewnością teraz nurtuje to zwalnianie pamięci. Otóż w przypadku C++ mieliśmy instrukcję delete[] tab; W kodzie unsafe C# nigdzie nie zwalniałem pamięci zarezerwowanej przez stackalloc. Otóż w tej kwestii wyręcza nas znów CLR i samo zajmie się zwolnieniem pamięci w momencie opuszczenia bloku instrukcji (w tym przypadku funkcji).
Podsumowując - stackalloc przydaje się w przypadku częstego tworzenia tablic. Pozwala przyśpieszyć kod nawet 3 krotnie (po dodaniu optymalizacji kodu). Tak więc niekiedy warto zaryzykować i pobawić się wskaźnikami aby uzyskać lepszą wydajność;)
Fajny artykuł. Właśnie pracuje nad optymalizacją mojego algorytmu za pomocą tego sposobu.
OdpowiedzUsuńMam problem z wielkością stosu. Proszę o pomoc:
- informacje w jaki sposób możliwe jest zwiększenie wielkości stosu powyżej tego 1 MB? Pracuje w Visual C# 2010.
- czy możliwe jest stworzenie tablicy na stosie a następnie uruchomienie wątków, które będą mogły do tej tablicy się odnosić ? W jaki sposób można to zrobić ?
Z góry dziękuje za pomoc,
Pozdrawiam