Link to home
Start Free TrialLog in
Avatar of basiclife
basiclife

asked on

Another Stack Question - programatically modify it's size

OK, with the standard stack size of 1M, my recursion nests approx 7180 times before it frops to the console.

I'm using MS Visual C++ 6, WinXP

I've found ways to modify the stack size at compile time using stack size and editbin /stack 4096 filename.exe etc...

My problem is, the size of the stack required depends on the input file passed to the program. I need, therefore, to be able to allocate more space to the stack IN my code. Also, I'm not looking to do anything clever with the stack - I don't store variables there myself, just use it to keep track of local var when recursing.

Any help greatly appreciated

Thanks,

Simon,
ASKER CERTIFIED SOLUTION
Avatar of brettmjohnson
brettmjohnson
Flag of United States of America image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of basiclife
basiclife

ASKER

Ok, could you explain 2 & 4 if you wouldn't mind - I've found out everything I have so far by googling excessively. I'm guessing by 3 you mean just increase the stack size using the compiler in which case, yes I know it.

Thanks foir your help.

Also, is there no way to dynamically modify the stack size for an existing thread?
You could try switching to a new stack. I do this in a TSR so forgive the naming:

// Huge pointers force compiler to do segment arithmetic for us.
char __huge *TsrStack;
char __huge *AppStack;

...

                              // Switch to my stack.
                              _disable();
                              __asm mov  sp, WORD PTR TsrStack[0]
                              __asm mov  ss, WORD PTR TsrStack[2]
                              _enable();

...

                              // Restore application stack.
                              _disable();
                              __asm mov  sp, WORD PTR AppStack[0]
                              __asm mov  ss, WORD PTR AppStack[2]
                              _enable();

You could allocate some large chunk of memory and treat it as a stack while you recurse.

Paul
Paul,

Switching stacks doesn't work if you use any of the Microsoft libraries, which
are usually compiled with stack overflow checking enabled (or so it was some
10 years ago.)   I actually accomplished a stack swap in the past by overriding
the system stack overflow check routine.  Given a day, I could probably dig up
the code.

Brett
There should be no downside to setting up a big stack at compile time.

The stack isnt saved in the .exe file, so a big stack doesnt make the executable file any bigger.

And most machines nowadays have a lot more than 1 megabyte of memory, so you can afford to splurge on the stack size.

Messing with the stack at run-time is darned difficult, you have to know a lot of details about exception stack frames, regular stack frames, ebp links,segment attributes,  and more stuff than you probably care to know.

Ok, the stack isn't saved in the exe so that's not a problem exe-wise but let me explain more:

my prog is looking at adjacent "squares" in an array and calling itself (or other functions) based on what it finds. (and yes I KNOW recursion is horribly inefficient! but that's the method in place). The size of the arrays is variable and so assigned dynamically using malloc. I'm looking for somethign similar to work for the addresses in the stack.

I could just assign 256MB (All avaiable mem in this case) but then that's horribly inefficient if the arrays are tiny, on the other hand if I assign 2MB and the functions need 2.5, the prog drops out without an error message.

And yes I am using MS libraries

grg99: Can you point me to somewhere where I can find out about the things mentioned? Or is there some library which handles it all for you hidden on the web under the GPL / Similar?
Specifying a large stack will not by "horribly inefficient" if you don't use it.  Modern OS's will reserve
sufficient address space to hold that size stack, but will not actually allocate or the full memory in
advance.  The OS  will allocate new virtual memory pages for stack space as you need it.
Reserving a huge amount of address space for your stack will diminish the amount of memory
available for dynamic memory allocations.

OK, my misunderstanding, so I can reserve it but not have it allocated? If I specify (request I suppose) a stack size of 1 Gig, it'll be there if I need it but there will be no penalty to the system UNLESS I use it? Please excuse my lack of knowledge I've come from Aseembler, PHP so I get the REALLY low-level stuff and the REALLY high level stuff but am vague about the middle bits

Obv. 1 G is ridiculous but you get the idea?
brett's right:  If you're using a OS with virtual memory, just asking for 100MB of stack doesnt really tie up 100MB of RAM immediately.  It's only allocated a chunk at a time to actual RAM when your stack expands into a new chunk.  

Also, are you sure your program is working correctly?   It's hard to imagine a recursive algorithm that really needs to go 7000 levels deep.  Look the algorithm over and see if there's some simple case that could be done by looping instead of by recursion..  Good candidates for looping are places where you're just linearly going down a list, no need to do this by recursion.

As others have suugested,  you might look over your local variable usage, it looks like you're using about 120 bytes per call. Factor out or reduce the size of any variables you don't really need to save at each call.  For example if you have a "char TempStr[80]", it's likely you don't need this saved for each invocation.   Also watch out for hidden stack variables, allocated by the compiler if it needs any anonymous structs.

My prog is working as per spec  *unfoirtunately) and 7000 was when I gave it a HUGE task with worst-case situation but still... It should be able to either handle it or fall over nicely.

