Rekursion vermeiden... Wieso?

[rapso]

Ishildur schrieb:

Ich erspahre mir also den rekursiven Funktionsaufruf...

du sparst dir vor allem returns.
compiler veruchen das aber schon zu optimieren, wenn du also ne rekursion hast die z.b. immer die selben objekte weitergibt, diese aber nach dem return aus der rekursiven funktion nicht weiter verwendet, werden manche compiler den call+return zu einem simplen jump umstellen.

...Und tausche diesen gegen gleich zwei davon (Push und Pop auf der Hilfstruktur Stack)??

push und pop hast du sowieso auf dem stack, jedoch
-sparst du dir das ablegen von ein paar registern und legst nur wirklich noetige dinge ab
-kannst du cpu freundlicher sein wenn du alle deine variablen per index, also pStack[0]=...;pStack[1]=....; ablegst statt mit *pStack++= zu arbeiten wie es die CPU normalerweise macht.
-..

Ausserdem habe ich dann noch entweder ein new und delete (LinkedList) oder sonstige Umkopiererei (DynamicArray) je nach Stack Implementation.

sowas zu machen waere natuerlich dumm, wenn jemand das vor hat, dann wird er natuerlich schlechter abschneiden als ne rekursion zu machen.
Die idee an sich ist nur die rekursionsaufrufe zu sparen, andere laufzeiteigenschaften sollten sich nicht veraendern. alle allokationen die sonst auf dem stack waeren muessen also weiterhin auf dem stack liegen.

Der Einzige Vorteil für den iterativen Approach sehe ich darin, dass damit die Gefahr eines Überlaufs des Applikationsstacks durch die rekursiven Aufrufe gebannt ist.

nicht sonderlich, man muss beim aufruf der funktion gleich den stack anlegen. man wird also eher merken falls man in einen kritischen bereich kommt (also wenig stack da ist), weil unabhaengig von der rekursionstiefe gleich der volle speicher allokiert ist.
mehr noch, es ist relativ billig nen stackcheck einzubauen, da man das ja nicht rekursiv immer wieder macht, sondern nur im entry der funktion.

Was sagt ihr dazu?

du hast schon recht, die meisten labern bei sowas nach was sie gehoert haben und machen dann implementationsfehler weil sie sich keine gedanken darueber machen "Iterativ ist schneller, basta, aus".

du wirst aber auch vermutlich mal feststellen, dass deine iterative implementierung langsammer ist als die stackversion, obwohl du alles richtig gemacht hast. gruende koennen sein
- dass CPU hersteller (eigentlich nur amd+intel) einiges an optimierungen haben um die ueblichen stackprobleme zu umgehen.
- stack lokalitaet verloren ist aufgrund der initialen grossen allokation, z.b.

uint8_t Stack[1<<20];
size_t StackPtr=0;

sorgt dafuer dass der erste zugriff auf den stackptr garantiert ein cachemiss ist, weil fast alle cpus <=64kb an L1 cache haben, man aber 1MB weiter zugreifen will.
- compiler eben auch stackoptimierungen haben, sie verwenden moeglichst viel wieder an stack memory und versuchen unnoetige rekursionen mit jmps zu ersetzen, was sie nicht machen wenn du per hand in nem loop deinen stack bearbeitest.

am ende hilft nur benchmarken was schneller ist.

[hustbaer]

frosch03 schrieb:

Aber sehe ich das richtig, mit dieser Erkennung rettet man nur das OS vor dem sichern
Suizid? Der Prozess der den stack-overflow verursacht hat davon erstmal wenig?

Dem OS ist das herzlich egal.
Ich denke da gehts eher darum das Programm davor zu schützen dass es seine eigenen Daten überschreibt.

"Neben" dem Stack könnten ja andere Daten liegen. Und ohne Stack-Probes könnte man die überschreiben, ohne jemals die Guard-Page zu treffen. z.B. wenn man von einem grossen Puffer nur einen kleinen Teil verwendet.

Das Programm würde dann ganz normal weiterlaufen, aber der Datenbereich "neben" dem Stack wäre voll mit lauter Schrott aus alten Flippern.

Da ist es denke ich besser, wenn man den Prozess sterben lässt.

BTW: ich weiss garnicht ob man den Prozess sterben lassen *muss* in so einem Fall. Es kann leicht sein, dass man nur den Thread der den Stack-Overflow ausgelöst hat sterben lassen muss. Vielleicht sogar nichtmal den, wobei mir auf die Schnelle aber nicht einfällt, wie man den vernünftig weiterlaufen lassen könnte.

[Bashar]

hustbaer schrieb:

