Performance of alloca vs malloc
Christian Näger
I have a function that is called very often. The function needs to
temporarily allocate memory which can be freed on return.
I have heard that malloc is quite expensive. How does alloca compare to
malloc (on linux+gcc)? I assume it is faster (as memory is allocated on the
stack).
One solution to my problem would be to alloca on the stack (which is
probably faster) and have the memory freed automatically on function return.
The other solution would be to allocate once and reuse the memory between
the function calls via a static variable:
void test() {
static struct mydata *d;
if (d == NULL) d = (struct mydata*)malloc(sizeof(struct mydata));
...
/* no free */
}
But this gives me an additional if... and can I rely on d == NULL if d has
not been allocated?
The third solution, a global variable, is inacceptable.
What is the best way to handle this case?
Thanks, Chris
Christian Näger
--CN
Felix von Leitner
> void test() {
> static struct mydata *d;
> if (d == NULL) d = (struct mydata*)malloc(sizeof(struct mydata));
> ...
> /* no free */
> }
> But this gives me an additional if... and can I rely on d == NULL if d has
> not been allocated?
So ein Bullshit. Wenn du genau einmal eine Struktur brauchst, dann
kannst du die auch direkt auf den Stack tun und brauchst überhaupt kein
Malloc. Es ist absoluter Unfug, da irgendwelche Allokationsroutinen zu
benutzen.
> The third solution, a global variable, is inacceptable.
Du willst dich mal über static informieren.
> What is the best way to handle this case?
Erstmal anständig C lernen.
Christian Näger
> So ein Bullshit. Wenn du genau einmal eine Struktur brauchst, dann
> kannst du die auch direkt auf den Stack tun und brauchst überhaupt kein
> Malloc. Es ist absoluter Unfug, da irgendwelche Allokationsroutinen zu
> benutzen.
Aber fuer was ist dann alloca da (die die Struktur ja auch auf dem Stack
anlegt)?
--CN
Patrick Schaaf
>Felix von Leitner wrote:
Natuerlich fuer Faelle, wo die Groesse des benoetigten Bereichs nicht
zur "compiletime" bekannt ist.
Gruss
Patrick
Christian Näger
> Thus spake Christian Näger (nae...@web.de):
spake? SPO?
>> void test() {
>> static struct mydata *d;
>> if (d == NULL) d = (struct mydata*)malloc(sizeof(struct mydata));
>> ...
>> /* no free */
>> }
...
> Du willst dich mal über static informieren.
Kernighan/Ritchie (Kap. 4.6 Static variables): "Internal static variables
are local to a particular function just as automatic variables are, but
unlike automatics, they remain in existence rather than coming and going
each time the function is activated. This means that internal static
variables provide private, permanent storage within a single function."
Also muesste der Code doch korrekt sein, der Pointer d ist lokal zeigt aber
trotzdem immer (bei jedem Aufruf) auf den richtigen Speicherbereich.
Meine Frage war aber viel mehr: was ist schneller: automatische variable
(auf dem Stack), alloca (auf dem Stack) oder malloc und static pointer (wie
oben)?
> Erstmal anständig C lernen.
Drum frag ich ja...
--CN
Christian Näger
>>Aber fuer was ist dann alloca da (die die Struktur ja auch auf dem Stack
>>anlegt)?
>
> Natuerlich fuer Faelle, wo die Groesse des benoetigten Bereichs nicht
> zur "compiletime" bekannt ist.
Ah, ja klar, da faellt es mir wie Schuppen ...
Wie sieht es mir der Performance aus?
eher so wie malloc (also langsamer) oder so wie automatische
Stack-Variablen (schneller).
Danke, Chris
Peter Simons
allgemein gültigen Aussagen machen. Wie schnell oder langsam die eine
oder die andere Routine ist, hängt ausschließlich von deren
Implementation ab.
Selbst wenn Du feststellst, daß Dein Program unter Linux mit alloca()
dreimal schneller läuft als mit malloc(), so muß dies unter Solaris
noch lange nicht stimmen. Das Laufzeitverhalten kann sich sogar auf
ein und derselben Maschine ändern, wenn Du lediglich die
Systembibliothek "libc" austauschst oder das Programm mit einem
anderen Compiler übersetzt.
Sieh Dir doch mal
http://www.memorymanagement.org/articles/begin.html
oder
http://g.oswego.edu/dl/html/malloc.html
an; da findest Du einiges an Grundlagenwissen über Speichermanagement
generell, und mit dem Wissen verstehst Du auch leichter, wie Du Dein
Programm _wirksam_ optimieren kannst.
King Leo - Martin Oberzalek
> Selbst wenn Du feststellst, daß Dein Program unter Linux mit alloca()
> dreimal schneller läuft als mit malloc(), so muß dies unter Solaris noch
> lange nicht stimmen. Das Laufzeitverhalten kann sich sogar auf ein und
> derselben Maschine ändern, wenn Du lediglich die Systembibliothek "libc"
> austauschst oder das Programm mit einem anderen Compiler übersetzt.
Wozu gibts configure Scripte, die eventuell vorher automatisch rausinden,
was schneller ist ud dann eben diese Technik verwenden.
alloca durch malloc, oder umgekehrt ersetzen is ja trivial.
> an; da findest Du einiges an Grundlagenwissen über Speichermanagement
> generell, und mit dem Wissen verstehst Du auch leichter, wie Du Dein
> Programm _wirksam_ optimieren kannst.
Das ist natürlich noch besser.
--
Soweit ich weiß ist Windows ein eigenständiges Betriebssystem.
(Daniel Tiefnig in at.linux)
King Leo - Martin Oberzalek
wobei alloca wohl seit C99 kaum mehr benötigt werden wird:
void foo( unsigned int size )
{
char bar[size];
}
--
GNU löst nicht alle Probleme der Welt, sondern nur bestimmte.
(Das GNU-Manifest)
Patrick Schaaf
>alloca durch malloc, oder umgekehrt ersetzen is ja trivial.
alloca durch malloc zu ersetzen, ist fast trivial - man muss nur an
alle Austrittsstellen die passenden free()s schreiben, sonst gibt
es ein memory leak.
malloc zu alloca ist im Allgemeinen nicht machbar, da die Semantik
von alloca (der implizite free bei Verlassen der jeweiligen Funktion)
nicht identisch zu malloc ist.
>> an; da findest Du einiges an Grundlagenwissen über Speichermanagement
>> generell, und mit dem Wissen verstehst Du auch leichter, wie Du Dein
>> Programm _wirksam_ optimieren kannst.
>Das ist natürlich noch besser.
Ja. Sich ueber die relative Performance von malloc und alloca zuerst
Sorgen zu machen, zeugt von voelligem Unverstaendnis in der Optimierung
von Software. Man verwendet malloc, weil es die "normale" Methode ist.
Falls sich spaeter bei Profiling-Laeufen herausstellt, dass dort die
Hauptzeit verbraten wird, sucht man eine semantisch identische gute
malloc-Library. Nur wenn das gemacht ist, und das Profiling immer noch
zeigt, dass es ein signifikantes Problem mit der Allozierung gibt,
UND das alloc/free-Pattern auf "funktionslokal" passt, wuerde ich
alloca als nicht-so-Standard-Methode in Erwaegung ziehen.
Gruss
Patrick
Janusch Lisson
> was schneller ist ud dann eben diese Technik verwenden.
>
> alloca durch malloc, oder umgekehrt ersetzen is ja trivial.
Man kann nicht einfach malloc durch alloca ersetzten, es ist nicht das
gleiche!
man malloc
man alloca
Janusch
--
Bei einer Raumtemperatur von 21 Grad und einer relativen Luftfeuchtigkeit
von 80 Prozent etwa verströmt der 10-Euro-Schein einen erdigen bis stoffigen
Geruch, mit einer leicht blumigen Note.
Peter Simons
> Wozu gibts configure Scripte, die eventuell vorher automatisch rausinden,
> was schneller ist ud dann eben diese Technik verwenden.
Ein solches Configure-Skript mißt die Performance aber nur in einer
Momentaufnahme. Wenn man nicht gerade statisch linkt, kann sich das
Performance-Verhalten durchaus auch nachträglich ändern, zum Beispiel,
wenn eine neue libc oder ein neuer Kernel eingespielt wird. Insofern
hielte ich eine solche Maßnahme für nutzlos.
Hinzu kommt, daß die Performance des einen oder des anderen
Speichermanagers sehr stark davon abhängt, was für Blöcke reserviert
werden: Viele kleine? Wenige große? Werden die Blöcke regelmäßig
wieder freigegeben, oder bleiben einmal reservierte Speicherbereiche
über lange Zeit bestehen? Werden sie in der Reihenfolge freigegeben,
wie sie reserviert wurden, oder wild durcheinander? Es dürfte
schwierig sein, einen Test zu schreiben, der das tatsächliche
Verhalten der Anwendung genau genug simuliert, um zu einem sinnvollen
Ergebnis zu kommen.
> alloca durch malloc, oder umgekehrt ersetzen is ja trivial.
Nicht unbedingt. Wenn man nicht aufpaßt, gibt es da sogar einige
Fallstricke:
(1) Mit malloc() reservierter Speicher bleibt über den Scope hinaus
bestehen, in dem er reserviert wurde. Mit alloca() reservierter
Speicher tut das nicht. Für Speicherblöcke, die auch oberhalb
dieses Scopes verwendet werden, kann man alloca() also gar nicht
benutzen.
(2) Mit alloca() reservierter Speicher kann nicht explizit
freigegeben werden. Mit malloc() reservierten Speicher _muß_
dagegen (in aller Regel) explizit freigeben werden. Je nachdem,
ob also Modell A oder B verwendet wird, muß auch die Verwendung
von free() angepaßt werden.
(3) Nicht auf allen Systemen kann man auf dem Stack überhaupt ähnlich
große Speicherblöcke reservieren, wie man es auf dem Heap kann.
Ein malloc(x) für große x mag gelingen, ein alloca(x) für
dasselbe x gelingt eventuell nicht, weil im System
Einschränkungen für die Stackgröße bestehen.
Betrachte ich unter Linux beispielsweise die gängigen
Systemlimits, so sehe ich folgendes:
| data seg size unlimited
| max locked memory unlimited
| max memory size unlimited
| virtual memory unlimited
Aber:
| stack size 8192 kbytes
Die beiden Routinen alloca() und malloc() tun prinzipiell verschiedene
Dinge. Die Entscheidung, das eine oder andere System zu verwenden,
sollte sich unbedingt an den algorithmischen Bedürfnissen der
Anwendung orientieren, nicht an Performancemessungen. Wenn man es ganz
sicher richtig machen will, dann benutzt man alloca() schlicht und
einfach gar nicht. Die Routine ist nicht portabel implementierbar, sie
ist durch keinen mir bekannten Standard festgelegt, und sie ist auf
vielen Systemen schlicht und einfach gar nicht vorhanden.
Wer sich für die Performance des Speichermanagements interessiert, der
sollte darüber nachdenken, verschiedene Bibliotheken auszuprobieren,
die malloc() und Konsorten mit verschiedenen Strategien zur
Speicherverwaltung implementieren.[1] Diese kann man dann wahlweise
statt der Implementation des Systems linken, ohne seinen Quellcode
überhaupt anfassen zu müssen.
Wer sich dagegen wirklich für die Optimierung seiner Anwendung
interessiert, der fragt sich lange bevor er über solche Themen
nachdenkt erstmal "Wie kommt es eigentlich, daß mein Programm
andauernd im Speicher rumreserviert?" und schaut sich das Design
seines Programms an. Am wenigsten Zeit wird in dem Speichermanager
verschwendet, der kaum oder gar nicht aufgerufen wird.
-peter
[1] Ein schönes Beispiel für eine alternative malloc()-Implementation
findet man unter <http://dmalloc.com/>; weitere Bibliotheken wird
es zweifelsohne geben.
Felix von Leitner
> eher so wie malloc (also langsamer) oder so wie automatische
> Stack-Variablen (schneller).
Ist das eine Trick-Frage?
malloc muß Locken (wegen der Threads), muß umfängliche Datenstrukturen
bearbeiten, muß eventuell brk oder mmap aufrufen...
alloca muß eine Zahl von einem Register abziehen.
Welches wird _da_ wohl schneller sein...? ;)
King Leo - Martin Oberzalek
>> Wozu gibts configure Scripte, die eventuell vorher automatisch
>> rausinden, was schneller ist ud dann eben diese Technik verwenden.
>>
>> alloca durch malloc, oder umgekehrt ersetzen is ja trivial.
> Wahnsinnig...?
> Man kann nicht einfach malloc durch alloca ersetzten, es ist nicht das
> gleiche!
> man malloc
> man alloca
Das Bezog sich auf die Funktion vom orig Poster. Mir is schon klar, dass
man malloc nicht einfach überall durch alloca ersetzen kann.
Aber bevor man sich alloca, oder andere Methoden überlegt sollte man
erstmal grundsätzlich den profiler dazu befragen.
--
^^
The line must be drawn here!
Felix von Leitner
> Über das Laufzeitverhalten von malloc() oder alloca() kann man keine
> allgemein gültigen Aussagen machen.
ROTFL
> Wie schnell oder langsam die eine oder die andere Routine ist, hängt
> ausschließlich von deren Implementation ab.
Klar. Ob bsearch schneller als lineares Durchlaufen ist, das hängt voll
von der Implementation des linearen Durchlaufens ab!1!!
Wie kommst du Troll nur dazu, dir so eine blasphemische Domain zu
greifen? Das ist ja grotesk!
> Selbst wenn Du feststellst, daß Dein Program unter Linux mit alloca()
> dreimal schneller läuft als mit malloc(), so muß dies unter Solaris
> noch lange nicht stimmen.
Du weißt ja nicht, wovon du redest, Mann!
alloca wird im Compiler implementiert, nicht in der Library.
Und der Compiler macht daraus einen Maschinenbefehl (und kann damit
sogar mehrere allocas und automatische Variablen zusammenfassen).
> Das Laufzeitverhalten kann sich sogar auf ein und derselben Maschine
> ändern, wenn Du lediglich die Systembibliothek "libc" austauschst oder
> das Programm mit einem anderen Compiler übersetzt.
Nicht in dem Maß, daß malloc plötzlich schneller als alloca wird.
> Sieh Dir doch mal
> http://www.memorymanagement.org/articles/begin.html
Mit Verlaub: diese Page ist Scheiße.
> http://g.oswego.edu/dl/html/malloc.html
Und die ist unrelevant.
> an; da findest Du einiges an Grundlagenwissen über Speichermanagement
> generell, und mit dem Wissen verstehst Du auch leichter, wie Du Dein
> Programm _wirksam_ optimieren kannst.
Wie willst du das beurteilen können?
Andreas Bierhals
Christian =?ISO-8859-1?Q?N=E4ger?= <nae...@web.de> writes:
> >> void test() {
> >> static struct mydata *d;
> >> if (d == NULL) d = (struct mydata*)malloc(sizeof(struct mydata));
> >> ...
> >> /* no free */
> >> }
> Also muesste der Code doch korrekt sein, der Pointer d ist lokal zeigt aber
> trotzdem immer (bei jedem Aufruf) auf den richtigen Speicherbereich.
warum schreibst Du nicht einfach anstelle Deiner beiden Zeilen
static struct mydata d;
und verwendest dann einfach d?
Ich glaube das war es, was Felix meinte...
Bis dann
Andreas
Uwe Ohse
>void foo( unsigned int size )
>{
> char bar[size];
>}
Das ist schön wenn man size beim Eintritt in foo schon kennt.
alloca funktioniert auch sonst - und der Fall ist eher häufiger.
Gruß, Uwe
Klaus von der Heyde
>
> wobei alloca wohl seit C99 kaum mehr benötigt werden wird:
>
> void foo( unsigned int size )
> {
> char bar[size];
> }
Muss es nicht "const unsigned int size" oder sowas heissen?
Klaus
--
Klaus von der Heyde -- he...@informatik.uni-bonn.de
Klaus von der Heyde
>
> malloc muß Locken (wegen der Threads), muß umfängliche Datenstrukturen
> bearbeiten, muß eventuell brk oder mmap aufrufen...
... je nach rechnerarchitektur ist die vorgehensweise verschieden ...
> alloca muß eine Zahl von einem Register abziehen.
Prueft alloca, ob noch platz auf dem stack frei ist? Die man-page
suggeriert es (rueckgabewert NULL bei "scheitern").
Bei unsachgemaesser anwendung kann man mit alloca in schwierigkeiten
kommen: verwendung des zeigers nach der automatischen "freigabe".
Das war in dem beispiel uebrigens auch der fall.
C hat eben immer noch ein paar nette ueberraschungen :)
Gibt es unix-plattformen/compiler ohne alloca, die noch verbreitet
sind?
Felix von Leitner
> > malloc muß Locken (wegen der Threads), muß umfängliche Datenstrukturen
> > bearbeiten, muß eventuell brk oder mmap aufrufen...
> ... je nach rechnerarchitektur ist die vorgehensweise verschieden ...
Nein.
> > alloca muß eine Zahl von einem Register abziehen.
> Prueft alloca, ob noch platz auf dem stack frei ist? Die man-page
> suggeriert es (rueckgabewert NULL bei "scheitern").
Die Man-Page lügt.
> Bei unsachgemaesser anwendung kann man mit alloca in schwierigkeiten
> kommen: verwendung des zeigers nach der automatischen "freigabe".
> Das war in dem beispiel uebrigens auch der fall.
> C hat eben immer noch ein paar nette ueberraschungen :)
Soll das ein Witz sein? Verwenden von freigegebenen Zeigern ist
selbstverständlich unabhängig von der Allozierungsmethode ein Fehler.
> Gibt es unix-plattformen/compiler ohne alloca, die noch verbreitet
> sind?
Ich kenne keinen.
Felix
King Leo - Martin Oberzalek
> King Leo - Martin Oberzalek <kin...@gmx.at> wrote:
>>
>> wobei alloca wohl seit C99 kaum mehr benötigt werden wird:
>>
>> void foo( unsigned int size )
>> {
>> char bar[size];
>> }
>
> Muss es nicht "const unsigned int size" oder sowas heissen?
Wie ich oben sagte, seit C99 nicht mehr.
Klaus von der Heyde
>> Prueft alloca, ob noch platz auf dem stack frei ist? Die man-page
>> suggeriert es (rueckgabewert NULL bei "scheitern").
>
> Die Man-Page lügt.
Das ist 1. schlecht und 2. schlecht. Also im zweifelsfall doch
lieber malloc verwenden, um keinen stack overflow zu riskieren?
Ist das ein (eventuell sicherheitsrelevantes) loch?
> Soll das ein Witz sein? Verwenden von freigegebenen Zeigern ist
> selbstverständlich unabhängig von der Allozierungsmethode ein Fehler.
Na klar ist das falsch. Nachdem ich das beispiel sah, hatte ich
den eindruck, alloca provoziert das falschmachen.
Bei C muss man eben auf jeden sch* achten :)
Patrick Schaaf
>Felix von Leitner <usenet-...@fefe.de> wrote:
>>
>>> > alloca muß eine Zahl von einem Register abziehen.
>>> Prueft alloca, ob noch platz auf dem stack frei ist? Die man-page
>>> suggeriert es (rueckgabewert NULL bei "scheitern").
>>
>> Die Man-Page lügt.
>Das ist 1. schlecht und 2. schlecht. Also im zweifelsfall doch
>lieber malloc verwenden, um keinen stack overflow zu riskieren?
>Ist das ein (eventuell sicherheitsrelevantes) loch?
Benutzt Du Funktionsaufrufe oder lokale Variablen?
>> Soll das ein Witz sein? Verwenden von freigegebenen Zeigern ist
>> selbstverständlich unabhängig von der Allozierungsmethode ein Fehler.
>Na klar ist das falsch. Nachdem ich das beispiel sah, hatte ich
>den eindruck, alloca provoziert das falschmachen.
>Bei C muss man eben auf jeden sch* achten :)
Willst Du, dass es funktioniert?
Matthias Bethke
> warum schreibst Du nicht einfach anstelle Deiner beiden Zeilen
> static struct mydata d;
> und verwendest dann einfach d?
> Ich glaube das war es, was Felix meinte...
Er meinte das ohne static, was natürlich nicht das selbe tut wie ein
malloc; in dem Fall will man wohl static. So eine Alloziererei kann
sinnvoll sein, wenn man Speicherattribute zu beachten hat, in normalen
Unix-Programmen also nicht.
regards
Matthias
--
PGP used here!
2048/0x90CF8389 / 8E 1F 10 81 A4 66 29 46 B9 8A B9 E2 09 9F 3B 91
Felix von Leitner
> > warum schreibst Du nicht einfach anstelle Deiner beiden Zeilen
> > static struct mydata d;
> > und verwendest dann einfach d?
> > Ich glaube das war es, was Felix meinte...
> Er meinte das ohne static, was natürlich nicht das selbe tut wie ein
> malloc; in dem Fall will man wohl static.
Unfug. Du bist offenbar gerade echt verwirrt.
static für Variablen in einer Funktion ist Speicherverschwendung und
sollte nur in Ausnahmefällen benutzt werden, wenn man weiß, was man tut.
Felix
Matthias Bethke
>> Er meinte das ohne static, was natürlich nicht das selbe tut wie ein
>> malloc; in dem Fall will man wohl static.
> Unfug. Du bist offenbar gerade echt verwirrt.
Der OP wollte irgendwas allozieren, was ausdrücklich nicht mehr in der
Funktion freigegeben wird (warum, weiß ich nicht, aber von mir aus), und
hat eine umständliche Methode dafür vorgeschlagen. Meine bzw. Andreas'
Methode tut das selbe auf einfachere Art. Deine tut etwas ganz anderes.
> static für Variablen in einer Funktion ist Speicherverschwendung und
> sollte nur in Ausnahmefällen benutzt werden, wenn man weiß, was man tut.
Du weiß nicht, wie groß seine Struktur ist, und was er im selben Block
sonst noch an Auto-Variablen anlegt. Sind es sonst keine, ist ein extra
link/unlk u.U. nicht wesentlich kleiner, dafür aber langsamer.