Thanks everyone for your help. Will play around with the stack size tonight and then award tomorrow.
Have you tried emulating a stack for most of the data?

I.E. instead of:

void function ( int q )
{
 struct S s;
...
 function (q+1);
...
}

use:

void function ( int q )
{
 struct S * = (struct S *)  calloc ( sizeof(S), 1 );
...
 function (q+1);
...
 free ( s );
}

This should reduce the per-iteration stack munch to just return addresses and parameter variables.

Paul
Excellent suggestion, thanks! I'll have a go at that now...
Thanks!

Dont forget to:

...
struct S *s = (struct S *)  calloc ( sizeof(S), 1 );
if ( s != NULL )
{
...
 function (q+1);
...
 free ( s );
}
else
{
 // Collapse quietly in a heap.
 // Do not display a message here as we may be quite deep in the recursion.
 // Perhaps here should be a setting of an error condition.
}
Why would actually outputting ane rror cause a problem? Shouldn'yt this condition ONLY occur at the latestr ecursion? So say we're 300 deep, the 300th one would pop an error and then the rest would pop back up in order quetly? Although I can see why an error bit would be useful or just returning some impossible value
Good point!!

Not enough coffee??

Paul
Please note this warning again:  recurring more than 64 times seem to my fuzzy intuition, logically implies you're doing something that could be done in a linear fashion:  each recursion that really does recursive work usually results in a splitting into two sub-trees.  If you have 64 levels of this, that's 2^64 active nodes, which is an unlikely amount of data you have to process.

Easiest way to explain this is to explain the situation: It's pretty close to the age-old solving of a maze. In each "square" defined on a dynamically sized 2D array, I look at each square next to me and if it's not a wall, I call a the "look" function again on that square until I find a goal. If there are no free squares (not including the one I came from), I return a 0, thereby "backtracking". So if the maze is huge (ie 300x300) that's 90K squares. The adv. of recursion is that it backtracks nicely at dead-ends.

This was actually a Q. I was set in the 1st year at Uni. It always bugged me that I had a limit on my maze size (Actually one Q was something like "why is there a limit on how deep you can nest recursions?") and I REALLY wanted to be able to say my program has no limit except available memory. The problem is running out of stack space, hence this question. Ideally I want to solve ANY sized maze (memory permitting).

Now I'm in the 2nd year and not doing C any more (mostly assembler / xlilinx / etc...) and I want to keep the C knowledge going. This seemed like a good problem to solve as it's technically challenging and (hopefully) worth knowing.
Okay, you might want to look into these optimization tricks:

(1)  skip along a corridor until you find a doorway instead of just recurring to the next position.  That should save a LOT of calls.

(2) Figure out why each call uses 120 bytes of stack space.  You might be able to trim that way down, giving you lots more levels of recursion.

Ok, my Step function is:

