Despgraph: Optimize cycles detection algorithm

The idea is simple: when falling back to one of the nodes which was partially
handled we "resume" checking outgoing relations from the index which we stopped.

This gives about 15-20% depsgraph construction time save.

1 files changed, 20 insertions, 15 deletions

diff --git a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
index 225cc64ae4d..d84a590b29f 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
@@ -56,12 +56,14 @@ struct StackEntry {
 
 void deg_graph_detect_cycles(Depsgraph *graph)
 {
-	/* Not is not visited at all during traversal. */
-	const int NODE_NOT_VISITED = 0;
-	/* Node has been visited during traversal and not in current stack. */
-	const int NODE_VISITED = 1;
-	/* Node has been visited during traversal and is in current stack. */
-	const int NODE_IN_STACK = 2;
+	enum {
+		/* Not is not visited at all during traversal. */
+		NODE_NOT_VISITED = 0,
+		/* Node has been visited during traversal and not in current stack. */
+		NODE_VISITED = 1,
+		/* Node has been visited during traversal and is in current stack. */
+		NODE_IN_STACK = 2,
+	};
 
 	std::stack<StackEntry> traversal_stack;
 	foreach (OperationDepsNode *node, graph->operations) {
@@ -77,21 +79,23 @@ void deg_graph_detect_cycles(Depsgraph *graph)
 			entry.from = NULL;
 			entry.via_relation = NULL;
 			traversal_stack.push(entry);
-			node->done = NODE_IN_STACK;
+			node->tag = NODE_IN_STACK;
 		}
 		else {
-			node->done = NODE_NOT_VISITED;
+			node->tag = NODE_NOT_VISITED;
 		}
+		node->done = 0;
 	}
 
 	while (!traversal_stack.empty()) {
-		StackEntry &entry = traversal_stack.top();
+		StackEntry entry = traversal_stack.top();
 		OperationDepsNode *node = entry.node;
 		bool all_child_traversed = true;
-		foreach (DepsRelation *rel, node->outlinks) {
+		for (int i = node->done; i < node->outlinks.size(); ++i) {
+			DepsRelation *rel = node->outlinks[i];
 			if (rel->to->type == DEPSNODE_TYPE_OPERATION) {
 				OperationDepsNode *to = (OperationDepsNode *)rel->to;
-				if (to->done == NODE_IN_STACK) {
+				if (to->tag == NODE_IN_STACK) {
 					printf("Dependency cycle detected:\n");
 					printf("  '%s' depends on '%s' through '%s'\n",
 					       to->full_identifier().c_str(),
@@ -107,23 +111,24 @@ void deg_graph_detect_cycles(Depsgraph *graph)
 						       current->via_relation->name);
 						current = current->from;
 					}
-					/* TODO(sergey): So called roussian rlette cycle solver. */
+					/* TODO(sergey): So called russian roulette cycle solver. */
 					rel->flag |= DEPSREL_FLAG_CYCLIC;
 				}
-				else if (to->done == NODE_NOT_VISITED) {
+				else if (to->tag == NODE_NOT_VISITED) {
 					StackEntry new_entry;
 					new_entry.node = to;
 					new_entry.from = &entry;
 					new_entry.via_relation = rel;
 					traversal_stack.push(new_entry);
-					to->done = NODE_IN_STACK;
+					to->tag = NODE_IN_STACK;
 					all_child_traversed = false;
+					node->done = i;
 					break;
 				}
 			}
 		}
 		if (all_child_traversed) {
-			node->done = NODE_VISITED;
+			node->tag = NODE_VISITED;
 			traversal_stack.pop();
 		}
 	}