How to multithread "tail call" recursion using TBB
c++, c++11, multithreading, recursion, tbb
Solution
There are really two questions here:
- Is the TBB implementation of task_group::run thread-safe? Yes. (We should document this more clearly).
- Is having many threads invoke method run() on the same task_group scalable? No. (I believe the Microsoft documentation mentions this somewhere.) The reason is that the task_group becomes a centralized point of contention. It's just a fetch-and-add in the implementation, but that's still ultimately unscalable since the affected cache line has to bounce around.
It's generally best to spawn a small number of tasks from a task_group. If using recursive parallelism, give each level its own task_group. Though the performance will likely not be any better than using parallel_invoke.
The low-level tbb::task interfaces is the best bet. You can even code the tail-recursion in that, using the trick where tasK::execute returns a pointer to the tail-call task.
But I'm a bit concerned about the idling threads. I'm wondering if there is enough work to keep the threads busy. Consider doing work-span analysis first. If you are using the Intel compiler (or gcc 4.9) you might try experimenting with a Cilk version first. If that won't speed up, then even the low-level tbb::task interface is unlikely to help, and higher-level issues (work and span) need to be examined.
Problem
I am trying to use tbb to multi-thread an existing recursive algorithm. The single-thread version uses tail-call recursion, structurally it looks something like this: ``` void my_func() { my_recusive_func (0); } bool doSomeWork (int i, int& a, int& b, int& c) { // do some work } void my_recusive_func (int i) { int a, b, c; bool notDone = doSomeWork (i, a, b, c); if (notDone) { my_recusive_func (a); my_recusive_func (b); my_recusive_func (c); } } ``` I am a tbb novice so my first attempt used the parallel_invoke function: ``` void my_recusive_func (int i) { int a, b, c; bool notDone = doSomeWork (i, a, b, c); if (notDone) { tbb::parallel_invoke ( [a]{my_recusive_func (a);}, [b]{my_recusive_func (b);}, [c]{my_recusive_func (c);}); } } ``` This does work and it runs faster than the single-threaded version but it doesn't seem to scale well with number of cores. The machine I'm targeting has 16 cores (32 hyper-threads) so scalability is very important for this project, but this version only gets about 8 times speedup at best on that machine and many cores seem idle while the algorithm is running. My theory is that tbb is waiting for the child tasks to complete after the parallel_invoke so there may be many tasks sitting around idle waiting unnecessarily? Would this explain the idle cores? Is there any way to get the parent task to return without waiting for the children? I was thinking perhaps something like this but I don't know enough about the scheduler yet to know if this is OK or not: ``` void my_func() { tbb::task_group g; my_recusive_func (0, g); g.wait(); } void my_recusive_func (int i, tbb::task_group& g) { int a, b, c; bool notDone = doSomeWork (i, a, b, c); if (notDone) { g.run([a,&g]{my_recusive_func(a, g);}); g.run([b,&g]{my_recusive_func(b, g);}); my_recusive_func (c, g); } } ``` My first question is is `tbb::task_group::run()` thread-safe? I couldn't figure that out from the documentation. Also, is there better way to go about this? Perhaps I should be using the low-level scheduler calls instead? (I typed this code without compiling so please forgive typos.)