[Bf-blender-cvs] [aaf5ee7] master: Fix for O(N^2) runtime tagging in the new depsgraph.

[Lukas Tönne]

Commit: aaf5ee73f0d987940aa95e6fb603e2045d2fea2b
Author: Lukas Tönne
Date:   Thu Apr 28 12:00:51 2016 +0200
Branches: master
https://developer.blender.org/rBaaf5ee73f0d987940aa95e6fb603e2045d2fea2b

Fix for O(N^2) runtime tagging in the new depsgraph.

Some of the tagging functions would be called for every operation, and then
in turn tag their ID nodes with all their operations again. With extensive rigs
we get ID nodes with a lot (10,000+) operation nodes, which leads to millions
of unnecessary tagging calls.

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

M	source/blender/depsgraph/intern/depsgraph_build.cc
M	source/blender/depsgraph/intern/depsgraph_tag.cc

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

diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc
index a62b23b..877ce6e 100644
--- a/source/blender/depsgraph/intern/depsgraph_build.cc
+++ b/source/blender/depsgraph/intern/depsgraph_build.cc
@@ -244,17 +244,21 @@ static void deg_graph_build_finalize(Depsgraph *graph)
 					id_node->layers |= id_to->layers;
 				}
 			}
-
-			/* Re-tag ID for update if it was tagged before the relations
-			 * update tag.
-			 */
-			ID *id = id_node->id;
-			if (id->tag & LIB_TAG_ID_RECALC_ALL &&
-			    id->tag & LIB_TAG_DOIT)
-			{
-				id_node->tag_update(graph);
-				id->tag &= ~LIB_TAG_DOIT;
-			}
+		}
+	}
+	
+	/* Re-tag IDs for update if it was tagged before the relations update tag. */
+	for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin();
+	     it != graph->id_hash.end();
+	     ++it)
+	{
+		IDDepsNode *id_node = it->second;
+		ID *id = id_node->id;
+		if (id->tag & LIB_TAG_ID_RECALC_ALL &&
+		    id->tag & LIB_TAG_DOIT)
+		{
+			id_node->tag_update(graph);
+			id->tag &= ~LIB_TAG_DOIT;
 		}
 	}
 }
diff --git a/source/blender/depsgraph/intern/depsgraph_tag.cc b/source/blender/depsgraph/intern/depsgraph_tag.cc
index 486526e..7c660ca 100644
--- a/source/blender/depsgraph/intern/depsgraph_tag.cc
+++ b/source/blender/depsgraph/intern/depsgraph_tag.cc
@@ -436,12 +436,11 @@ void DEG_graph_on_visible_update(Main *bmain, Scene *scene)
 		 * This is mainly needed on file load only, after that updates of invisible objects
 		 * will be stored in the pending list.
 		 */
-		for (Depsgraph::OperationNodes::const_iterator it = graph->operations.begin();
-		     it != graph->operations.end();
+		for (Depsgraph::IDNodeMap::const_iterator it = graph->id_hash.begin();
+		     it != graph->id_hash.end();
 		     ++it)
 		{
-			OperationDepsNode *node = *it;
-			IDDepsNode *id_node = node->owner->owner;
+			IDDepsNode *id_node = it->second;
 			ID *id = id_node->id;
 			if ((id->tag & LIB_TAG_ID_RECALC_ALL) != 0 ||
 			    (id_node->layers & scene->lay_updated) == 0)