Rekursionstiefe und Exceptions
-
Skym0sh0 schrieb:
Frage (1): Wie sieht ein solcher Abbruch/Crash aus. Laut Standard undefiniert?! Wie sieht das in der Praxis aus? (Visual Stduio 2012 Ultimate, mit/ohne Debug)
In der Praxis liegt "am Ende des Stack" eine Guard-Page. Der vom Compiler generierte Code ist dabei so ausgelegt, dass nie eine Stack-Seite übersprungen werden kann. Dazu werden ggf. extra "Stack-Probes" eingefügt, um sicherzustellen dass Stack Seite X erstmal angefasst wird bevor Seite X+1 angefasst wird.
Dadurch ist Garantiert dass es erstmal nen Zugriff auf die Guard-Page gibt, bevor dahinterliegende Teile die nicht mehr für den Stack reserviert sind angegriffen werden. Bzw. würden, denn beim Zugriff auf die Guard-Page wirft dir das OS einen Fehler um die Ohren.
Den kann man mit entsprechenden Funktionen des OS dann abfangen und selbst behandeln. Macht man das nicht, dann bricht das OS das Programm ab.Langer Rede kruzer Sinn: es ist in der Praxis garantiert dass das Programm bei einem Stack-Overflow eben kein UB zeigt, sondern kontrolliert abgebrochen wird. Man muss also keine Angst haben dass das Programm in so einem Fall Unsinn als Ergebnis produziert, und man nicht mitbekommt dass was schlimmes passiert ist.
Skym0sh0 schrieb:
Frage (2): Wie kann ich abschätzen wie viele Rekursionsschritte er schafft/macht?
Naja "macht" sollte einfach sein: zähl halt mit. Mit Thread-lokalen Variablen und einer kleinen RAII Hilfsklasse ist das recht einfach.
Wie viel er schafft kann man dann ganz einfach ausprobieren. Bzw. Pi*Daumen hochrechnen: (Stack Grösse)/(Geschätzte Stack-Frame Grösse)In deinem Beispiel wird aber in der Praxis gar keine Rekursion rauskommen, da der einzige rekursive Pfad ein Tail-Call ist. Der vom Compiler als solcher erkannt, und in einen einfachen Sprung umgeschrieben wird.
Frage (3): Was passiert, wenn der Stackspeicher gesprengt wird, aber das Programm bricht nicht ab, und dann fliegt die Exception?
Wenn das Programm mehr Stack braucht als für den Stack reserviert ist, und das OS diesen Fehler nicht abfängt, dann passiert das selbe wie sonst passiert wenn man wahllos auf Speicher zugreift: irgendwas (UB).
D.h. es kann sein dass alles glatt geht, weil "hinter" dem für den Stack reservierten Bereich zufällig auch Speicherseiten gemappt waren, deren Inhalt das Programm aber nicht mehr braucht.
Es kann aber auch sein dass diese Daten sehr wohl noch gebraucht werden, und sich dann später ein Fehler ergibt. Das kann beim Unwinding sein, oder auch noch viel später.
UB halt.
Ist aber in der Praxis kein Problem, da Compiler und OS hier zusammenarbeiten damit genau das nicht passieren kann. Siehe meine Antwort auf deine 1. Frage.
-
Okay, danke für die ausführliche Antwort.
Das bedeutet also, dass zu viele/tiefe Rekursionen in meinem Fall eigentlich nicht das Problem waren. Andererseits: MSVC 2012, baut der daraus eine Endrekursion, wenn die Optimierungen abgeschaltet sind?
Ich meine beim Debuggen konnte ich ja noch schön ejden Rekursionsschritt mitgehen und damit auch sehen. Ist der aber zu eine Tailrekursion optimiert, dann dürfte ich den doch gar nicht sehen, oder nicht?!Versuch die Frage selbst zu beantworten: Nein, ich dürfte den orignalen Quellcode sehen, aber trotzdem ist eine Tailrekursion vorgenommen worden. Dabei ist es aber so, dass keine reale Rekursion stattfindet, sondern lediglich das Ergebnis des jeweils nächsten (vermeintlichen, aber nicht realen) Funktionsaufrufes (aka Rekursionsschritt) direkt an die Call-Postion eingesetzt wird. Ergo kommt quasi eine iterative Folge von Funktionensaufrufen raus, die aber den Mantel der Rekursion trägt.
Ist das in etwa richtig?
Nächste Frage: Mein Rechner aht 16GB RAM, laut Ressourcenmonitor sind zwischen 3 und 4 GB in Verwendung. Knapp 5Gb sind frei und 8Gb sind auf Standby.
Summasumarum -> 1/4 des Rams ist in Benutzung, 3/4 sind frei.Lasse ich mein Programm laufen, braucht es mit der Zeit Speicher, und das auch immer mehr. Bisher bin ich laut Taskmanager in etwa Regionen von 2GB(nur für das Programm) gekommen. Dann kommt aber eine bad_alloc-Exception.
Müsste die nicht eigentlich erst kommen, wenn mein RAM voll ist? Und eventuell die Auslagerungsdatei auch?
Laut [url=]Reference[/url] ist nicht definiert, welche Gründe eine solche Exception haben kann/muss. Es ist halt nicht möglich, den angeforderten Speicher zu allokieren. Aber was sind die Gründe?
Wieso lässt mich mein OS oder der Compiler nur ~2GB Speicher nutzen?
-
Ist das 'n 64-Bit-Build?
-
Skym0sh0 schrieb:
Andererseits: MSVC 2012, baut der daraus eine Endrekursion, wenn die Optimierungen abgeschaltet sind?
Ich meine beim Debuggen konnte ich ja noch schön ejden Rekursionsschritt mitgehen und damit auch sehen. Ist der aber zu eine Tailrekursion optimiert, dann dürfte ich den doch gar nicht sehen, oder nicht?!Wenn du schon so schön am Debuggen bist, guck dir dabei doch den Callstack an.
-
Bashar schrieb:
Skym0sh0 schrieb:
Andererseits: MSVC 2012, baut der daraus eine Endrekursion, wenn die Optimierungen abgeschaltet sind?
Ich meine beim Debuggen konnte ich ja noch schön ejden Rekursionsschritt mitgehen und damit auch sehen. Ist der aber zu eine Tailrekursion optimiert, dann dürfte ich den doch gar nicht sehen, oder nicht?!Wenn du schon so schön am Debuggen bist, guck dir dabei doch den Callstack an.
Der Callstack sagt, dass er in die Funktion rein geht. also die Rekursion auch durchführt. Und Tailrecursion war doch genau die Geschichte, dass anstatt der immer tiefer gehenden Rekursionsschritte, das aktuelle Ergebnis quasi direkt an die Aufrufposition eignesetzt werden kann so dass nicht n-mal ein neuer Stackframe erzeugt werden muss, sondern die Umgebung quasi gleich bleibt.
Caligulaminus schrieb:
Ist das 'n 64-Bit-Build?
Nein. ich muss auch ehrlich zugeben, dass ich von 32Bit vs 64Bit approximativ keine Ahnung habe.
Was sind die Vor- bzw. Nachteile. Und wie stelle ich das eine oder andere ein?
-
Skym0sh0 schrieb:
Der Callstack sagt, dass er in die Funktion rein geht. also die Rekursion auch durchführt. Und Tailrecursion war doch genau die Geschichte, dass anstatt der immer tiefer gehenden Rekursionsschritte, das aktuelle Ergebnis quasi direkt an die Aufrufposition eignesetzt werden kann so dass nicht n-mal ein neuer Stackframe erzeugt werden muss, sondern die Umgebung quasi gleich bleibt.
Also Frage beantwortet?
-
= keine Tailrekursion?!
-
Ich versteh nicht, wieso du immer noch fragst.
-
Skym0sh0 schrieb:
Mein Rechner hat 16GB RAM [..] Wieso lässt mich mein OS oder der Compiler nur [..]
Caligulaminus schrieb:
Ist das 'n 64-Bit-Build?
Skym0sh0 schrieb:
Nein.
...
-
-.-
Ja ok, ich kann mit 32Bit nur 4GB adressieren. Aber das sind immer noch weiter mehr als 2Gb...
Bashar schrieb:
Ich versteh nicht, wieso du immer noch fragst.
Weil es anfangs hieß, dass jeder dumme Compiler das wegoptimiert.
Ausserdem hätte es ja sein können, dass Visual Studio der Benutzerfreundlichkeit oder was, im Debugmodus irgendwelchen Nichtexistenten Quellcode zeigt (wie z.B. bei Releasecompilierungen)
-
Caligulaminus schrieb:
Skym0sh0 schrieb:
Mein Rechner hat 16GB RAM [..] Wieso lässt mich mein OS oder der Compiler nur [..]
Caligulaminus schrieb:
Ist das 'n 64-Bit-Build?
Skym0sh0 schrieb:
Nein.
...
Typisches Vorurteil. Windows 32 kann mit PAE die ganzen 16GB nutzen. Nur einzelne Applikationen sind auf 4GB begrenzt, dafür sind diese schneller weil Pointer kompakter dargestellt sind.
-
pae schrieb:
Caligulaminus schrieb:
Skym0sh0 schrieb:
Mein Rechner hat 16GB RAM [..] Wieso lässt mich mein OS oder der Compiler nur [..]
Caligulaminus schrieb:
Ist das 'n 64-Bit-Build?
Skym0sh0 schrieb:
Nein.
...
Typisches Vorurteil. Windows 32 kann mit PAE die ganzen 16GB nutzen. Nur einzelne Applikationen sind auf 4GB begrenzt, dafür sind diese schneller weil Pointer kompakter dargestellt sind.
Unabhängig davon wieviel Speicher das Betriebsystem verwenden kann, standardmäßig sind Prozesse auf 2gb beschränkt, weil angenommen wird das viel Platz für DLLs und andere geteilte Daten benötigt werden. Lösung: http://msdn.microsoft.com/en-us/library/wz223b1z.aspx
-
pae schrieb:
Typisches Vorurteil. Windows 32 kann mit PAE die ganzen 16GB nutzen. Nur einzelne Applikationen sind auf 4GB begrenzt
Geht es hier um mehr als eine?
Skym0sh0 schrieb:
Ja ok, ich kann mit 32Bit nur 4GB adressieren. Aber das sind immer noch weiter mehr als 2Gb...
Win32 rückt m.W. nur ~2G pro Prozess rum.
-
Skym0sh0 schrieb:
Bashar schrieb:
Ich versteh nicht, wieso du immer noch fragst.
Weil es anfangs hieß, dass jeder dumme Compiler das wegoptimiert.
Das stimmt erstens nicht, und zweitens höchstens, wenn die Optimierung aktiviert ist.
Ausserdem hätte es ja sein können, dass Visual Studio der Benutzerfreundlichkeit oder was, im Debugmodus irgendwelchen Nichtexistenten Quellcode zeigt (wie z.B. bei Releasecompilierungen)
Im Call-Stack-Fenster im Debugger steht hoffentlich kein Quelltext, sondern die gegenwärtige Aufrufhierarchie. Und da türmen sich entweder die rekursiven Aufrufe oder sie tun es nicht.
-
pae schrieb:
Windows 32 kann mit PAE die ganzen 16GB nutzen.
Das ist theoretisch korrekt, praktisch aber völlig falsch. Die meisten Windows-Systeme, die einem so unterkommen, können kein PAE - Microsoft verkauft dies als Enterprise-Feature, für das man gefälligst eine der teureren Server-Versionen kaufen soll. Siehe auch http://msdn.microsoft.com/en-us/windows/hardware/gg487503.aspx
pae schrieb:
Nur einzelne Applikationen sind auf 4GB begrenzt, dafür sind diese schneller weil Pointer kompakter dargestellt sind.
Das ist mindestens eine sinnentstellend vereinfachte Darstellung. Die breiteren Zeiger können zu einem Performanceverlust führen, weil mit ihnen eine größere zu verarbeitende Datenmenge einher geht, aber es gibt viele Bereiche, in denen die neuen 64-Bit-Instructions große Geschwindigkeitsvorteile bringen -- memcmp, strlen und derlei können kräftig davon profitieren, dass sie in doppelt so großen Schritten arbeiten können. GMP holt aus dem gleichen Grund für einige Operationen nochmal grob Faktor 4 raus.
64-Bit-Binaries bedeuten nicht automatisch einen Performancegewinn, aber sie gegenüber 32-Bit-Builds als generell langsamer darzustellen, geht an der Realität vorbei.
-
seldon schrieb:
pae schrieb:
Windows 32 kann mit PAE die ganzen 16GB nutzen.
Das ist theoretisch korrekt, praktisch aber völlig falsch. Die meisten Windows-Systeme, die einem so unterkommen, können kein PAE - Microsoft verkauft dies als Enterprise-Feature, für das man gefälligst eine der teureren Server-Versionen kaufen soll. Siehe auch http://msdn.microsoft.com/en-us/windows/hardware/gg487503.aspx
Da widerspricht dir deine Quelle etwas. Es wird sehr wohl PAE unterstützt und verwendet. Ohne dem wäre das No-Execution-Bit nicht verwendbar, welches seit Windows XP mit SP 2 unterstützt wird. Die Begrenzung auf 4GB ist künstlich (Lizenz und Treiber Probleme).
seldon schrieb:
pae schrieb:
Nur einzelne Applikationen sind auf 4GB begrenzt, dafür sind diese schneller weil Pointer kompakter dargestellt sind.
Das ist mindestens eine sinnentstellend vereinfachte Darstellung. Die breiteren Zeiger können zu einem Performanceverlust führen, weil mit ihnen eine größere zu verarbeitende Datenmenge einher geht, aber es gibt viele Bereiche, in denen die neuen 64-Bit-Instructions große Geschwindigkeitsvorteile bringen -- memcmp, strlen und derlei können kräftig davon profitieren, dass sie in doppelt so großen Schritten arbeiten können. GMP holt aus dem gleichen Grund für einige Operationen nochmal grob Faktor 4 raus.
64-Bit-Binaries bedeuten nicht automatisch einen Performancegewinn, aber sie gegenüber 32-Bit-Builds als generell langsamer darzustellen, geht an der Realität vorbei.
Ich habe das so verstanden das es an dieser Stelle um 32-Bit mit PAE ging und nicht um 64-Bit. 32-Bit mit PAE hat keinerlei Vorteile gegenüber der normalen 32-Bit Ausführung, aber ein aufwändigeres Paging. Das kann nur langsamer sein.
-
Skym0sh0 schrieb:
= keine Tailrekursion?!
Im DebugßModus wird dein Compiler diese Optimierung auch schwer vornehmen.
-
knivil schrieb:
Skym0sh0 schrieb:
= keine Tailrekursion?!
Im DebugßModus wird dein Compiler diese Optimierung auch schwer vornehmen.
Hä?
Und genau solche Aussagen verwirren total. Heisst das jetzt, dass die Optimierungvorgenommen wird und das Wort "schwer" das unterstreichen soll. Oder heisst das, dass es eben nicht optimiert wird, weils schwer geht?!
-
Ob dein Compiler tail-call-Optimierung durchfuehrt, siehst du nur am generiertem Maschinencode. Gewoehnlich wird im Debugbuild keine Optimierung vorgenommen, d.h. auch keine tail-calls aufgeloest. D.h. der Debugger hilft dir nicht. Zwar gibt es XYZ-Optionen mancher Compiler, die Optimierung auch bei Debugbuilds aktivieren, ist aber nicht der Regelfall.
-
Heisst das jetzt, dass die Optimierungvorgenommen wird und das Wort "schwer" das unterstreichen soll.
Sieht nach einem Anglizismus aus ("hardly" falsch übertragen).
