std::stack wird zu groß ...?

Hallo!

Ich hab ein lustiges Problem. Ich schreib gerade eine Funktion um, die sich bisher rekursiv selbst aufgerufen hat, und das schonmal locker 100.000nde von Malen. Ergbnis: regelmäßige Abstürze.

Die neue Variante funktioniert so: Alle Daten, die noch verarbeitet werden müssen werden jetzt in einen std::stack gelegt. Also keine rekursiven Aufrufe mehr, sondern nurnoch ein großer Stack, der in einer while-Schleife abwechselnd abgearbeitet bzw. aufgefüllt wird.

Unter Linux 64Bit war damit das Problem mit dem Absturz wegen immenser Rekursionstiefe erledigt - alles läuft. Unter Windows 32Bit scheint das Problem quasi das selbe zu sein. Bei kleinen Datenmengen tut alles, bei den großen (=großer Stack mit 100.000nden Einträgen) schmiert das Programm ab. Genauso wie damals mit der Rekursions-Variante, die lief auch nur mit kleinen Eingabedaten.

Wie kann ich da vorgehen?? Ein Stack sollte doch wohl auch Millionen von Einträgen verwalten können...?!

Hier ein grober Auszug aus dem Code, für den Fall...

int size;
int from;
T value;
long mapIndexStack;
int pos[4];

std::stack<int>   positionStack;
positionStack.push( x );
positionStack.push( y );
positionStack.push( z );
positionStack.push( -1 );

   size = 0;
   while ( !positionStack.empty() )
     {
     pos[3] = positionStack.top();
     positionStack.pop();
     pos[2] = positionStack.top();
     positionStack.pop();
     pos[1] = positionStack.top();
     positionStack.pop();
     pos[0] = positionStack.top();
     positionStack.pop();
     from = pos[3];
     value = inPtr[ pos[2]*incZ + pos[1]*incY + pos[0] ];
     mapIndexStack = dims[0]*dims[1]*pos[2] + dims[0]*pos[1] + pos[0];
     if (value == match)
       {
       if (LabelMap.find(mapIndexStack) == LabelMap.end())
         {
         LabelMap[mapIndexStack] = currentLabel;
         size++;
         /// continue in -/+ X directions
         if ( (pos[0]>0) && (from != 1) )
           {
           positionStack.push( pos[0]-1 );
           positionStack.push( pos[1] );
           positionStack.push( pos[2] );
           positionStack.push( 0 );
           }
         if ( (pos[0]<dims[0]) && (from != 0) )
           //... und das ganze noch 5 Mal für alle Richtungen
         } // if pixel wasn't currentLabeled
       } // if pixel is foreground
     } // while stack not empty
  ///set object size
  ...

theliquidwave

Ich kenne std::stack nicht. Aber vom Namen lasse ich mal darauf schließen, dass es alle Daten auf dem Stack speichert. Und unter Windows ist der Stack afaik nur 8MB groß - wenn es mehr werden crasht es. Heap benutzen oder wirklich schauen, ob du alle Daten im Stack haben musst.

Gruß

std::stack ist ein Container-Adapter, der die Funktionalität eines Stapelspeichers zur Verfügung stellt. Per Default speichert er die Daten in einer std::deque.

Bei ein paar hunderttausend Elementen bewegen wir uns, wenn die Implementierung nicht völlig hirnverbrannt ist, im Bereich von ein paar Megabyte auf dem Heap, das sollte also problemlos gehen. Wie groß wird dein Stack denn genau, und gibt es vielleicht noch andere Teile des Programms, die eine Menge Speicher anfordern? Und bist du sicher, dass es ein Speicherproblem ist (will sagen, schmeißt er std::bad_alloc)?

volkard

in den std::stack kriegst du locker ein gigabyte an daten rein. daran liegt es also nicht.

Sorry Leute, es lag mal wieder am User. Irgendwo im Code greif ich brutal auf nicht-reservierten Speicher zu. Das gute alte 0...size-1 Problem, im Speziellen hier:

if ( (pos[2]<dims[2]) && (from != 5) )

muss heißen

if ( (pos[2]<dims[2]-1) && (from != 5) )

Nur weil das Ding halt schon ewig in Linux funktionierte und hier in Windohs auch auf kleinen Bildern war ich etwas vom eigentlichen Problem abgelenkt...

Trotzdem Danke und viele Grüße,
Chiristian80

Nexus

Wenn du statt rohen Arrays das Klassentemplate std::tr1::array (oder boost::array ) nimmst, hast du solche Probleme nicht mehr. Dort gibt es nämlich im Debug-Modus wertvolle Laufzeitprüfungen. Ausserdem ist das Interface STL-kompatibel, bietet also nützliche Funktionen wie size() , begin() , end() . Und das Beste: Du hast im Release-Modus keinen Laufzeitoverhead. Es gibt also kaum einen Grund, auf diese Vorteile zu verzichten.

Ich persönlich verwende schon lange keine C-Arrays mehr.