?
Solved

Another Stack Question - programatically modify it's size

Posted on 2004-11-08
37
Medium Priority
?
1,172 Views
Last Modified: 2008-02-01
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,
0
Comment
Question by:basiclife
  • 16
  • 7
  • 7
  • +2
34 Comments
 
LVL 23

Accepted Solution

by:
brettmjohnson earned 500 total points
ID: 12530513
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
 
LVL 5

Author Comment

by:basiclife
ID: 12530576
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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12531193
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
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 23

Expert Comment

by:brettmjohnson
ID: 12532034
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
 
LVL 22

Expert Comment

by:grg99
ID: 12532123
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
 
LVL 5

Author Comment

by:basiclife
ID: 12535629
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
 
LVL 23

Expert Comment

by:brettmjohnson
ID: 12535832
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
 
LVL 5

Author Comment

by:basiclife
ID: 12536065
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
 
LVL 22

Expert Comment

by:grg99
ID: 12536148
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
 
LVL 5

Author Comment

by:basiclife
ID: 12537070
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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12542097
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
 
LVL 5

Author Comment

by:basiclife
ID: 12543642
Excellent suggestion, thanks! I'll have a go at that now...
0
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12543699
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
 
LVL 5

Author Comment

by:basiclife
ID: 12543926
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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12544069
Good point!!

Not enough coffee??

Paul
0
 
LVL 22

Expert Comment

by:grg99
ID: 12544074
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
 
LVL 5

Author Comment

by:basiclife
ID: 12544492
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
 
LVL 22

Expert Comment

by:grg99
ID: 12544707
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
 
LVL 5

Author Comment

by:basiclife
ID: 12545532
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
 
LVL 5

Author Comment

by:basiclife
ID: 12545554
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
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12545702
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
 
LVL 22

Assisted Solution

by:grg99
grg99 earned 500 total points
ID: 12545862
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
 
LVL 5

Author Comment

by:basiclife
ID: 12547025
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
 
LVL 5

Author Comment

by:basiclife
ID: 12547033
Meant to say thanks to PaulCaswell as well. Didn't see your post as I clicked on the link in the email... Sorry
0
 
LVL 5

Author Comment

by:basiclife
ID: 12547053
Oh and 'cos I know y'all want to see it, a screenshot:

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

:D
0
 
LVL 12

Assisted Solution

by:stefan73
stefan73 earned 500 total points
ID: 12557755
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
 
LVL 5

Author Comment

by:basiclife
ID: 12558073
What if there's a complete circuit around the outside of the maze? Also, backtracking at dead ends unless I'm misunderstanding you?
0
 
LVL 16

Expert Comment

by:PaulCaswell
ID: 12563418
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
 
LVL 5

Author Comment

by:basiclife
ID: 12564325
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
 
LVL 16

Assisted Solution

by:PaulCaswell
PaulCaswell earned 500 total points
ID: 12564415
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
 
LVL 22

Expert Comment

by:grg99
ID: 12564633
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
 
LVL 5

Author Comment

by:basiclife
ID: 12585114
Could you show me how you did that?
0
 
LVL 5

Author Comment

by:basiclife
ID: 12585123
Oh and sorry I was awayf or a few days - Had to disappear over ythe weekend. Should be here from now on
0
 
LVL 22

Expert Comment

by:grg99
ID: 12585985
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

Featured Post

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use switch statements in the C programming language.
Suggested Courses

850 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question