Cee Stack Konzept
 
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern

Bei der Performance-Optimierung von C-Programmen ist ein wiederkehrendes Muster die Vermeidung von dynamischer Speicherbeschaffung mittels malloc/free. Die Verwendung des auto-Bereichs (im Volksmund Stack genannt) ist oft einfacher und immer schneller.
Das Stack-Konzept
Ich trete ganz entschieden dafür ein, den Speicherbedarf eines C-Programms soweit wie möglich im Stack anzulegen.
Natürlich gibt es Fälle, wo man malloc() unbedingt braucht - die kommen aber vergleichsweise recht selten vor! (--HelmutSchellong)

Vorteile:

Nachteile: Erklärungen zur hohen Geschwindigkeit:
Ein Standard-Stackframe (iX86, masm-Syntax)
Die folgenden Maschinensprachbefehle sind der typische "Rahmen" für jede C-Funktion auf einem Intel-Prozessor (esp=Stack pointer):
push  ebp
mov   ebp, esp
sub   esp, 24       ;z.B. 24 Byte Stack reserviert
mov   eax, [ebp+8]  ;erstes Arg
;...
mov   esp, ebp
pop   ebp
ret
Wie man sieht, ändert der Subtraktionswert nichts am Zeitbedarf! (@1)
Ob nun 24 oder 650000 subtrahiert wird, ist (fast immer) egal.
Oft sind sogar alle Instruktionen für den Stackframe pauschal vorhanden, egal ob man den auto-Bereich benutzt oder nicht. Beispielsweise verwenden die Compiler den Stack auch für sich selbst, wenn z.B. die Anzahl der Register knapp wird.
Die "Nullzeit" ist folglich durchaus zutreffend!

Beispielsweise der Borland Builder hat u.a. folgende 4 Optionen:

 -lS:0xhhhhhhhh    Stack reserviert (1 MB)
 -lSc:0xhhhhhhhh   Stack zugewiesen (8 KB)
 -lH:0xhhhhhhhh    Heap  reserviert (1 MB)
 -lHc:0xhhhhhhhh   Heap  zugewiesen (4 KB)
 (Defaults)
malloc() besorgt hier Speicher vom Heap.
sub esp,n besorgt Speicher vom Stack.
(je 1 MB maximal)

Die Verwendung von malloc()/... war und ist für mich ein Notnagel!
malloc() soll nur dort verwendet werden, wo es notwendig ist.
Stack-lastige Programme sind fast immer vergleichsweise kompakt, sicher, stabil und ultraschnell,
denn malloc/free ist ein vergleichsweise langsamer Mechanismus.
Immerhin sind malloc/realloc/free ausgewachsene Library-Funktionen.
malloc/free ist ein vergleichsweise fehleranfälliger Mechanismus - die Leute ' mallocen sich zu Tode'

Über die richtige Verwendung von malloc(), calloc(), realloc() und free() herrschen viele falsche Vorstellungen, gerade bei Einsteigern. Im Umgang mit diesen Funktionen können mehr Fehler gemacht werden als im Umgang mit lokalen Variablen -- kw

--HelmutSchellong


Zustimmende Anmerkungen
Es ist auch interessant, daß im neuen C99-Standard eine der wichtigen Neuerungen, die VLAs (Cee99 VLA) genau in diese Richtung stößt. VLAs erlauben die Erzeugung von Datenstrukturen am Stack, deren Dimension erst zur Laufzeit (bzw. zum Zeitpunkt des Funktionsaufrufs über Parameter) festgelegt wird. Auf diese Weise können die Vorteile der stackorientierten Arbeitsweise noch besser genutzt werden.--hl

Bisher hat die Funktion alloca() diese Aufgabe übernommen.
(alloca ist bereits 1983 im BSD-Bereich aufgetaucht.)
AllocA ist oft compiler-intern.
In den cc der SCO-Unix-Systeme: Option -K alloca,no_alloca
Im gcc ist alloca IMO am besten -intern- implementiert.
In den Quellen des gcc wird alloca sehr intensiv benutzt.

