Ich habe eben wieder im Namen der Optimierung einen Hack durchgeführt, durch den ich mich enorm schmutzig fühle. Aber statt weinend unter der Dusche zu liegen poste ich solche Sachen in Zukunft hier und hoffe, dass mich die Beichte erleichert.
Das wird so ähnlich wie der Mikrooptimierungs-Log; mit dem Unterschied, dass ich die Sachen hier drin nicht empfehle wenn ihr nicht genau wisst, was ihr tut. Oder in die Ecke gedrängt seid, sowas unbedingt zu brauchen.
Einträge folgen in den nächsten Stunden (wenn ich damit fertig bin, mich zu ohrfeigen).
[C++] Schmutzige Tricks
-
Krishty
- Establishment
- Beiträge: 8267
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
[C++] Schmutzige Tricks
Zuletzt geändert von Krishty am 01.12.2013, 15:16, insgesamt 1-mal geändert.
-
Krishty
- Establishment
- Beiträge: 8267
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
1. Auf dem Stapelspeicher allokieren bis er überläuft
Ich hasse dynamische Allokation via new. Ich hasse sie nicht von sich aus, sondern wegen der Art, wie sie in C++ implementiert ist: als externe Wirkung. Nehmen wir das folge Stück Maschinentext:
auto x = new int;
delete x;
Jeder Programmierer erkennt sofort, dass diese Zeilen sinnlos sind: Die erste tut etwas, und die zweite macht es wieder rückgängig. Vernünftige Sprachen würden das wegoptimieren. In C++ ist das nicht möglich.
Warum? Weil new und delete in C++ auf externe Funktionen verweisen. Üblicherweise rufen sie (unter Windows) HeapAlloc() und HeapFree() auf: Das sind die Funktionen der Windows-Speicherverwaltung, die euch Speicher beschaffen und wieder freigeben.
Der Knackpunkt ist, dass wir als Menschen zwar wissen, was diese Funktionen tun; aber der Compiler nicht. Für ihn sind das unbekannte Code-Stücke, die eingebunden werden: kein Unterschied zu CreateWindow() oder CreateFile(). Es steht ja nicht einmal fest, dass sie tatsächlich aufs Betriebssystem verweisen – vielleicht verweisen sie auf eine Debug-Bibliothek, die eure Speicherallokationen loggt. Es ist einfach nicht zu sagen.
Darum tut der Compiler das, was unter diesem Gesichtspunkt richtig ist: „Oh mein Gott ich weiß nicht was die Funktion hinter new macht; vielleicht zeigt sie ein Fenster an oder sonst was Wichtiges; bloß nicht wegoptimieren!“. In anderen Sprachen geht das, weil die Sprache dort genau festlegt, was new tut. Aber in C++ ist die Speicherverwaltung nunmal anpassbar. Und dafür müssen wir bezahlen.
Es geht weiter: Der Compiler kann nicht bestimmen, worauf der Zeiger zeigt, den new zurückgibt. Idealerweise sollte er eine neue, ungekannte Adresse sein. Aber vielleicht hat jemand einen Pool-Allocator geschrieben, der einfach ein Stück eines vorher allokierten Arrays zurückgibt? In diesem Fall ändert sich auch der Inhalt des Pools, wenn man in die neue Adresse schreibt. Solche Dinge muss der Compiler beachten. Darum kann der Compiler, sobald dynamisch allokiert wurde, nicht mehr genau bestimmen, welcher Speicher im Programm welchen Wert enthält.
tl;dr: Dynamische Allokation ist doof und wird schlecht optimiert. Also allokiere ich so ziemlich alles auf dem Stack. Der Compiler weiß, wo die Dinge liegen, und er kennt ihren Inhalt. Das lässt sich perfekt optimieren.
– Aber was ist, wenn man nicht weiß, wie viele Daten kommen? Man kann keine dynamischen Arrays auf dem Stapel haben!
Doch, kann man. Der C++-14-Standard übernimmt Arrays variabler Größe aus dem C99-Standard. Diese Funktionalität ist auch heute schon via _alloca() verfügbar. damit könnt ihr lokalen Arrays tatsächlich beliebige Größen zuweisen.
Ich mache es trotzdem nicht, weil es ein Register verschwendet: Normalerweise weiß der Compiler, wo welche Variable in einer Funktion liegt, und kennt dadurch auch ihre Adresse. Aber sobald ein dynamisches lokales Array in einer Funktion liegt, ist die Position der Variablen im Speicher von der Größe des Arrays abhängig. Damit lokale Variablen trotzdem adressiert werden können, muss gespeichert werden, wie groß das dynamische lokale Array ist. Dafür stellt der Compiler üblicherweise ein Register ab. Jeder Zugriff auf andere lokale Variablen erfolgt nun nicht mehr durch eine feste Adresse im Maschinentext, sondern wird zur Laufzeit über das zusätzliche Register berechnet, das dann nicht mehr zur Verfügung steht. Die gesamte Funktion wird minimal langsamer.
Darum allokiere ich einfach ein Array des größten sinnvollen Umfangs und benutze nur den Speicher am Anfang, den ich auch brauche.
– Aber der Stack ist doch nur 1 MiB groß! Das stürzt doch ab, wenn man größere lokale Arrays anlegt!
Ja genau. Aber das lässt sich einstellen: In Visual C++ findet sich unter den Projekt-Properties → Linker → System die Stack Reserve Size. Setzt man die hoch, reserviert Windows beim Start des Programms einen entsprechend großen Stapel. Bei mir sind das z.B. gerade ungefähr 40 MiB. Und voilà: Ich kann ein 35-MiB-Array für alle meine Assets direkt in der main() als lokale Variable anlegen und alles funktioniert perfekt!
– Ist das nicht Speicherverschwendung?
Ja – aber aus komplett anderen Gründen als man zuerst denkt! Und sie lässt sich vermeiden. Darum wird es im nächsten Beitrag gehen.
Ich hasse dynamische Allokation via new. Ich hasse sie nicht von sich aus, sondern wegen der Art, wie sie in C++ implementiert ist: als externe Wirkung. Nehmen wir das folge Stück Maschinentext:
auto x = new int;
delete x;
Jeder Programmierer erkennt sofort, dass diese Zeilen sinnlos sind: Die erste tut etwas, und die zweite macht es wieder rückgängig. Vernünftige Sprachen würden das wegoptimieren. In C++ ist das nicht möglich.
Warum? Weil new und delete in C++ auf externe Funktionen verweisen. Üblicherweise rufen sie (unter Windows) HeapAlloc() und HeapFree() auf: Das sind die Funktionen der Windows-Speicherverwaltung, die euch Speicher beschaffen und wieder freigeben.
Der Knackpunkt ist, dass wir als Menschen zwar wissen, was diese Funktionen tun; aber der Compiler nicht. Für ihn sind das unbekannte Code-Stücke, die eingebunden werden: kein Unterschied zu CreateWindow() oder CreateFile(). Es steht ja nicht einmal fest, dass sie tatsächlich aufs Betriebssystem verweisen – vielleicht verweisen sie auf eine Debug-Bibliothek, die eure Speicherallokationen loggt. Es ist einfach nicht zu sagen.
Darum tut der Compiler das, was unter diesem Gesichtspunkt richtig ist: „Oh mein Gott ich weiß nicht was die Funktion hinter new macht; vielleicht zeigt sie ein Fenster an oder sonst was Wichtiges; bloß nicht wegoptimieren!“. In anderen Sprachen geht das, weil die Sprache dort genau festlegt, was new tut. Aber in C++ ist die Speicherverwaltung nunmal anpassbar. Und dafür müssen wir bezahlen.
Es geht weiter: Der Compiler kann nicht bestimmen, worauf der Zeiger zeigt, den new zurückgibt. Idealerweise sollte er eine neue, ungekannte Adresse sein. Aber vielleicht hat jemand einen Pool-Allocator geschrieben, der einfach ein Stück eines vorher allokierten Arrays zurückgibt? In diesem Fall ändert sich auch der Inhalt des Pools, wenn man in die neue Adresse schreibt. Solche Dinge muss der Compiler beachten. Darum kann der Compiler, sobald dynamisch allokiert wurde, nicht mehr genau bestimmen, welcher Speicher im Programm welchen Wert enthält.
tl;dr: Dynamische Allokation ist doof und wird schlecht optimiert. Also allokiere ich so ziemlich alles auf dem Stack. Der Compiler weiß, wo die Dinge liegen, und er kennt ihren Inhalt. Das lässt sich perfekt optimieren.
– Aber was ist, wenn man nicht weiß, wie viele Daten kommen? Man kann keine dynamischen Arrays auf dem Stapel haben!
Doch, kann man. Der C++-14-Standard übernimmt Arrays variabler Größe aus dem C99-Standard. Diese Funktionalität ist auch heute schon via _alloca() verfügbar. damit könnt ihr lokalen Arrays tatsächlich beliebige Größen zuweisen.
Ich mache es trotzdem nicht, weil es ein Register verschwendet: Normalerweise weiß der Compiler, wo welche Variable in einer Funktion liegt, und kennt dadurch auch ihre Adresse. Aber sobald ein dynamisches lokales Array in einer Funktion liegt, ist die Position der Variablen im Speicher von der Größe des Arrays abhängig. Damit lokale Variablen trotzdem adressiert werden können, muss gespeichert werden, wie groß das dynamische lokale Array ist. Dafür stellt der Compiler üblicherweise ein Register ab. Jeder Zugriff auf andere lokale Variablen erfolgt nun nicht mehr durch eine feste Adresse im Maschinentext, sondern wird zur Laufzeit über das zusätzliche Register berechnet, das dann nicht mehr zur Verfügung steht. Die gesamte Funktion wird minimal langsamer.
Darum allokiere ich einfach ein Array des größten sinnvollen Umfangs und benutze nur den Speicher am Anfang, den ich auch brauche.
– Aber der Stack ist doch nur 1 MiB groß! Das stürzt doch ab, wenn man größere lokale Arrays anlegt!
Ja genau. Aber das lässt sich einstellen: In Visual C++ findet sich unter den Projekt-Properties → Linker → System die Stack Reserve Size. Setzt man die hoch, reserviert Windows beim Start des Programms einen entsprechend großen Stapel. Bei mir sind das z.B. gerade ungefähr 40 MiB. Und voilà: Ich kann ein 35-MiB-Array für alle meine Assets direkt in der main() als lokale Variable anlegen und alles funktioniert perfekt!
– Ist das nicht Speicherverschwendung?
Ja – aber aus komplett anderen Gründen als man zuerst denkt! Und sie lässt sich vermeiden. Darum wird es im nächsten Beitrag gehen.
Zuletzt geändert von Krishty am 03.01.2014, 18:06, insgesamt 2-mal geändert.
-
Krishty
- Establishment
- Beiträge: 8267
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
2. Ins Regal stellen, aber bloß nie anfassen!
Um überhaupt einschätzen zu können, wie man Speicher verschwendet, muss man mit der Funktionsweise von virtuellem Speicher vertraut sein. Wer das ist, kann das hier überspringen:
Auf das gigantische Stack-Array übertragen bedeutet das: So lange die hinteren Einträge des Riesen-Arrays nicht benutzt werden, verbrauchen sie keinen Speicher. Theoretisch. Praktisch kommt nämlich was anderes dazwischen …
Um überhaupt einschätzen zu können, wie man Speicher verschwendet, muss man mit der Funktionsweise von virtuellem Speicher vertraut sein. Wer das ist, kann das hier überspringen:
- Die meisten Leute denken: Wenn sie in einen Wert im Speicher schreiben, wandert die Zahl aus der CPU direkt an die Adresse der Variable im RAM. Tatsächlich steckt da aber mehr hinter; viel mehr.
Zu allererst ist der Speicher in Pages unterteilt, deutsch Kacheln, oder neudeutsch Seiten. Auf den gängigen PCs ist jede Kachel 4 KiB (4096 B) groß. Startet ihr einen 32-Bit-Prozess, legt das Betriebssystem (Achtung: stark vereinfacht!) eine Tabelle von 1.048.576 Einträgen an: ein Eintrag für jede 4-KiB-Kachel der 4 GiB, die euer Prozess adressieren kann. Diese Tabelle nennt sich Page Table, und sie übersetzt die Adressen, die ihr im Programm seht, in physische Adressen (z.B. Adressen im RAM). Jedes Mal, bevor die CPU einen Wert an die Adresse, die ihr im Programm seht, schreibt, schlägt sie dort nach, welche Adresse wirklich gemeint ist und schreibt dann dort hin. Ebenso beim Lesen, und sogar beim Lesen der Befehle, bevor die CPU sie ausführt.
Das ist erst einmal mordsmäßiger Aufwand bei jedem einzelnen Speicherzugriff; hat aber dermaßen viele Vorteile, dass es sogar Smartphones schon so machen. Die wichtigsten Vorteile sind, dass man Speicher trennen kann (zwei Prozesse wollen beide auf die Adresse 0x12340000 zugreifen, aber in ihren Tabellen stehen unterschiedliche RAM-Adressen, so können die Programme nicht gegenseitig ihren Speicher sehen oder gar überschreiben) und dass man Speicher teilen kann (zwei Programme benutzen die selbe DLL, dann wird sie nur einmal in den RAM geladen und diese eine RAM-Adresse wird beiden Prozessen in ihre Seitentabellen geschrieben).
Nun stehen da nicht nur Adressen, sondern auch Flags – z.B., ob die Adresse nur lesbar oder auch beschreibbar ist. Außerdem ein Flag, das Auslagerungsdateien ermöglicht: Geht dem System der RAM aus, nimmt es eine unbenutzte 4-KiB-Kachel eines Prozesses; schreibt sie in die Auslagerungsdatei; ändert den Eintrag von einer RAM-Adresse zu einer Adresse auf der Festplatte; und setzt das „ist ausgelagert“-Flag. Dann sind wieder 4 KiB RAM für Wichtigeres freigeworden.
Bei jedem Zugriff auf eine Speicheradresse liest die CPU erst einmal die Flags aus um zu sehen, ob sich die Adresse auf dem RAM oder die Festplatte oder sonstwas bezieht. Sobald etwas anomales passiert – etwa, dass ihr in eine Adresse schreiben wollt, für die das nur lesen-Flag gesetzt ist, oder dass eine Adresse nicht zugewiesen ist – löst die CPU eine Ausnahme (nicht zu verwechseln mit C++-Ausnahmen!) aus, die vom Betriebssystem behandelt wird. Dann erscheint euer gewohntes „0x0000000C: access violation writing location 0xF00“.
Für uns ist hier vor allem das Flag wichtig, das unterscheidet, ob der Speicher reserved oder committed ist. Wird Speicher allokiert, gibt euch das Betriebssystem nämlich überlicherweise eine Adresse zurück, verweist aber nicht auf den RAM. Die Kacheln hinter der Adresse, die ihr angefordert habt, sind nur reserviert. Erst, wenn ihr den Speicher tatsächlich lest oder beschreibt, bemerkt die CPU das Flag. Dann wird eine Ausnahme ausgelöst; die Kontrolle wird dem Betriebssystem übergeben; das sucht eine Adresse im RAM; weist der benutzten Kachel in der Page Table die frische RAM-Adresse zu; ändert das Flag von reserved zu committed; und gibt die Kontrolle an die CPU zurück, die das Programm normal fortsetzt.
(Klingt das nach viel Aufwand? Ist es auch. Darum müsst ihr, wenn ihr Benchmarks schreibt, unbedingt allen allokierten Speicher einmal beschreiben bevor ihr euer Benchmark startet. Sonst zählt ihr nämlich die Zeit, die das Betriebssystem zum Zuweisen der Adressen an tatsächlichen RAM braucht, mit!)
Auf das gigantische Stack-Array übertragen bedeutet das: So lange die hinteren Einträge des Riesen-Arrays nicht benutzt werden, verbrauchen sie keinen Speicher. Theoretisch. Praktisch kommt nämlich was anderes dazwischen …
-
Krishty
- Establishment
- Beiträge: 8267
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
3. Vorantasten wie ein Blinder beim Gruppensex
Dummerweise wird Stapelspeicher anders behandelt als dynamisch allokierter Speicher. Den exakten Grund kenne ich nicht; ich tippe auf Historisches (wer es weiß, soll es mir bitte hier schreiben :) ).
Und zwar gibt es extra für Kacheln des Stapelspeichers ein weiteres Flag: guard page.
Der Stapel wird erstmal nur reserviert; d.h., er bekommt einen Platz im Adressraum aber verweist nicht auf physikalischen Speicher (RAM). Die erste Kachel bekommt das guard page-Flag gesetzt.
Wird dann die erste Funktion aufgerufen, werden ihre Parameter auf den Stapelspeicher geschrieben. Beim Schreiben erkennt die CPU das guard page-Flag und löst eine Ausnahme aus, die dem Betriebssystem übergeben wird. Das prüft, ob der Stapel bis zur Maximalgröße gewachsen ist. Falls ja, wird eine Stapelüberlaufausnahme ausgelöst (und das Programm stürzt ziemlich sicher ab). Falls nicht, wird RAM für die beschriebene Kachel gesucht; das Flag wird gelöscht; die nächste Kachel bekommt das guard page-Flag gesetzt; und die CPU setzt die Ausführung normal fort.
Beim Programmstart:
g □ □ □ □ □ □ … □ □ □ × × × × …
Nach Aufruf der main():
■ g □ □ □ □ □ … □ □ □ × × × × …
↑main
Ein paar Aufrufe mehr:
■ ■ ■ ■ g □ □ … □ □ □ × × × × …
↑innerFunc
↑…
↑func2, func3
↑main
In einem tief verschachtelten Funktionsaufruf, kurz vorm Stapelüberlauf:
■ ■ ■ ■ ■ ■ ■ … ■ ■ g × × × × …
↑current
↑caller
↑main
Der Stapel kann zwar wachsen, aber nicht schrumpfen. Kurz vor Programmende, wenn die main() zurückkehrt, sieht der Stapel also immernoch so aus:
■ ■ ■ ■ ■ ■ ■ … ■ ■ g × × × × …
↑main()
Das wirft ein besonderes Problem auf: Wie wir sehen, kann der Stapel immer nur um eine Kachel, also 4 KiB, auf einmal wachsen. Was passiert, wenn eine Funktion mehr als 4 KiB an lokalen Variablen anlegt? Normalerweise müsste das Programm dann abstürzen, weil die Guard Page übersprungen wird und der Stapel inkonsistent wird …
… und hier kommt eines der am wenigsten bekannten Compiler-Features ins Spiel: Stack Probes. Eine Funktion, die viel Stapelspeicher verbraucht und die Guard Page überspringen würde:
void stackTerror() {
int huge[10000];
int bad = 1; // Crash
}
bekommt vom Compiler automatisch Stack Probes verpasst, die sicher stellen, dass der Stapel nie schneller als eine Kachel wächst:
void stackTerror() {
int huge[10000];
for(int i = 0; i < sizeof(huge); i += 4096) {
huge[i / sizeof(int)] = 0;
}
int bad = 1;
}
Dadurch tastet sich die Funktion Kachel für Kachel durch den Stapelspeicher, bis er die Größe erreicht haben muss, die sie maximal benutzen könnte. Das garantiert, dass der Stapel konsistent bleibt – und vernichtet die Sparstrategie, die virtueller Speicher verfolgt. Und es zerstört die Lokalität der Funktion, weil sie erstmal zig Kacheln im Speicher abläuft (und dadurch den Cache verpestet) obwohl das Abtasten nur beim ersten Mal nötig ist.
Hier kommt eine andere Linker-Einstellung von Visual C++ ins Spiel: Die Stack Commit Size. Der Name ist leicht irreführend, weil sie nicht wirklich dafür sorgt, dass die Größe auch committed wird – sie bestimmt, wo die Guard Page gesetzt wird. Gleicht die Stack Reserve Size der Stack Commit Size, liegt die Guard Page ganz hinten und Windows weist dem Stapelspeicher direkt beim Programmstart physische Adressen zu.
Stack Probes schaltet das aber nicht ab (weil der C++-Compiler nichts von den Einstellungen des später aufgerufenen Linkers weiß). Um sie loszuwerden muss man unter Properties → C/C++ → Command Line von Hand einfügen: /Gs1000000000 (was die Stack Probes für Funktionen mit weniger als 1 GB lokaler Variablen abschaltet).
So. Speicher wird immernoch verschwendet, aber dafür habe ich eine supertolle Leistung weil mein ganzer Speicher beim Programmstart einmal zugewiesen und dann nie mehr was allokiert wird. Aber ich habe dafür ein richtig fettes Problem geschaffen. Beim nächsten Mal wird es richtig schmutzig!
Dummerweise wird Stapelspeicher anders behandelt als dynamisch allokierter Speicher. Den exakten Grund kenne ich nicht; ich tippe auf Historisches (wer es weiß, soll es mir bitte hier schreiben :) ).
Und zwar gibt es extra für Kacheln des Stapelspeichers ein weiteres Flag: guard page.
Der Stapel wird erstmal nur reserviert; d.h., er bekommt einen Platz im Adressraum aber verweist nicht auf physikalischen Speicher (RAM). Die erste Kachel bekommt das guard page-Flag gesetzt.
Wird dann die erste Funktion aufgerufen, werden ihre Parameter auf den Stapelspeicher geschrieben. Beim Schreiben erkennt die CPU das guard page-Flag und löst eine Ausnahme aus, die dem Betriebssystem übergeben wird. Das prüft, ob der Stapel bis zur Maximalgröße gewachsen ist. Falls ja, wird eine Stapelüberlaufausnahme ausgelöst (und das Programm stürzt ziemlich sicher ab). Falls nicht, wird RAM für die beschriebene Kachel gesucht; das Flag wird gelöscht; die nächste Kachel bekommt das guard page-Flag gesetzt; und die CPU setzt die Ausführung normal fort.
Beim Programmstart:
g □ □ □ □ □ □ … □ □ □ × × × × …
Nach Aufruf der main():
■ g □ □ □ □ □ … □ □ □ × × × × …
↑main
Ein paar Aufrufe mehr:
■ ■ ■ ■ g □ □ … □ □ □ × × × × …
↑innerFunc
↑…
↑func2, func3
↑main
In einem tief verschachtelten Funktionsaufruf, kurz vorm Stapelüberlauf:
■ ■ ■ ■ ■ ■ ■ … ■ ■ g × × × × …
↑current
↑caller
↑main
Der Stapel kann zwar wachsen, aber nicht schrumpfen. Kurz vor Programmende, wenn die main() zurückkehrt, sieht der Stapel also immernoch so aus:
■ ■ ■ ■ ■ ■ ■ … ■ ■ g × × × × …
↑main()
Das wirft ein besonderes Problem auf: Wie wir sehen, kann der Stapel immer nur um eine Kachel, also 4 KiB, auf einmal wachsen. Was passiert, wenn eine Funktion mehr als 4 KiB an lokalen Variablen anlegt? Normalerweise müsste das Programm dann abstürzen, weil die Guard Page übersprungen wird und der Stapel inkonsistent wird …
… und hier kommt eines der am wenigsten bekannten Compiler-Features ins Spiel: Stack Probes. Eine Funktion, die viel Stapelspeicher verbraucht und die Guard Page überspringen würde:
void stackTerror() {
int huge[10000];
int bad = 1; // Crash
}
bekommt vom Compiler automatisch Stack Probes verpasst, die sicher stellen, dass der Stapel nie schneller als eine Kachel wächst:
void stackTerror() {
int huge[10000];
for(int i = 0; i < sizeof(huge); i += 4096) {
huge[i / sizeof(int)] = 0;
}
int bad = 1;
}
Dadurch tastet sich die Funktion Kachel für Kachel durch den Stapelspeicher, bis er die Größe erreicht haben muss, die sie maximal benutzen könnte. Das garantiert, dass der Stapel konsistent bleibt – und vernichtet die Sparstrategie, die virtueller Speicher verfolgt. Und es zerstört die Lokalität der Funktion, weil sie erstmal zig Kacheln im Speicher abläuft (und dadurch den Cache verpestet) obwohl das Abtasten nur beim ersten Mal nötig ist.
Hier kommt eine andere Linker-Einstellung von Visual C++ ins Spiel: Die Stack Commit Size. Der Name ist leicht irreführend, weil sie nicht wirklich dafür sorgt, dass die Größe auch committed wird – sie bestimmt, wo die Guard Page gesetzt wird. Gleicht die Stack Reserve Size der Stack Commit Size, liegt die Guard Page ganz hinten und Windows weist dem Stapelspeicher direkt beim Programmstart physische Adressen zu.
Stack Probes schaltet das aber nicht ab (weil der C++-Compiler nichts von den Einstellungen des später aufgerufenen Linkers weiß). Um sie loszuwerden muss man unter Properties → C/C++ → Command Line von Hand einfügen: /Gs1000000000 (was die Stack Probes für Funktionen mit weniger als 1 GB lokaler Variablen abschaltet).
So. Speicher wird immernoch verschwendet, aber dafür habe ich eine supertolle Leistung weil mein ganzer Speicher beim Programmstart einmal zugewiesen und dann nie mehr was allokiert wird. Aber ich habe dafür ein richtig fettes Problem geschaffen. Beim nächsten Mal wird es richtig schmutzig!
-
Krishty
- Establishment
- Beiträge: 8267
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
4. Selbsttäuschung ist eine Optimierung
Wir wissen nun, dass die Kapazität des Stapelspeichers unter Windows durch eine Linker-Einstellung bestimmt wird. Genauer gesagt wird sie in den Header der Exe-Datei geschrieben. Dieser Wert wird dann verwendet, wann immer der Prozess einen Thread erzeugt.
Und hier liegt der Hund begraben: Kaum ein Programm erzeugt nur einen Thread. Auf meiner Achtkern-CPU habe ich einen Haupt-Thread, einen Direct3D-Thread, und einen XAudio-Thread. Die letzten beiden erzeugen jeweils einen Pool von sieben Worker Threads, an die sie die Arbeit weiterleiten.
Weil im Header meiner Exe steht, dass jeder Thread mit 40 MiB Stapelspeicher erzeugt werden soll, bedeutet das bei mir, dass 680 MiB Speicher für Stapel reserviert werden. Und das, obwohl keiner dieser Threads jemals mit meinem Code in Berührung kommt – vielmehr sind die Verfasser von DirectX davon ausgegangen, dass jedes System die Standardgröße von 1 MiB für seinen Stapelspeicher benutzt.
Das ist an sich erstmal kein Problem, weil der Speicher nur reserviert, aber nicht zugewiesen ist. Es beginnt jedoch zum Problem auf 32-Bit-Systemen zu werden, wo dann 25 % des eh schon knappen Adressraums für nicht benutzten Stapel draufgehen. Wenn mein Stapel noch größer wird, oder ich mehr Threads brauche, wird diesen Systemen die Puste ausgehen.
An den DirectX-Quelltext, der die Worker Threads erzeugt, komme ich nicht ran. Wie komme ich also aus dieser Bredouille raus?
Die optimale Lösung wäre, die Größe nur temporär zu verändern bis mein Haupt-Thread gestartet ist, und zurückzustellen, bevor andere Bibliotheken ihre Threads erzeugen. Leider ist das nicht möglich: Sobald mein Code ausgeführt wird, ist mein Thread bereits gestartet (denn sonst würde ich keinen Code ausführen). Der Start wird von Windows übernommen. Und die Linker-Einstellungen sind nach Programmstart nicht mehr veränderbar.
Oder?
Doch! Wenn Windows eine Exe lädt, kopiert es den Header in den Speicher – unter anderem, um daraus die Stack Reserve Size zu lesen, bevor das Programm gestartet wird (und wann immer es einen neuen Thread erzeugt). Diese Kopie im Speicher ist manipulierbar.
Was ich jetzt also mache ist: Ich suche den Header meiner Exe im Speicher. Unter Windows entspricht diese Adresse ganz einfach dem HINSTANCE, das die WinMain() erwartet. Mit Visual C++ ist es sogar noch einfacher, weil der Linker die Peudovariable __ImageBase anlegt, die auf den Header verweist.
Normalerweise ist die Kopie schreibgeschützt, aber da das der Speicher unseres Prozesses ist, dürfen wir den Schreibschutz aufheben:
extern "C" IMAGE_DOS_HEADER __ImageBase;
int main() {
// Header finden:
auto toHeader = reinterpret_cast<IMAGE_NT_HEADERS *>(reinterpret_cast<char *>(&__ImageBase) + __ImageBase.e_lfanew);
// Schreibschutz des Modul-Headers aufheben:
DWORD originalProtection;
if(0 != VirtualProtect(toHeader, sizeof *toHeader, PAGE_EXECUTE_READWRITE, &originalProtection)) {
// Stapeleinstellungen auf Standardwerte zurücksetzen:
toHeader->OptionalHeader.SizeOfStackReserve = 1024 * 1024;
toHeader->OptionalHeader.SizeOfStackCommit = 4096;
// Schreibschutz wiederherstellen:
DWORD temp;
VirtualProtect(toHeader, sizeof *toHeader, originalProtection, &temp);
}
… und tatsächlich sind jetzt weniger als 60 MiB Speicher reserviert und der Prozess rechnet ganz normal mit der Standardgröße während der Haupt-Thread mit dem XXL-Stack erzeugt wurde.
Wir wissen nun, dass die Kapazität des Stapelspeichers unter Windows durch eine Linker-Einstellung bestimmt wird. Genauer gesagt wird sie in den Header der Exe-Datei geschrieben. Dieser Wert wird dann verwendet, wann immer der Prozess einen Thread erzeugt.
Und hier liegt der Hund begraben: Kaum ein Programm erzeugt nur einen Thread. Auf meiner Achtkern-CPU habe ich einen Haupt-Thread, einen Direct3D-Thread, und einen XAudio-Thread. Die letzten beiden erzeugen jeweils einen Pool von sieben Worker Threads, an die sie die Arbeit weiterleiten.
Weil im Header meiner Exe steht, dass jeder Thread mit 40 MiB Stapelspeicher erzeugt werden soll, bedeutet das bei mir, dass 680 MiB Speicher für Stapel reserviert werden. Und das, obwohl keiner dieser Threads jemals mit meinem Code in Berührung kommt – vielmehr sind die Verfasser von DirectX davon ausgegangen, dass jedes System die Standardgröße von 1 MiB für seinen Stapelspeicher benutzt.
Das ist an sich erstmal kein Problem, weil der Speicher nur reserviert, aber nicht zugewiesen ist. Es beginnt jedoch zum Problem auf 32-Bit-Systemen zu werden, wo dann 25 % des eh schon knappen Adressraums für nicht benutzten Stapel draufgehen. Wenn mein Stapel noch größer wird, oder ich mehr Threads brauche, wird diesen Systemen die Puste ausgehen.
An den DirectX-Quelltext, der die Worker Threads erzeugt, komme ich nicht ran. Wie komme ich also aus dieser Bredouille raus?
Die optimale Lösung wäre, die Größe nur temporär zu verändern bis mein Haupt-Thread gestartet ist, und zurückzustellen, bevor andere Bibliotheken ihre Threads erzeugen. Leider ist das nicht möglich: Sobald mein Code ausgeführt wird, ist mein Thread bereits gestartet (denn sonst würde ich keinen Code ausführen). Der Start wird von Windows übernommen. Und die Linker-Einstellungen sind nach Programmstart nicht mehr veränderbar.
Oder?
Doch! Wenn Windows eine Exe lädt, kopiert es den Header in den Speicher – unter anderem, um daraus die Stack Reserve Size zu lesen, bevor das Programm gestartet wird (und wann immer es einen neuen Thread erzeugt). Diese Kopie im Speicher ist manipulierbar.
Was ich jetzt also mache ist: Ich suche den Header meiner Exe im Speicher. Unter Windows entspricht diese Adresse ganz einfach dem HINSTANCE, das die WinMain() erwartet. Mit Visual C++ ist es sogar noch einfacher, weil der Linker die Peudovariable __ImageBase anlegt, die auf den Header verweist.
Normalerweise ist die Kopie schreibgeschützt, aber da das der Speicher unseres Prozesses ist, dürfen wir den Schreibschutz aufheben:
extern "C" IMAGE_DOS_HEADER __ImageBase;
int main() {
// Header finden:
auto toHeader = reinterpret_cast<IMAGE_NT_HEADERS *>(reinterpret_cast<char *>(&__ImageBase) + __ImageBase.e_lfanew);
// Schreibschutz des Modul-Headers aufheben:
DWORD originalProtection;
if(0 != VirtualProtect(toHeader, sizeof *toHeader, PAGE_EXECUTE_READWRITE, &originalProtection)) {
// Stapeleinstellungen auf Standardwerte zurücksetzen:
toHeader->OptionalHeader.SizeOfStackReserve = 1024 * 1024;
toHeader->OptionalHeader.SizeOfStackCommit = 4096;
// Schreibschutz wiederherstellen:
DWORD temp;
VirtualProtect(toHeader, sizeof *toHeader, originalProtection, &temp);
}
… und tatsächlich sind jetzt weniger als 60 MiB Speicher reserviert und der Prozess rechnet ganz normal mit der Standardgröße während der Haupt-Thread mit dem XXL-Stack erzeugt wurde.
-
Schrompf
- Moderator
- Beiträge: 4878
- Registriert: 25.02.2009, 23:44
- Benutzertext: Lernt nur selten dazu
- Echter Name: Thomas Ziegenhagen
- Wohnort: Dresden
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
Finster! Aber sehr lehrreich. Danke für diese schöne Aufstellung!
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
-
Spiele Programmierer
- Establishment
- Beiträge: 426
- Registriert: 23.01.2013, 15:55
Re: [C++] Schmutzige Tricks
Sehr interessant!
Vielen dank für die Ausführungen! :!:
Ich setzte selber in meinen Programm ein Hilfsmakro für Stackallokationen ein ("FASTNEWMEMORY"), dass werde ich ausgehend von den neuen Erkenntnissen nochmal überarbeiten müssen.
Weißt du zufällig vielleicht auch wie das auf anderen Betriebssystem oder Compilern aussieht? Zum Beispiel auf dem MinGW oder GCC/Clang+Linux? Hat es auch irgendeinen Nachteil wenn man die Stack Propes zum Beispiel mit "/Gs1000000000" abschaltet?
Vielen dank für die Ausführungen! :!:
Ich setzte selber in meinen Programm ein Hilfsmakro für Stackallokationen ein ("FASTNEWMEMORY"), dass werde ich ausgehend von den neuen Erkenntnissen nochmal überarbeiten müssen.
Weißt du zufällig vielleicht auch wie das auf anderen Betriebssystem oder Compilern aussieht? Zum Beispiel auf dem MinGW oder GCC/Clang+Linux? Hat es auch irgendeinen Nachteil wenn man die Stack Propes zum Beispiel mit "/Gs1000000000" abschaltet?
-
Krishty
- Establishment
- Beiträge: 8267
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
Falls du dafür alloca() nutzt, ist das sicher schon deutlich besser als new.Spiele Programmierer hat geschrieben:Ich setzte selber in meinen Programm ein Hilfsmakro für Stackallokationen ein ("FASTNEWMEMORY"), dass werde ich ausgehend von den neuen Erkenntnissen nochmal überarbeiten müssen.
Nein. Du darfst es aber gern ausprobieren :-)Weißt du zufällig vielleicht auch wie das auf anderen Betriebssystem oder Compilern aussieht? Zum Beispiel auf dem MinGW oder GCC/Clang+Linux?
Naja; du musst Stack Reserve Size und Stack Commit Size passend bemessen, sonst stürzt es natürlich ab. Aber abgesehen davon, nein.Hat es auch irgendeinen Nachteil wenn man die Stack Propes zum Beispiel mit "/Gs1000000000" abschaltet?
-
Spiele Programmierer
- Establishment
- Beiträge: 426
- Registriert: 23.01.2013, 15:55
Re: [C++] Schmutzige Tricks
Ja, ich nutzte "alloca".
Ich habe es momentan so definiert, mit "Fallback auf malloc" bei größeren Mengen:
Früher hatte ich es ohne "alloca" mit einen Stackarray fester Größe implementiert, habe mich aber manchmal gewundert, warum am Anfang der Methoden, die das Makro verwenden, der Debugger zu einem seltsamen Codeabschnitt springt, der nur als Disassembly verfügbar ist und dort scheinbar irgendwie eine Schleife durchläuft. Aber ich habe angenommen, dass dort die Pages nur aus irgendwelchen Gründen zum Debugging durchgegangen werden und es im Release das wegfällt, weil mir kein vernümftiger Grund dafür eingefallen ist.
Dadurch das es halb auf dem Heap basiert, habe ich halt auch noch die von dir genannte globale Abhänigkeit die einige weitere Optimierungen verhindert. :?
Ich habe es momentan so definiert, mit "Fallback auf malloc" bei größeren Mengen:
Code: Alles auswählen
#define ALLOCA_MAXSIZE(TYPE) (16384 / sizeof(TYPE))
#if defined(WINDOWS) || defined(LINUX) || defined(BSD)
#if defined(WINDOWS)
#define ALLOCA_FUNCNAME _alloca
#elif defined(LINUX)
#include <alloca.h>
#define ALLOCA_FUNCNAME alloca
#else
#define ALLOCA_FUNCNAME alloca
#endif
#define ALLOCA(TYPE,NAME,SIZE) \
TYPE* NAME = reinterpret_cast<TYPE*>(ALLOCA_FUNCNAME(sizeof(TYPE) * SIZE)); \
do {} while (0)
#define ALLOCA_CONDITIONAL(TYPE,NAME,SIZE,CONDITION) \
TYPE* const NAME = (CONDITION) ? reinterpret_cast<TYPE*>(ALLOCA_FUNCNAME(sizeof(TYPE) * SIZE)) : nullptr; \
do {} while (0)
#else
#define ALLOCA(TYPE,NAME,SIZE) \
char NAME ## RawBuffer [sizeof(TYPE) * ALLOCA_MAXSIZE(TYPE)]; \
TYPE* const NAME = NAME ## RawBuffer; \
do {} while (0)
#define ALLOCA_CONDITIONAL(TYPE,NAME,SIZE,CONDITION) ALLOCA(TYPE,NAME,SIZE)
#warning Inefficient ALLOCA and ALLOCA_CONDITIONAL on this operating system
#endif
///@brief Makro, das uninitialisierten Speicher bei kleinen Mengen auf dem Stack reserviert und bei Größeren auf dem langsameren Heap.
///@details
///@warning Es sollte nicht vergessen werden, nach der Benutzung auch wieder "FASTDELETEMEMORY" aufzurufen! (Ausnahmesicherheit)
///@warning Der Speicher ist uninitialisiert. Ggf. Placement-New aufrufen!
///@sa FASTDELETEMEMORY
#define FASTNEWMEMORY(TYPE,NAME,COUNT) \
const std::size_t NAME ## FixedBufferObjectCount = ALLOCA_MAXSIZE(TYPE); \
const std::size_t NAME ## FixedBufferSize = NAME ## FixedBufferObjectCount * sizeof(TYPE); \
const std::size_t NAME ## Count = (COUNT); \
ALLOCA_CONDITIONAL(char, NAME ## FixedBuffer, NAME ## FixedBufferSize, NAME ## Count <= NAME ## FixedBufferObjectCount); \
TYPE* const NAME = reinterpret_cast<TYPE*>( \
NAME ## Count > NAME ## FixedBufferObjectCount ? \
std::malloc(NAME ## Count * sizeof(TYPE)) : \
NAME ## FixedBuffer); \
do {} while (0)
///@brief Makro, das den Speicher freigibt, der mit "FASTNEWMEMORY" reserviert wurde.
///@details
///@sa FASTNEWMEMORY
#define FASTDELETEMEMORY(NAME) \
if (NAME ## Count > NAME ## FixedBufferObjectCount) \
std::free( NAME ); \
do {} while (0)Dadurch das es halb auf dem Heap basiert, habe ich halt auch noch die von dir genannte globale Abhänigkeit die einige weitere Optimierungen verhindert. :?
-
Krishty
- Establishment
- Beiträge: 8267
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
Unter Windows kannst du _malloca() benutzen, das weicht auch automatisch auf den Freispeicher aus falls die Sachen zu groß werden. Aber ich kann gerade nicht erkennen, ob man explizit free()n muss. Ich glaube auch nicht, dass VC das weitgehend optimiert.
Mir fällt jetzt wieder das Haupt-Kontra gegen alloca() auf Windows ein: Es funktioniert nicht immer. Man darf es nicht aufrufen, falls man sich in einem catch-Block befindet, sonst bricht alles zusammen …
Mir fällt jetzt wieder das Haupt-Kontra gegen alloca() auf Windows ein: Es funktioniert nicht immer. Man darf es nicht aufrufen, falls man sich in einem catch-Block befindet, sonst bricht alles zusammen …
-
Spiele Programmierer
- Establishment
- Beiträge: 426
- Registriert: 23.01.2013, 15:55
Re: [C++] Schmutzige Tricks
Hat "_malloca" irgendeinen Vorteil zum Selbstbau, außer dass man die maximale Stackgröße nicht wählen kann? (1024 scheint es zu sein. Das ist relativ wenig, finde ich.)
Laut MSDN, muss man es schon freigeben...
Laut MSDN, muss man es schon freigeben...
Und die Probleme von alloca scheint es da auch zu geben..._malloca requires the use of _freea to free memory.
There are restrictions to explicitly calling _malloca in an exception handler (EH).
In Windows XP, if _malloca is called inside a try/catch block, you must call _resetstkoflw in the catch block.
-
Krishty
- Establishment
- Beiträge: 8267
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
Ich weiß nicht, wie es implementiert ist. Falls es ein Intrinsic ist, könnte es besser optimierbar sein. Mit Pech ist es aber bloß das gleiche wie der Selbstbau …
_freea() hatte ich übersehen; danke :-)
_freea() hatte ich übersehen; danke :-)
-
FlorianB82
- Beiträge: 70
- Registriert: 18.11.2010, 05:08
- Wohnort: Darmstadt
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
Danke für diese Infos zur Stackgröße von Threads! Sehr interessant, wenngleich auch recht hackig ;). Ich persönlich hätte Bedenken, dass Windows auch in Zukunft (aufgrund neuer Versionen, Service Packs, und whatever) beim Erzeugen von Threads immer die von dir herausgepfriemelte Speicherstelle ausliest um die anzulegende Stackgröße zu bestimmten - denkbar wäre ja auch, dass diese Infos noch irgendwo anders gechacht werden, weil die Windows-Entwickler es nicht eingeplant haben, dass jemand zur Laufzeit an dem PE-Header herumpfuscht ;).
Zwei Alternativen wüsste ich auch noch. Die erstere ist ähnlich hackig. Die zweite ist schon schöner, aber auch nicht perfekt.
Zwei Alternativen wüsste ich auch noch. Die erstere ist ähnlich hackig. Die zweite ist schon schöner, aber auch nicht perfekt.
- Dem Hauptthread der EXE gibt man über die Linker-Einstellungen einen großen Stack vor, meinetwegen die erwähnten 50MiB. Um die anderen Threads wie gewünscht mit einer Stacksize von 1MiB zu erstellen, bedient man sich folgenden Kniffes: Da diese letzten Endes über die WinAPI gestartet werden müssen (ist das so? nehme ich zumindest stark an...), kann man einfach CreateThread() hooken. In der eigenen Implementierung ruft man natürlich wieder CreateThread() auf, aber mit der gewünschten Stackgröße von 1 MiB. Das Hooking braucht man natürlich nur für die Threads, die man nicht direkt selbst erstellt, wie z.B. die DirectX Threads - den anderen kann man ja direkt bei der Erstellung die gewünschte Stackgröße mitgeben.
- Diesmal gibt man in den Linker-Einstellungen einen kleinen Stack vor, z.B. die default Größe von 1MiB. Damit werden alle Threads, soweit nicht explizit anders angegeben, mit dieser Stackgröße erzeugt. Im Hauptthread der Anwendung, also im Funktionsrumpf der main(), macht man nun nichts weiter als einen Thread explizit mit der gewünschten erhöhten Stackgröße zur erzeugen, zu starten, und auf sein Ende zu warten. Den erzeugten Thread verwendet man nun als Anwendungshauptthread. Nachteil hierbei ist eben, dass man einen Thread mehr erzeugen muss als eigentlich nötig.
Re: [C++] Schmutzige Tricks
Erste Alternative würde ich nicht empfehlen. Threads können auch von Treiber und von anderen Prozessen erstellt werden. Außerdem sind Hooks benauso unelegant wir im PE Header rumzupfuschen.
Zweiteres ist aber eine gute Idee. Man kann sogar den Mainthread mit ExitThread beenden. Der Prozess wird weiterlaufen.
Zweiteres ist aber eine gute Idee. Man kann sogar den Mainthread mit ExitThread beenden. Der Prozess wird weiterlaufen.
-
FlorianB82
- Beiträge: 70
- Registriert: 18.11.2010, 05:08
- Wohnort: Darmstadt
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
Ja. Hooks habe ich auch nie so wirklich toll gefunden, aber ich wollte es zumindest erwähnt haben. Schmutzig ist es ja ;).Helmut hat geschrieben:Erste Alternative würde ich nicht empfehlen. Threads können auch von Treiber und von anderen Prozessen erstellt werden. Außerdem sind Hooks benauso unelegant wir im PE Header rumzupfuschen.
Oha, das wusste ich noch nicht. Ich hätte gewettet, das Windows bei Ableben des Main-Thread alles abräumt. Dann ist diese Lösung ja noch ein Stück hübscher geworden...Helmut hat geschrieben:Zweiteres ist aber eine gute Idee. Man kann sogar den Mainthread mit ExitThread beenden. Der Prozess wird weiterlaufen.
Re: [C++] Schmutzige Tricks
In der LLVM gibt es einen Pass, der solche Malloc-Free-Paare findet. Da geschieht mittels des Memory Luvetime Tracking. Und es mach auch Sinn, da einige Templates Speicher allokieren, um dort Daten zwischenzlagern. Die LLVM kan allerdings die doppelte Kopieroperation a->b,b->c in a->b,a->c umwandeln, wodurch das malloc, memcpy und free auf b komplett entfallen kann. LLVM hat übrigens irgendwas angekündigt, dass die kompatibler mit Microsoft werden wollen.Krishty hat geschrieben:1. Auf dem Stapelspeicher allokieren bis er überläuft
Ich hasse dynamische Allokation via new. Ich hasse sie nicht von sich aus, sondern wegen der Art, wie sie in C++ implementiert ist: als externe Wirkung. Nehmen wir das folge Stück Maschinentext:
auto x = new int;
delete x;
Jeder Programmierer erkennt sofort, dass diese Zeilen sinnlos sind: Die erste tut etwas, und die zweite macht es wieder rückgängig. Vernünftige Sprachen würden das wegoptimieren. In C++ ist das nicht möglich.
Warum? Weil new und delete in C++ auf externe Funktionen verweisen. Üblicherweise rufen sie (unter Windows) HeapAlloc() und HeapFree() auf: Das sind die Funktionen der Windows-Speicherverwaltung, die euch Speicher beschaffen und wieder freigeben.
Der Knackpunkt ist, dass wir als Menschen zwar wissen, was diese Funktionen tun; aber der Compiler nicht. Für ihn sind das unbekannte Code-Stücke, die eingebunden werden: kein Unterschied zu CreateWindow() oder CreateFile(). Es steht ja nicht einmal fest, dass sie tatsächlich aufs Betriebssystem verweisen – vielleicht verweisen sie auf eine Debug-Bibliothek, die eure Speicherallokationen loggt. Es ist einfach nicht zu sagen.
Darum tut der Compiler das, was unter diesem Gesichtspunkt richtig ist: „Oh mein Gott ich weiß nicht was die Funktion hinter new macht; vielleicht zeigt sie ein Fenster an oder sonst was Wichtiges; bloß nicht wegoptimieren!“. In anderen Sprachen geht das, weil die Sprache dort genau festlegt, was new tut. Aber in C++ ist die Speicherverwaltung nunmal anpassbar. Und dafür müssen wir bezahlen.
Es geht weiter: Der Compiler kann nicht bestimmen, worauf der Speicher zeigt, den new zurückgibt. Idealerweise sollte er eine neue, ungekannte Adresse sein. Aber vielleicht hat jemand einen Pool-Allocator geschrieben, der einfach ein Stück eines vorher allokierten Arrays zurückgibt? In diesem Fall ändert sich auch der Inhalt des Pools, wenn man in die neue Adresse schreibt. Solche Dinge muss der Compiler beachten. Darum kann der Compiler, sobald dynamisch allokiert wurde, nicht mehr genau bestimmen, welcher Speicher im Programm welchen Wert enthält.
tl;dr: Dynamische Allokation ist doof und wird schlecht optimiert. Also allokiere ich so ziemlich alles auf dem Stack. Der Compiler weiß, wo die Dinge liegen, und er kennt ihren Inhalt. Das lässt sich perfekt optimieren.
– Aber was ist, wenn man nicht weiß, wie viele Daten kommen? Man kann keine dynamischen Arrays auf dem Stapel haben!
Doch, kann man. Der C++-14-Standard übernimmt Arrays variabler Größe aus dem C99-Standard. Diese Funktionalität ist auch heute schon via _alloca() verfügbar. damit könnt ihr lokalen Arrays tatsächlich beliebige Größen zuweisen.
Ich mache es trotzdem nicht, weil es ein Register verschwendet: Normalerweise weiß der Compiler, wo welche Variable in einer Funktion liegt, und kennt dadurch auch ihre Adresse. Aber sobald ein dynamisches lokales Array in einer Funktion liegt, ist die Position der Variablen im Speicher von der Größe des Arrays abhängig. Damit lokale Variablen trotzdem adressiert werden können, muss gespeichert werden, wie groß das dynamische lokale Array ist. Dafür stellt der Compiler üblicherweise ein Register ab. Jeder Zugriff auf andere lokale Variablen erfolgt nun nicht mehr durch eine feste Adresse im Maschinentext, sondern wird zur Laufzeit über das zusätzliche Register berechnet, das dann nicht mehr zur Verfügung steht. Die gesamte Funktion wird minimal langsamer.
Darum allokiere ich einfach ein Array des größten sinnvollen Umfangs und benutze nur den Speicher am Anfang, den ich auch brauche.
– Aber der Stack ist doch nur 1 MiB groß! Das stürzt doch ab, wenn man größere lokale Arrays anlegt!
Ja genau. Aber das lässt sich einstellen: In Visual C++ findet sich unter den Projekt-Properties → Linker → System die Stack Reserve Size. Setzt man die hoch, reserviert Windows beim Start des Programms einen entsprechend großen Stapel. Bei mir sind das z.B. gerade ungefähr 40 MiB. Und voilà: Ich kann ein 35-MiB-Array für alle meine Assets direkt in der main() als lokale Variable anlegen und alles funktioniert perfekt!
– Ist das nicht Speicherverschwendung?
Ja – aber aus komplett anderen Gründen als man zuerst denkt! Und sie lässt sich vermeiden. Darum wird es im nächsten Beitrag gehen.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
-
Krishty
- Establishment
- Beiträge: 8267
- Registriert: 26.02.2009, 11:18
- Benutzertext: state is the enemy
- Kontaktdaten:
Re: [C++] Schmutzige Tricks
@FlorianB82: Ich teile deine Bedenken, darum ist es ein „schmutziger“ Trick. Aber Helmut hat dazu schon so ziemlich alles gesagt, mit einer Krishty-spezifischen Ausnahme: Das mit dem Erzeugen eines „neuen“ Haupt-Threads würde meine CRT aufblähen weil ich sicherstellen müsste, dass alle globalen Variablen nach Beenden freigegeben werden (und nicht schon beim Beenden des Einsprung-Threads, was deutlich einfacher ist).
Unter C++ <14 ist das jedenfalls nicht erlaubt (weil Allokationsverhalten beobachtbares Verhalten ist und die as-if-Regel beschränkt). Der Vorschlag „Clarifying Memory Allocation“ von Google vom September dieses Jahres würde es für new-delete-Paare erlauben. Ist er durchgesetzt worden? Er würde jedoch weiterhin versagen, falls das Paar von einem globalen Aufruf unterbrochen wird.antisteo hat geschrieben:In der LLVM gibt es einen Pass, der solche Malloc-Free-Paare findet. Da geschieht mittels des Memory Luvetime Tracking. Und es mach auch Sinn, da einige Templates Speicher allokieren, um dort Daten zwischenzlagern. Die LLVM kan allerdings die doppelte Kopieroperation a->b,b->c in a->b,a->c umwandeln, wodurch das malloc, memcpy und free auf b komplett entfallen kann.
Re: [C++] Schmutzige Tricks
Der C++-Standard ist da relativ lax, allerdings kann man bei malloc-free-Paaren Lokalität annehmen, obwohl das faktisch nicht so ist (sich aber trotzdem so verhält).Krishty hat geschrieben:Er würde jedoch weiterhin versagen, falls das Paar von einem globalen Aufruf unterbrochen wird.
Zudem kannst du dich einfach selber an die strengere Variante halten und deinen eigenen Pass schreiben, der aufgrund deiner Constraints mehr Optimierungen findet.
http://fedoraproject.org/ <-- freies Betriebssystem
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.
http://launix.de <-- kompetente Firma
In allen Posts ist das imo und das afaik inbegriffen.