Unikanięcie nadmiernego zużycia pamięci przez wielokrotnie wywoływaną funkcję

Question

Witam,

Usiłuję zaimplementować algorytm SHA-1 w języku C, docelowo w celu przeniesienia na mikrokontroler AVR. Minimalne zużycie pamięci jest więc dla mnie priorytetem. Drażni mnie jednak pewne pytanie. Załóżmy, że mam zdefiniowaną pewną funkcję, a w niej zadeklarowane zmienne lokalne o łącznej wielkości N bajtów. Powiedzmy, że dalej wykonam tę funkcję w moim kodzie i razy (różne wejścia). Ile pamięci będzie zajęte po opuszczeniu ostatniego wykonania funkcji? N, i*N, czy może 0 bajtów?

Jeśli i*N, to jak ograniczyć je do N? Myślałem o zastosowaniu globalnej struktury ze zmiennymi funkcji - niezbyt estetyczne w zapisie przy wielu zmiennych. O stosowaniu dynamicznej alokacji pamięci w AVRach słyszałem, że to kiepski pomysł.

Pozdrawiam i z góry dziękuję za odpowiedzi.

 

Answer 1

Zakładając że Twoja funkcja ma wyłącznie zmienne automatyczne (nie posiada zmiennych statycznych), zajętość pamięci po opuszczeniu ostatniej to będzie 0 (zero) bajtów. Nieco inaczej będzie z zajętością chwilową pamięci.

Jeśli funkcja będzie wywoływana i będą z niej powroty bezpośrednio (np. pętla for czy while i wywołanie funkcji w ciele pętli a przed powrotem do następnej iteracji jest wyjście z funkcji), to zajętość chwilowa to N. Czyli N bajtów poświęcanych na zmienne automatyczne (patrz założenie braku statycznych). 

Jeśli jednak sama funkcja rekurencyjne będzie wołała siebie lub inne, tu problem będzie złożony. W najgorszym przypadku będzie to N * i gdzie i to ilość zagnieżdżeń rekurencji. 

I w tym ostatnim przypadku także jest wyście. Można stosować tzw. rekurencję ogonową która ( choć tak standard C jak i C++ o tym nie mówi), w większości kompilatorów powoduje optymalizację. Z całą pewnością dzieje się tak w avr-gcc. Wtedy zużycie chwilowe RAM to N.