Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > stack overflow

Reply
Thread Tools

stack overflow

 
 
Allen
Guest
Posts: n/a
 
      11-16-2003
Hi all,

What are some different approaches to dealing with stack overflows in
C++? I'm especially interested in approaches concerned with speed for
infrequent overflows.
--

Best wishes,
Allen




 
Reply With Quote
 
 
 
 
Allen
Guest
Posts: n/a
 
      11-17-2003
> What are some different approaches to dealing with stack overflows in
> C++? I'm especially interested in approaches concerned with speed for
> infrequent overflows.

Even more specifically, I have a recursive BST function for a
potentially very large tree. What kinds of schemes have others come up with
for dealing with stack overruns of this type?
--

Best wishes,
Allen




 
Reply With Quote
 
 
 
 
Tanguy Fautré
Guest
Posts: n/a
 
      11-17-2003

"Allen" <allen-terri-ng!@#att.net> wrote in message
news:NnUtb.271894$(E-Mail Removed)...
> > What are some different approaches to dealing with stack overflows

in
> > C++? I'm especially interested in approaches concerned with speed for
> > infrequent overflows.

> Even more specifically, I have a recursive BST function for a
> potentially very large tree. What kinds of schemes have others come up

with
> for dealing with stack overruns of this type?
> --
>
> Best wishes,
> Allen
>
>


You can optimize the recursive function to use up less stack, for example by
using global (or member) variables instead of local variables.

See if you really need the recursivity. For example, IIRC a search in a BST
tree doesn't require a recursive function scheme but can work simply within
a loop.

There are other ways to optimize recursive functions.
But sometimes if there is really no solution then you have to make your own
stack and de-recursive the whole thing. But think of it as a last ressort,
and it's a very rare situation.

But I still think that for a BST there is no need for recursivity at all in
most, if not all, cases.

Yours,

Tanguy


 
Reply With Quote
 
Tanguy Fautré
Guest
Posts: n/a
 
      11-17-2003
>
> "Allen" <allen-terri-ng!@#att.net> wrote in message
> news:NnUtb.271894$(E-Mail Removed)...
> > > What are some different approaches to dealing with stack overflows

> in
> > > C++? I'm especially interested in approaches concerned with speed for
> > > infrequent overflows.

> > Even more specifically, I have a recursive BST function for a
> > potentially very large tree. What kinds of schemes have others come up

> with
> > for dealing with stack overruns of this type?
> > --
> >
> > Best wishes,
> > Allen
> >
> >

>
> You can optimize the recursive function to use up less stack, for example

by
> using global (or member) variables instead of local variables.
>
> See if you really need the recursivity. For example, IIRC a search in a

BST
> tree doesn't require a recursive function scheme but can work simply

within
> a loop.
>
> There are other ways to optimize recursive functions.
> But sometimes if there is really no solution then you have to make your

own
> stack and de-recursive the whole thing. But think of it as a last ressort,
> and it's a very rare situation.
>
> But I still think that for a BST there is no need for recursivity at all

in
> most, if not all, cases.
>
> Yours,
>
> Tanguy
>
>


Well there are cases where you cannot easily avoid recursivity, like a
prefix run through the tree (or any other depthfirst run), but then if you
have a stack overflow with a well written recursive function it means your
tree is unbalanced and then I suggest you look up for another structure but
similar such as a red-black tree (which is by the way the most common
implementation of std::map, so...)


 
Reply With Quote
 
Gianni Mariani
Guest
Posts: n/a
 
      11-17-2003
Allen wrote:
>> What are some different approaches to dealing with stack overflows in
>>C++? I'm especially interested in approaches concerned with speed for
>>infrequent overflows.

>
> Even more specifically, I have a recursive BST function for a
> potentially very large tree. What kinds of schemes have others come up with
> for dealing with stack overruns of this type?



Have you tried to allocate a bigger stack ? Some OS's allow you to
create bigger stacks.

Another alternative is to not use a recursive call but to create an
object that allows you to "stack" state in a "frame" object.


e.g.

// recursive function

int Recursive( node * here )
{

int has_stuff = 0;

if ( here )
{
has_stuff = here->do_some_stuff();

has_stuff += Recursive( here->left );

has_stuff += Recursive( here->right );

}

return has_stuff;
}

//
// non-recursive way to do the same thing -
//

//
// This class stores the state that would have been stored
// on the stack.
//

class Stuffer
{
public:

int m_has_stuff;
node * m_node;

enum State
{
DoLeft,
DoRight,
Done
};

State m_state;

Stuffer( node * i_here )
: m_has_stuff( i_here->do_some_stuff() ),
m_here( i_here ),
m_state( DoLeft )
{}

void Next()
{
switch ( m_state )
case DoLeft : m_state = DoRight; break;
case DoRight : m_state = Done; break;
case Done : break;
}
}
};

//
// This method performs everything in a while loop - no
// recursive calls.
//

int NonRecursive(node * here)
{

std::list<Stuffer> stuff_stack;

stuff_stack->push_front( Stuffer( here ) );

while ( stuff_stack->begin() != stuff_stack->end() )
{
std::list<Stuffer>::iterator p_stuffer = stuff_stack->begin();

switch ( p_stuffer->m_state )
{
case DoLeft :
stuff_stack->push_front(Stuffer(here->left));
p_stuffer->Next();
break;
case DoRight :
stuff_stack->push_front(Stuffer(here->right));
p_stuffer->Next();
break;
case Done :
std::list<Stuffer>::iterator p_last = p_stuffer;
p_last ++;
if ( p_last == stuff_stack->end() )
{
return p_stuffer->m_has_stuff;
}
p_last->m_has_stuff += p_stuffer->m_has_stuff;
stuff_stack->erase( p_stuffer );
break;
}


}

// should never get here
return 0;
}


..... this is all off the top of my brain - I didn't compile or verify
that this works - I just thought it's a good example of how to decompose
a recursive function into a separate stack.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
Why stack overflow with such a small stack? Kenneth McDonald Ruby 7 09-01-2007 04:21 AM
SDM Java stack overflow Art Cisco 1 02-18-2006 07:34 PM
smart navigation gives stack overflow Mr m?ll ASP .Net 2 10-16-2004 01:09 PM
Stack overflow exception =?Utf-8?B?amJpeEBuZXdzZ3JvdXBzLm5vc3BhbQ==?= ASP .Net 5 04-22-2004 04:48 AM



Advertisments