Im Vergleich zu Vorgängersprachen war der Mechanismus der dynamische Speicherverwaltung mit malloc/free (SpracheCee) und die damit verbundene flexible Wiederverwendung des Speichers ein großer Schritt vorwärts.

Andererseits erzeugten diese neuen Möglichkeiten endlose Fehlermöglichkeiten in der Anwendung (MemoryLeak, PointerArithmetik?, etc.) und führten letzlich zur Entwicklung von Sprachen wie Java, Python oder Perl, wo dem Programmierer diese Verwaltungsprobleme völlig aus der Hand genommen werden. Aber kein Vorteil ohne Nachteil: Programmierer entwickeln jetzt weniger Verständnis für den Speicherbedarf und die Effizienz ihrer Programme, weil viel unsichtbar im Hintergrund abläuft.

Wesentlich für alle Optimierungen ist, zu verstehen, dass malloc/free (oder das Erzeugen und Freigeben von Objekten) nach IO-Vorgängen meist der zeitraubendste Vorgang ist. Optimieren heißt deswegen auch fast immer MallocFreeVermeiden.

Die Kosten von malloc/free

• Es gibt einen Speicheroverhead von ca. 8-16 Byte pro Speicherallocation. Ein Teil des Overheads kommt von notwendigen Verwaltungsinformationen: es muss ja für die spätere Freigabe eines Speicherblocks irgendwo im System seine Länge (normalerweise 4 Byte) gespeichert werden. Weiters werden Blocklängen normalerweise nur in Vielfachen von 8 oder meist 16 Byte (Erfahrungswert, implementierungsabhängig) zugeordnet; das heißt es gibt noch einen Aufrundungsschritt. 1 Byte allokieren heißt also oft: 16 Byte verbrauchen.
• malloc/free sind relativ zeitraubende Funktionen, weil sie mit Suchvorgängen verbunden sind. Auch geschicktes Caching kann nicht verhindern, dass geschaut werden muss, ob ein in der Größe passender Block vorhanden ist; allenfalls ein größerer Block unterteilt werden muss, eventuell vom Betriebssystem neuer Speicher angefordert werden muss, bei der Freigabe die Möglichkeit der Verschmelzung mit freien Nachbarblöcken geprüft und durchgeführt werden muss, usw.; ...und das kostet eben entsprechend viel Zeit!

• Manche Systeme der dynamischen Speicherverwaltung haben zusätzlich ein Fragmentierungsproblem. D. h. nehmen wir an, dass 1 MB Speicher dynamisch zur Verfügung stehen, davon 50% vom Programm tatsächlich mit malloc/calloc benutzt werden, dann sind im Prinzip noch 0.5 MB frei. Diese stehen aber meist nicht als geschlossener Bereich zur Verfügung, weil sich durch die Geschichte der Speicherungzuordnungen und Speicherfreigaben normalerweise eine Zerstückelung ergibt:

z. B. ein Muster BBB-BB----BBBB-BBB---BB---BB--BBB----BB---BB----BB

Wenn oben jedes Zeichen für 20 KB steht, dann wären zwar 500 KB frei, der größte verfügbare Block wäre aber 80 KB groß. D. h. wenn es keine Erweiterungsmöglichkeit gibt, dann würde eine Speicheranforderung >80 KB fehlschlagen, obwohl 500 KB frei sind.

• Moderne Systeme mildern dieses Problem zwar durch virtuelle Speicherverwaltung, trotzdem kann man den Faktor Fragmentierung nicht immer ignorieren. Vor allem weil komplex verlinkte, zerstückelte Datenstrukuren ein weniger effizientes Caching zulassen als kompakte Speicherblöcke. Es kann z.B. in der Bildverarbeitung günstiger sein, ein 1000x1000x1Byte Bild in einem Block zu allokieren und zu verarbeiten, als das gleiche in 1000 Bildzeilen á 1000 Byte zu tun, wobei die Fragmentierung dabei aber nur ein Teilaspekt ist.

• ToDo. (Freigegebener Speicher ist meist nicht von anderen Programmen nutzbar)

mall/stack 129.300 19.300 [us] ta/tb = 6.70 Bem.: PentiumIII700/¦UnixWare mall/stack 233.500 20.100 [us] ta/tb = 11.62 Bem.: PentiumIII700/¦Linux mall/stack 275.000 26.000 [us] ta/tb = 10.74 Bem.: PentiumIII700/¦WinNT mall/stack 435.938 26.562 [us] ta/tb = 16.41 Bem.: PentiumIII700/¦FreeBSD43 mall/stack 4880.000 663.000 [us] ta/tb = 7.36 Bem.: Pentium60/¦OpenServer

# include <stdlib.h> int mall(int n) { int r=0; if (n<1000) { char *p; p= malloc(32); if (p) { p[20]='m'; r= mall(n+1); free(p); } else r=1; } return r; } int stack(int n) { int r=0; if (n<1000) { char p[32]; if (p) { p[20]='s'; r= stack(n+1); } else r=1; } return r; }

--hs

Zu deinem Benchmark muss ich noch ein paar Fragen und Anmerkungen deponieren:

