Depsgraph: Remove workarounds from depsgraph for keeping threads alive
[blender-staging.git] / source / blender / depsgraph / intern / eval / deg_eval.cc
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2013 Blender Foundation.
19  * All rights reserved.
20  *
21  * Original Author: Joshua Leung
22  * Contributor(s): None Yet
23  *
24  * ***** END GPL LICENSE BLOCK *****
25  */
26
27 /** \file blender/depsgraph/intern/eval/deg_eval.cc
28  *  \ingroup depsgraph
29  *
30  * Evaluation engine entrypoints for Depsgraph Engine.
31  */
32
33 #include "intern/eval/deg_eval.h"
34
35 #include "PIL_time.h"
36
37 extern "C" {
38 #include "BLI_utildefines.h"
39 #include "BLI_task.h"
40 #include "BLI_ghash.h"
41
42 #include "BKE_depsgraph.h"
43 #include "BKE_global.h"
44
45 #include "DEG_depsgraph.h"
46 } /* extern "C" */
47
48 #include "atomic_ops.h"
49
50 #include "intern/eval/deg_eval_debug.h"
51 #include "intern/eval/deg_eval_flush.h"
52 #include "intern/nodes/deg_node.h"
53 #include "intern/nodes/deg_node_component.h"
54 #include "intern/nodes/deg_node_operation.h"
55 #include "intern/depsgraph.h"
56 #include "intern/depsgraph_intern.h"
57 #include "util/deg_util_foreach.h"
58
59 /* Unfinished and unused, and takes quite some pre-processing time. */
60 #undef USE_EVAL_PRIORITY
61
62 /* Use integrated debugger to keep track how much each of the nodes was
63  * evaluating.
64  */
65 #undef USE_DEBUGGER
66
67 namespace DEG {
68
69 /* ********************** */
70 /* Evaluation Entrypoints */
71
72 /* Forward declarations. */
73 static void schedule_children(TaskPool *pool,
74                               Depsgraph *graph,
75                               OperationDepsNode *node,
76                               const unsigned int layers,
77                               const int thread_id);
78
79 struct DepsgraphEvalState {
80         EvaluationContext *eval_ctx;
81         Depsgraph *graph;
82         unsigned int layers;
83 };
84
85 static void deg_task_run_func(TaskPool *pool,
86                               void *taskdata,
87                               int thread_id)
88 {
89         DepsgraphEvalState *state =
90                 reinterpret_cast<DepsgraphEvalState *>(BLI_task_pool_userdata(pool));
91         OperationDepsNode *node = reinterpret_cast<OperationDepsNode *>(taskdata);
92
93         BLI_assert(!node->is_noop() && "NOOP nodes should not actually be scheduled");
94
95         /* Should only be the case for NOOPs, which never get to this point. */
96         BLI_assert(node->evaluate);
97
98         /* Get context. */
99         /* TODO: Who initialises this? "Init" operations aren't able to
100          * initialise it!!!
101          */
102         /* TODO(sergey): We don't use component contexts at this moment. */
103         /* ComponentDepsNode *comp = node->owner; */
104         BLI_assert(node->owner != NULL);
105
106         /* Since we're not leaving the thread for until the graph branches it is
107          * possible to have NO-OP on the way. for which evaluate() will be NULL.
108          * but that's all fine, we'll just scheduler it's children.
109          */
110         if (node->evaluate) {
111                         /* Take note of current time. */
112 #ifdef USE_DEBUGGER
113                 double start_time = PIL_check_seconds_timer();
114                 DepsgraphDebug::task_started(state->graph, node);
115 #endif
116
117                 /* Perform operation. */
118                 node->evaluate(state->eval_ctx);
119
120                         /* Note how long this took. */
121 #ifdef USE_DEBUGGER
122                 double end_time = PIL_check_seconds_timer();
123                 DepsgraphDebug::task_completed(state->graph,
124                                                node,
125                                                end_time - start_time);
126 #endif
127         }
128
129         schedule_children(pool, state->graph, node, state->layers, thread_id);
130 }
131
132 typedef struct CalculatePengindData {
133         Depsgraph *graph;
134         unsigned int layers;
135 } CalculatePengindData;
136
137 static void calculate_pending_func(void *data_v, int i)
138 {
139         CalculatePengindData *data = (CalculatePengindData *)data_v;
140         Depsgraph *graph = data->graph;
141         unsigned int layers = data->layers;
142         OperationDepsNode *node = graph->operations[i];
143         IDDepsNode *id_node = node->owner->owner;
144
145         node->num_links_pending = 0;
146         node->scheduled = false;
147
148         /* count number of inputs that need updates */
149         if ((id_node->layers & layers) != 0 &&
150             (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0)
151         {
152                 foreach (DepsRelation *rel, node->inlinks) {
153                         if (rel->from->type == DEPSNODE_TYPE_OPERATION &&
154                             (rel->flag & DEPSREL_FLAG_CYCLIC) == 0)
155                         {
156                                 OperationDepsNode *from = (OperationDepsNode *)rel->from;
157                                 IDDepsNode *id_from_node = from->owner->owner;
158                                 if ((id_from_node->layers & layers) != 0 &&
159                                     (from->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0)
160                                 {
161                                         ++node->num_links_pending;
162                                 }
163                         }
164                 }
165         }
166 }
167
168 static void calculate_pending_parents(Depsgraph *graph, unsigned int layers)
169 {
170         const int num_operations = graph->operations.size();
171         const bool do_threads = num_operations > 256;
172         CalculatePengindData data;
173         data.graph = graph;
174         data.layers = layers;
175         BLI_task_parallel_range(0,
176                                 num_operations,
177                                 &data,
178                                 calculate_pending_func,
179                                 do_threads);
180 }
181
182 #ifdef USE_EVAL_PRIORITY
183 static void calculate_eval_priority(OperationDepsNode *node)
184 {
185         if (node->done) {
186                 return;
187         }
188         node->done = 1;
189
190         if (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
191                 /* XXX standard cost of a node, could be estimated somewhat later on */
192                 const float cost = 1.0f;
193                 /* NOOP nodes have no cost */
194                 node->eval_priority = node->is_noop() ? cost : 0.0f;
195
196                 foreach (DepsRelation *rel, node->outlinks) {
197                         OperationDepsNode *to = (OperationDepsNode *)rel->to;
198                         BLI_assert(to->type == DEPSNODE_TYPE_OPERATION);
199                         calculate_eval_priority(to);
200                         node->eval_priority += to->eval_priority;
201                 }
202         }
203         else {
204                 node->eval_priority = 0.0f;
205         }
206 }
207 #endif
208
209 /* Schedule a node if it needs evaluation.
210  *   dec_parents: Decrement pending parents count, true when child nodes are
211  *                scheduled after a task has been completed.
212  */
213 static void schedule_node(TaskPool *pool, Depsgraph *graph, unsigned int layers,
214                           OperationDepsNode *node, bool dec_parents,
215                           const int thread_id)
216 {
217         unsigned int id_layers = node->owner->owner->layers;
218
219         if ((node->flag & DEPSOP_FLAG_NEEDS_UPDATE) != 0 &&
220             (id_layers & layers) != 0)
221         {
222                 if (dec_parents) {
223                         BLI_assert(node->num_links_pending > 0);
224                         atomic_sub_and_fetch_uint32(&node->num_links_pending, 1);
225                 }
226
227                 if (node->num_links_pending == 0) {
228                         bool is_scheduled = atomic_fetch_and_or_uint8(
229                                 (uint8_t *)&node->scheduled, (uint8_t)true);
230                         if (!is_scheduled) {
231                                 if (node->is_noop()) {
232                                         /* skip NOOP node, schedule children right away */
233                                         schedule_children(pool, graph, node, layers, thread_id);
234                                 }
235                                 else {
236                                         /* children are scheduled once this task is completed */
237                                         BLI_task_pool_push_from_thread(pool,
238                                                                        deg_task_run_func,
239                                                                        node,
240                                                                        false,
241                                                                        TASK_PRIORITY_HIGH,
242                                                                        thread_id);
243                                 }
244                         }
245                 }
246         }
247 }
248
249 static void schedule_graph(TaskPool *pool,
250                            Depsgraph *graph,
251                            const unsigned int layers)
252 {
253         foreach (OperationDepsNode *node, graph->operations) {
254                 schedule_node(pool, graph, layers, node, false, 0);
255         }
256 }
257
258 static void schedule_children(TaskPool *pool,
259                               Depsgraph *graph,
260                               OperationDepsNode *node,
261                               const unsigned int layers,
262                               const int thread_id)
263 {
264         foreach (DepsRelation *rel, node->outlinks) {
265                 OperationDepsNode *child = (OperationDepsNode *)rel->to;
266                 BLI_assert(child->type == DEPSNODE_TYPE_OPERATION);
267                 if (child->scheduled) {
268                         /* Happens when having cyclic dependencies. */
269                         continue;
270                 }
271                 schedule_node(pool,
272                               graph,
273                               layers,
274                               child,
275                               (rel->flag & DEPSREL_FLAG_CYCLIC) == 0,
276                               thread_id);
277         }
278 }
279
280 /**
281  * Evaluate all nodes tagged for updating,
282  * \warning This is usually done as part of main loop, but may also be
283  * called from frame-change update.
284  *
285  * \note Time sources should be all valid!
286  */
287 void deg_evaluate_on_refresh(EvaluationContext *eval_ctx,
288                              Depsgraph *graph,
289                              const unsigned int layers)
290 {
291         /* Generate base evaluation context, upon which all the others are derived. */
292         // TODO: this needs both main and scene access...
293
294         /* Nothing to update, early out. */
295         if (BLI_gset_size(graph->entry_tags) == 0) {
296                 return;
297         }
298
299         DEG_DEBUG_PRINTF("%s: layers:%u, graph->layers:%u\n",
300                          __func__,
301                          layers,
302                          graph->layers);
303
304         /* Set time for the current graph evaluation context. */
305         TimeSourceDepsNode *time_src = graph->find_time_source();
306         eval_ctx->ctime = time_src->cfra;
307
308         /* XXX could use a separate pool for each eval context */
309         DepsgraphEvalState state;
310         state.eval_ctx = eval_ctx;
311         state.graph = graph;
312         state.layers = layers;
313
314         TaskScheduler *task_scheduler;
315         bool need_free_scheduler;
316
317         if (G.debug & G_DEBUG_DEPSGRAPH_NO_THREADS) {
318                 task_scheduler = BLI_task_scheduler_create(1);
319                 need_free_scheduler = true;
320         }
321         else {
322                 task_scheduler = BLI_task_scheduler_get();
323                 need_free_scheduler = false;
324         }
325
326         TaskPool *task_pool = BLI_task_pool_create(task_scheduler, &state);
327
328         calculate_pending_parents(graph, layers);
329
330         /* Clear tags. */
331         foreach (OperationDepsNode *node, graph->operations) {
332                 node->done = 0;
333         }
334
335         /* Calculate priority for operation nodes. */
336 #ifdef USE_EVAL_PRIORITY
337         foreach (OperationDepsNode *node, graph->operations) {
338                 calculate_eval_priority(node);
339         }
340 #endif
341
342         DepsgraphDebug::eval_begin(eval_ctx);
343
344         schedule_graph(task_pool, graph, layers);
345
346         BLI_task_pool_work_and_wait(task_pool);
347         BLI_task_pool_free(task_pool);
348
349         DepsgraphDebug::eval_end(eval_ctx);
350
351         /* Clear any uncleared tags - just in case. */
352         deg_graph_clear_tags(graph);
353
354         if (need_free_scheduler) {
355                 BLI_task_scheduler_free(task_scheduler);
356         }
357 }
358
359 }  // namespace DEG