Jak mogę sprawdzić ile stosu wymaga mój program (ile zjada w najgorszym momencie)? Są do tego jakieś narzędzia? A może jakieś funkcje/biblioteki... Oczywiście mam dostęp do źródeł programu, bo sam je klepię. :)

Odpowiedź znajdziesz w AmigaFAQ na PPA. :D

TaskList



Ostatnia modyfikacja: 26.08.2009 19:57:40

Jeśli masz dostęp do źródeł programu to przeanalizuj kod źródłowy w celu oszacowania potrzebnej wielkości stosu. Zwróć przede wszystkim uwagę na funkcje rekurencyjne, np.

Funkcja silni jest najprostszym przykładem rekurencji

unsigned short int silnia(unsigned short int a)
{
if (a == 0) return 1;
else
return (a * silnia(a - 1));
}

Na stosie program odkłada wszystkie zmienne lokalne i adres zwrotny. Naszą zmienną lokalną jest argument funkcji "short int a", który zawiera 2 bajty, a adres zwrotny to 1 długie słowo, więc 4 bajty. W sumie więc gdy wywołamy silnia z argumentem "n" to potrzebujemy "6n" miejsca na stosie, np. silnia(10) potrzebuje 600 bajtów wolnego miejsca na stosie. Tyle jeśli chodzi o analizę potrzebnej wielkości stosu.

Śledzić nie muszę programu, bo znam go na pamięć. Już mi się wręcz śni. ;) Każdą z kilkuset tysięcy linii mógłbym napisać z pamięci. ;) Przy pisaniu uważam żeby nie przesadzać z takimi rzeczami więc orientacyjnie wiem, że pod tym względem nie jest źle. Jednak z ciekawości chciałem się dowiedzieć czy jakimś narzędziem mogę dostać dokładną maksymalną wartość stosu jaka jest zjadana podczas działania programu.

APC74, Korni:

Dzięki! Już rzucam okiem na polecone rozwiązania. Na początek zerknę na to co jest na AmiNecie i o czym jest mowa w Amiga FAQ (nigdy tam nie zaglądałem), czyli: StackCheck i WatchStack.

Skoro znasz algorytm na pamięć to powinieneś jednak przeprowadzić taką analizę. Da to wymierne korzyści, nigdy nie wiadomo jakie dane otrzyma Twój program. W zależności od wprowadzonych danych wielkość zużycia stosu może ulegać dużym zmianom. Na przykład gdy program korzysta z drzew i rekurencji aby przechodzić pomiędzy kolejnymi węzłami drzewa to w zależności od konstrukcji danego drzewa wielkość stosu może być bardzo różna. Poprawna analiza algorytmu programu da lepszy rezultat niż korzystanie z dodatkowych programów śledzących zużycie stosu. Jeśli program jest bardzo rozbudowany to oczywiście można podzielić go na mniejsze części i przeprowadzić analizę na poszczególnych częściach. Przykład funkcji "silnia" jest jednym z najprostszych algorytmów wykorzystujących rekurencję. Oczywiście funkcję "silnia" można napisać za pomocą iteracji, dzięki czemu zużycie stosu ulegnie znacznej redukcji. Jak już powiedziałem musisz być gotów na dowolne dane jakie dostanie Twój program.

Innym przykładem jest np. funkcja szybkiego sortowania (quick sort). Działa ona na zasadzie "dziel i zwyciężaj": polega to na podzieleniu głównego zadania na mniejsze podzadania. W tym wypadku funkcja "qsort" dzieli dany ciąg liczb na dwie części i przeprowadza sortowanie "qsort" na obu częściach, po czym łączy obie posortowane już części w całość tak, by zachowana była kolejność liczb. W tym wypadku poziom zagnieżdżenia funkcji można wyrazić za pomocą prostego wzoru - jest to logarytm przy podstawie 2 z liczby elementów danego ciągu. Np. dla ciągu o 1024 elementach poziom zagnieżdżenia funkcji wyniesie 10, bo 2 do potęgi 10 = 1024. Zatem można wnioskować, że wielkość stosu będzie rzędu pewnej stałej wielokrotnośći 10 (ta stała to wielkość zajmowanych przez tę funkcję zmiennych lokalnych). W przypadku funkcji "qsort" wielkość stosu zależy tylko od ilości liczb w sortowanym ciągu. Ale jak już wspomniałem na tę wielkość stosu może składać się znacznie więcej czynników. Warto przeprowadzać taką analizę algorytmu w celu uniknięcia niemiłych niespodzianek i ustalenia dokładnego rzędu wielkości stosu, jaki program powinien dostać.



Ostatnia modyfikacja: 26.08.2009 23:30:27