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.

2 files changed, 18 insertions, 15 deletions

diff --git a/source/blender/depsgraph/intern/depsgraph_build.cc b/source/blender/depsgraph/intern/depsgraph_build.cc
index a62b23bde68..877ce6e52e9 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 486526ed46c..7c660caa2f9 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)