-
-
Notifications
You must be signed in to change notification settings - Fork 1.4k
Expand file tree
/
Copy pathExamplesMakeGraph.html
More file actions
344 lines (342 loc) · 31.3 KB
/
Copy pathExamplesMakeGraph.html
File metadata and controls
344 lines (342 loc) · 31.3 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
<!-- 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: Incremental Build Graph</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('ExamplesMakeGraph.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">Incremental Build Graph</div></div>
</div><!--header-->
<div class="contents">
<div class="toc"><h3>Table of Contents</h3>
<ul>
<li class="level1">
<a href="#MakeGraphIntroduction">What is an Incremental Build?</a>
</li>
<li class="level1">
<a href="#MakeGraphProblem">A Concrete Build Graph</a>
</li>
<li class="level1">
<a href="#MakeGraphConditionTask">Using Condition Tasks for Staleness</a>
</li>
<li class="level1">
<a href="#MakeGraphPitfall">The Task Race at the Join Point</a>
</li>
<li class="level1">
<a href="#MakeGraphJoinTask">The Auxiliary Join Task Pattern</a>
</li>
<li class="level1">
<a href="#MakeGraphImplementation">Implementation</a>
</li>
<li class="level1">
<a href="#MakeGraphDesignPoints">Design Points</a>
</li>
</ul>
</div>
<div class="textblock"><p>We implement a <em>make-style</em> <em>incremental</em> <em>build</em> <em>system</em> as a <a class="el" href="classtf_1_1Taskflow.html" title="class to create a taskflow object">tf::Taskflow</a> that uses condition tasks to skip up-to-date targets and recompile only what is stale. This example demonstrates how condition tasks express data-dependent branching in a structurally fixed graph, and how to apply the <em>auxiliary</em> <em>join</em> <em>task</em> pattern to avoid the task race that arises at every multi-predecessor join point in the build graph.</p>
<h1><a class="anchor" id="MakeGraphIntroduction"></a>
What is an Incremental Build?</h1>
<p>A build system such as <code>make</code> or <code>ninja</code> maintains a directed acyclic graph of <em>targets:</em> source files, object files, libraries, and final binaries. Each directed edge means "this target depends on that file." When a build is requested, the build system traverses the graph and recompiles only the targets whose inputs have changed since they were last built — the target is <em>stale</em>. Targets whose inputs are all newer than the target are silently skipped.</p>
<p>The staleness check is a simple timestamp comparison: if any input file has a modification time newer than the target, the target must be rebuilt. This conditional skip-or-rebuild decision is exactly what condition tasks are designed to express — a task that inspects runtime state and routes the scheduler down one of two paths.</p>
<h1><a class="anchor" id="MakeGraphProblem"></a>
A Concrete Build Graph</h1>
<p>Consider a small C project with three translation units and a single binary:</p>
<div class="fragment"><div class="line">Sources: main.c util.c math.c</div>
<div class="line">Headers: util.h math.h</div>
<div class="line"> </div>
<div class="line">Compile rules:</div>
<div class="line"> main.o <- main.c, util.h, math.h</div>
<div class="line"> util.o <- util.c, util.h</div>
<div class="line"> math.o <- math.c, math.h</div>
<div class="line"> </div>
<div class="line">Link rule:</div>
<div class="line"> app <- main.o, util.o, math.o</div>
</div><!-- fragment --><p>The dependency graph is:</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_make_dag.svg" width="360" height="336"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>Source and header files (blue) have no dependencies and always exist on disk. Object files (yellow) depend on their source and included headers. The final binary (green) depends on all three object files. <code>main.o</code>, <code>util.o</code>, and <code>math.o</code> have no mutual dependency and can be processed simultaneously on separate cores.</p>
<h1><a class="anchor" id="MakeGraphConditionTask"></a>
Using Condition Tasks for Staleness</h1>
<p>Each object file target has two possible outcomes at runtime: either it is up-to-date (skip compilation) or it is stale (run the compiler). This is a binary branch — the natural role for a condition task. Each condition task checks the timestamps of its inputs against its output and returns <code>0</code> to skip or <code>1</code> to rebuild.</p>
<p>Condition tasks fit naturally here because the <em>graph</em> <em>structure</em> is entirely static — it is determined by the build rules, not by file contents — while the <em>routing</em> <em>decision</em> is dynamic, determined at runtime by timestamp comparison. Static tasks handle the fixed structure; condition tasks handle the dynamic branch.</p>
<h1><a class="anchor" id="MakeGraphPitfall"></a>
The Task Race at the Join Point</h1>
<p>A first attempt might wire the condition tasks directly to <code>app:</code> each condition task returns <code>1</code> to run the compile step, which then feeds <code>app</code> with a strong edge, and returns <code>0</code> to route directly to <code>app</code> via a weak edge, skipping compilation.</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_make_wrong.svg" width="626" height="523"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>This graph has a fatal flaw. Task <code>app</code> sits at the junction of three condition tasks' outputs. All three condition tasks can complete simultaneously — if all three find their object files stale, all three fire their <code>"1 (rebuild)"</code> branch and the three compile tasks each try to satisfy <code>app's</code> strong dependency counter concurrently. This is the correct path. But if some condition tasks return <code>0</code> (skip), they schedule <code>app</code> directly through a weak edge at the same time that other compile tasks are also converging on <code>app</code> via strong edges. <code>app</code> can be scheduled more than once, which is undefined behaviour.</p>
<p>This is precisely <b>Pitfall</b> <b>2</b> (Task Race) from <a class="el" href="ConditionalTasking.html#AvoidCommonPitfalls">Avoid Common Pitfalls</a> where a task sitting at the convergence of multiple condition task outputs is at risk of being scheduled concurrently by different paths.</p>
<h1><a class="anchor" id="MakeGraphJoinTask"></a>
The Auxiliary Join Task Pattern</h1>
<p>The fix is to insert one <em>join</em> task per object file between the condition task and <code>app</code>. Each join task is a lightweight no-op that serves as a controlled merge point for the skip and rebuild paths of a single object file. <code>app</code> then has exactly three strong dependencies — one per join task — and is enqueued exactly once, after all three join tasks have completed.</p>
<div class="dotgraph">
<iframe scrolling="no" frameborder="0" src="dot_make_correct.svg" width="788" height="450"><p><b>This browser is not able to show SVG: try Firefox, Chrome, Safari, or Opera instead.</b></p></iframe></div>
<p>For each object file the structure is:</p>
<div class="fragment"><div class="line">sources --> obj.cond --0 (skip)----> obj.join</div>
<div class="line"> --1 (rebuild)-> cc obj.o --> obj.join</div>
<div class="line">obj.join --> app</div>
</div><!-- fragment --><p>The join task has one weak dependency (from the condition task on the skip path) and one strong dependency (from the compile task on the rebuild path). Exactly one of these two paths activates the join task on any given run, so it is scheduled exactly once. The following table lists the strong and weak dependency counts for all tasks in the graph:</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">main.c, util.c, util.h, math.c, math.h </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">0 </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft">main.o? </td><td class="markdownTableBodyCenter">3 </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">3 </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft">util.o? </td><td class="markdownTableBodyCenter">2 </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">2 </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft">math.o? </td><td class="markdownTableBodyCenter">2 </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">2 </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft">cc main.o </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">1 </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft">cc util.o </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">1 </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft">cc math.o </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">1 </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft">main.o (join) </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">2 </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft">util.o (join) </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">2 </td></tr>
<tr class="markdownTableRowEven">
<td class="markdownTableBodyLeft">math.o (join) </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">1 </td><td class="markdownTableBodyCenter">2 </td></tr>
<tr class="markdownTableRowOdd">
<td class="markdownTableBodyLeft">app </td><td class="markdownTableBodyCenter">3 </td><td class="markdownTableBodyCenter">0 </td><td class="markdownTableBodyCenter">3 </td></tr>
</table>
</div><p>Every task has a unique, unambiguous activation path. No task can be scheduled more than once simultaneously.</p>
<h1><a class="anchor" id="MakeGraphImplementation"></a>
Implementation</h1>
<p>We represent each build target as a <code>Target</code> struct carrying its output path, input paths, and compile command. The staleness check compares modification times; condition tasks return the result. Join tasks are plain no-op lambdas whose only purpose is to serve as the controlled merge point described above.</p>
<div class="fragment"><div class="line"><span class="preprocessor">#include <taskflow/taskflow.hpp></span></div>
<div class="line"><span class="preprocessor">#include <filesystem></span></div>
<div class="line"> </div>
<div class="line"><span class="keyword">namespace </span>fs = std::filesystem;</div>
<div class="line"> </div>
<div class="line"><span class="comment">// Returns true if output is missing or older than any input.</span></div>
<div class="line"><span class="keywordtype">bool</span> is_stale(<span class="keyword">const</span> std::string& output,</div>
<div class="line"> <span class="keyword">const</span> std::vector<std::string>& inputs) {</div>
<div class="line"> <span class="keywordflow">if</span>(!fs::exists(output)) <span class="keywordflow">return</span> <span class="keyword">true</span>;</div>
<div class="line"> <span class="keyword">auto</span> out_time = fs::last_write_time(output);</div>
<div class="line"> <span class="keywordflow">for</span>(<span class="keyword">auto</span>& in : inputs) {</div>
<div class="line"> <span class="keywordflow">if</span>(fs::exists(in) && fs::last_write_time(in) > out_time) <span class="keywordflow">return</span> <span class="keyword">true</span>;</div>
<div class="line"> }</div>
<div class="line"> <span class="keywordflow">return</span> <span class="keyword">false</span>;</div>
<div class="line">}</div>
<div class="line"> </div>
<div class="line"><span class="keywordtype">int</span> main() {</div>
<div class="line"> </div>
<div class="line"> <a class="code hl_class" href="classtf_1_1Executor.html">tf::Executor</a> executor;</div>
<div class="line"> <a class="code hl_class" href="classtf_1_1Taskflow.html">tf::Taskflow</a> taskflow(<span class="stringliteral">"incremental-build"</span>);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── source/header leaf tasks ────────────────────────────────────</span></div>
<div class="line"> <span class="comment">// These always exist and are never stale; they act only as</span></div>
<div class="line"> <span class="comment">// dependency anchors.</span></div>
<div class="line"> <a class="code hl_class" href="classtf_1_1Task.html">tf::Task</a> main_c = taskflow.emplace([](){}).name(<span class="stringliteral">"main.c"</span>);</div>
<div class="line"> tf::Task util_c = taskflow.emplace([](){}).name(<span class="stringliteral">"util.c"</span>);</div>
<div class="line"> tf::Task util_h = taskflow.emplace([](){}).name(<span class="stringliteral">"util.h"</span>);</div>
<div class="line"> tf::Task math_c = taskflow.emplace([](){}).name(<span class="stringliteral">"math.c"</span>);</div>
<div class="line"> tf::Task math_h = taskflow.emplace([](){}).name(<span class="stringliteral">"math.h"</span>);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── condition tasks: check staleness, return 0=skip, 1=rebuild ──</span></div>
<div class="line"> tf::Task main_cond = taskflow.emplace([]() -> <span class="keywordtype">int</span> {</div>
<div class="line"> <span class="keywordflow">return</span> is_stale(<span class="stringliteral">"main.o"</span>, {<span class="stringliteral">"main.c"</span>, <span class="stringliteral">"util.h"</span>, <span class="stringliteral">"math.h"</span>}) ? 1 : 0;</div>
<div class="line"> }).name(<span class="stringliteral">"main.o?"</span>);</div>
<div class="line"> </div>
<div class="line"> tf::Task util_cond = taskflow.emplace([]() -> <span class="keywordtype">int</span> {</div>
<div class="line"> <span class="keywordflow">return</span> is_stale(<span class="stringliteral">"util.o"</span>, {<span class="stringliteral">"util.c"</span>, <span class="stringliteral">"util.h"</span>}) ? 1 : 0;</div>
<div class="line"> }).name(<span class="stringliteral">"util.o?"</span>);</div>
<div class="line"> </div>
<div class="line"> tf::Task math_cond = taskflow.emplace([]() -> <span class="keywordtype">int</span> {</div>
<div class="line"> <span class="keywordflow">return</span> is_stale(<span class="stringliteral">"math.o"</span>, {<span class="stringliteral">"math.c"</span>, <span class="stringliteral">"math.h"</span>}) ? 1 : 0;</div>
<div class="line"> }).name(<span class="stringliteral">"math.o?"</span>);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── compile tasks: invoked only on the rebuild (return 1) path ──</span></div>
<div class="line"> tf::Task main_cc = taskflow.emplace([](){</div>
<div class="line"> printf(<span class="stringliteral">"[build] cc main.o\n"</span>);</div>
<div class="line"> std::system(<span class="stringliteral">"cc -c main.c -o main.o"</span>);</div>
<div class="line"> }).name(<span class="stringliteral">"cc main.o"</span>);</div>
<div class="line"> </div>
<div class="line"> tf::Task util_cc = taskflow.emplace([](){</div>
<div class="line"> printf(<span class="stringliteral">"[build] cc util.o\n"</span>);</div>
<div class="line"> std::system(<span class="stringliteral">"cc -c util.c -o util.o"</span>);</div>
<div class="line"> }).name(<span class="stringliteral">"cc util.o"</span>);</div>
<div class="line"> </div>
<div class="line"> tf::Task math_cc = taskflow.emplace([](){</div>
<div class="line"> printf(<span class="stringliteral">"[build] cc math.o\n"</span>);</div>
<div class="line"> std::system(<span class="stringliteral">"cc -c math.c -o math.o"</span>);</div>
<div class="line"> }).name(<span class="stringliteral">"cc math.o"</span>);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── join tasks: no-op merge point for skip and rebuild paths ────</span></div>
<div class="line"> <span class="comment">// Each join task is activated by exactly one of its two incoming</span></div>
<div class="line"> <span class="comment">// paths (skip via weak dep, or rebuild via strong dep from compile).</span></div>
<div class="line"> <span class="comment">// This guarantees app has exactly 3 strong deps satisfied before</span></div>
<div class="line"> <span class="comment">// it is enqueued.</span></div>
<div class="line"> tf::Task main_join = taskflow.emplace([](){}).name(<span class="stringliteral">"main.o (join)"</span>);</div>
<div class="line"> tf::Task util_join = taskflow.emplace([](){}).name(<span class="stringliteral">"util.o (join)"</span>);</div>
<div class="line"> tf::Task math_join = taskflow.emplace([](){}).name(<span class="stringliteral">"math.o (join)"</span>);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── link task ───────────────────────────────────────────────────</span></div>
<div class="line"> tf::Task app = taskflow.emplace([](){</div>
<div class="line"> <span class="keywordflow">if</span>(is_stale(<span class="stringliteral">"app"</span>, {<span class="stringliteral">"main.o"</span>, <span class="stringliteral">"util.o"</span>, <span class="stringliteral">"math.o"</span>})) {</div>
<div class="line"> printf(<span class="stringliteral">"[build] link app\n"</span>);</div>
<div class="line"> std::system(<span class="stringliteral">"cc main.o util.o math.o -o app"</span>);</div>
<div class="line"> } <span class="keywordflow">else</span> {</div>
<div class="line"> printf(<span class="stringliteral">"[up-to-date] app\n"</span>);</div>
<div class="line"> }</div>
<div class="line"> }).name(<span class="stringliteral">"app"</span>);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// ── wire the graph ──────────────────────────────────────────────</span></div>
<div class="line"> </div>
<div class="line"> <span class="comment">// sources feed condition tasks (strong dependencies)</span></div>
<div class="line"> main_cond.<a class="code hl_function" href="classtf_1_1Task.html#a331b1b726555072e7c7d10941257f664">succeed</a>(main_c, util_h, math_h);</div>
<div class="line"> util_cond.<a class="code hl_function" href="classtf_1_1Task.html#a331b1b726555072e7c7d10941257f664">succeed</a>(util_c, util_h);</div>
<div class="line"> math_cond.<a class="code hl_function" href="classtf_1_1Task.html#a331b1b726555072e7c7d10941257f664">succeed</a>(math_c, math_h);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// condition tasks route: 0 -> join (skip), 1 -> compile (rebuild)</span></div>
<div class="line"> main_cond.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(main_join, main_cc); <span class="comment">// 0=main_join, 1=main_cc</span></div>
<div class="line"> util_cond.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(util_join, util_cc);</div>
<div class="line"> math_cond.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(math_join, math_cc);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// compile tasks feed join tasks (strong dependency — satisfies</span></div>
<div class="line"> <span class="comment">// join's strong dep counter on the rebuild path)</span></div>
<div class="line"> main_cc.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(main_join);</div>
<div class="line"> util_cc.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(util_join);</div>
<div class="line"> math_cc.<a class="code hl_function" href="classtf_1_1Task.html#a8c78c453295a553c1c016e4062da8588">precede</a>(math_join);</div>
<div class="line"> </div>
<div class="line"> <span class="comment">// join tasks feed app (strong dependencies — app runs exactly once)</span></div>
<div class="line"> app.<a class="code hl_function" href="classtf_1_1Task.html#a331b1b726555072e7c7d10941257f664">succeed</a>(main_join, util_join, math_join);</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"><div class="ttname"><a href="classtf_1_1Executor.html">tf::Executor</a></div><div class="ttdoc">class to create an executor</div><div class="ttdef"><b>Definition</b> executor.hpp:62</div></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"><div class="ttname"><a href="classtf_1_1Task.html">tf::Task</a></div><div class="ttdoc">class to create a task handle over a taskflow node</div><div class="ttdef"><b>Definition</b> task.hpp:569</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 class="ttc" id="aclasstf_1_1Taskflow_html"><div class="ttname"><a href="classtf_1_1Taskflow.html">tf::Taskflow</a></div><div class="ttdoc">class to create a taskflow object</div><div class="ttdef"><b>Definition</b> taskflow.hpp:64</div></div>
</div><!-- fragment --><p>On a fully clean build the expected output is:</p>
<div class="fragment"><div class="line">[build] cc main.o</div>
<div class="line">[build] cc util.o</div>
<div class="line">[build] cc math.o</div>
<div class="line">[build] link app</div>
</div><!-- fragment --><p>After touching only <code>util.c</code> and rebuilding:</p>
<div class="fragment"><div class="line">[build] cc util.o</div>
<div class="line">[build] link app</div>
</div><!-- fragment --><p><code>main.o</code> and <code>math.o</code> are skipped because their condition tasks return <code>0</code> and route directly to their join tasks, bypassing compilation entirely. <code>app</code> runs its own link check and finds <code>util.o</code> newer than <code>app</code>, so it relinks.</p>
<h1><a class="anchor" id="MakeGraphDesignPoints"></a>
Design Points</h1>
<ul>
<li>Condition tasks express the skip-or-rebuild branch cleanly: The decision of whether to recompile is made at the condition task, not scattered through the task bodies. The condition task queries the filesystem and routes the scheduler; the compile task only compiles. This separation keeps each task's responsibility narrow and makes the graph readable: a diamond node in the dump output signals a binary routing decision, and its two outgoing dashed edges show exactly what each outcome triggers.</li>
<li>The join task is the canonical fix for Pitfall 2 at build join points: Without join tasks, <code>app</code> sits at the convergence of three condition task outputs and can be scheduled up to three times simultaneously. The join task absorbs this convergence: it has one weak incoming edge (from the skip path) and one strong incoming edge (from the compile path), so exactly one path activates it per run. <code>app</code> then has only strong incoming edges and is enqueued exactly once. This is the <em>auxiliary</em> <em>task</em> pattern described in <a class="el" href="ConditionalTasking.html#AvoidCommonPitfalls">Avoid Common Pitfalls</a>, applied systematically at every join point in the build graph.</li>
<li><code>taskflow.dump()</code> makes the routing explicit: Calling <code>taskflow.dump(std::cout)</code> before running the executor emits a Graphviz description of the full graph, including the dashed weak edges from condition tasks. Inspecting the strong and weak dependency counts of each task (see <a class="el" href="ConditionalTasking.html#TaskSchedulingPolicy">Understand our Task-level Scheduling</a>) provides a quick sanity check: any task with multiple incoming weak edges from concurrently executable condition tasks is a potential race site, and should be given an auxiliary join task.</li>
<li>The link task performs its own staleness check: Unlike object file targets, the link step cannot be expressed as a condition task because it must always run <em>after</em> all three join tasks complete — its strong dependency count of three already guarantees the correct ordering. The staleness check inside <code>app's</code> lambda is a secondary guard that avoids re-linking when all three join tasks came through the skip path and no object file changed. This is consistent with how <code>make</code> behaves: the link rule runs its recipe only when its inputs are newer than its output.</li>
</ul>
<dl class="section note"><dt>Note</dt><dd>This example models a three-target project for clarity. A real build system with hundreds of targets follows the same pattern: one condition task and one join task per non-leaf target, wired according to the project's dependency declarations. The number of tasks grows linearly with the number of targets, and the executor automatically exploits all available parallelism among independent targets in the same topological level. </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>