fibonacci.c
°

Beamer

Dieses Programm ist definitiv kein Beispiel für guten Code!
Es soll die Verwendung verschiedener Arten von Speicher anschaulich machen.

Sourcecode   pdf

Statische Daten

#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.

Rekursion

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.

Cache

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.

Hauptschleife

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.