Wenn sie nicht compiler-intern ist, ist sie gefährlich !.
Man muß dann sicherstellen, daß der Compiler konservativ/klassisch mit dem Stack-Pointer umgeht (z.B. Optimierungen wegnehmen).

alloca() ist nicht ANSI-C und nur halbwegs portabel.
VLAs sind sicher auch als Versuch zu sehen, einen noch besseren, portablen und im Standard verankerten Zugangsweg für den Stackspeicher zu schaffen (und damit alloca() zu ersetzen).--hl

Legt ein Programm mit lokalen offenen Feldern vielleicht doch die Felder auf den Heap und nur die Zeiger auf den Stapel? Beim gcc sieht man (per Option -S), daß gcc nur auf dem Stapel arbeitet. Wie kann er dann eine feste Struktur der lokalen Variablen auf dem Stapel sicherstellen? Nur diese garantiert einen Zugriff mit konstanter Zeit auf eine lokale Variable. Wahrscheinlich legt das Programm zuerst die Felder auf den Stapel und darunter die lokalen Variablen und Zeiger auf die offenen Felder. Dass auf dem Stapel im Falle offener Felder nur Zeiger im Variablenblock liegen, kann man auch ohne Disassembler nachprüfen. Man deklariere dazu eine Variable a und ein Feld b. Dann holt man sich einen Zeiger auf a, erhöht den Adresswert und schreibt an die neue Position. Hat das Feld b feste Größe, ändert sich durch diese Aktion sein Inhalt, hat das Feld b dynamische Größe, gibt es beim Zugriff auf das Feld über den jetzt zerstörten Zeiger einen illegalen Speicherzugriff. -- HenningThielemann

Die VLAs haben keine dynamische Größe, sondern eine feste, die aber erst zur Laufzeit bestimmt wird. Der Compiler kann sich also noch darauf verlassen, dass es einen festen Stackframe gibt, wie groß dieser ist, weiß er aber nicht mehr. Das macht aber nichts, weil ja sowieso immer relativ zum Stackende adressiert wird.

Felder, die wachsen können, gleichgültig ob als Bytehaufen oder als Datenstruktur (wie ein Rope) implementiert, muss man selbstredend im Heap anlegen. Ein echter C-Programmierer würde natürlich bezweifeln, dass man so etwas überhaupt braucht...


Kritische Anmerkungen
Vorsicht bei Systemen mit stark begrenztem Stack. Z.B. war im DOS die Default-Stack-Größe vieler Compiler bei 2 KB. Es kann dann schnell zu Stack-Overflow-Problemen bzw. Portabilitätsproblemen kommen.

Antwort: Kein Problem (DOS16-bcc,small,medium):--hs

 extern unsigned _stklen=30*1024;
 extern unsigned _heaplen=1*256;
 extern unsigned __brklvl;
Ja, aber das Problem besteht darin, dass viele UNIX-Programme schon alleine wegen des verschwenderischen Speicherumgangs unter DOS (mit oder ohne Stack) nur schwer zum Laufen gebracht werden können.

Unix-Programme sollten aber nicht pauschal DOS-portabel geschrieben werden.
Wenn man das von vornherein einplanen kann - umso besser.


Beispiele:

malloc-Bemühungen eines Anfängers:

Bemühung A:
unsigned char* readline(int fd)
{
        int i;
        unsigned char *line;

        line=(char*)malloc(1);
        for(i=1;line[i]!='\n' || line[i]!='#';i++)
        {
                        read(fd,&line[i],1);
                        line = realloc(line,1);

        }

return(line);
}

