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!

Answer 1

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;
}

Answer 2

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();
}

See http://goo.gl/dZMRDC

Answer 3

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!