From 15692c8cfe5aac896227cfd4594e0a6f84df01b0 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 30 May 2017 11:09:44 +0200 Subject: Move hash_combine utility function to a more generic place This way everyone can benefit from it, not only dependency graph. --- source/blender/depsgraph/intern/nodes/deg_node.cc | 5 ++--- source/blender/depsgraph/intern/nodes/deg_node_component.cc | 6 +++--- source/blender/depsgraph/intern/nodes/deg_node_operation.cc | 4 +--- 3 files changed, 6 insertions(+), 9 deletions(-) (limited to 'source/blender/depsgraph/intern') diff --git a/source/blender/depsgraph/intern/nodes/deg_node.cc b/source/blender/depsgraph/intern/nodes/deg_node.cc index 57b25c10670..b1d5b538e25 100644 --- a/source/blender/depsgraph/intern/nodes/deg_node.cc +++ b/source/blender/depsgraph/intern/nodes/deg_node.cc @@ -49,7 +49,6 @@ extern "C" { #include "intern/nodes/deg_node_operation.h" #include "intern/depsgraph_intern.h" #include "util/deg_util_foreach.h" -#include "util/deg_util_hash.h" namespace DEG { @@ -158,8 +157,8 @@ static unsigned int id_deps_node_hash_key(const void *key_v) { const IDDepsNode::ComponentIDKey *key = reinterpret_cast(key_v); - return hash_combine(BLI_ghashutil_uinthash(key->type), - BLI_ghashutil_strhash_p(key->name)); + return BLI_ghashutil_combine_hash(BLI_ghashutil_uinthash(key->type), + BLI_ghashutil_strhash_p(key->name)); } static bool id_deps_node_hash_key_cmp(const void *a, const void *b) diff --git a/source/blender/depsgraph/intern/nodes/deg_node_component.cc b/source/blender/depsgraph/intern/nodes/deg_node_component.cc index 06f91ac7fdc..136c66b9516 100644 --- a/source/blender/depsgraph/intern/nodes/deg_node_component.cc +++ b/source/blender/depsgraph/intern/nodes/deg_node_component.cc @@ -35,6 +35,7 @@ extern "C" { #include "BLI_utildefines.h" +#include "BLI_ghash.h" #include "DNA_object_types.h" @@ -44,7 +45,6 @@ extern "C" { #include "intern/nodes/deg_node_operation.h" #include "intern/depsgraph_intern.h" #include "util/deg_util_foreach.h" -#include "util/deg_util_hash.h" namespace DEG { @@ -95,8 +95,8 @@ static unsigned int comp_node_hash_key(const void *key_v) { const ComponentDepsNode::OperationIDKey *key = reinterpret_cast(key_v); - return hash_combine(BLI_ghashutil_uinthash(key->opcode), - BLI_ghashutil_strhash_p(key->name)); + return BLI_ghashutil_combine_hash(BLI_ghashutil_uinthash(key->opcode), + BLI_ghashutil_strhash_p(key->name)); } static bool comp_node_hash_key_cmp(const void *a, const void *b) diff --git a/source/blender/depsgraph/intern/nodes/deg_node_operation.cc b/source/blender/depsgraph/intern/nodes/deg_node_operation.cc index 9eed4dfe8d8..cbf397bc7a9 100644 --- a/source/blender/depsgraph/intern/nodes/deg_node_operation.cc +++ b/source/blender/depsgraph/intern/nodes/deg_node_operation.cc @@ -32,13 +32,11 @@ #include "MEM_guardedalloc.h" -extern "C" { #include "BLI_utildefines.h" -} /* extern "C" */ +#include "BLI_ghash.h" #include "intern/depsgraph.h" #include "intern/depsgraph_intern.h" -#include "util/deg_util_hash.h" namespace DEG { -- cgit v1.2.3 From 31bc9beeac9f7d2d5a272e77fa0e0ec5c22d7291 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 30 May 2017 11:22:54 +0200 Subject: Depsgraph: Use own implementation of stack rather than the one from STL This way we always have predictable behavior, especially from the performance point of view. Additionally, if some bottleneck is found in stack implementation it'll be easier for us to address. --- .../depsgraph/intern/builder/deg_builder.cc | 21 +++++++------ .../depsgraph/intern/builder/deg_builder_cycle.cc | 36 ++++++++++++---------- 2 files changed, 32 insertions(+), 25 deletions(-) (limited to 'source/blender/depsgraph/intern') diff --git a/source/blender/depsgraph/intern/builder/deg_builder.cc b/source/blender/depsgraph/intern/builder/deg_builder.cc index 7f62eb122db..143f9908db8 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder.cc @@ -30,9 +30,6 @@ #include "intern/builder/deg_builder.h" -// TODO(sergey): Use own wrapper over STD. -#include - #include "DNA_anim_types.h" #include "DNA_object_types.h" #include "DNA_ID.h" @@ -40,6 +37,10 @@ #include "BLI_utildefines.h" #include "BLI_ghash.h" +extern "C" { +#include "BLI_stack.h" +} + #include "intern/depsgraph.h" #include "intern/depsgraph_types.h" #include "intern/nodes/deg_node.h" @@ -71,7 +72,8 @@ static bool check_object_needs_evaluation(Object *object) void deg_graph_build_flush_layers(Depsgraph *graph) { - std::stack stack; + BLI_Stack *stack = BLI_stack_new(sizeof(OperationDepsNode*), + "DEG flush layers stack"); foreach (OperationDepsNode *node, graph->operations) { IDDepsNode *id_node = node->owner->owner; node->done = 0; @@ -84,15 +86,15 @@ void deg_graph_build_flush_layers(Depsgraph *graph) } } if (node->num_links_pending == 0) { - stack.push(node); + BLI_stack_push(stack, &node); node->done = 1; } node->owner->layers = id_node->layers; id_node->id->tag |= LIB_TAG_DOIT; } - while (!stack.empty()) { - OperationDepsNode *node = stack.top(); - stack.pop(); + while (!BLI_stack_is_empty(stack)) { + OperationDepsNode *node; + BLI_stack_pop(stack, &node); /* Flush layers to parents. */ foreach (DepsRelation *rel, node->inlinks) { if (rel->from->type == DEPSNODE_TYPE_OPERATION) { @@ -109,12 +111,13 @@ void deg_graph_build_flush_layers(Depsgraph *graph) --from->num_links_pending; } if (from->num_links_pending == 0 && from->done == 0) { - stack.push(from); + BLI_stack_push(stack, &from); from->done = 1; } } } } + BLI_stack_free(stack); } void deg_graph_build_finalize(Depsgraph *graph) diff --git a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc index 9b37aaa12ff..1420b5fc8a5 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc @@ -32,10 +32,10 @@ // TOO(sergey): Use some wrappers over those? #include #include -#include extern "C" { #include "BLI_utildefines.h" +#include "BLI_stack.h" } #include "util/deg_util_foreach.h" @@ -48,12 +48,6 @@ extern "C" { namespace DEG { -struct StackEntry { - OperationDepsNode *node; - StackEntry *from; - DepsRelation *via_relation; -}; - void deg_graph_detect_cycles(Depsgraph *graph) { enum { @@ -65,7 +59,15 @@ void deg_graph_detect_cycles(Depsgraph *graph) NODE_IN_STACK = 2, }; - std::stack traversal_stack; + struct StackEntry { + OperationDepsNode *node; + StackEntry *from; + DepsRelation *via_relation; + }; + + BLI_Stack *traversal_stack = BLI_stack_new(sizeof(StackEntry), + "DEG detect cycles stack"); + foreach (OperationDepsNode *node, graph->operations) { bool has_inlinks = false; foreach (DepsRelation *rel, node->inlinks) { @@ -78,7 +80,7 @@ void deg_graph_detect_cycles(Depsgraph *graph) entry.node = node; entry.from = NULL; entry.via_relation = NULL; - traversal_stack.push(entry); + BLI_stack_push(traversal_stack, &entry); node->tag = NODE_IN_STACK; } else { @@ -87,9 +89,9 @@ void deg_graph_detect_cycles(Depsgraph *graph) node->done = 0; } - while (!traversal_stack.empty()) { - StackEntry& entry = traversal_stack.top(); - OperationDepsNode *node = entry.node; + while (!BLI_stack_is_empty(traversal_stack)) { + StackEntry *entry = (StackEntry *)BLI_stack_peek(traversal_stack); + OperationDepsNode *node = entry->node; bool all_child_traversed = true; for (int i = node->done; i < node->outlinks.size(); ++i) { DepsRelation *rel = node->outlinks[i]; @@ -102,7 +104,7 @@ void deg_graph_detect_cycles(Depsgraph *graph) node->full_identifier().c_str(), rel->name); - StackEntry *current = &entry; + StackEntry *current = entry; while (current->node != to) { BLI_assert(current != NULL); printf(" '%s' depends on '%s' through '%s'\n", @@ -117,9 +119,9 @@ void deg_graph_detect_cycles(Depsgraph *graph) else if (to->tag == NODE_NOT_VISITED) { StackEntry new_entry; new_entry.node = to; - new_entry.from = &entry; + new_entry.from = entry; new_entry.via_relation = rel; - traversal_stack.push(new_entry); + BLI_stack_push(traversal_stack, &new_entry); to->tag = NODE_IN_STACK; all_child_traversed = false; node->done = i; @@ -129,9 +131,11 @@ void deg_graph_detect_cycles(Depsgraph *graph) } if (all_child_traversed) { node->tag = NODE_VISITED; - traversal_stack.pop(); + BLI_stack_discard(traversal_stack); } } + + BLI_stack_free(traversal_stack); } } // namespace DEG -- cgit v1.2.3 From 71dcead79098bbe0e5a9570e3fe28b5aa2da4b17 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 30 May 2017 12:21:19 +0200 Subject: Move GHash/GSet/LinkList iterators to BLI files Those are not depsgraph or C++ specific and can be used by everyone. --- source/blender/depsgraph/intern/depsgraph_tag.cc | 1 + 1 file changed, 1 insertion(+) (limited to 'source/blender/depsgraph/intern') diff --git a/source/blender/depsgraph/intern/depsgraph_tag.cc b/source/blender/depsgraph/intern/depsgraph_tag.cc index e74972a688b..8c4c0b8c8a5 100644 --- a/source/blender/depsgraph/intern/depsgraph_tag.cc +++ b/source/blender/depsgraph/intern/depsgraph_tag.cc @@ -43,6 +43,7 @@ extern "C" { #include "DNA_windowmanager_types.h" #include "BLI_task.h" +#include "BLI_listbase.h" #include "BKE_idcode.h" #include "BKE_library.h" -- cgit v1.2.3 From 34cb93434354b29425d6998e57e3bea9b2d4b730 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 30 May 2017 14:34:42 +0200 Subject: Depsgraph: Fix object being tagged for data update when it shouldn't --- .../depsgraph/intern/eval/deg_eval_flush.cc | 34 +++++++++++++++++----- 1 file changed, 26 insertions(+), 8 deletions(-) (limited to 'source/blender/depsgraph/intern') diff --git a/source/blender/depsgraph/intern/eval/deg_eval_flush.cc b/source/blender/depsgraph/intern/eval/deg_eval_flush.cc index e10f86f6e95..d64fdd83d39 100644 --- a/source/blender/depsgraph/intern/eval/deg_eval_flush.cc +++ b/source/blender/depsgraph/intern/eval/deg_eval_flush.cc @@ -164,14 +164,32 @@ void deg_graph_flush_updates(Main *bmain, Depsgraph *graph) * Plus it ensures visibility changes and relations and * layers visibility update has proper flags to work with. */ - if (comp_node->type == DEPSNODE_TYPE_ANIMATION) { - object->recalc |= OB_RECALC_TIME; - } - else if (comp_node->type == DEPSNODE_TYPE_TRANSFORM) { - object->recalc |= OB_RECALC_OB; - } - else { - object->recalc |= OB_RECALC_DATA; + switch (comp_node->type) { + case DEPSNODE_TYPE_UNDEFINED: + case DEPSNODE_TYPE_OPERATION: + case DEPSNODE_TYPE_ROOT: + case DEPSNODE_TYPE_TIMESOURCE: + case DEPSNODE_TYPE_ID_REF: + case DEPSNODE_TYPE_SUBGRAPH: + case DEPSNODE_TYPE_PARAMETERS: + case DEPSNODE_TYPE_SEQUENCER: + /* Ignore, does not translate to object component. */ + break; + case DEPSNODE_TYPE_ANIMATION: + object->recalc |= OB_RECALC_TIME; + break; + case DEPSNODE_TYPE_TRANSFORM: + object->recalc |= OB_RECALC_OB; + break; + case DEPSNODE_TYPE_GEOMETRY: + case DEPSNODE_TYPE_EVAL_POSE: + case DEPSNODE_TYPE_BONE: + case DEPSNODE_TYPE_EVAL_PARTICLES: + case DEPSNODE_TYPE_SHADING: + case DEPSNODE_TYPE_CACHE: + case DEPSNODE_TYPE_PROXY: + object->recalc |= OB_RECALC_DATA; + break; } } } -- cgit v1.2.3 From f92fc950c22edaba860ef8bf09a5692d284bf167 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 30 May 2017 17:38:22 +0200 Subject: Depsgraph: Remove extra modifiers callback loop Seems to be a copy-paste error from code above. --- source/blender/depsgraph/intern/builder/deg_builder_nodes.cc | 1 - 1 file changed, 1 deletion(-) (limited to 'source/blender/depsgraph/intern') diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc index fa47b4dfb19..49ebdc8b8ac 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc @@ -427,7 +427,6 @@ void DepsgraphNodeBuilder::build_object(Scene *scene, Base *base, Object *ob) BuilderWalkUserData data; data.builder = this; data.scene = scene; - modifiers_foreachObjectLink(ob, modifier_walk, &data); BKE_constraints_id_loop(&ob->constraints, constraint_walk, &data); } -- cgit v1.2.3 From d1d359b792fd30a109d8fe70444b8645c8f3998f Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Tue, 30 May 2017 17:42:04 +0200 Subject: Depsgraph: Fix missing relations for objects which are indirectly linked This is a corresponding part of 7dda3cf. --- .../intern/builder/deg_builder_relations.cc | 50 ++++++++++++++++++++++ 1 file changed, 50 insertions(+) (limited to 'source/blender/depsgraph/intern') diff --git a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc index ce238de4be9..df56ff5897c 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc @@ -113,6 +113,41 @@ extern "C" { namespace DEG { +namespace { + +struct BuilderWalkUserData { + DepsgraphRelationBuilder *builder; + Main *bmain; + Scene *scene; +}; + +static void modifier_walk(void *user_data, + struct Object * /*ob*/, + struct Object **obpoin, + int /*cb_flag*/) +{ + BuilderWalkUserData *data = (BuilderWalkUserData *)user_data; + if (*obpoin) { + data->builder->build_object(data->bmain, data->scene, *obpoin); + } +} + +void constraint_walk(bConstraint * /*con*/, + ID **idpoin, + bool /*is_reference*/, + void *user_data) +{ + BuilderWalkUserData *data = (BuilderWalkUserData *)user_data; + if (*idpoin) { + ID *id = *idpoin; + if (GS(id->name) == ID_OB) { + data->builder->build_object(data->bmain, data->scene, (Object *)id); + } + } +} + +} /* namespace */ + /* ***************** */ /* Relations Builder */ @@ -407,6 +442,21 @@ void DepsgraphRelationBuilder::build_object(Main *bmain, Scene *scene, Object *o "[ObLocal -> ObParent]"); } + if (ob->modifiers.first != NULL) { + BuilderWalkUserData data; + data.builder = this; + data.bmain = bmain; + data.scene = scene; + modifiers_foreachObjectLink(ob, modifier_walk, &data); + } + if (ob->constraints.first != NULL) { + BuilderWalkUserData data; + data.builder = this; + data.bmain = bmain; + data.scene = scene; + BKE_constraints_id_loop(&ob->constraints, constraint_walk, &data); + } + /* object constraints */ if (ob->constraints.first != NULL) { OperationKey constraint_key(&ob->id, -- cgit v1.2.3 From a481908232ef20449e6ad6951769677e0b108ca8 Mon Sep 17 00:00:00 2001 From: Sergey Sharybin Date: Wed, 31 May 2017 15:24:09 +0200 Subject: Task scheduler: Optimize subsequent pushing bunch of tasks The idea is to accumulate all new tasks in a thread local queue first without doing any thread synchronization (aka, locks and conditional variables) and move those tasks to a scheduler queue once they are all ready. This way we avoid per-task-pool lock and only have one lock per bunch of tasks. This is particularly handy when scheduling new dependency graph node children. Brings FPS of cached simulation from the linked below file from ~30 to ~50. See documentation for BLI_task_pool_delayed_push_{begin, end} and for TaskThreadLocalStorage::do_delayed_push. Fixes T50027: Rigidbody playback and simulation performance regression with new depsgraph Thanks Bastien for the review! --- source/blender/depsgraph/intern/eval/deg_eval.cc | 2 ++ 1 file changed, 2 insertions(+) (limited to 'source/blender/depsgraph/intern') diff --git a/source/blender/depsgraph/intern/eval/deg_eval.cc b/source/blender/depsgraph/intern/eval/deg_eval.cc index e739bc9dbb5..54947ddbb5e 100644 --- a/source/blender/depsgraph/intern/eval/deg_eval.cc +++ b/source/blender/depsgraph/intern/eval/deg_eval.cc @@ -126,7 +126,9 @@ static void deg_task_run_func(TaskPool *pool, #endif } + BLI_task_pool_delayed_push_begin(pool, thread_id); schedule_children(pool, state->graph, node, state->layers, thread_id); + BLI_task_pool_delayed_push_end(pool, thread_id); } typedef struct CalculatePengindData { -- cgit v1.2.3