[Bf-blender-cvs] [21350b7] master: Despgraph: Optimize cycles detection algorithm

[Sergey Sharybin]

Commit: 21350b73df0ebd78accf3567269e77d6dc774557
Author: Sergey Sharybin
Date:   Fri Nov 4 17:45:14 2016 +0100
Branches: master
https://developer.blender.org/rB21350b73df0ebd78accf3567269e77d6dc774557

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.

===================================================================

M	source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
M	source/blender/depsgraph/intern/depsgraph_build.cc
M	source/blender/depsgraph/intern/nodes/deg_node.h

===================================================================

diff --git a/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc b/source/blender/depsgraph/intern/builder/deg_builder_cycle.cc
index 225cc64..d84a590 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();
 		}
 	}
diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc
index 7b3922a..e21dac8 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cc
+++ b/source/blender/depsgraph/intern/depsgraph_build.cc
@@ -32,7 +32,7 @@
 
 #include "MEM_guardedalloc.h"
 
-// #define DEBUG_TIME
+#define DEBUG_TIME
 
 extern "C" {
 #include "DNA_cachefile_types.h"
diff --git a/source/blender/depsgraph/intern/nodes/deg_node.h b/source/blender/depsgraph/intern/nodes/deg_node.h
index 810c6ee..7c2f538 100644
--- a/source/blender/depsgraph/intern/nodes/deg_node.h
+++ b/source/blender/depsgraph/intern/nodes/deg_node.h
@@ -80,8 +80,9 @@ struct DepsNode {
 	/* Nodes which depend on this one. */
 	Relations outlinks;
 
-	/* Generic tag for traversal algorithms */
+	/* Generic tags for traversal algorithms. */
 	int done;
+	int tag;
 
 	/* Methods. */