doStep (int stepX, int stepY, int nestDepth) {
      int testCoords[8];            //Store the steps to test
      int testNum;                  //Loop through each test Step
      int testStepX, testStepY;
      writePath(stepX, stepY, nestDepth);
      nicePath(nestDepth);


      /*

      This is where we're going to do most of the processing...

      In short: We will try each cell (up, down, left, right) from teh current. if the cell is
      blocked we will ignore it. If not, we will call this proceudure again, with the new cell
      if we find the goal, we will write our current position into the solvePath array at
      the item that corresponds to your current nest depth, then we will return a 1 to tell the
      parent function that we have found the goal and that it should do the same.

      Also, as we process each cell, we will mark it as "current path" so the function doesn't
      keep oscillating between cells.

      
      NB: In the map;

            0=Wall
            1=Path
            2=Goal
            3=Tested (Invalid / dead end path)
            4=Buggy (current (live) path)
      */


      //Begin by marking this square tested...
      writeMap(stepX, stepY, 4);


      if(showSteps == 1) {
            cls();
            drawMap();
            printf("Press return to see the next step... Path Length %i. Solve path length: %i", nestDepth, solvePathLength);
            gets(tmpString);
      }

      if(nestDepth == 7180) {
            printf("WARNING:: Nest Depth is %i: We will run out of stack space (1MB) soon, unless stack size was increased at compile-time!!\n", nestDepth); //Kick up a stink is we're running out of stack space
      }

      //List the co-ordinates to try from current square


            testCoords[6] = stepX-1;      //Left
            testCoords[7] = stepY;
            testCoords[4] = stepX;            //Up
            testCoords[5] = stepY-1;
            testCoords[2] = stepX+1;      //Right
            testCoords[3] = stepY;
            testCoords[0] = stepX;            //Down
            testCoords[1] = stepY+1;      

      for(testNum=0; testNum<4; testNum++) {
            testStepX = testCoords[testNum*2];
            testStepY = testCoords[testNum*2+1];

            if(testStepX >= 0 && testStepX <=arrSize && testStepY >= 0 && testStepY <=arrSize ){ // Check we haven't left the map. This should never fail as there should always be a border.
                  switch(readMap(testStepX, testStepY))
                  {
                        case 0:                        // Wall
                              break;

                        case 1:                        //Path
                              if(doStep(testStepX, testStepY, nestDepth+1) != 1) {
                                    break;
                              }

                        case 2:                        // Goal
                              writePath(testStepX, testStepY, nestDepth);
                              if(readMap(testStepX, testStepY)==2) {solvePathLength = nestDepth;}
                              return 1;
                              break;

                        default: //If we haven't already caught it, we don't care about it
                              break;
                  }
            }
      }
      writeMap(stepX, stepY, 3);
      return 0;
}

Now I'm certain there are thousands of ways to optimise it but... Why is it using so much data on the stack? Would I be better off not using testCoords[] and just having 4 loops hard coded with 4 directions?
As tos kipping down a coridor, excellent idea  which would work in most cases except the worst-case (ie empty maze with goal in far corner from start) in which case it takes pretty much the longest possible path
With a bit of maths you should be able to do without:

     int testCoords[8];          //Store the steps to test
     int testNum;               //Loop through each test Step
     int testStepX, testStepY;

and 'nestDepth' for that matter but that may not be a good plan at this stage.

Paul
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
grg99: Thanks :) I'll implement those changes ASAP. As long as nestDepth contains the current depth (which it should with your method) it'll still all work OK

When it finds the goal, as it steps back through the itterations, it fills in the solution path using nestDepth as the index for the array


The full code is at:

http://bristol-house.demon.co.uk/pathfinder/Pathfinder.c

OR

You can download the compiled version with the specification map (and some LARGE ones generated randomly oin /debug) from :

http://bristol-house.demon.co.uk/pathfinder/dlaszip.php

FYI:

nicePath: (converts the plain text characters used into the map into relatively nice ASCII.) It's huge and bloated and added as an afterthought but it looks so much nicer. Still needs work minimising it though. drawMap() was modified to take these changes into account too...

Also, the code is OS-specific - it requires a windows OS (it uses the Cls command as it was a simple way of avoiding clearing the screer, moving the cursor, etc...) that's inside the Cls() function.

I'm only posting all this here so you acn see the prog dying yourself.
Meant to say thanks to PaulCaswell as well. Didn't see your post as I clicked on the link in the email... Sorry
Oh and 'cos I know y'all want to see it, a screenshot:

http://bristol-house.demon.co.uk/pathfinder/screenshot.jpg

:D
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
What if there's a complete circuit around the outside of the maze? Also, backtracking at dead ends unless I'm misunderstanding you?
Nice snapshot! It shows some room for optimisation.

First I'd split the 'for' loop up into 2. First cycle will do a complete scan around the current position looking for solution. Second looks for wall/path. Thi would avoid the rather embarassing moment where you walk right past the solution.

Second I'd alternate the order of search around the current point. E.G. Depending on low 3 bits of level or perhaps a random number, look North/North-East/East/... first. This may stop at least the predictability of the wiggle when tracking open space.

Paul
Good thinking, thanks for the input!

"Thi would avoid the rather embarassing moment where you walk right past the solution." Yeah it's even worse when stepping through and it gets to next to the goal and someone says "well done!" and then it carries right on past it :D

I'm going to play some more with this then dish out points. I have also increased this to 500 points, considering how much help everyone has offered.
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Ok, I downloaded the source code and made some rough stack-economizing patches.  Got the stack usage down from 48 bytes per call to 20.  Hard to get it lower than that as the recursive routine pushes 5 registers.

Could you show me how you did that?
Oh and sorry I was awayf or a few days - Had to disappear over ythe weekend. Should be here from now on
remove the depth as a parameter.

remove the array as a local variable, make a global array that is initialized to the x and y deltas.

Thats about it.