• C

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,
LVL 5
basiclifeAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

brettmjohnsonCommented:
You can:

1) Minimize stack used by using dynamically structures to hold state.
This can limit the size of your passed parameters to 1 pointer, and local variables to 0 or 1 pointer.

2) Use 'fastcall' syntax if your compiler supports it.  This uses registers to pass data rather than the
stack.

3) Compile your program to preallocate more stack up front.  You already know this, but set it BIG.

4) If the native threads package allows you to specify the stack size at thread creation time, run
you recursive algorithm in a separate thread (specifying a sufficient stack size).


0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
basiclifeAuthor Commented:
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?
0
PaulCaswellCommented:
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
0
ON-DEMAND: 10 Easy Ways to Lose a Password

Learn about the methods that hackers use to lift real, working credentials from even the most security-savvy employees in this on-demand webinar. We cover the importance of multi-factor authentication and how these solutions can better protect your business!

brettmjohnsonCommented:
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
0
grg99Commented:
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.

0
basiclifeAuthor Commented:
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?
0
brettmjohnsonCommented:
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.

0
basiclifeAuthor Commented:
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?
0
grg99Commented:
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.

0
basiclifeAuthor Commented:
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.
0
PaulCaswellCommented:
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
0
basiclifeAuthor Commented:
Excellent suggestion, thanks! I'll have a go at that now...
0
PaulCaswellCommented:
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.
}
0
basiclifeAuthor Commented:
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
0
PaulCaswellCommented:
Good point!!

Not enough coffee??

Paul
0
grg99Commented:
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.

0
basiclifeAuthor Commented:
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.
0
grg99Commented:
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.

0
basiclifeAuthor Commented:
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?
0
basiclifeAuthor Commented:
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
0
PaulCaswellCommented:
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
0
grg99Commented:
Your code looks pretty clean, just a few things that could be tidied up:

you don't need to pass nestdepth as a parameter, I think it could be a global, you could just increment it  on entry, decrement on exit.  Won't keep track of exactly the "deepest" nesting, instead it keeps track of the current number of calls, which is quite similar.

Your little array is basically -1, 0, 1 plus the current x and y coords.  You should be able to just have a global array with -1, 0, 1, and then just add your current x and y to them, in a for loop going thru all three possibiities, both in x and y.  That saves a bunch of stack space per call.

I still don't see why it blows up at ~7000, hmmm....




0
basiclifeAuthor Commented:
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.
0
basiclifeAuthor Commented:
Meant to say thanks to PaulCaswell as well. Didn't see your post as I clicked on the link in the email... Sorry
0
basiclifeAuthor Commented:
Oh and 'cos I know y'all want to see it, a screenshot:

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

:D
0
stefan73Commented:
Hi basiclife,

>It always bugged me that I had a limit on my maze size

If you want to solve a maze, why do you backtrack at all?

You could use an entirely different algorithm, involving "keeping the wall on your right", each "step" consisting of:

Turn right;
while(standing in front of wall)
    turn left;
forward;

Store each step's maze coordinates in an array.
For each field of the maze, have a pointer (or array index) to the step's address (or array index). A field not entered yet is NULL/-1. Once a maze field is re-entered, the field won't be empty, so an unnecessary detour can be avoided.

For an n*n maze, memory consumption is O(n^2), with no nasty surprises.



Cheers!

Stefan
0
basiclifeAuthor Commented:
What if there's a complete circuit around the outside of the maze? Also, backtracking at dead ends unless I'm misunderstanding you?
0
PaulCaswellCommented:
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
0
basiclifeAuthor Commented:
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.
0
PaulCaswellCommented:
Further thought has suggested that the random approach to the first direction to check might be the most entertaining option as, since you are recursing through all possible solutions your first solution might be entertainingly creative.

A really long option would be detecting whether you have enumerated ALL solutions and only print the shortest ones. That could take weeks to run but would be quite fun to see. You'd have to print ALL the solutions that are shortest, there may be many of them. I'd expect a two-pass solution, one pass to find the length of the shortest solution and one pass to print all solutions of that length. As I said, a weeks-long run could be expected.

Paul


0
grg99Commented:
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.

0
basiclifeAuthor Commented:
Could you show me how you did that?
0
basiclifeAuthor Commented:
Oh and sorry I was awayf or a few days - Had to disappear over ythe weekend. Should be here from now on
0
grg99Commented:
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.



0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.