-
-
Notifications
You must be signed in to change notification settings - Fork 1.4k
Expand file tree
/
Copy pathExamplesSpeculativeExecution.html
More file actions
362 lines (360 loc) · 33 KB
/
Copy pathExamplesSpeculativeExecution.html
File metadata and controls
362 lines (360 loc) · 33 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
<!-- HTML header for doxygen 1.13.1-->
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "https://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" lang="en-US">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=11"/>
<meta name="generator" content="Doxygen 1.13.1"/>
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<title>Taskflow: A General-purpose Task-parallel Programming System: Speculative Execution</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<script type="text/javascript" src="clipboard.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="cookie.js"></script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
<link href="custom.css" rel="stylesheet" type="text/css"/>
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
<tbody>
<tr id="projectrow">
<td id="projectlogo"><img alt="Logo" src="taskflow_logo.png"/></td>
<td id="projectalign">
<div id="projectname"><a href="https://github.com/taskflow/taskflow" style="color:inherit; text-decoration:none;">Taskflow: A General-purpose Task-parallel Programming System</a>
</div>
</td>
</tr>
</tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.13.1 -->
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
var searchBox = new SearchBox("searchBox", "search/",'.html');
/* @license-end */
</script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() { codefold.init(0); });
/* @license-end */
</script>
<script type="text/javascript" src="menudata.js"></script>
<script type="text/javascript" src="menu.js"></script>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function() {
initMenu('',true,false,'search.php','Search',true);
$(function() { init_search(); });
});
/* @license-end */
</script>
<div id="main-nav"></div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
<div id="nav-tree">
<div id="nav-tree-contents">
<div id="nav-sync" class="sync"></div>
</div>
</div>
<div id="splitbar" style="-moz-user-select:none;"
class="ui-resizable-handle">
</div>
</div>
<script type="text/javascript">
/* @license magnet:?xt=urn:btih:d3d9a9a6595521f9666a5e94cc830dab83b65699&dn=expat.txt MIT */
$(function(){initNavTree('ExamplesSpeculativeExecution.html',''); initResizable(true); });
/* @license-end */
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
onmouseover="return searchBox.OnSearchSelectShow()"
onmouseout="return searchBox.OnSearchSelectHide()"
onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>
<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<div id="MSearchResults">
<div class="SRPage">
<div id="SRIndex">
<div id="SRResults"></div>
<div class="SRStatus" id="Loading">Loading...</div>
<div class="SRStatus" id="Searching">Searching...</div>
<div class="SRStatus" id="NoMatches">No Matches</div>
</div>
</div>
</div>
</div>
<div><div class="header">
<div class="headertitle"><div class="title">Speculative Execution</div></div>
</div><!--header-->
<div class="contents">
<div class="toc"><h3>Table of Contents</h3>
<ul>
<li class="level1">
<a href="#SpecMotivation">Motivation</a>
</li>
<li class="level1">
<a href="#SpecProblem">The Problem: Bloom Filter Lookup</a>
</li>
<li class="level1">
<a href="#SpecSingleItem">Per-Item Graph Structure</a>
</li>
<li class="level1">
<a href="#SpecBatchGraph">Batch Graph: N Keys in Parallel</a>
</li>
<li class="level1">
<a href="#SpecImplementation">Implementation</a>
</li>
<li class="level1">
<a href="#SpecDesignPoints">Design Points</a>
</li>
</ul>
</div>
<div class="textblock"><p>We implement a <em>speculative</em> <em>execution</em> pattern using condition tasks to route a batch of queries through a fast approximate path or a slow exact path based on a runtime probe. This example demonstrates how condition tasks express performance-driven branching — not just correctness-driven control flow — and how to correctly wire the convergence of two exclusive branches into a single downstream task without deadlock.</p>
<h1><a class="anchor" id="SpecMotivation"></a>
Motivation</h1>
<p>Many real-world computations have two valid execution strategies for the same result: a <em>fast</em> <em>path</em> that succeeds most of the time with low cost, and a <em>slow</em> <em>fallback</em> that is always correct but expensive. Classic examples include:</p>
<ul>
<li>A <b>Bloom</b> <b>filter</b> probed before a full hash-table lookup: the filter answers <em>definitely not present</em> or <em>probably present</em> in O(1) without touching the backing store. A negative answer routes directly to a cheap "not found" handler. A positive answer (which may be a false positive) routes to the full lookup to confirm.</li>
<li>A <b>branch</b> <b>predictor</b> in CPU microarchitecture: the processor speculatively executes the predicted path while the branch condition is still being evaluated, rolling back only on mis-prediction.</li>
<li>A <b>cache</b> <b>probe</b> before a database query: if the key is in an in-process LRU cache the result is returned immediately; on a miss the full query is issued.</li>
</ul>
<p>In all three cases the routing decision is made by a cheap probe whose cost is negligible compared to the fallback. The structure is always: probe → fast path <em>or</em> slow path → merge result. This is exactly the branching structure condition tasks are designed to express.</p>
<h1><a class="anchor" id="SpecProblem"></a>
The Problem: Bloom Filter Lookup</h1>
<p>We process a batch of <code>N</code> string keys against a set stored in a hash table. Before querying the hash table, each key is probed against a Bloom filter — a space-efficient probabilistic data structure that can definitively rule out absent keys in O(k) hash operations, where <code>k</code> is the number of hash functions.</p>
<p>The two execution paths per key are:</p>
<ul>
<li><b>Fast</b> <b>path</b> (Bloom filter says <em>not present</em>): the key is definitely absent. Return <em>not found</em> immediately without touching the hash table.</li>
<li><b>Slow</b> <b>path</b> (Bloom filter says <em>probably present</em>): the key may be in the table. Perform the full hash-table lookup to confirm or deny.</li>
</ul>
<p>The Bloom filter has no false negatives: if it says <em>not present</em>, the key is guaranteed absent. It may have false positives: a key the filter calls <em>probably present</em> may still be absent, in which case the hash-table lookup returns <em>not found</em> after doing the full work. The fast-path short circuit is therefore exact in the negative case and conservative (but correct) in the positive case.</p>
<h1><a class="anchor" id="SpecSingleItem"></a>
Per-Item Graph Structure</h1>
<p>For a single key the task graph is a diamond: a condition task (<code>speculate</code>) probes the Bloom filter and routes to either <code>fast_handler</code> or <code>slow_fallback</code>, both of which must then converge on a single <code>merge</code> point before the result is recorded.</p>
<p>A naive first attempt makes <code>fast_handler</code> and <code>slow_fallback</code> regular tasks and feeds both into <code>merge</code> via strong edges:</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_spec_wrong.svg" width="694" height="122"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>This graph deadlocks. Task <code>merge</code> has two strong dependencies — one from <code>fast_handler</code> and one from <code>slow_fallback</code> — but only the branch selected by <code>speculate</code> will actually execute. The other branch is never scheduled, so <code>merge's</code> strong dependency counter drops from 2 to 1 and never reaches 0. <code>merge</code> waits forever. This is <b>Pitfall</b> <b>2</b> from <a class="el" href="ConditionalTasking.html#AvoidCommonPitfalls">Avoid Common Pitfalls</a> applied to the switch pattern: just as both the switch task and each case task must be condition tasks in a switch control flow (see <a class="el" href="ConditionalTasking.html#ImplementSwitchControlFlow">Implement Switch Control Flow</a>), here both the routing task <em>and</em> the two branch tasks must be condition tasks so that their outgoing edges to <code>merge</code> are <em>weak</em>, bypassing the strong dependency counter entirely.</p>
<p>The correct per-item graph is:</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_spec_correct.svg" width="998" height="151"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>Every node that has an outgoing edge to <code>merge</code> is a condition task. <code>merge</code> itself is a condition task that always returns <code>0</code> to route to <code>done</code>, making the <code>merge→done</code> edge weak. The dependency counts for the single-item graph are:</p>
<div align="center"> <table class="markdownTable">
<tr class="markdownTableHead">
<th class="markdownTableHeadLeft">Task </th><th class="markdownTableHeadCenter">Strong </th><th class="markdownTableHeadCenter">Weak </th><th class="markdownTableHeadCenter">Total </th></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft">prepare </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">0 </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft">speculate </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">1 </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft">fast_handler </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">1 </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft">slow_fallback </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">1 </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft">merge </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">2 </td><td class="markdownTableBodyCenter">2 </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft">done </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">1 </td></tr>
</table>
</div><p><code>merge</code> has two weak incoming edges but only one fires per execution, so it is enqueued exactly once. <code>done</code> has one weak incoming edge from <code>merge</code> and is also enqueued exactly once.</p>
<h1><a class="anchor" id="SpecBatchGraph"></a>
Batch Graph: N Keys in Parallel</h1>
<p>For a batch of <code>N</code> keys, each key gets its own independent (<code>speculate</code>, <code>fast_handler</code>, <code>slow_fallback</code>, <code>merge</code>, <code>done</code>) chain. The <code>N</code> chains have no mutual dependencies and execute fully in parallel across available workers. A final <code>collect</code> task gathers results; it waits for all <code>N</code> <code>done</code> tasks via <em>strong</em> dependencies, so it is enqueued exactly once after every chain has completed.</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_spec_batch.svg" width="986" height="547"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>Because <code>done</code> is reached via a chain of weak edges (<code>merge→done</code> is weak), <code>done</code> itself has zero strong dependencies. It is a regular task, so its outgoing edge to <code>collect</code> is strong. This gives <code>collect</code> exactly <code>N</code> strong dependencies, one per chain, and it runs once all keys have been processed.</p>
<h1><a class="anchor" id="SpecImplementation"></a>
Implementation</h1>
<p>We implement a minimal Bloom filter and a hash-table backing store. For each key in the batch we build the five-task chain and wire it into the taskflow. Results are recorded into a per-key array so that <code>collect</code> can aggregate without any synchronization.</p>
<div class="fragment"><div class="line"><span class="preprocessor">#include <taskflow/taskflow.hpp></span></div>
<div class="line"><span class="preprocessor">#include <bitset></span></div>
<div class="line"><span class="preprocessor">#include <unordered_set></span></div>
<div class="line"><span class="preprocessor">#include <functional></span></div>
<div class="line"><span class="preprocessor">#include <string></span></div>
<div class="line"><span class="preprocessor">#include <vector></span></div>
<div class="line"> </div>
<div class="line"><span class="comment">// ── Bloom filter ────────────────────────────────────────────────────</span></div>
<div class="line"><span class="comment">// A minimal Bloom filter using two independent hash functions and a</span></div>
<div class="line"><span class="comment">// fixed-size bit array. Real implementations use k > 2 hash functions</span></div>
<div class="line"><span class="comment">// and tune the array size to the expected element count and target FPR.</span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">struct </span>BloomFilter {</div>
<div class="line"> <span class="keyword">static</span> <span class="keyword">constexpr</span> <span class="keywordtype">size_t</span> M = 1024; <span class="comment">// bit-array size</span></div>
<div class="line"> std::bitset<M> bits;</div>
<div class="line"> </div>
<div class="line"> <span class="keyword">static</span> <span class="keywordtype">size_t</span> h1(<span class="keyword">const</span> std::string& s) {</div>
<div class="line"> <span class="keywordflow">return</span> std::hash<std::string>{}(s) % M;</div>
<div class="line"> }</div>
<div class="line"> <span class="keyword">static</span> <span class="keywordtype">size_t</span> h2(<span class="keyword">const</span> std::string& s) {</div>
<div class="line"> <span class="keywordflow">return</span> (std::hash<std::string>{}(s) * 2654435761ULL) % M;</div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="keywordtype">void</span> insert(<span class="keyword">const</span> std::string& s) {</div>
<div class="line"> bits.set(h1(s));</div>
<div class="line"> bits.set(h2(s));</div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// Returns false if s is definitely absent; true if probably present.</span></div>
<div class="line"> <span class="keywordtype">bool</span> probe(<span class="keyword">const</span> std::string& s)<span class="keyword"> const </span>{</div>
<div class="line"> <span class="keywordflow">return</span> bits.test(h1(s)) && bits.test(h2(s));</div>
<div class="line"> }</div>
<div class="line">};</div>
<div class="line"> </div>
<div class="line"><span class="comment">// ── Result tag ──────────────────────────────────────────────────────</span></div>
<div class="line"><span class="keyword">enum class</span> Result { NOT_FOUND, FOUND };</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── build the backing store and Bloom filter ─────────────────────</span></div>
<div class="line"> std::unordered_set<std::string> table = {</div>
<div class="line"> <span class="stringliteral">"alpha"</span>, <span class="stringliteral">"bravo"</span>, <span class="stringliteral">"charlie"</span>, <span class="stringliteral">"delta"</span>, <span class="stringliteral">"echo"</span></div>
<div class="line"> };</div>
<div class="line"> </div>
<div class="line"> BloomFilter bloom;</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keyword">auto</span>& s : table) bloom.insert(s);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── query batch ──────────────────────────────────────────────────</span></div>
<div class="line"> <span class="comment">// Mix of present keys, absent keys, and keys that may be false</span></div>
<div class="line"> <span class="comment">// positives in the Bloom filter.</span></div>
<div class="line"> std::vector<std::string> keys = {</div>
<div class="line"> <span class="stringliteral">"alpha"</span>, <span class="comment">// present</span></div>
<div class="line"> <span class="stringliteral">"foxtrot"</span>, <span class="comment">// absent, Bloom filter correctly says "not present"</span></div>
<div class="line"> <span class="stringliteral">"bravo"</span>, <span class="comment">// present</span></div>
<div class="line"> <span class="stringliteral">"golf"</span>, <span class="comment">// absent, may be a Bloom filter false positive</span></div>
<div class="line"> <span class="stringliteral">"charlie"</span>, <span class="comment">// present</span></div>
<div class="line"> <span class="stringliteral">"hotel"</span>, <span class="comment">// absent</span></div>
<div class="line"> };</div>
<div class="line"> </div>
<div class="line"> <span class="keyword">const</span> <span class="keywordtype">int</span> N = <span class="keyword">static_cast<</span><span class="keywordtype">int</span><span class="keyword">></span>(keys.size());</div>
<div class="line"> std::vector<Result> results(N, Result::NOT_FOUND);</div>
<div class="line"> </div>
<div class="line"> tf::Executor executor;</div>
<div class="line"> tf::Taskflow taskflow(<span class="stringliteral">"speculative-lookup"</span>);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── build one chain per key ──────────────────────────────────────</span></div>
<div class="line"> std::vector<tf::Task> done_tasks(N);</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keywordtype">int</span> i = 0; i < N; i++) {</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// prepare: a named anchor task, zero dependencies.</span></div>
<div class="line"> tf::Task prepare = taskflow.emplace([](){})</div>
<div class="line"> .name(<span class="stringliteral">"prepare_"</span> + std::to_string(i));</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// speculate: probe the Bloom filter.</span></div>
<div class="line"> <span class="comment">// returns 0 -> fast_handler (definitely absent)</span></div>
<div class="line"> <span class="comment">// returns 1 -> slow_fallback (probably present, do full lookup)</span></div>
<div class="line"> tf::Task speculate = taskflow.emplace([&, i]() -> <span class="keywordtype">int</span> {</div>
<div class="line"> <span class="keywordflow">return</span> bloom.probe(keys[i]) ? 1 : 0;</div>
<div class="line"> }).name(<span class="stringliteral">"speculate_"</span> + std::to_string(i));</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// fast_handler: Bloom filter says "not present" — key is absent.</span></div>
<div class="line"> <span class="comment">// Condition task returning 0 -> merge (weak edge, avoids deadlock).</span></div>
<div class="line"> tf::Task fast_handler = taskflow.emplace([&, i]() -> <span class="keywordtype">int</span> {</div>
<div class="line"> results[i] = Result::NOT_FOUND;</div>
<div class="line"> printf(<span class="stringliteral">"[fast] key='%s' -> not found (Bloom filter negative)\n"</span>,</div>
<div class="line"> keys[i].c_str());</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line"> }).name(<span class="stringliteral">"fast_"</span> + std::to_string(i));</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// slow_fallback: Bloom filter says "probably present" — do full lookup.</span></div>
<div class="line"> <span class="comment">// Condition task returning 0 -> merge (weak edge, avoids deadlock).</span></div>
<div class="line"> tf::Task slow_fallback = taskflow.emplace([&, i]() -> <span class="keywordtype">int</span> {</div>
<div class="line"> <span class="keywordtype">bool</span> found = table.count(keys[i]) > 0;</div>
<div class="line"> results[i] = found ? Result::FOUND : Result::NOT_FOUND;</div>
<div class="line"> printf(<span class="stringliteral">"[slow] key='%s' -> %s (full lookup)\n"</span>,</div>
<div class="line"> keys[i].c_str(), found ? <span class="stringliteral">"found"</span> : <span class="stringliteral">"not found (false positive)"</span>);</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line"> }).name(<span class="stringliteral">"slow_"</span> + std::to_string(i));</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// merge: convergence point for fast and slow paths.</span></div>
<div class="line"> <span class="comment">// Condition task returning 0 -> done (weak edge).</span></div>
<div class="line"> <span class="comment">// Has two weak incoming edges; exactly one fires per execution.</span></div>
<div class="line"> tf::Task merge = taskflow.emplace([]() -> <span class="keywordtype">int</span> {</div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line"> }).name(<span class="stringliteral">"merge_"</span> + std::to_string(i));</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// done: regular task, records completion.</span></div>
<div class="line"> <span class="comment">// Has one weak incoming edge from merge; strong outgoing edge to collect.</span></div>
<div class="line"> tf::Task done = taskflow.emplace([&, i](){</div>
<div class="line"> printf(<span class="stringliteral">"[done] key='%s'\n"</span>, keys[i].c_str());</div>
<div class="line"> }).name(<span class="stringliteral">"done_"</span> + std::to_string(i));</div>
<div class="line"> </div>
<div class="line"> done_tasks[i] = done;</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── wire the chain ─────────────────────────────────────────────</span></div>
<div class="line"> speculate.<a class="code hl_function" href="classtf_1_1Task.html#a331b1b726555072e7c7d10941257f664">succeed</a>(prepare); <span class="comment">// strong: prepare -> speculate</span></div>
<div class="line"> speculate.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(fast_handler, slow_fallback); <span class="comment">// weak: 0=fast, 1=slow</span></div>
<div class="line"> fast_handler.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(merge); <span class="comment">// weak: fast -> merge (return 0)</span></div>
<div class="line"> slow_fallback.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(merge); <span class="comment">// weak: slow -> merge (return 0)</span></div>
<div class="line"> merge.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(done); <span class="comment">// weak: merge -> done (return 0)</span></div>
<div class="line"> }</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── collect: waits for all N done tasks via strong dependencies ──</span></div>
<div class="line"> tf::Task collect = taskflow.emplace([&](){</div>
<div class="line"> <span class="keywordtype">int</span> found = 0;</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keyword">auto</span>& r : results) <span class="keywordflow">if</span>(r == Result::FOUND) found++;</div>
<div class="line"> printf(<span class="stringliteral">"\nSummary: %d/%d keys found\n"</span>, found, N);</div>
<div class="line"> }).name(<span class="stringliteral">"collect"</span>);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// done_tasks[i] -> collect: strong edges, collect enqueued exactly once</span></div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keyword">auto</span>& d : done_tasks) d.precede(collect);</div>
<div class="line"> </div>
<div class="line"> executor.<a class="code hl_function" href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069">run</a>(taskflow).wait();</div>
<div class="line"> </div>
<div class="line"> <span class="keywordflow">return</span> 0;</div>
<div class="line">}</div>
<div class="ttc" id="aclasstf_1_1Executor_html_a519777f5783981d534e9e53b99712069"><div class="ttname"><a href="classtf_1_1Executor.html#a519777f5783981d534e9e53b99712069">tf::Executor::run</a></div><div class="ttdeci">tf::Future< void > run(Taskflow &taskflow)</div><div class="ttdoc">runs a taskflow once</div></div>
<div class="ttc" id="aclasstf_1_1Task_html_a331b1b726555072e7c7d10941257f664"><div class="ttname"><a href="classtf_1_1Task.html#a331b1b726555072e7c7d10941257f664">tf::Task::succeed</a></div><div class="ttdeci">Task & succeed(Ts &&... tasks)</div><div class="ttdoc">adds precedence links from other tasks to this</div><div class="ttdef"><b>Definition</b> task.hpp:1266</div></div>
<div class="ttc" id="aclasstf_1_1Task_html_a8c78c453295a553c1c016e4062da8588"><div class="ttname"><a href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">tf::Task::precede</a></div><div class="ttdeci">Task & precede(Ts &&... tasks)</div><div class="ttdoc">adds precedence links from this to other tasks</div><div class="ttdef"><b>Definition</b> task.hpp:1258</div></div>
</div><!-- fragment --><p>A sample run with the keys above produces output such as:</p>
<div class="fragment"><div class="line">[fast] key='foxtrot' -> not found (Bloom filter negative)</div>
<div class="line">[slow] key='alpha' -> found (full lookup)</div>
<div class="line">[fast] key='hotel' -> not found (Bloom filter negative)</div>
<div class="line">[slow] key='bravo' -> found (full lookup)</div>
<div class="line">[slow] key='golf' -> not found (false positive)</div>
<div class="line">[slow] key='charlie' -> found (full lookup)</div>
<div class="line">[done] key='foxtrot'</div>
<div class="line">[done] key='alpha'</div>
<div class="line">[done] key='hotel'</div>
<div class="line">[done] key='bravo'</div>
<div class="line">[done] key='golf'</div>
<div class="line">[done] key='charlie'</div>
<div class="line"> </div>
<div class="line">Summary: 3/6 keys found</div>
</div><!-- fragment --><p>The fast and slow paths for different keys interleave freely because the <code>N</code> chains are fully independent. The <code>collect</code> task appears last, after all <code>done</code> tasks have completed.</p>
<h1><a class="anchor" id="SpecDesignPoints"></a>
Design Points</h1>
<ul>
<li>Both the routing task and each branch task must be condition tasks: The deadlock in <code>spec_wrong</code> arises because <code>fast_handler</code> and <code>slow_fallback</code> are regular tasks, making their edges to <code>merge</code> strong. <code>merge</code> then waits for two strong dependencies that can never both be satisfied. The fix is for every task that has an outgoing edge to a shared convergence point to be a condition task, so those edges are weak and bypass the strong dependency counter. This is the same rule as for switch control flow (see <a class="el" href="ConditionalTasking.html#ImplementSwitchControlFlow">Implement Switch Control Flow</a>): whenever a condition task fans out to <code>k</code> branches that all converge on the same downstream task, all <code>k</code> branch tasks must also be condition tasks.</li>
<li><code>merge</code> is a pass-through condition task: <code>merge</code> performs no computation — it exists solely as a controlled convergence point. It has two incoming weak edges (exactly one fires) and one outgoing weak edge to <code>done</code>. Its return value is always <code>0</code>, which is the index of its only successor. This pattern — a no-op condition task used purely to merge exclusive branches — is the condition-task analogue of the auxiliary join task used for the same purpose with regular tasks in <a class="el" href="ExamplesMakeGraph.html">Incremental Build Graph</a>.</li>
<li><code>done</code> bridges the condition-task chain to the strong-dependency world: <code>collect</code> needs strong incoming edges so that it is enqueued exactly once after all <code>N</code> chains have completed. <code>done</code> is a regular task reached via a weak edge from <code>merge</code>, so its outgoing edge to <code>collect</code> is strong. It serves as the re-entry point from the condition-task world (all weak edges, activated by routing) back to the regular-task world (strong edges, activated by reference counting). Without <code>done</code>, <code>collect</code> would need <code>N</code> weak incoming edges from <code>merge</code> and would be enqueued up to <code>N</code> times simultaneously — a task race analogous to <b>Pitfall</b> <b>2</b> from <a class="el" href="ConditionalTasking.html#AvoidCommonPitfalls">Avoid Common Pitfalls</a>.</li>
<li>The fast-path short circuit is a scheduling gain, not just a code organisation gain: When <code>speculate</code> returns <code>0</code>, the scheduler enqueues <code>fast_handler</code> immediately and never touches <code>slow_fallback</code>. <code>slow_fallback</code> is never dequeued, never invoked, and its slot in the worker queue is never occupied. On a workload where 90% of keys are absent and the Bloom filter has a low false-positive rate, 90% of the per-key chains skip the hash-table lookup entirely, and those workers are freed to pick up the next available chain sooner. This throughput gain is automatic: it requires no explicit thread management, no condition variables, and no external job queue.</li>
</ul>
<dl class="section note"><dt>Note</dt><dd>The Bloom filter in this example uses two hash functions for clarity. Production Bloom filters typically use <code>k</code> = ln(2) * m/n hash functions, where <code>m</code> is the bit-array size and <code>n</code> is the number of inserted elements, to minimise the false-positive rate for a given memory budget. The graph structure and condition task wiring are identical regardless of <code>k</code>; only the <code>probe</code> function changes. </dd></dl>
</div></div><!-- contents -->
</div><!-- PageDoc -->
</div><!-- doc-content -->
<!-- HTML footer for doxygen 1.13.1-->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
<ul>
<li class="navelem"><a class="el" href="Examples.html">Learning from Examples</a></li>
<li class="footer">
Maintained by <a href="https://tsung-wei-huang.github.io/">Dr. Tsung-Wei Huang</a>
—
Generated by <a href="https://www.doxygen.org/index.html"><img class="footer" src="doxygen.svg" width="104" height="31" alt="doxygen"/></a> 1.13.1
</li>
</ul>
</div>