Warum heißt es immer, der Stack sei schneller als der Heap?

[Stannis]

Sofern Ich einfach eine Adresse habe, kann Ich direkt auf jeden Speicherbereich zugreifen, unabhängig davon ob Stack oder Heap. Ich nehme an, dass damit nicht die Speicherzugriffszeit gemeint ist, sondern das Allokieren. Arrays auf dem Stack können einfach draufgeknallt werden, während malloc (unter C) erstmal verkettete Listen nach freien Bereichen durchsuchen muss. Demnach ist der Zugriff auf Speicher vom Tempo her immer gleich, nur das Anlegen von neuem Speicher zur Laufzeit kann unterschiedlich lange dauern.
Sehe Ich das richtig, oder gehört noch mehr dazu?

Bonusfrage:
Linus Torvalds meint, dass die Nutzung von Arrays dynamischer Länge langsameren Code verursacht: Warum sei dem so? Dynamische Arrays kommen ja auf den Stack.

 

[new Account()]

Sehe Ich das richtig, oder gehört noch mehr dazu?

Ich denke du meinst es richtig

Dynamische Arrays kommen ja auf den Stack.

Was für dynamische arrays?

 

[Stannis]

Na

int i;
scanf("%i", &i);
float array[i];
/* bzw.
 * float *arr = alloca(i);
 */

 

[new Account()]

EDIT: Wenn du die aus C99 meinst, dürfte das wohl weiterhelfen: https://softwareengineering.stackexchange.com/questions/279565/what-is-vla-and-how-it-is-implemented

TLDR: Hängt vom Compiler ab, da es nicht festgelegt ist, wo das array allokiert wird.

 

[Faust2011]

Ich weiß nicht, ob ich Deine Frage(n) richtig verstehe, aber ich versuchs mal mit einer Antwort.

Arrays auf dem Stack können einfach draufgeknallt werden, während malloc (unter C) erstmal verkettete Listen nach freien Bereichen durchsuchen muss

Die Zugriffszeit auf den Stack ist vermutlich für die CPU deshalb schneller, weil das Zeugs meistens direkt in Registern liegt und damit ein vielfaches schneller gelesen/geschrieben werden kann also der Zugriff aufs DRAM.

dass die Nutzung von Arrays dynamischer Länge langsameren Code verursacht

Dynamische Arrays sind meistens als verkettete Listen implementiert, d.h. die Elemente der Liste liegen nicht direkt hintereinander im Speicher. Für Zugriffe muss dann meist die CPU immer wieder bis raus aufs DRAM gehen (die Daten sind ja wie folgt im Zugriff der CPU: Register -> Caches -> DRAM mit jeweils längeren Zugriffszeiten). Bei statischen Arrays kann die Zieladresse des gewünschten Elements direkt berechnet werden und dementsprechend sollte es sich schneller ver/bearbeiten lassen.

 

[new Account()]

@Faust2011 Lies mal den Eingangspost nochmal genau durch

 

[Faust2011]

Hilf mir mal auf die Sprünge

 

[new Account()]

Es geht um die Allokierung, was er auch nochmal explizit erwähnt. Nicht um den Zugriff auf den Speicher.

 

[Stannis]

Ich würde es ohnehin anzweifeln, dass Kram ausm Stack eher im Cache vorgehalten wird. Caches arbeiten sinnvollerweise so, dass alle Speicherbereiche, auf die sehr häufig zugegriffen wird, vorsorglich im Cache gehalten werden – egal ob Stack, Heap oder TXT-segment

 

[Faust2011]

Ok, dann probiers ich mal andersrum.

Arrays auf dem Stack können einfach draufgeknallt werden

Das macht in der Praxis eigentlich niemand, denn Parameter an eine Funktion werden alle als "call by reference" übergeben und nicht "call by value". Konkret bedeutet das, dass nur die Adresse auf den Beginn des Arrays/die Struktur übergeben wird und eben nicht die eigentlichen Elemente.

während malloc (unter C) erstmal verkettete Listen nach freien Bereichen durchsuchen muss

