TBB task_groups без использования стека

Question

Я хотел бы выполнить обход дерева после заказа в C ++. Дерево может быть настолько глубоким, что я не могу использовать рекурсию (оно исчерпывает стек). Вместо этого я создаю std::stack<...>, который помещает все в кучу и перебирает дерево в цикле while, а не с помощью вызовов функций. Это прекрасно работает.

Теперь я хотел бы распараллелить весь процесс, используя TBB. Я думал о создании task_group на каждом узле и запуске одинакового functor на каждом из его дочерних элементов. Но мне приходит в голову, что это столкнется с той же проблемой с глубиной дерева, что и раньше: выполнение functor на каждом узле самого глубокого пути будет поглощать что-то из стека, пока все не закончится.

Есть ли выход из этой проблемы? Или я представляю себе все это; Есть ли какая-то магия за task_group::wait(), которая позволяет избежать этой проблемы?

Answer 1

Из документации TBB (о неявном продолжении):

Поскольку родительский блок, стек его потока еще не может быть извлечен. Нить должна быть осторожна с тем, какую работу она выполняет, потому что постоянное воровство и блокировка могут привести к росту стека без границ.

Это не совсем так, но показывает, что TBB не использует магию стека для очистки стека для текущих заблокированных задач. Это означает, что вы получите переполнение стека чуть позже (распределяется между стеками нескольких потоков) при использовании неявного продолжения.

Использование явного продолжения может решить проблему, но это сильно зависит от внутренней реализации TBB планировщика потоков (что не задокументировано). Есть большая вероятность, что это будет работать правильно - единственный способ узнать, это либо просмотреть источники TBB и посмотреть, как обрабатывается задача, либо написать простую тестовую программу с небольшим стеком и посмотреть, сможет ли что-то простое исчерпать ее.

Answer 2

Просто комментарий, подтверждающий, что вам нужно будет использовать продолжения для этого. В task_group :: wait нет ничего волшебного, что могло бы помешать ему использовать стек.

task_group находится в ppl, и вы можете использовать продолжения задач, описанные в msdn blog и доступные в пакете примеров ppl.