"Neben" dem Stack könnten ja andere Daten liegen. Und ohne Stack-Probes könnte man die überschreiben, ohne jemals die Guard-Page zu treffen. z.B. wenn man von einem grossen Puffer nur einen kleinen Teil verwendet.

Wozu muss man das überhaupt über eine Guard-Page realisieren? Man kann doch bei jedem Funktionsaufruf erstmal gucken, ob über dem Stackpointer bis zum Beginn des Heaps oder was auch immer danach kommt noch genug Platz ist?

Wenn das ginge, müsste man den Aufruf mit einer Exception sterben lassen und das wärs gewesen. In Java ist das ja leider ein VirtualMachineError, d.h. man kann danach nicht weitermachen, aber dass das zwingend ist, seh ich nicht ganz ein.

[;fricky]

Bashar schrieb:

In Java ist das ja leider ein VirtualMachineError, d.h. man kann danach nicht weitermachen, aber dass das zwingend ist, seh ich nicht ganz ein.

kannste aber abfangen, z.b. so:

public class test
{
    static void smash_the_stack()
    {
        smash_the_stack();
    }

    public static void main( String[] args )
    {
        try
        {
            smash_the_stack();    
        }
        catch (StackOverflowError e)
        {
            System.out.println ("huch? ein ... " + e);
        }
        System.out.println ("still alive :)");
    }
}

^^der stack ist danach auch wieder wie neu.

[rüdiger]

@;fricky
Das ist aber iirc undefined behaviour. Weil es ein VirtualMachineError ist (wie Bashar schon gesagt hat).

[Bashar]

Bitte nicht füttern

[;fricky]

rüdiger schrieb:

Das ist aber iirc undefined behaviour. Weil es ein VirtualMachineError ist

probier's aus. die sun-VM jedenfalls crashed nicht dabei und der stackspeicher wird auch freigegeben. gibt es überhaupt java-VMs, bei denen StackOverflowError nicht fangbar ist?

[ykcirf;]

;fricky schrieb:

probier's aus. die sun-VM jedenfalls crashed nicht dabei

Du kennst die Bedeutung von "undefined behaviour"?

[;fricky]

ykcirf; schrieb:

;fricky schrieb:

probier's aus. die sun-VM jedenfalls crashed nicht dabei

Du kennst die Bedeutung von "undefined behaviour"?

klar, aber ich glaube nicht, dass es undefiniert ist. wozu bräuchte man dann einen fangbaren 'StackOverflowError'? es soll angeblich JVMs, die stattdessen einen 'OutOfMemoryError' bringen (die haben einen dynamisch erweiterbaren stack, der den selben bereich nutzt, wie normale Java-objekte auch). da könnte es sein, das bei 'nem stacküberlauf die VM aussteigt. vielleicht kann uns mal einer erleuchten.

[hustbaer]

Bashar schrieb:

hustbaer schrieb:

"Neben" dem Stack könnten ja andere Daten liegen. Und ohne Stack-Probes könnte man die überschreiben, ohne jemals die Guard-Page zu treffen. z.B. wenn man von einem grossen Puffer nur einen kleinen Teil verwendet.

Wozu muss man das überhaupt über eine Guard-Page realisieren?

Weil es schneller ist.

Bei Funktionen die weniger als 1 Page Stack brauchen muss bei Verwendung von Guard-Pages garkein zusätzlicher Code erzeugt werden/laufen.
Und "nix" ist halt immer schneller als "nicht nix".

Wenn das ginge, müsste man den Aufruf mit einer Exception sterben lassen und das wärs gewesen. In Java ist das ja leider ein VirtualMachineError, d.h. man kann danach nicht weitermachen, aber dass das zwingend ist, seh ich nicht ganz ein.

Ich bin mir fast sicher, dass es sowohl mit Java als auch mit C, C++, ... möglich wäre, dem Thread bloss eine Exception vor den Latz zu knallen, und ihn dann weiterlaufen zu lassen.

Bloss würde das wirklich viel bringen? Ist es so wichtig nach eine Stack-Overflow weitermachen zu können?
IMO ist das ähnlich wie wenn man Access-Violations in C++ fangen möchte. Mit diversen Compilern geht das auch durchaus, nur bestreite ich dass es sonderlich sinnvoll ist. Lieber ein Programm schreiben was garnicht erst solchen Mist baut, als dann schwindligerweise diverse Exceptions zu fangen.

[Bashar]

hustbaer schrieb:

Bloss würde das wirklich viel bringen? Ist es so wichtig nach eine Stack-Overflow weitermachen zu können?
IMO ist das ähnlich wie wenn man Access-Violations in C++ fangen möchte. Mit diversen Compilern geht das auch durchaus, nur bestreite ich dass es sonderlich sinnvoll ist. Lieber ein Programm schreiben was garnicht erst solchen Mist baut, als dann schwindligerweise diverse Exceptions zu fangen.