Bemühung B:
unsigned char* readline(int fd) {

   int chars=0, xbuf=0, xbufc=1, stop=0;
   int wwhite=1, iwhite=0;
   long i=0, j=0, size=0, whitec=0;
   unsigned char *line, *clean;

   line=calloc(16,1);
   xbuf=16;
   do {
           chars=read(fd,&line[i],1);
           if(chars<=0)
           {
               fprintf(stderr,"Error while reading from file\n");
               stop=1;
           }
           i+=chars;
           xbuf--;
           if(xbuf==0) {
           line = realloc(line, xbufc * 16);
           xbufc++;
           xbuf=16;
           }
   } while(!stop && line[i-1]!=';' && line[i-1]!='#');

   line[i] = '\0';
   size = xbufc * 16 - (xbuf+1) ;
   realloc(line, size);
   printf("Debug: *%i* Buffers allocated ... *%i* bytes overhead\n",xbufc,xbuf);
   printf("Debug: Size: *%i* Data: *%s*\n",size,line);
   fflush(stdout);
   clean=calloc(size,1);
   i = 0;
   do {
       if(line[i]==' ') iwhite = 1;
       else if(line[i]=='\t') {
           iwhite = 1;
           line[i] = ' ';
           whitec++;
       }
       if((wwhite + iwhite) == 2) {
               j--;
               whitec++;
       }
       clean[j] = line[i];
       i++;
       j++;
       wwhite = iwhite;
       iwhite = 0;
   } while (i<size);

   printf("\nDebug: Cleaned: *%i* Data: *%s*\n",whitec,clean);
   fflush(stdout);
return(clean);
}

Komischerweise sehe ich solche extrem grauenhaften und mit Fehlern aller Art gespickten Beispiele (A,B) immer nur im Zusammenhang mit malloc()/...
Deshalb auch der Ausspruch: "... mallocen sich zu Tode."

Ich gewinne den Eindruck, als gelte es als schick, zuallererst malloc zu können!

Unerfahrene Programmierer sollten erstmal mit auto-Objekten und globalen Objekten üben!

--HelmutSchellong

Ist mir auf einmal schlecht. Bemühung A ist einfach unglaublich dumm und Bemühung B macht einen klassischen Fehler: lineares Wachstum des Puffers. Er sollte exponentiell wachsen, das erhält lineares Laufzeitverhalten. Dieser "Anfängerfehler" war übrigens in frühen Versionen der MFC enthalten und hat vermutlich dafür gesorgt, dass C++ den Ruf hat, viel langsamer als C zu sein. Davon abgesehen gehört solcher Code in eine Bibliothek ausgelagert, sowas möchte man nicht täglich ansehen müssen.

@Helmut: dein Programm ist fehlerhaft. Für Zeilenlängen >2048 Zeichen produziert es Müll (aber zumindest keinen Pufferüberlauf).

Na klar ist das kein Produktionskode!
Ist gänzlich ungetestet und stellt darauf ab, daß keine Zeile länger als oben sichtbar angegeben ist.

Wohl wahr, aber trotzdem ein schlechtes Beispiel, dass später durch Copy-And-Paste zu Produktionscode mutiert. Ja, es gibt einen haufen Programmierer, die so etwas dummes tun; vergleiche auch Bemühung A...

Ich finde, willkürliche, endliche Puffer haben in einem Programm nichts zu suchen. Es ist ja okay, einen Datenstrom konzeptionell als Folge von Puffern zu betrachten, einfach aus Effizienzgründen. Sowas gehört aber in eine Bibliothek -- und die Standardbibliothek hat das ja schon, es heißt FILE! Zur Repräsentation einer "Zeile" oder irgendeiner anderen semantischen Einheit nimmt man was anderes. Ich mag ja ext::rope in C++... leider nicht Standard, aber verbreitet. In C würde ich vielleicht Cords empfehlen.


Anhang:
Diskussionen
Diverses siehe RantArchiv.
KategorieOptimierung
StartSeite | Neues | TestSeite | ForumSeite | Teilnehmer | Kategorien | Index | Hilfe | Einstellungen | Ändern
Text dieser Seite ändern (zuletzt geändert: 12. April 2014 23:09 (diff))
Suchbegriff: gesucht wird
im Titel
im Text