From 869472b3f0eb08d5db474c59f380752ad7f69200 Mon Sep 17 00:00:00 2001 From: Brecht Van Lommel Date: Thu, 23 Apr 2020 15:05:06 +0200 Subject: Fix T75611: slow transform of many objects at the same time Solve O(n^2) time complexity problem where a dependency graph iterator loops over all nodes to clear flags, which happened for every object at the start of transform. Differential Revision: https://developer.blender.org/D7503 --- .../depsgraph/intern/depsgraph_query_foreach.cc | 87 +++++++++++----------- 1 file changed, 43 insertions(+), 44 deletions(-) (limited to 'source/blender/depsgraph/intern') diff --git a/source/blender/depsgraph/intern/depsgraph_query_foreach.cc b/source/blender/depsgraph/intern/depsgraph_query_foreach.cc index 6409f5b3cea..4882897ad8d 100644 --- a/source/blender/depsgraph/intern/depsgraph_query_foreach.cc +++ b/source/blender/depsgraph/intern/depsgraph_query_foreach.cc @@ -23,6 +23,8 @@ * Implementation of Querying and Filtering API's */ +#include + #include "MEM_guardedalloc.h" extern "C" { @@ -48,24 +50,12 @@ extern "C" { namespace DEG { namespace { +using std::unordered_set; + typedef deque TraversalQueue; -enum { - DEG_NODE_VISITED = (1 << 0), -}; typedef void (*DEGForeachOperation)(OperationNode *op_node, void *user_data); -void deg_foreach_clear_flags(const Depsgraph *graph) -{ - for (OperationNode *op_node : graph->operations) { - op_node->scheduled = false; - op_node->owner->custom_flags = 0; - } - for (IDNode *id_node : graph->id_nodes) { - id_node->custom_flags = 0; - } -} - bool deg_foreach_needs_visit(const OperationNode *op_node, const int flags) { if (flags & DEG_FOREACH_COMPONENT_IGNORE_TRANSFORM_SOLVERS) { @@ -77,23 +67,20 @@ bool deg_foreach_needs_visit(const OperationNode *op_node, const int flags) } void deg_foreach_dependent_operation(const Depsgraph *graph, - const ID *id, + const IDNode *target_id_node, eDepsObjectComponentType source_component_type, int flags, DEGForeachOperation callback, void *user_data) { - /* Start with getting ID node from the graph. */ - IDNode *target_id_node = graph->find_id_node(id); if (target_id_node == nullptr) { /* TODO(sergey): Shall we inform or assert here about attempt to start * iterating over non-existing ID? */ return; } - /* Make sure all runtime flags are ready and clear. */ - deg_foreach_clear_flags(graph); /* Start with scheduling all operations from ID node. */ TraversalQueue queue; + unordered_set scheduled; GHASH_FOREACH_BEGIN (ComponentNode *, comp_node, target_id_node->components) { if (source_component_type != DEG_OB_COMP_ANY && nodeTypeToObjectComponent(comp_node->type) != source_component_type) { @@ -104,12 +91,10 @@ void deg_foreach_dependent_operation(const Depsgraph *graph, continue; } queue.push_back(op_node); - op_node->scheduled = true; - op_node->owner->custom_flags |= DEG_NODE_VISITED; + scheduled.insert(op_node); } } GHASH_FOREACH_END(); - target_id_node->custom_flags |= DEG_NODE_VISITED; /* Process the queue. */ while (!queue.empty()) { /* get next operation node to process. */ @@ -120,8 +105,9 @@ void deg_foreach_dependent_operation(const Depsgraph *graph, /* Schedule outgoing operation nodes. */ if (op_node->outlinks.size() == 1) { OperationNode *to_node = (OperationNode *)op_node->outlinks[0]->to; - if (to_node->scheduled == false && deg_foreach_needs_visit(to_node, flags)) { - to_node->scheduled = true; + if (scheduled.find(to_node) == scheduled.end() && + deg_foreach_needs_visit(to_node, flags)) { + scheduled.insert(to_node); op_node = to_node; } else { @@ -131,9 +117,10 @@ void deg_foreach_dependent_operation(const Depsgraph *graph, else { for (Relation *rel : op_node->outlinks) { OperationNode *to_node = (OperationNode *)rel->to; - if (to_node->scheduled == false && deg_foreach_needs_visit(to_node, flags)) { + if (scheduled.find(to_node) == scheduled.end() && + deg_foreach_needs_visit(to_node, flags)) { queue.push_front(to_node); - to_node->scheduled = true; + scheduled.insert(to_node); } } break; @@ -145,17 +132,20 @@ void deg_foreach_dependent_operation(const Depsgraph *graph, struct ForeachIDComponentData { DEGForeachIDComponentCallback callback; void *user_data; + IDNode *target_id_node; + unordered_set visited; }; void deg_foreach_dependent_component_callback(OperationNode *op_node, void *user_data_v) { ForeachIDComponentData *user_data = reinterpret_cast(user_data_v); ComponentNode *comp_node = op_node->owner; - if ((comp_node->custom_flags & DEG_NODE_VISITED) == 0) { - IDNode *id_node = comp_node->owner; + IDNode *id_node = comp_node->owner; + if (id_node != user_data->target_id_node && + user_data->visited.find(comp_node) == user_data->visited.end()) { user_data->callback( id_node->id_orig, nodeTypeToObjectComponent(comp_node->type), user_data->user_data); - comp_node->custom_flags |= DEG_NODE_VISITED; + user_data->visited.insert(comp_node); } } @@ -169,13 +159,20 @@ void deg_foreach_dependent_ID_component(const Depsgraph *graph, ForeachIDComponentData data; data.callback = callback; data.user_data = user_data; - deg_foreach_dependent_operation( - graph, id, source_component_type, flags, deg_foreach_dependent_component_callback, &data); + data.target_id_node = graph->find_id_node(id); + deg_foreach_dependent_operation(graph, + data.target_id_node, + source_component_type, + flags, + deg_foreach_dependent_component_callback, + &data); } struct ForeachIDData { DEGForeachIDCallback callback; void *user_data; + IDNode *target_id_node; + unordered_set visited; }; void deg_foreach_dependent_ID_callback(OperationNode *op_node, void *user_data_v) @@ -183,9 +180,10 @@ void deg_foreach_dependent_ID_callback(OperationNode *op_node, void *user_data_v ForeachIDData *user_data = reinterpret_cast(user_data_v); ComponentNode *comp_node = op_node->owner; IDNode *id_node = comp_node->owner; - if ((id_node->custom_flags & DEG_NODE_VISITED) == 0) { + if (id_node != user_data->target_id_node && + user_data->visited.find(id_node) == user_data->visited.end()) { user_data->callback(id_node->id_orig, user_data->user_data); - id_node->custom_flags |= DEG_NODE_VISITED; + user_data->visited.insert(id_node); } } @@ -197,8 +195,9 @@ void deg_foreach_dependent_ID(const Depsgraph *graph, ForeachIDData data; data.callback = callback; data.user_data = user_data; + data.target_id_node = graph->find_id_node(id); deg_foreach_dependent_operation( - graph, id, DEG_OB_COMP_ANY, 0, deg_foreach_dependent_ID_callback, &data); + graph, data.target_id_node, DEG_OB_COMP_ANY, 0, deg_foreach_dependent_ID_callback, &data); } void deg_foreach_ancestor_ID(const Depsgraph *graph, @@ -213,18 +212,18 @@ void deg_foreach_ancestor_ID(const Depsgraph *graph, * iterating over non-existing ID? */ return; } - /* Make sure all runtime flags are ready and clear. */ - deg_foreach_clear_flags(graph); /* Start with scheduling all operations from ID node. */ TraversalQueue queue; + unordered_set scheduled; GHASH_FOREACH_BEGIN (ComponentNode *, comp_node, target_id_node->components) { for (OperationNode *op_node : comp_node->operations) { queue.push_back(op_node); - op_node->scheduled = true; + scheduled.insert(op_node); } } GHASH_FOREACH_END(); - target_id_node->custom_flags |= DEG_NODE_VISITED; + unordered_set visited; + visited.insert(target_id_node); /* Process the queue. */ while (!queue.empty()) { /* get next operation node to process. */ @@ -234,18 +233,18 @@ void deg_foreach_ancestor_ID(const Depsgraph *graph, /* Check whether we need to inform callee about corresponding ID node. */ ComponentNode *comp_node = op_node->owner; IDNode *id_node = comp_node->owner; - if ((id_node->custom_flags & DEG_NODE_VISITED) == 0) { + if (visited.find(id_node) == visited.end()) { /* TODO(sergey): Is it orig or CoW? */ callback(id_node->id_orig, user_data); - id_node->custom_flags |= DEG_NODE_VISITED; + visited.insert(id_node); } /* Schedule incoming operation nodes. */ if (op_node->inlinks.size() == 1) { Node *from = op_node->inlinks[0]->from; if (from->get_class() == NodeClass::OPERATION) { OperationNode *from_node = (OperationNode *)from; - if (from_node->scheduled == false) { - from_node->scheduled = true; + if (scheduled.find(from_node) == scheduled.end()) { + scheduled.insert(from_node); op_node = from_node; } else { @@ -258,9 +257,9 @@ void deg_foreach_ancestor_ID(const Depsgraph *graph, Node *from = rel->from; if (from->get_class() == NodeClass::OPERATION) { OperationNode *from_node = (OperationNode *)from; - if (from_node->scheduled == false) { + if (scheduled.find(from_node) == scheduled.end()) { queue.push_front(from_node); - from_node->scheduled = true; + scheduled.insert(from_node); } } } -- cgit v1.2.3