Das ist nicht ganz vergleichbar. Ein Stackoverflow heißt ja erstmal nur, dass das Programm zuviele Resourcen belegt. Vielleicht hätten ja 4 zusätzliche Bytes schon ausgereicht, wer weiß? Das ist eher einem OutOfMemory vergleichbar. Eine Access Violation deutet dagegen immer auf einen Programmierfehler hin.

[;fricky]

hustbaer schrieb:

Ich bin mir fast sicher, dass es sowohl mit Java als auch mit C, C++, ... möglich wäre, dem Thread bloss eine Exception vor den Latz zu knallen, und ihn dann weiterlaufen zu lassen.

mit java geht's ja (siehe oben), mit C (C++ wohl auch), allerdings mit unterstützung des OS (windoof in dem fall) geht es so:

include <stdio.h>                

#define GET_ESP(x) __asm mov x, esp;

void crash (void)
{
  unsigned stackptr;
  GET_ESP(stackptr);
  printf ("%x ", stackptr);
  crash();  // recursive on all control paths, function will cause runtime stack overflow
}

int main(void) 
{
  unsigned before, after;

  GET_ESP(before);
  __try
  {
    crash();
  }
  __except (1)
  {
    puts ("\nCRASH!");
  }
  GET_ESP(after);

  printf ("ESP before: %x after: %x\n", before, after);

}

^^ und der compiler muss __try/__except kennen (ms visualC z.b.)

[hustbaer]

@Bashar:
Ein Stack-Overflow ist IMO auch ein Programmierfehler.

In C++ kommt übrigens auch noch etwas dazu: das Stack-Unwinding. Schreib mal eine Klasse mit dtor, wo der dtor sagen wir mal 10KB Stack braucht.

Dann nimm den Code von fricky, und leg in "crash" eine lokale Instanz dieser Klasse an.
Und dann guck, ob das Programm das überlebt.

Ich schätze die Chancen sind fast null. Du wirst während des Stack-Unwinding nach dem Stack-Overflow einen weiteren Stack-Overflow basteln. Und tschüss.

Da es mittlerweile recht üblich ist, diverse potentiell Stack-hungrige Operationen in einem dtor laufen zu lassen (RAII, bzw. ganz allgemein modernes C++), ist das Beispiel IMO auch nicht ganz unrealistisch.

Stack-Overflow ist Kacke, und hat in einem korrekten Programm nix verloren. Gibt IMO keine Entschuldigung dafür. Daher finde ich die Suche nach Möglichkeiten nach einem Stack-Overflow zu recovern auch nicht sinnvoll.

[Bashar]

hustbaer schrieb:

@Bashar:
Ein Stack-Overflow ist IMO auch ein Programmierfehler.

Das heißt Rekursion ist ein Programmierfehler. Magst du so sehen, seh ich anders.

[hustbaer]

*seufz*

Jetzt sind wir wieder ganz am Anfang angelangt, der ganze schöne Thread war also für nichts.

Naja, es kann nicht jeder alles verstehen.

Dabei steht doch schon in der Bibel "Du sollst nicht Stapel überlaufen" (oder so ähnlich).

[;fricky]

hustbaer schrieb:

In C++ kommt übrigens auch noch etwas dazu: das Stack-Unwinding. Schreib mal eine Klasse mit dtor, wo der dtor sagen wir mal 10KB Stack braucht.
Dann nimm den Code von fricky, und leg in "crash" eine lokale Instanz dieser Klasse an.
Und dann guck, ob das Programm das überlebt.

ich schätze das wird es, denn das __try merkt sich den ESP vorm funktionsaufruf, sollte also egal sein, was die funktion mit dem stack anstellt. schon mal ausprobiert?

Bashar schrieb:

Das heißt Rekursion ist ein Programmierfehler.

rekursion, ohne die rekursionstiefe zu berücksichtigen, ist ein programmierfehler. aber zum glück brauchen sinnvolle rekursive algos garnicht so viel stackspeicher wie's scheint.

[Bashar]

hustbaer schrieb:

Jetzt sind wir wieder ganz am Anfang angelangt, der ganze schöne Thread war also für nichts.

Wir waren die ganze Zeit am Anfang. Ich wollte nur nochmal wissen, ob du das wirklich meinst, was du die ganze Zeit andeutest.

Dabei steht doch schon in der Bibel "Du sollst nicht Stapel überlaufen" (oder so ähnlich).