malloc macht doch nichts anderes, als es an das Betriebssystem zu delegieren. Unter Linux geht das letztlich beispielsweise über die libc und dann reserviert Dir der Kernel einen passenden Speicherbereich. Keine Ahnung, wie gut das letztlich optimiert ist. Linux nutzt da beispielsweise ein copy-on-write, d.h. solange keine modifizierenden Änderungen an Deinem Array stattfinden, sieht Deine angesprungene Methode erstmal nur die Liste, wie sie der Aufrufer in Richtung Stack gepushed hat. Diese Operation ist dann entsprechend verdammt billig bzgl. Ausführungszeit.

 

[new Account()]

Ich würde es ohnehin anzweifeln, dass Kram ausm Stack eher im Cache vorgehalten wird.

Hmm, der Stack hat hier einen kleinen Bonus: Da die aktuell benutzten Addressen nicht zufällig sind, sondern immer etwa an der selben Stelle (beim Stackende), ist der Speicher vom Stack einfacher vorhersehbar und daher Cachefreundlicher (imho)

 

[nullPtr]

malloc macht doch nichts anderes, als es an das Betriebssystem zu delegieren.

Dem ist nicht so, bzw. bedingt. Die Zeiten, in denen Malloc einfach den program break versetzt hat, sind vorbei. Es kann durchaus noch sein, dass wenn man einen demnach großen Speicherbereich anfordert, unter POSIX mmap(2) verwendet wird. Aber die Freispeicherliste selbst ist z.B. für C in der C-Runtime der jeweiligen C-Standardbibliothek implementiert.

Klar ist, dass das Durchlaufen und Verwalten der Freispeicherliste Zeit kostet. Es gibt im Internet diverse Benchmarks der verschiedenen Malloc-Implementierungen, es gibt extra Bibliotheken, die für Multithreading Core-affinen Speicher liefern, etc.

Übrigens wird in der C-Spezifikation nie Stack/Heap erwähnt, sondern nur automatisch und nicht-automatisch verwalteter Speicher. Stack/Heap sind die Implementierungen dieser Konzepte.

Nun ist die Implementierung eines Arrays auf dem Stack, wenn es eine zur Compilezeit konstante Größe hat ziemlich trivial: Der Stackpointer wird einfach um die Array-Größe weiter geschoben. Der freie Bereich ist dann für das Array. Da das Array fixe Größe hat, bleibt im Code sonst alles wie es ist Hier empfiehlt es sich, mal ein bisschen Assembly anzuschauen, z.B. auf godbolt.org.

Wenn man allerdings ein VLA auf dem Stack hat, ist die Größe nicht mehr Compilezeit-Konstant. Das sorgt dafür, dass der Kompiler keine Optimierungen, die die Größe betreffen mehr einfließen lassen kann. Siehe z.B.: https://gcc.godbolt.org/z/IMdrI9
Außerdem sind die Adressen nicht mehr Konstant, z.B. bei a[n-i] und können damit nicht zur Kompilezeit in die Assembly geschrieben werden. Da muss zur Laufzeit rumgerechnet werden.
Außerdem kann es auch sein, dass andere Code-Teile in Mitleidenschaft gezogen werden, wenn der Kompiler z.B. eine Variable nach einem VLA auf den Stack legen sollte, hat deren Adresse dasselbe Problem. Das dürften mitunter Gründe für Torvalds Aussage sein.

Generell sollte man mit VLAs sehr vorsichtig sein und sie nur benutzen, wenn man sicher weiß, dass der erforderliche Speicher vorhanden ist. Eine gängige Stack-Größe sind 8 MB. Es gibt keine Möglichkeit festzustellen, ob eine VLA-Allokation erfüllt werden kann bzw. konnte (wie z.B. bei malloc). Das Programm geht normalerweise einfach mit einem Segfault baden.

 

[Faust2011]

Hier empfiehlt es sich, mal ein bisschen Assembly anzuschauen, z.B. auf godbolt.org.

Das ist ja mal eine klasse Seite. Ich kannte das bisher nur für Javascript-Snippets und auch SQL. Es gibt doch tatsächlich für fast alles aus der IT eine Snippets-Seite

 

[new Account()]

Godbolt kompiliert C++.

 

[nullPtr]

Das ist richtig. Gccs g++ unterstützt allerdings VLAs.

 

[Stannis]

