Bug 1472338: part 2) Change `clipboard.readText()` to read from the clipboard asynchr...
[gecko.git] / taskcluster / docs / optimization-process.rst
blob388b7848e62ba0f32d7928f1ae3efc828a1e9b02
1 Optimization Process
2 ====================
4 Optimization proceeds in three phases: removing tasks, replacing tasks,
5 and finally generating a subgraph containing only the remaining tasks.
7 Assume the following task graph as context for these examples::
9     TC1 <--\     ,- UP1
10           , B1 <--- T1a
11     I1 <-|       `- T1b
12           ` B2 <--- T2a
13     TC2 <--/     |- T2b
14                  `- UP2
16 Removing Tasks
17 --------------
19 This phase begins with tasks on which nothing depends and follows the
20 dependency graph backward from there -- right to left in the diagram above. If
21 a task is not removed, then nothing it depends on will be removed either.
22 Thus if T1a and T1b are both removed, B1 may be removed as well. But if T2b is
23 not removed, then B2 may not be removed either.
25 For each task with no remaining dependencies, the decision whether to remove is
26 made by calling the optimization strategy's ``should_remove_task`` method. If
27 this method returns True, the task is removed.
29 The optimization process takes a ``do_not_optimize`` argument containing a list
30 of tasks that cannot be removed under any circumstances. This is used to
31 "force" running specific tasks.
33 Replacing Tasks
34 ---------------
36 This phase begins with tasks having no dependencies and follows the reversed
37 dependency graph from there -- left to right in the diagram above. If a task is
38 not replaced, then anything depending on that task cannot be replaced.
39 Replacement is generally done on the basis of some hash of the inputs to the
40 task. In the diagram above, if both TC1 and I1 are replaced with existing
41 tasks, then B1 is a candidate for replacement. But if TC2 has no replacement,
42 then replacement of B2 will not be considered.
44 It is possible to replace a task with nothing.  This is similar to optimzing
45 away, but is useful for utility tasks like UP1. If such a task is considered
46 for replacement, then all of its dependencies (here, B1) have already been
47 replaced and there is no utility in running the task and no need for a
48 replacement task.  It is an error for a task on which others depend to be
49 replaced with nothing.
51 The ``do_not_optimize`` set applies to task replacement, as does an additional
52 ``existing_tasks`` dictionary which allows the caller to supply as set of
53 known, pre-existing tasks. This is used for action tasks, for example, where it
54 contains the entire task-graph generated by the original decision task.
56 Subgraph Generation
57 -------------------
59 The first two phases annotate each task in the existing taskgraph with their
60 fate: removed, replaced, or retained. The tasks that are replaced also have a
61 replacement taskId.
63 The last phase constructs a subgraph containing the retained tasks, and
64 simultaneously rewrites all dependencies to refer to taskIds instead of labels.
65 To do so, it assigns a taskId to each retained task and uses the replacement
66 taskId for all replaced tasks.
68 The `soft-dependencies` are then solved for each task, by adding all the
69 remaining tasks in the subgraph from that list to its `dependencies`.
71 The result is an optimized taskgraph with tasks named by taskId instead of
72 label. At this phase, the edges in the task graph diverge from the
73 ``task.dependencies`` attributes, as the latter may contain dependencies
74 outside of the taskgraph (for replacement tasks).
76 As a side-effect, this phase also expands all ``{"task-reference": ".."}`` and
77 ``{"artifact-reference": ".."}`` objects within the task definitions.