Mir doch egal was die Schweizer abstimmen.

[hustbaer]

;fricky schrieb:

hustbaer schrieb:

In C++ kommt übrigens auch noch etwas dazu: das Stack-Unwinding. Schreib mal eine Klasse mit dtor, wo der dtor sagen wir mal 10KB Stack braucht.
Dann nimm den Code von fricky, und leg in "crash" eine lokale Instanz dieser Klasse an.
Und dann guck, ob das Programm das überlebt.

ich schätze das wird es, denn das __try merkt sich den ESP vorm funktionsaufruf, sollte also egal sein, was die funktion mit dem stack anstellt. schon mal ausprobiert?

Er kann sich ESP und EBP merken und dazu noch in dreifacher Ausfertigung ausdrucken und es wird nix bringen. Der Dtor muss laufen, bevor der Stack-Pointer zurückgesetzt wird, da das zu zerstörende Objekt ja schliesslich auf dem Stack liegt. Ergebnis: BUMM.

Folgendes Programm:

#include <windows.h>
#include <stdio.h>

class needs_muchos_stackos_in_dtor
{
public:
	~needs_muchos_stackos_in_dtor()
	{
		char muchos_stackos[10 * 1024];
		strcpy(muchos_stackos, "~needs_muchos_stackos_in_dtor\n");
		::OutputDebugStringA(muchos_stackos);
	}

	char some_wasted_space_to_speed_things_up[50];
};

int recusrion()
{
	needs_muchos_stackos_in_dtor nms;
	if (::GetVersion() == 0)
		return 123;
	else
		return recusrion() + recusrion();
}

int main(int argc, char* args[])
{
	__try 
	{
		printf("%d\n", recusrion());
	}
	__except (EXCEPTION_EXECUTE_HANDLER)
	{
		::OutputDebugStringA("__except\n");
	}
}

Ergebnis mit /EHsc:

First-chance exception at 0x00cf1407 in vc9test.exe: 0xC00000FD: Stack overflow.
__except
The program '[876] vc9test.exe: Native' has exited with code 0 (0x0).

Der Dtor wird wie erwartet nicht ausgeführt, da /EHsc. Das Programm verhält sich nicht korrekt, da auf den Dtor geschissen wurde. Inakzeptabel.

Ergebnis mit /EHa:

First-chance exception at 0x00d21407 in vc9test.exe: 0xC00000FD: Stack overflow.
First-chance exception at 0x00d219c7 in vc9test.exe: 0xC0000005: Access violation reading location 0x00150000.
First-chance exception at 0x00d219c7 in vc9test.exe: 0xC0000005: Access violation reading location 0x00150000.
First-chance exception at 0x00d219c7 in vc9test.exe: 0xC0000005: Access violation reading location 0x00150000.
Unhandled exception at 0x00d219c7 in vc9test.exe: 0xC0000005: Access violation reading location 0x00150000.
The program '[5012] vc9test.exe: Native' has exited with code -1073741819 (0xc0000005).

Bumm. Inakzeptabel.

Noch Fragen?

[;fricky]

hustbaer schrieb:

Er kann sich ESP und EBP merken und dazu noch in dreifacher Ausfertigung ausdrucken und es wird nix bringen. Der Dtor muss laufen, bevor der Stack-Pointer zurückgesetzt wird, da das zu zerstörende Objekt ja schliesslich auf dem Stack liegt. Ergebnis: BUMM.

ein 'bumm' ist es ja eben nicht, wenn du die exception geeignet abfängst.

hustbaer schrieb:

Das Programm verhält sich nicht korrekt, da auf den Dtor geschissen wurde

das ist allerdings wahr.

hustbaer schrieb:

Noch Fragen?

nö. ich könnte jetzt mal wieder ein paar ätzende bemerkungen über eine bestimmte programmiersprache machen, aber dass lasse ich diesmal.

[hustbaer]

;fricky schrieb:

hustbaer schrieb:

Er kann sich ESP und EBP merken und dazu noch in dreifacher Ausfertigung ausdrucken und es wird nix bringen. Der Dtor muss laufen, bevor der Stack-Pointer zurückgesetzt wird, da das zu zerstörende Objekt ja schliesslich auf dem Stack liegt. Ergebnis: BUMM.

ein 'bumm' ist es ja eben nicht, wenn du die exception geeignet abfängst.

Man kann die Exception nicht geeignet abfangen, das ist es ja gerade.
Wenn du C programmieren willst fein, programmier C. Wenn du C++ programmieren willst kannst du es aber vergessen.

BTW: du kannst in C genauso probleme bekommen, wenn du __finally Blöcke verwendest die einiges an Stack brauchen.