[Bf-blender-cvs] [065def5] depsgraph_refactor: First steps toward scheduling: calculate priorities for all nodes based on their dependants.
Lukas Tönne
noreply at git.blender.org
Wed May 21 00:15:18 CEST 2014
Commit: 065def57acae2019c1072c8df76f325b81fe89b1
Author: Lukas Tönne
Date: Wed May 21 00:11:43 2014 +0200
https://developer.blender.org/rB065def57acae2019c1072c8df76f325b81fe89b1
First steps toward scheduling: calculate priorities for all nodes
based on their dependants.
This heuristic can be improved later for more optimized scheduling.
The basic idea is to push all nodes which are evaluatable (all
dependencies satisfied) onto the queue, then pop the highest
priority node for evaluation.
===================================================================
M source/blender/depsgraph/DEG_depsgraph_debug.h
M source/blender/depsgraph/intern/depsgraph_debug.cpp
M source/blender/depsgraph/intern/depsgraph_eval.cpp
M source/blender/depsgraph/intern/depsnode_operation.cpp
M source/blender/depsgraph/intern/depsnode_operation.h
M source/blender/makesrna/intern/rna_depsgraph.c
===================================================================
diff --git a/source/blender/depsgraph/DEG_depsgraph_debug.h b/source/blender/depsgraph/DEG_depsgraph_debug.h
index 81c690b..24174f5 100644
--- a/source/blender/depsgraph/DEG_depsgraph_debug.h
+++ b/source/blender/depsgraph/DEG_depsgraph_debug.h
@@ -40,7 +40,7 @@ extern "C" {
/* ************************************************ */
/* Graphviz Debugging */
-void DEG_debug_graphviz(const struct Depsgraph *graph, FILE *stream, const char *label, bool show_tags);
+void DEG_debug_graphviz(const struct Depsgraph *graph, FILE *stream, const char *label, bool show_eval);
typedef void (*DEG_DebugBuildCb_NodeAdded)(void *userdata, const struct DepsNode *node);
typedef void (*DEG_DebugBuildCb_RelationAdded)(void *userdata, const struct DepsRelation *rel);
diff --git a/source/blender/depsgraph/intern/depsgraph_debug.cpp b/source/blender/depsgraph/intern/depsgraph_debug.cpp
index 033ad23..465f759 100644
--- a/source/blender/depsgraph/intern/depsgraph_debug.cpp
+++ b/source/blender/depsgraph/intern/depsgraph_debug.cpp
@@ -117,6 +117,7 @@ static int deg_debug_node_type_color_index(eDepsNode_Type type)
struct DebugContext {
FILE *file;
bool show_tags;
+ bool show_eval_priority;
};
static void deg_debug_printf(const DebugContext &ctx, const char *fmt, ...)
@@ -305,12 +306,18 @@ static void deg_debug_graphviz_node_single(const DebugContext &ctx, const DepsNo
{
const char *shape = "box";
const char *name = node->name.c_str();
+ float priority = -1.0f;
+ if (ctx.show_eval_priority && node->tclass == DEPSNODE_CLASS_OPERATION)
+ priority = ((OperationDepsNode *)node)->eval_priority;
deg_debug_printf(ctx, "// %s\n", name);
deg_debug_printf(ctx, "\"node_%p\"", node);
deg_debug_printf(ctx, "[");
// deg_debug_printf(ctx, "label=<<B>%s</B>>", name);
- deg_debug_printf(ctx, "label=<%s>", name);
+ if (priority >= 0.0f)
+ deg_debug_printf(ctx, "label=<%s (<I>%f</I>)>", name, priority);
+ else
+ deg_debug_printf(ctx, "label=<%s>", name);
deg_debug_printf(ctx, ",fontname=\"%s\"", deg_debug_graphviz_fontname);
deg_debug_printf(ctx, ",fontsize=%f", deg_debug_graphviz_node_label_size);
deg_debug_printf(ctx, ",shape=%s", shape);
@@ -583,7 +590,7 @@ static void deg_debug_graphviz_graph_relations(const DebugContext &ctx, const De
#endif
}
-void DEG_debug_graphviz(const Depsgraph *graph, FILE *f, const char *label, bool show_tags)
+void DEG_debug_graphviz(const Depsgraph *graph, FILE *f, const char *label, bool show_eval)
{
#if 0 /* generate shaded color set */
static char colors[][3] = {{0xa6, 0xce, 0xe3},{0x1f, 0x78, 0xb4},{0xb2, 0xdf, 0x8a},{0x33, 0xa0, 0x2c},
@@ -600,7 +607,8 @@ void DEG_debug_graphviz(const Depsgraph *graph, FILE *f, const char *label, bool
DebugContext ctx;
ctx.file = f;
- ctx.show_tags = show_tags;
+ ctx.show_tags = show_eval;
+ ctx.show_eval_priority = show_eval;
deg_debug_printf(ctx, "digraph depgraph {" NL);
deg_debug_printf(ctx, "rankdir=LR;" NL);
diff --git a/source/blender/depsgraph/intern/depsgraph_eval.cpp b/source/blender/depsgraph/intern/depsgraph_eval.cpp
index 49db9fb..4fb4afb 100644
--- a/source/blender/depsgraph/intern/depsgraph_eval.cpp
+++ b/source/blender/depsgraph/intern/depsgraph_eval.cpp
@@ -65,6 +65,7 @@ extern "C" {
#include "depsgraph_eval.h"
#include "depsgraph_queue.h"
#include "depsgraph_intern.h"
+#include "depsgraph_util_priority_queue.h"
/* *************************************************** */
/* Multi-Threaded Evaluation Internals */
@@ -126,6 +127,35 @@ static void deg_exec_node(Depsgraph *graph, DepsNode *node, eEvaluationContextTy
/* *************************************************** */
/* Evaluation Entrypoints */
+struct CompareOperationNode {
+ bool operator() (OperationDepsNode *a, OperationDepsNode *b)
+ {
+ return a->eval_priority < b->eval_priority;
+ }
+};
+
+typedef priority_queue<OperationDepsNode *, vector<OperationDepsNode *>, CompareOperationNode> EvalQueue;
+
+static void calculate_eval_priority(OperationDepsNode *node)
+{
+ if (node->done)
+ return;
+ node->done = 1;
+
+ if (node->flag & DEPSOP_FLAG_NEEDS_UPDATE) {
+ node->eval_priority = 1.0f;
+
+ for (OperationDepsNode::Relations::const_iterator it = node->outlinks.begin(); it != node->outlinks.end(); ++it) {
+ DepsRelation *rel = *it;
+ calculate_eval_priority(rel->to);
+
+ node->eval_priority += rel->to->eval_priority;
+ }
+ }
+ else
+ node->eval_priority = 0.0f;
+}
+
/* Evaluate all nodes tagged for updating
* ! This is usually done as part of main loop, but may also be
* called from frame-change update
@@ -135,9 +165,22 @@ void DEG_evaluate_on_refresh(Depsgraph *graph, eEvaluationContextType context_ty
/* generate base evaluation context, upon which all the others are derived... */
// TODO: this needs both main and scene access...
+ /* clear tags */
+ for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); it != graph->operations.end(); ++it) {
+ OperationDepsNode *node = *it;
+ node->done = 0;
+ }
+
+ /* calculate values (priority) for operation nodes */
+ for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin(); it != graph->operations.end(); ++it) {
+ OperationDepsNode *node = *it;
+ calculate_eval_priority(node);
+ }
+
+ DEG_debug_eval_step("Eval Priority Calculation");
+
/* from the root node, start queuing up nodes to evaluate */
// ... start scheduler, etc.
-
// ...
/* clear any uncleared tags - just in case */
diff --git a/source/blender/depsgraph/intern/depsnode_operation.cpp b/source/blender/depsgraph/intern/depsnode_operation.cpp
index fd45779..722ecd8 100644
--- a/source/blender/depsgraph/intern/depsnode_operation.cpp
+++ b/source/blender/depsgraph/intern/depsnode_operation.cpp
@@ -44,7 +44,8 @@ extern "C" {
/* ******************************************************** */
/* Inner Nodes */
-OperationDepsNode::OperationDepsNode()
+OperationDepsNode::OperationDepsNode() :
+ eval_priority(0.0f)
{
}
diff --git a/source/blender/depsgraph/intern/depsnode_operation.h b/source/blender/depsgraph/intern/depsnode_operation.h
index 6d27599..fd568a4 100644
--- a/source/blender/depsgraph/intern/depsnode_operation.h
+++ b/source/blender/depsgraph/intern/depsnode_operation.h
@@ -84,6 +84,7 @@ struct OperationDepsNode : public DepsNode {
double last_time; /* (seconds) time in seconds that last evaluation took */
uint32_t num_links_pending; /* how many inlinks are we still waiting on before we can be evaluated... */
+ float eval_priority;
short optype; /* (eDepsOperation_Type) stage of evaluation */
short flag; /* (eDepsOperation_Flag) extra settings affecting evaluation */
diff --git a/source/blender/makesrna/intern/rna_depsgraph.c b/source/blender/makesrna/intern/rna_depsgraph.c
index cc709e0..c3fd37d 100644
--- a/source/blender/makesrna/intern/rna_depsgraph.c
+++ b/source/blender/makesrna/intern/rna_depsgraph.c
@@ -34,9 +34,10 @@
#include "rna_internal.h"
+#include "DEG_depsgraph.h"
+
#ifdef RNA_RUNTIME
-#include "DEG_depsgraph.h"
#include "DEG_depsgraph_debug.h"
@@ -75,7 +76,7 @@ static void rna_Depsgraph_debug_simulate_cb(DepsgraphEvalDebugInfo *info, const
++info->step;
}
-static void rna_Depsgraph_debug_simulate(Depsgraph *graph, const char *filename)
+static void rna_Depsgraph_debug_simulate(Depsgraph *graph, const char *filename, int context_type)
{
DepsgraphEvalDebugInfo debug_info;
debug_info.filename = filename;
@@ -86,6 +87,7 @@ static void rna_Depsgraph_debug_simulate(Depsgraph *graph, const char *filename)
(DEG_DebugEvalCb)rna_Depsgraph_debug_simulate_cb);
DEG_graph_flush_updates(graph);
+ DEG_evaluate_on_refresh(graph, (eEvaluationContextType)context_type);
DEG_debug_eval_end();
}
@@ -98,6 +100,13 @@ static void rna_def_depsgraph(BlenderRNA *brna)
FunctionRNA *func;
PropertyRNA *parm;
+ static EnumPropertyItem context_type_items[] = {
+ {DEG_EVALUATION_CONTEXT_VIEWPORT, "VIEWPORT", 0, "Viewport", "Viewport Display"},
+ {DEG_EVALUATION_CONTEXT_RENDER, "RENDER", 0, "Render", "Render Engine DB Conversion"},
+ {DEG_EVALUATION_CONTEXT_BAKE, "BAKE", 0, "Bake", "Background baking operation"},
+ {0, NULL, 0, NULL, NULL}
+ };
+
srna = RNA_def_struct(brna, "Depsgraph", NULL);
RNA_def_struct_ui_text(srna, "Dependency Graph", "");
@@ -110,6 +119,7 @@ static void rna_def_depsgraph(BlenderRNA *brna)
parm = RNA_def_string_file_path(func, "filename", NULL, FILE_MAX, "File Name",
"File in which to store graphviz debug output");
RNA_def_property_flag(parm, PROP_REQUIRED);
+ parm = RNA_def_enum(func, "context_type", context_type_items, DEG_EVALUATION_CONTEXT_VIEWPORT, "Context Type", "");
}
void RNA_def_depsgraph(BlenderRNA *brna)
More information about the Bf-blender-cvs
mailing list