Parallel semi-sequential bottom-up tree traversal algorithm

Question

I'm trying to traverse a tree-like structure from the bottom-up, and in parallel. Due to some other constraints I also have to allow for thread counts that may be lower than the width of a given set of child nodes. Each parent node also requires all child nodes to be visited before it itself can be visited. I've come up with an implementation that seems to work, but I'd like to get your opinion on it, and know whether there are some obvious issues with the logic it depends on. Note that I'm using the dp thread pool library for the thread pool itself.

Algorithm

#include <iostream>
#include <map>
#include <queue>

class node {
public:
    node(int value)
        : m_value(value) {}

    const std::vector<node*>& get_children() const {
        return m_children;
    }

    void add_child(node* child) {
        m_children.push_back(child);
    }

    void print() const {
        std::cout << m_value << '\n';
    }
private:
    int m_value;
    std::vector<node*> m_children;
};

// get nodes in breadth-first order
std::vector<node*> get_bfs_ordered_nodes(node* root) {
    std::vector<node*> order;
    std::queue<node*> q;
    q.push(root);

    while (!q.empty()) {
        node* current_node = q.front();
        q.pop();
        order.push_back(current_node);

        for (node* child : current_node->get_children()) {
            q.push(child);
        }
    }

    return order;
}

void parallel_bottom_up_traversal(node* root, dp::thread_pool<>& pool) {
    // get nodes in breadth-first order
    std::vector<node*> nodes = get_bfs_ordered_nodes(root);
    std::map<node*, std::shared_future<void>> node_futures;

    for (auto it = nodes.rbegin(); it != nodes.rend(); ++it) {
        node* current_node = *it;

        // store futures of children
        std::vector<std::shared_future<void>> child_futures;
        for (node* child : current_node->get_children()) {
            child_futures.push_back(node_futures[child]);
        }

        // create a task for the node and add it to the thread pool
        const auto future = pool.enqueue([current_node, child_futures]() {
            // wait for all children to be processed
            for (auto& fut : child_futures) {
                fut.get();
            }

            // process the node
            current_node->print();
        });

        // store the future for this node
        node_futures[current_node] = future;
    }

    // wait for the root to be processed
    node_futures[root].get();
}

Usage

int main() {
   dp::thread_pool pool(2);

    node* root = new node(0);
    node* child1 = new node(1);
    node* child2 = new node(2);
    node* child3 = new node(3);
    node* child4 = new node(4);
    node* child5 = new node(5);

    root->add_child(child1);
    root->add_child(child2);
    child1->add_child(child3);
    child3->add_child(child4);
    child3->add_child(child5);

    parallel_bottom_up_traversal(root, pool);

    delete child5;
    delete child4;
    delete child3;
    delete child2;
    delete child1;
    delete root;

    return 0;
}

The tree represented in my usage example can be seen below:

The traversal order is as follows:

5
4
3
2
1

Answer 1

Use a depth-first search

I know you want the results to be in bottom-up order, but that doesn't mean you have to do a reverse breadth-first search. You can greatly simplify your algorithm by using a depth-first search, which is easy to do using recursion:

std::future<void> parallel_bottom_up_traversal(node* root, dp::thread_pool<>& pool) {
    std::vector<std::future<void>> futures;

    for (auto child: root->get_children()) {
        futures.push_back(parallel_bottom_up_traversal(child, pool));
    }

    return pool.enqueue([root, futures=std::move(futures)]() mutable {
        for (auto& future: futures)
            future.get();

        root->print();
    });
}

How does this work? For each node we will first descend to its children, collect the std::futures the recursive calls return, then enqueue a task that waits for those futures to finish, and then it prints the node's value.

The order in which tasks are enqueued is different from your algorithm, but since the tasks are all executed in parallel, and thus there is no guarantee in which order they are completed (apart from that parents wait for children in both your and my version), does that matter?

Note that in the version above, a future is returned for the root node. The caller has to call .get() on that future. If you want a function that waits for the algorithm to complete and that returns void, you could make a helper function that does this. Although I think this is nicer; it allows the caller to start multiple traversals in parallel.

This DFS version also has the advantage that parallel work is started much sooner; your version first needs a sequential step where it gets the nodes in BFS order. Memory is saved as well; there's no longer a need for nodes and node_futures, only the equivalent of child_futures is used.

Make it more generic

Your code only works with trees that store ints, and it can only print those ints. What if I want to sum the values of a tree of floats? It's quite easy to make your code more generic by making node a templated class, and have parallel_bottom_up_traversal() take an arbitrary function as a parameter:

template<typename T>
class node {
    …
    T m_value;
    std::vector<node*> children;
};

template<typename T, typename Function>
parallel_bottom_up_traversal(node<T>* root, dp::thread_pool<>& pool, Function& function) {
    …
    std::invoke(function, current_node);
    …
}

And use it like:

auto root = new node<float>(3.1415);
…
std::atomic<float> sum = 0;
parallel_bottom_up_traversal(root, pool, [](auto& value) {
    sum += value;
});

Even nicer would be to allow functions that return values as well, and that take a vector of futures as an argument so it can access the values returned by the children. That way, the above summation could be done without needing an atomic variable:

auto root = new node<float>(3.1415);
…
auto sum = parallel_bottom_up_traversal(root, pool,
    [](auto& value, auto& child_futures) {
        float child_sum = 0;
        for (auto& future: child_futures)
            child_sum += future.get();
        return child_sum + value;
    }
).get();

How to change parallel_bottom_up_traversal() for this to work is left as an excercise for the reader.

Avoid raw pointers

It's easy to make mistakes when using raw pointers, new and delete. Consider using std::unique_ptr to manage memory. For example, you could make a parent node own its children:

class node {
    void add_child(std::unique_ptr<node>&& child) {
        children.push_back(std::move(child));
    }
    …
    std::vector<std::unique_ptr<node>> children;
};

int main() {
    auto root = std::make_unique<node>(0);
    auto child1 = std::make_unique<node>(1);
    auto child3 = std::make_unique<node>(3);
    …

    // Move children into parents, bottom up
    …
    child1.add_child(std::move(child3));
    root.add_child(std::move(child1));

    parallel_bottom_up_traversal(root.get(), pool);

    // No need to delete anything!
}

Note that this is just one way to do it, the main point is that ownership is clear and you don't have to do manual cleanups.