Im Grund wird nicht malloc/stack gemessen, sondern Funktionsrumpf+malloc/Funktionsrumpf+stack. Nachdem stack aber so gut wie keine Zeit verbraucht misst der Benchmark eigentlich Funktionsrumpf+malloc/Funktionsrumpf. Die Ergebnisse von 7:1 bis 16:1 decken sich mit einer alten, von mir verwendeten Faustformel: dass ein malloc/free ca. 10x so viel Zeit braucht wie ein Funktionsrumpf.

Genau richtig, ta/tb würde bei ganz richtigen Messungen gegen Unendlich gehen. Wegen dieser 'unglaublichen' Werte habe ich es nicht 'ganz richtig' gemacht, und weil ich keinen Stack fortlaufend in einer Schleife allokieren kann, und weil meine Meßeinrichtung Funktionen als Meßobjekte braucht. Die mall-Funktion allokiert ja auch Stack für r, p und n, was zeitlich vollkommen untergeht.

Der Sinn von n und r erschließt sich mir nicht unmittelbar. Wäre es nicht einfacher, n nach unten zu variieren und mit n die Aufruftiefe anzugeben, statt dies nach oben und mit der willkürlichen Grwenze 1000 zu koppeln? Und r scheint fast funktionslos; ergänzt im Benchmark nur zum 'typischen' Funktionsrumpf?

r soll nur einen eventuellen malloc-Fehlschlag durchschleusen. Besser zum Variieren wäre sicher, n von einem hohen Startwert aus zu dekrementieren. Ich habe die Funktionen absichtlich gleich gehalten (r in stack), da mir sonst möglicherweise sofort wieder Betrug vorgeworfen würde. In dclc z.B. ist dieser Bench sowieso irrelevant, da ich nur mengenmäßig relevante Plattformen gemessen habe, nicht aber die irrelevanten Plattformen mit SPARC, MIPS, etc.

Der obige Benchmark begünstigt im Prinzip noch malloc/free, weil er nur mit 32-Byte Speicherblöcken arbeitet. Die Wiederverwendung von Blöcken und das Cachen ist für ein intelligentes malloc/free somit leicht möglich. In einer realen Situation mit wechselnder Blockgröße würde malloc/free vermutlich noch schlechter abschneiden.

Genau richtig. Ich könnte auf meinem ruhenden System alles ver-10000-fachen und malloc hätte immer noch ideale Verhältnisse. Ich kann mir vorstellen, daß auf einem System, wo so richtig was los ist (z.B. WebSpace?-Server) malloc 30-fach langsamer ist als Stack. --hs

Interessant ist auch ein vertikaler Vergleich. Die (eigentlich kommerziellen) SCO-Systeme sind besser, besonders das moderne UnixWare, das unter Caldera als OpenUnix8 weitergeführt wird (mit Linux 'verheiratet'). --hs

Irgendwie verstehe ich das Problem nicht wirklich. Eine Variable auf dem Stack zu alloziieren ist doch einfacher als malloc/free zu benutzen. Demzufolge wird ein Programmierer nur dann malloc/free benutzen wenn er es wirklich braucht: man kann ja nicht alles auf dem Stack machen. -- ThomasHolenstein

Aber ja, so ist es. Das Problem ist allerdings, daß malloc() sehr viele magisch anzuziehen scheint. Es wird gesagt, selbst bei Eingabe eines Integers, der nachfolgend mit atoi() oder sscanf() umgewandelt wird, reiche es nicht aus, [40] chars starr zu allokieren. Es wäre schlechter Programmierstil, überhaupt irgendwelche Grenzen zu setzen. Zum Beweis werden militärische Spezialrechner aus dem Jahr 1970 aufgeführt, die eine 2048 Bit breite ALU haben, usw. Es entsteht ein MegaThread, weil jemand gesagt hatte, 40 Byte seien dafür ausreichend und weil ich da zusätzlich zugestimmt hatte. --hs

Mhh, ist es nicht diese Art des Denkens, die zum JahrZweitausendProblem? geführt hat? Es wurde angenommen, die Programme würden niemals zu einem Zeitpunkt laufen, an dem mehr als zwei Ziffern benötigt werden. Vielleicht wird in zehn Jahren jeder GameBoy? eine 2048 Bit breite ALU haben, und vielleicht wird dann genau das Programm, das Du heute schreibst, damit Probleme bekommen...

Damit will ich natürlich nicht sagen, dass das Wissen um die Schwächen von malloc() und co nicht wertvoll ist - an den richtigen Stellen eines performancekritischen Algorithmus kann das sicherlich gute Dienste leisten. Aber ein kategorisches MallocFreeVermeiden halte ich doch für sehr fragwürdig. -- IljaPreuß

Warum verwendest du nicht einfach eine Konstante BUFFERSIZE anstatt 40. Dann ist das Problem nach der neukompilierung geloest. Leute die nicht mal das tolerieren sollen mir doch bitte erst ein Betriebsystem mit beliebing grossen Files schreiben... Viel Spass beim Implementieren der Langzahlarithmetik. --th

...ein kategorisches MallocFreeVermeiden halte ich doch für sehr fragwürdig...

Es gibt kein kategorisches MallocFreeVermeiden. Es gibt nur einen guten Rat im Rahmen der SoftwareOptimierung, zeitkritische Codeabschnitte auf unnötige malloc/free zu überprüfen, weil das einer der häufigsten Performancefresser ist. -- hl