@nullPtr Coole Antwort! Weißt Du, warum die Stack-Größe im Vergleich zum Heap überhaupt begrenzt ist? Der Heap wächst im virtuellen Speicher rauf, der Stack runter, und dazwischen ist die Finst- äh, Leere. Ergo machts keinen Sinn, dem Stack ein Limit zu geben – denn ob mir nun der Stack in den Heap reinwächst oder umgekehrt ist wurst; Fehler ist Fehler.

 

[Hancock]

Der Stack ist begrenzt, weil es mehr als einen Stack gibt (Multithreading) und man so am Anfang eine Größe reservieren muss. Auch ist "Leere" nicht umsonst: Overhead der virtuellen Speicherverwaltung.

 

[Multivac]

Der Stack ist nicht vollständig. commite vs reserve sind die begriffe nach denen du suchen solltest. Warum sollte der overhead für den stack groesser sein als fuer einen heap? ist also Quatsch. in der Regel ist am ende des stacks eine spezielle page die du nicht beschreiben solltest "stackguard", diese wird benutzt um stackoverflows und solche dinge zu erkennen. unter windows ist ein stack von 1GB glaube ich das maximum oder etwas in dieser
Groessenordnung. Das ist alles Altlast von 32Bit zeien, da war der Adressraum am ende schon ziemlich klein. der linker muss ja auch andere dinge wie andere libraries berücksichtigen. die brauchen auch Virtuelle Adressen. Ich denke heute geht es darum fehler moeglichst schnell zu finden z.b. inf Rekursion gibt der sehr schnell einen fehler wenn der stack klein ist. oder beim debuggen da willst du heute halt direkt sehen wie welche functionen aufgerufen wurden. man kann die gleichen Tabellen mehrfach benutzen wenn man versteht wie die Datenstruktur hinter dem cr3 reg aussieht.
https://en.wikipedia.org/wiki/Control_register#/media/File:X86_Paging_4K.svg

 

[Hancock]

Jede 4k Page hat ein paar Byte, die im Kernel verbraucht werden (reserved oder commited ist da erst mal egal), ergo 1 GB Stack würde gleich fix ein paar MB im Kernel kosten (hugeTBL mal außen vor). Macht daher keiner.

Der Standardstacksize ist unter Windows 1 MB. Das ist zwar historisch gewachsen, aber auch sinnvoll, da viele Programme ne Menge Threads erzeugen. Bei mir aktuell 191 Prozesse, 3100 Threads => ca. 20 Threads pro Prozess.

Aber warum sind Stackvariablen schneller: Der Compiler kann diese deutlich besser optimieren, bei Variablen auf dem Heap kann er aliasing nicht so einfach ausschließen, und Multithreading mit globalen Variablen ist ein Desaster.
Was kann der Compiler optimieren, ein paar Beispiele:

• Redundante Variablen können weggelassen werden
• Function inlining
• Lightweight leaf functions
• Static analysis für Optimierungen

Warum kann er das: Das Layout und die Anordnung von Stackvariablen sind nicht vorgeschrieben, daher kann er tun und lassen, was er will (ABI mal außen vor). Beim Heap kann es ja immer mal sein, dass jemand von außen genau das Layout erwartet, was im Quelltext vorgegeben ist, bei einer Funktion auf dem Stack ist das i.d.R. immer UB.

 

[Simple Man]

Der Stack (Stapel) ist schneller, weil die "relevanten" Dinge immer ganz oben sind. Stell dir vor, du hast einen Stapel Zettel. Ein neuer Zettel kommt einfach ganz oben drauf. Und du kannst auch vorerst nur auf diesen einen Zettel zugreifen. Möchtest du andere Zettel darunter haben, musst du erst Zettel vom Stapel oben runter nehmen. Es ist ein solider Block, der an einer Seite entweder größer oder kleiner wird.

Bei einem Heap kannst du den neuen Zettel irgendwo zwischen die anderen Zettel (=Speicherstellen) rein geben. Dadurch muss aber neuer Speicher dafür zur Verfügung gestellt werden. Dauert Zeit. Und aus dem Heap kannst du auch irgendwelche Zettel rausnehmen (Bauchschuss), musst erst suchen, aber dadurch enstehen auch "Löcher" im Speicher. Dein Block bekommt Löcher und plötzlich soll er irgendwo in der Mitte anwachsen. Deswegen ist das Ding auch dynamisch weil du Zettel hinzugeben und rausnehmen kannst wie es dir passt.