C++ stack overflow, how to increase stack size per thread?

Question

My C++ program is crashing recently, ASAN is showing me a stack-overflow error. I have recently rewritten my program to use multiple threads and since then the program crashes. I suspect the crash happens because of a too deep recursion because apparently on macOS the stack size for threads other than the main thread are reduced. I have compared my source code with other similiar programs. They usually increase the stack size to 8MB for each thread (the linux default) by using pthread_attr_setstacksize. However I am using std::thread, how would I do it with those?

Answer 1

A 100 deep recursive call is probably actually an unboundedly deep recursive call. These are generally not safe. Increasing stack size is a patch, it doesn't fix the issue.

Recursion with logarithmic depth is usually ok, as 2^50 is a big data set. But recursion with above-logarithmic depth is usually a sign you need to get fancier.

The simples solution is to start migrating off the stack. Take a look at your recursive state; move it into a struct, and store it on an explicit stack (like a std vector). (This means pointers won't be stable; a std deque or a vector of unique ptrs provides memory stability).

Once your recursive state is explicit, you can say "good enough", because now the call stack is holding next to nothing, or you could rotate your recursive code into iterative code with an explicit call stack of tasks to perform.

That second option can lead to further optimization.

Needless to say, with that kind of refactoring, you'll want some robust unit testing and version control so you don't break everything and can't fix it.

bool search( int const* begin, int const* end, int x ){
  switch(end-begin){
    case 0: return false;
    case 1: return x==*begin;
    default: return search( begin, begin+(end-begin)/2, x) || search(begin+(end-begin)/2, end, x);
  }
}

here is a toy recursive function.

Let us make state explicit.

struct search_state {
  int* begin=0;
  int* end=0;
  int x;
};
bool search( search_state s ){
  switch(s.end-s.begin){
    case 0: return false;
    case 1: return s.x==*s.begin;
    default: return search( {s.begin, s.begin+(s.end-s.begin)/2, x} ) || search( {s.begin+(s.end-s.begin)/2, s.end, s.x} );
  }
}

now migrate to an explicit stack.

bool search( std::vector<search_state>& v ){
  if (v.empty()) return false;
  auto s=v.back();
  v.pop_back();
  switch(s.end-s.begin){
    case 0: return false;
    case 1: return s.x==*s.begin;
    default: {
      v.push_back({s.begin, s.begin+(s.end-s.begin)/2, x} );
      bool r = search(v);
      if(r) return true;
      v.push_back({s.begin+(s.end-s.begin)/2, s.end, s.x} );
      return search(v);
    }
  }
}

next move the return value off of the automatic storage.

void search( std::vector<search_state>& v, bool* retval ){
  if (v.empty()) return false;
  auto s=v.back();
  v.pop_back();
  switch(s.end-s.begin){
    case 0: return;
    case 1: if(s.x==*s.begin)*retval=true; return;
    default: {
      v.push_back({s.begin, s.begin+(s.end-s.begin)/2, x} );
      search(v, retval);
      if(*retval) return;
      v.push_back({s.begin+(s.end-s.begin)/2, s.end, s.x} );
      return search(v, retval);
    }
  }
}

we now have 0 local variables.

We can now convert to an iterative version pretty mechanically.

void search( std::vector<search_state>& v, bool* retval ){
  while( !v.empty() && !*retval){
    auto s=v.back();
    v.pop_back();
    switch(s.end-s.begin){
      case 0: continue;
      case 1: if(s.x==*s.begin) *retval=true; continue;
      default: {
       v.push_back({s.begin, s.begin+(s.end-s.begin)/2, x} );
       v.push_back({s.begin+(s.end-s.begin)/2, s.end, s.x} );
      }
    }
 }

see how similar it is?

Now clean up retval and hide the vector:

bool search( search_state sin ){
  std::vector<search_state> v={sin};
  bool retval=false;
  while( !v.empty() && !retval){
    auto s=v.back();
    v.pop_back();
    switch(s.end-s.begin){
      case 0: continue;
      case 1: if(s.x==*s.begin) retval=true; continue;
      default: {
       v.push_back({s.begin, s.begin+(s.end-s.begin)/2, x} );
       v.push_back({s.begin+(s.end-s.begin)/2, s.end, s.x} );
      }
    }
  }
  return retval;
}

and we are good. You might want to swap the recursive "call" order, as this version does it backwards compared to the baseline recursive version.