<ahref="#RecursiveFibonacciParallelismUsingTaskGroup">Recursive Fibonacci with Task Group</a>
</li>
</ul>
</div>
<divclass="textblock"><p>We study recursive task parallelism using the Fibonacci sequence as a concrete example, demonstrating how <aclass="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">tf::Runtime</a> enables dynamic task creation and cooperative synchronisation without blocking worker threads.</p>
</div><!-- fragment --><p>The two recursive calls are mutually independent and can therefore run in parallel. The challenge is to express this recursive parallelism efficiently — spawning tasks that themselves spawn tasks — without blocking worker threads or creating unbounded overhead.</p>
<p>A runtime task accepts a <aclass="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">tf::Runtime</a>& parameter, giving it a live handle to the scheduling runtime. We use <aclass="el" href="classtf_1_1Runtime.html#a0ce29efa2106c8c5a1432e4a55ab2e05" title="runs the given function asynchronously without returning any future object">tf::Runtime::silent_async</a> to spawn both recursive branches in parallel and <aclass="el" href="classtf_1_1Runtime.html#aba54a7cacffb54f5eb133730d256a7c4" title="corun all tasks spawned by this runtime with other workers">tf::Runtime::corun</a> to wait for them cooperatively. <code>corun</code> does not block the calling worker — it participates in the work-stealing loop while waiting, so other tasks can run on the same thread:</p>
<divclass="line"> std::cout << N << <spanclass="stringliteral">"-th Fibonacci number is "</span> << res << <spanclass="charliteral">'\n'</span>;</div>
<divclass="ttc" id="aclasstf_1_1Executor_html_a0461cb2c459c9f9473c72af06af9c701"><divclass="ttname"><ahref="classtf_1_1Executor.html#a0461cb2c459c9f9473c72af06af9c701">tf::Executor::silent_async</a></div><divclass="ttdeci">void silent_async(P &&params, F &&func)</div><divclass="ttdoc">similar to tf::Executor::async but does not return a future object</div></div>
<divclass="ttc" id="aclasstf_1_1Executor_html_ab9aa252f70e9a40020a1e5a89d485b85"><divclass="ttname"><ahref="classtf_1_1Executor.html#ab9aa252f70e9a40020a1e5a89d485b85">tf::Executor::wait_for_all</a></div><divclass="ttdeci">void wait_for_all()</div><divclass="ttdoc">waits for all tasks to complete</div></div>
<divclass="ttc" id="aclasstf_1_1Runtime_html"><divclass="ttname"><ahref="classtf_1_1Runtime.html">tf::Runtime</a></div><divclass="ttdoc">class to create a runtime task</div><divclass="ttdef"><b>Definition</b> runtime.hpp:47</div></div>
<divclass="ttc" id="aclasstf_1_1Runtime_html_a0ce29efa2106c8c5a1432e4a55ab2e05"><divclass="ttname"><ahref="classtf_1_1Runtime.html#a0ce29efa2106c8c5a1432e4a55ab2e05">tf::Runtime::silent_async</a></div><divclass="ttdeci">void silent_async(F &&f)</div><divclass="ttdoc">runs the given function asynchronously without returning any future object</div><divclass="ttdef"><b>Definition</b> runtime.hpp:667</div></div>
<divclass="ttc" id="aclasstf_1_1Runtime_html_aba54a7cacffb54f5eb133730d256a7c4"><divclass="ttname"><ahref="classtf_1_1Runtime.html#aba54a7cacffb54f5eb133730d256a7c4">tf::Runtime::corun</a></div><divclass="ttdeci">void corun()</div><divclass="ttdoc">corun all tasks spawned by this runtime with other workers</div><divclass="ttdef"><b>Definition</b> runtime.hpp:642</div></div>
</div><!-- fragment --><p>Each call to <code>fibonacci</code> recursively spawns two async tasks and then waits cooperatively for both to finish. The executor distributes tasks across all available workers using work-stealing, achieving parallelism at every level of the recursion tree. The execution diagram for <code>fibonacci(4)</code> is shown below. The suffixes <em>_1</em> and <em>_2</em> denote the left and right children spawned by their parent runtime:</p>
<divclass="dotgraph">
<iframescrolling="no" frameborder="0" src="dot_fibonacci_4.svg" width="587" height="374"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>Spawning both branches asynchronously doubles the number of async tasks created: one branch is always available for inline computation in the current execution context, so spawning it asynchronously only adds scheduling overhead without increasing parallelism. The standard optimisation is to compute one branch <em>inline</em> (directly in the current context) and spawn only the other asynchronously. This halves the task count, reduces stack pressure, and cuts scheduling overhead at every level of recursion:</p>
<divclass="fragment"><divclass="line"><spanclass="keywordtype">size_t</span> fibonacci(<spanclass="keywordtype">size_t</span> N, <aclass="code hl_class" href="classtf_1_1Runtime.html">tf::Runtime</a>& rt) {</div>
</div><!-- fragment --><p>The optimised execution diagram for <code>fibonacci(4)</code> is shown below. The right branch at each level has been eliminated, replaced by inline computation:</p>
<divclass="dotgraph">
<iframescrolling="no" frameborder="0" src="dot_fibonacci_4_tail_optimized.svg" width="587" height="374"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<tdclass="markdownTableBodyCenter">20 </td><tdclass="markdownTableBodyCenter">0.23 ms </td><tdclass="markdownTableBodyCenter">0.31 ms </td></tr>
<trclass="markdownTableRowEven">
<tdclass="markdownTableBodyCenter">25 </td><tdclass="markdownTableBodyCenter">2 ms </td><tdclass="markdownTableBodyCenter">4 ms </td></tr>
<trclass="markdownTableRowOdd">
<tdclass="markdownTableBodyCenter">30 </td><tdclass="markdownTableBodyCenter">23 ms </td><tdclass="markdownTableBodyCenter">42 ms </td></tr>
<trclass="markdownTableRowEven">
<tdclass="markdownTableBodyCenter">35 </td><tdclass="markdownTableBodyCenter">269 ms </td><tdclass="markdownTableBodyCenter">483 ms </td></tr>
<trclass="markdownTableRowOdd">
<tdclass="markdownTableBodyCenter">40 </td><tdclass="markdownTableBodyCenter">3003 ms </td><tdclass="markdownTableBodyCenter">5124 ms </td></tr>
</table>
</div><p>The performance gap widens as <code>N</code> increases because the number of tasks created grows exponentially. At <code>N</code> = 40, tail optimisation cuts runtime by over 40% by eliminating half the task-creation and scheduling overhead at every recursive level.</p>
<p><aclass="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> offers a lighter-weight alternative to <aclass="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">tf::Runtime</a> for recursive parallelism from any calling context — no need for the caller itself to be a runtime task. The interface is the same: spawn sub-tasks with <code>silent_async</code>, then call <code>corun</code> to wait cooperatively.</p>
<divclass="line"> tg.<aclass="code hl_function" href="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc">corun</a>(); <spanclass="comment">// cooperatively wait for the left branch</span></div>
<divclass="line"><spanclass="keywordtype">size_t</span> N = 30;</div>
<divclass="line"><spanclass="keywordtype">size_t</span> res = executor.<aclass="code hl_function" href="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7">async</a>([&]() { <spanclass="keywordflow">return</span> fibonacci(N); }).get();</div>
<divclass="line"> std::cout << N << <spanclass="stringliteral">"-th Fibonacci number is "</span> << res << <spanclass="charliteral">'\n'</span>;</div>
<divclass="ttc" id="aclasstf_1_1Executor_html"><divclass="ttname"><ahref="classtf_1_1Executor.html">tf::Executor</a></div><divclass="ttdoc">class to create an executor</div><divclass="ttdef"><b>Definition</b> executor.hpp:62</div></div>
<divclass="ttc" id="aclasstf_1_1Executor_html_a8858a119b9ad697748293c4bb1408853"><divclass="ttname"><ahref="classtf_1_1Executor.html#a8858a119b9ad697748293c4bb1408853">tf::Executor::task_group</a></div><divclass="ttdeci">TaskGroup task_group()</div><divclass="ttdoc">creates a task group that executes a collection of asynchronous tasks</div><divclass="ttdef"><b>Definition</b> task_group.hpp:863</div></div>
<divclass="ttc" id="aclasstf_1_1Executor_html_af960048056f7c6b5bc71f4f526f05df7"><divclass="ttname"><ahref="classtf_1_1Executor.html#af960048056f7c6b5bc71f4f526f05df7">tf::Executor::async</a></div><divclass="ttdeci">auto async(P &&params, F &&func)</div><divclass="ttdoc">creates a parameterized asynchronous task to run the given function</div></div>
<divclass="ttc" id="aclasstf_1_1TaskGroup_html"><divclass="ttname"><ahref="classtf_1_1TaskGroup.html">tf::TaskGroup</a></div><divclass="ttdoc">class to create a task group from a task</div><divclass="ttdef"><b>Definition</b> task_group.hpp:61</div></div>
<divclass="ttc" id="aclasstf_1_1TaskGroup_html_a1f481dc466e3107a08346d1a124677bc"><divclass="ttname"><ahref="classtf_1_1TaskGroup.html#a1f481dc466e3107a08346d1a124677bc">tf::TaskGroup::corun</a></div><divclass="ttdeci">void corun()</div><divclass="ttdoc">corun all tasks spawned by this task group with other workers</div><divclass="ttdef"><b>Definition</b> task_group.hpp:721</div></div>
<divclass="ttc" id="aclasstf_1_1TaskGroup_html_acf90acfcaf9468adc56bf647208a9e78"><divclass="ttname"><ahref="classtf_1_1TaskGroup.html#acf90acfcaf9468adc56bf647208a9e78">tf::TaskGroup::silent_async</a></div><divclass="ttdeci">void silent_async(F &&f)</div><divclass="ttdoc">runs the given function asynchronously without returning any future object</div><divclass="ttdef"><b>Definition</b> task_group.hpp:752</div></div>
</div><!-- fragment --><dlclass="section note"><dt>Note</dt><dd>Prefer <aclass="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">tf::Runtime</a> when you are already inside a runtime task, as it avoids the construction overhead of a task group object. Use <aclass="el" href="classtf_1_1TaskGroup.html" title="class to create a task group from a task">tf::TaskGroup</a> when the recursive function is called from a context that does not hold a <aclass="el" href="classtf_1_1Runtime.html" title="class to create a runtime task">tf::Runtime</a> reference. </dd></dl>
</div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.13.1-->
<!-- start footer part -->
<divid="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<liclass="navelem"><aclass="el" href="Examples.html">Learning from Examples</a></li>
<liclass="footer">
Maintained by <ahref="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>
—
Generated by <ahref="https://www.doxygen.org/index.html"><imgclass="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.13.1