blender
/
blender
136
406
Fork 590
Code Issues 6.2k Pull Requests 760 Projects 19 Wiki Activity

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
This commit is contained in:
Brecht Van Lommel 2020-04-23 15:05:06 +02:00
parent 694c0547c2
commit 869472b3f0
Notes: blender-bot 2023-02-14 08:58:01 +01:00 
Referenced by issue #75611, Operating on large number of cubes takes a long time compared to 2.79
1 changed files with 43 additions and 44 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

87
source/blender/depsgraph/intern/depsgraph_query_foreach.cc
View File

@ -23,6 +23,8 @@
* Implementation of Querying and Filtering API's
*/
#include <unordered_set>
#include "MEM_guardedalloc.h"
extern "C" {
@ -48,24 +50,12 @@ extern "C" {
namespace DEG {
namespace {
using std::unordered_set;
typedef deque<OperationNode *> 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<OperationNode *> 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<ComponentNode *> visited;
};
void deg_foreach_dependent_component_callback(OperationNode *op_node, void *user_data_v)
{
ForeachIDComponentData *user_data = reinterpret_cast<ForeachIDComponentData *>(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<IDNode *> 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<ForeachIDData *>(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<OperationNode *> 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<IDNode *> 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);
}
}
}