c++ - 不使用堆栈的 TBB task_groups

Question

我想用 C++ 执行后序树遍历。树可能很深以至于我无法使用递归(它耗尽了堆栈)。相反，我创建了一个 std::stack<...>将所有内容都放在堆上，并在 while 循环中遍历树，而不是使用函数调用。这很好用。

现在我想使用 TBB 并行化整个过程。我正在考虑创建一个 task_group在每个节点，并运行相同的 functor在它的每个 child 身上。但我突然想到，这会遇到与我之前遇到的树深度相同的问题:运行 functor在最深路径的每个节点上都会从堆栈中吃掉一些东西，直到整个东西用完。

有没有办法解决这个问题？还是我在想象整个事情？ task_group::wait()背后有什么魔法吗？那避免了这个问题？

Answer 1

来自 TBB 文档(关于隐式延续):

Because the parent blocks, its thread’s stack cannot be popped yet. The thread must be careful about what work it takes on, because continually stealing and blocking could cause the stack to grow without bound.

这不完全是关于那个，但它表明 TBB 没有使用任何堆栈魔术来为当前阻塞的任务清空堆栈。这意味着当使用隐式延续时，您稍后会遇到堆栈溢出(分布在多个线程的堆栈中)。

使用显式延续可能会解决问题，但这在很大程度上取决于线程调度程序的内部 TBB 实现(未记录)。它很有可能会正常工作 - 唯一知道的方法是查看 TBB 源代码并查看任务是如何处理的，或者编写简单的小堆栈测试程序并查看是否有一些简单的东西能够耗尽它。