GNU Compiler - Rekursionstiefe

Christian++ 1

Hallo!

Ich wäre unglaublich froh, wenn mir jemand bei folgendem Problem weiterhelfen könnte: Ich habe einen Merge-Sort-Algorithmus implementiert, der bekanntlich (sofern man ihn nicht iterativ programmieren will) doppelt rekursiv ist:

void MergeSort (long *Array, long left, long right)
{
   (...)
   MergeSort (Array, Left, Middle);
   MergeSort (Array, Middle+1, Right);
   (...)
}

Die höchst mögliche Anzahl an Longs, die ich sortieren kann, liegt bei 252 ... darüber CTD ... gibt es irgend eine Möglichkeit, den GNU Compiler (g++ unter Win XP 32) so einzustellen, dass eine größere Rekursionstiefe möglich ist? Oder kommt der Absturz von einem unvermeidbaren Stack Overflow?

Im WWW hab ich diesbezüglich kaum Infos gefunden, und meine Kenntnisse in diese Richtung gehen leider gegen NULL...

Danke & lg
Christian

Jochen Kalmbach

Wenn man irgendwas nicht unbedingt rekursiv programmieren muss, dann sollte man es vermeiden!

Du kannst natürlich die Stack-Größe beim Linker größer angeben (default AFAIK 1 MB). Aber macht es lieber nicht rekursiv.

c.rackwitz

was ist ein CTD?

Christian++ 1

Tja ... Mir geht es unter anderem um die Laufzeitunterschiede zwischen iterativer & rekursiver Implementierung (und da hätte ich bei beiden gerne mehr als 250 items sortiert).

CTD = Crash to Desktop ... immer diese Abkürzungen: Programmabsturz meinte ich !

Wie lautet denn der Befehl für die Stacksizeveränderung beim Linker?

Jochen Kalmbach

Beim MS-Linker heisst der "/STACK:reserve,commit"... wie der bei g++ heisst keine Ahnung...

rüdiger

Tipp: Handbuch

http://www.gnu.org/software/binutils/manual/ld-2.9.1/ld.html
http://gcc.gnu.org/onlinedocs/

Maxi

also der compiler kann doch eigentlich unedlich tief rekursivieren
Für ihn ists ja nur ein function-call.

Zur Laufzeit schmiert das dann ja erst ab, wohl mit Stackoverflow.
Also hilft stack vergrößern, oder:
den Speicher den du auf dem Stack anforderst, pro funktionsaufruf zu minimieren. Also große Arrays etc nihct auf dem Stack sondern auf dem heap und danach wieder freigeben.
Eigentlich alle Variablen auf den Heap packen wenn sizeof(var)>sizeof(var*). Na man kanns auch übertreiben, aber du kannst ja ma versuchen den Stack nciht so zu belasten mit lokalen Variablen.

btw:

int rek()
{
  int rek();
  int rek();
}

Is imho vom Stackgebrauch das gleiche wie:

int rek()
{
  rek();
}

Es werden ja nciht beide Funktionen zugleich aufgerufen, sondern wenn die zwiete aufgerufen wird, is die erste ja schon wieder von stack runter.

Christian++ 1

Also im GNU Compiler/Linker Manual hab ich keine entsprechende Option gefunden - ist aber halb so schlimm, da ich per Remoteverbindung einen Linux-Server benutzen kann, der schafft eine Sortierung von 10 Millionen Items...

Danke trotzdem
Christian