C++ Multithreading stack overflow

Question

I'm trying to isolate a multithreading issue in my C++ application.

The Handler below gets created and "processed" within an auxiliary thread.

struct Handler 
{
    void process(const std::vector<size_t> ops)
    {
        std::vector<size_t>::const_iterator iter = ops.cbegin();
        while( iter != ops.cend() ) {
            processOperation( op );
        }
    }

    void processOperation(std::vector<size_t>::const_iterator& iter)
    {
        size_t op = *iter;
        iter++;

        switch( op ) {
            case frame_push : { 
                processOperation( iter );
                break;
            }
            case frame_pop : { 
                return;
            }
            default : { break; }
        }
    }
};

As you can see in the above, processOperation() calls itself recursively if the current "op" equals frame_push.

I'm aware that sufficient recursive operations here would cause the call stack to overflow. However, when I run this Handler on an auxiliary thread instead of the main thread, that seems to happen much more quickly.

It seems like the possibility of a call stack overflow is not my only issue here. Might there be a reentrancy problem as well?

I would really appreciate any insights. Thanks!

On many operating systems, the default size of the main thread's stack is much larger than the default size of the stacks of other threads. You might check the stack sizes of your threads to see if this is why you are seeing what you are seeing. — Jeremy Friesner
– Jeremy Friesner, Commented Jun 22, 2015 at 15:06
Hmm, thanks, great tip! Can you point me to any documentation of how to expose this info. I'm working in XCode. — pt3dNyc
– pt3dNyc, Commented Jun 22, 2015 at 15:08
unix.stackexchange.com/questions/127602/… developer.apple.com/library/mac/qa/qa1419/_index.html — Jeremy Friesner
– Jeremy Friesner, Commented Jun 22, 2015 at 15:08
This recursion can be easly linearised using cycle while(depth), where depth is your original recursion depth. — Tsyvarev
– Tsyvarev, Commented Jun 22, 2015 at 15:33
I seem to get the same stack size (524288 bytes) for both the main and auxiliary threads. Nonetheless, the code seems to run on the main thread but not on an auxiliary. I'm working on unrolling my recursion for test purposes... but this might be fairly difficult outside of a simplified test implementation — pt3dNyc
– pt3dNyc, Commented Jun 22, 2015 at 16:05

miken32 · Accepted Answer · 2025-06-20 20:16:50Z

First thing you've successfully eliminated is ownership of "ops" since you pass it by value, so we are dealing with a thread-local copy:

void process(const std::vector<size_t> ops)

Then you create an iterator

std::vector<size_t>::const_iterator iter = ops.cbegin();

Which you could probably write as:

auto iter = ops.begin();

but ok. Now we set our loop constraint:

while( iter != ops.cend() ) {

This however, it outside of the recursive call. So it will only be checked when we leave the recursive call.

void processOperation(std::vector<size_t>::const_iterator& iter)
{
    size_t op = *iter;
    iter++;

    switch( op ) {
        case frame_push : { 
            processOperation( iter );
            break;
        }
        case frame_pop : { 
            return;
        }
        default : { break; }
    }
}

There is no code in this call for the end of the container. I'm guessing that frame_push and frame_pop is to allow you to create scopes for whatever your default case would be replaced with, hence your need for recursion.

If that's the intent, it might be better to implement your own frame stack.

#include <vector>
#include <iostream>
#include <thread>

enum Operands { frame_push, frame_pop, other };

struct Frame {};

struct Handler
{
    size_t maxDepth, pushCount, popCount;

    Handler() : maxDepth(0), pushCount(0), popCount(0) {}

    void handle(const std::vector<Operands> ops_)
    {
        std::vector<Frame> stack;
        stack.reserve(256);
        stack.emplace_back(); // Create a default Frame
        for (auto iter = ops_.cbegin(); iter != ops_.cend(); ++iter) {
            switch (*iter) {
                case frame_push:
                    // make a copy of the current frame,
                    // remove the 'stack.back()' if new frames should
                    // start empty
                    ++pushCount;
                    stack.emplace_back(stack.back());
                    maxDepth = std::max(maxDepth, stack.size());
                break;
                case frame_pop:
                    stack.pop_back();
                    ++popCount;
                break;
                default: {
                    Frame& frame = stack.back();
                    (void)frame;
                }
                break;
            }
        }
        std::this_thread::yield();
        std::cout << "ops len " << ops_.size()
            << ", pushCount " << pushCount
            << ", popCount " << popCount
            << ", maxDepth " << maxDepth
            << std::endl;
        std::this_thread::yield();
    }
};

int main()
{
    std::vector<Operands> ops = {
        frame_push, other, other,
            frame_push, other, frame_pop,
            other,
            frame_push, frame_pop,
            other,
            frame_push,
                frame_push, other, other, frame_pop,
            frame_pop,
        frame_pop
    };

    Handler h;
    std::thread t1(&Handler::handle, &h, ops);
    t1.join();
}

@miken32 thanks -- I don't know that I've ever used tutorialspoint or their online compiler; godbolt or ideone, yes. thanks for catching/fixing.

Mital Vora · Accepted Answer · 2015-06-23 03:23:01Z

You are trying to iterate through your vector two ways with while loop as well as with recursion. You have to use one or the other to get your code working. There should not be any stack overflow condition if you try implementing it only one way. Following is the modified code which clearly isolates both type of recursion. Hope this helps solve your issue.

#include <iostream>
#include <vector>

using namespace std;

struct Handler 
{
    void processOperation(size_t& op)
    {
        std::cout << "Processing : " << op << std::endl;
        // TODO: Actual processing
    }

    void process(const std::vector<size_t> ops)
    {
        std::vector<size_t>::const_iterator iter = ops.cbegin();
        while( iter != ops.cend() ) {
            size_t op = *iter;
            processOperation(op);
            iter++;
        }
    }

    void processRecursive(std::vector<size_t>::const_iterator iter,
        std::vector<size_t>::const_iterator end)
    {
        if (iter != end)
        {
            size_t op = *iter;
            processOperation(op);
            processRecursive(++iter, end);
        }
    }
};

int main() {
    // your code goes here
    std::vector<size_t> ops;
    ops.push_back(1);
    ops.push_back(2);
    ops.push_back(3);
    ops.push_back(4);

    Handler h;
    h.process(ops);
    h.processRecursive(ops.cbegin(), ops.cend());
    return 0;
}

pt3dNyc · Accepted Answer · 2015-06-22 22:53:40Z

0

As suggested by commentator Jeremy Friesner, the thread's default stack size was too small and causing overflow. I was able to resolve the issue by setting a custom stack size for boost::thread (this feature apparently does not exist for std::thread) with the following code:

boost::thread::attributes attributes;
attributes.set_stack_size( customStackSize );

boost::thread aThread( attributes, /* function binding here */ );

However, as suggested by Tsyvarev, the real solution here will be to replace the recursive behavior.

Thanks all!

answered Jun 22, 2015 at 22:53

pt3dNyc

3692 silver badges17 bronze badges

Collectives™ on Stack Overflow

C++ Multithreading stack overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related