Dieses Programm ist definitiv kein Beispiel für guten Code!
Es soll die Verwendung verschiedener Arten von Speicher anschaulich machen.
#include <stdlib.h> #include <stdio.h> #include <unistd.h> static const unsigned short max_input = 23; static unsigned short* fibo_cache = NULL; static size_t fibo_cache_size = 0;
Diese drei Variablen existieren ab Programmstart bis Programmende. Wieviel Platz dafür gebraucht wird, bestimmt der Compiler schon beim Übersetzen. Der Speicherbedarf für diese Werte steht also vorab fest, er ist "statisch".
max_input
ist eine Konstante, die anderen beiden schreibbar.
Konstanten und schreibbare statische Daten liegen in unterschiedlichen
Segmenten.
static unsigned short fibo(unsigned short n) { if ((n < 0) || (n > max_input)) { fprintf(stderr, "Error %s() argument %u > %u\t%p\n", __func__, n, max_input, (void*) &max_input); return 0; } if (n < 2) return 1; if (fibo_cache && (n < fibo_cache_size) && fibo_cache[n]) return fibo_cache[n]; fprintf(stderr, ">>> %s(%2u)\t\t%p\n", __func__, n, (void*)&n); const unsigned short result = fibo(n-1) + fibo(n-2); if (fibo_cache && (n < fibo_cache_size)) fibo_cache[n] = result; fprintf(stderr, "<<< %s(%2u) =%5u\n", __func__, n, result); return result; }
Die Variable n
existiert genau so lange,
wie die Funktion ausgeführt wird.
Da es eine rekursive Funktion ist, kann sie mehrfach in Ausführung sein.
Dann gibt es auch mehrere n
mit unterschiedlichen Werten.
Für die lokalen Variablen einer Funktion wird bei jedem Aufruf
ein Stück des Stapels belegt (stack frame)
und mit dem Ende des Aufrufs wieder freigegeben.
Die Zeichenketten in den fprintf
-Aufrufen sind Konstanten.
Sie können in das gleiche Segment wie max_input
gelegt werden.
Die rekursive Berechnung von Fibonacci-Zahlen ist extrem ineffizient.
Zum Beispiel führt fibo(8)
zu den Aufrufen
fibo(7)
und fibo(6)
.
Aber fibo(7)
hat fibo(6)
zuvor schon aufgerufen,
dieser Wert wird also doppelt berechnet.
Entsprechend fibo(5)
dreifach, fibo(4) fünffach,
und so weiter nach der Fibonacci-Reihe.
Der Aufwand für die Rekursion ist
exponentiell,
statt linear bei einer Schleife von 2 bis n
.
Ein Cache schafft hier Abhilfe.
fibo(n)
speichert das Ergebnis beim ersten Aufruf im Cache
und liefert es bei späteren Aufrufen von dort.
Für die Berechnung einer einzelnen Fibonacci-Zahl
wäre eine Schleife noch effizienter als die Rekursion mit Cache,
weil auch die rekursiven Aufrufe entfallen.
static void prepare_cache(unsigned short index) { if (index < fibo_cache_size) return; if (fibo_cache) free(fibo_cache); // need one element more to access fibo_cache[index] const size_t size = index+1; fibo_cache = calloc(size, sizeof(unsigned short)); if (fibo_cache) { fibo_cache_size = size; fprintf(stderr, "fibo_cache allocated\t%p\nfibo_cache_size %zu\t%p\n", (void*)fibo_cache, size, (void*) &fibo_cache_size); } else { fibo_cache_size = 0; // memory allocation failed fprintf(stderr, "fibo_cache allocation failed\n"); } }
Mit calloc
wird ein Stück Speicher auf der Halde reserviert
und mit Nullen gefüllt. Dieser Speicherbereich bleibt so lange reserviert,
bis er mit free
freigegeben wird oder das Programm endet.
Die globalen Variablen fibo_cache
und
fibo_cache_size
enthalten die Informationen
über den gerade als Cache nutzbaren Speicherbereich.
Die Funktion fibo
nutzt den Cache, falls er existiert.
int main(int argc, const char* argv[]) { for (int i = 1; i < argc; i++) { char* end = NULL; long argument = strtol(argv[i], &end, 0); if (*end != 0) { fprintf(stderr, "invalid argument #%i: '%s'\n", i, argv[i]); continue; } if (argument < 0) { fprintf(stderr, "\nsleeping %li seconds, so you can look at:\n" "cat /proc/%u/maps\n", -argument, getpid()); sleep(-argument); continue; } unsigned short input = argument; prepare_cache(input); unsigned short result = fibo(input); printf("%2u -> %5u\n", input, result); } }
Das Programm erwartet ganze Zahlen als Aufrufargumente. Für positive Zahlen legt es den Cache an und berechnet die Fibonacci-Zahl. Negative Zahlen führen zu einer Pause von entsprechend vielen Sekunden.
Die über das Programm verstreuten fprintf()
mit %p
geben Adressen von Variablen und dem Cache aus.
In einer längeren Pause kann man diese Adressen mit den Segmenten
des laufenden Programms abgleichen.