Depsgraph: Store node input/output links in a vector rather than in set

Set is much slower to iterate through (due to cache misses and such) and
the only advantage of using set is faster removal of link. However, we are
iterating links much much more often than removing them, and even when we
are removing links we don't really need to remove link from nodes which it
connects -- we don't support partial depsgraph updates, so removing links
from nodes on destruction is a waste of time.

If we ever want to support partial updates we can have dedicated function
to remove link from nodes it connects.

This gives a surprising increase of fps from 42 to 56 with test file from
Mr. J.P.Bouza (blenrig_for_debugging.blend). Surprising because old DEG is
actually slower here (52 fps). Didn't see any regressions (and don't see
why they will happen), so let's ask our riggers and animators to perform
further speed tests ;)

4 files changed, 23 insertions, 22 deletions

diff --git a/source/blender/depsgraph/intern/depsgraph.cc b/source/blender/depsgraph/intern/depsgraph.cc
index 18c7c5bd8e1..d293d03f63d 100644
--- a/source/blender/depsgraph/intern/depsgraph.cc
+++ b/source/blender/depsgraph/intern/depsgraph.cc
@@ -413,18 +413,28 @@ DepsRelation::DepsRelation(DepsNode *from,
 */
 #endif
 
-	/* Hook it up to the nodes which use it. */
-	from->outlinks.insert(this);
-	to->inlinks.insert(this);
+	/* Hook it up to the nodes which use it.
+	 *
+	 * NOTE: We register relation in the nodes which this link connects to here
+	 * in constructor but we don't unregister it in the destructor.
+	 *
+	 * Reasoning:
+	 *
+	 * - Destructor is currently used on global graph destruction, so there's no
+	 *   real need in avoiding dangling pointers, all the memory is to be freed
+	 *   anyway.
+	 *
+	 * - Unregistering relation is not a cheap operation, so better to have it
+	 *   as an explicit call if we need this.
+	 */
+	from->outlinks.push_back(this);
+	to->inlinks.push_back(this);
 }
 
 DepsRelation::~DepsRelation()
 {
 	/* Sanity check. */
 	BLI_assert(this->from && this->to);
-	/* Remove it from the nodes that use it. */
-	this->from->outlinks.erase(this);
-	this->to->inlinks.erase(this);
 }
 
 /* Low level tagging -------------------------------------- */
diff --git a/source/blender/depsgraph/intern/depsgraph_eval.cc b/source/blender/depsgraph/intern/depsgraph_eval.cc
index 15c8b1a9dd3..febea7d993d 100644
--- a/source/blender/depsgraph/intern/depsgraph_eval.cc
+++ b/source/blender/depsgraph/intern/depsgraph_eval.cc
@@ -281,21 +281,17 @@ static void schedule_children(TaskPool *pool,
                               OperationDepsNode *node,
                               const int layers)
 {
-	for (OperationDepsNode::Relations::const_iterator it = node->outlinks.begin();
-	     it != node->outlinks.end();
-	     ++it)
+	DEPSNODE_RELATIONS_ITER_BEGIN(node->outlinks, rel)
 	{
-		DepsRelation *rel = *it;
 		OperationDepsNode *child = (OperationDepsNode *)rel->to;
 		BLI_assert(child->type == DEPSNODE_TYPE_OPERATION);
-
 		if (child->scheduled) {
 			/* Happens when having cyclic dependencies. */
 			continue;
 		}
-
 		schedule_node(pool, graph, layers, child, (rel->flag & DEPSREL_FLAG_CYCLIC) == 0);
 	}
+	DEPSNODE_RELATIONS_ITER_END;
 }
 
 /**
diff --git a/source/blender/depsgraph/intern/depsnode.cc b/source/blender/depsgraph/intern/depsnode.cc
index 7d4d6890c83..8aa1059d2dc 100644
--- a/source/blender/depsgraph/intern/depsnode.cc
+++ b/source/blender/depsgraph/intern/depsnode.cc
@@ -71,21 +71,16 @@ DepsNode::DepsNode()
 
 DepsNode::~DepsNode()
 {
-	/* free links
-	 * note: deleting relations will remove them from the node relations set,
-	 * but only touch the same position as we are using here, which is safe.
+	/* Free links. */
+	/* NOTE: We only free incoming links. This is to avoid double-free of links
+	 * when we're trying to free same link from both it's sides. We don't have
+	 * dangling links so this is not a problem from memory leaks point of view.
 	 */
 	DEPSNODE_RELATIONS_ITER_BEGIN(this->inlinks, rel)
 	{
 		OBJECT_GUARDED_DELETE(rel, DepsRelation);
 	}
 	DEPSNODE_RELATIONS_ITER_END;
-
-	DEPSNODE_RELATIONS_ITER_BEGIN(this->outlinks, rel)
-	{
-		OBJECT_GUARDED_DELETE(rel, DepsRelation);
-	}
-	DEPSNODE_RELATIONS_ITER_END;
 }
 
 
diff --git a/source/blender/depsgraph/intern/depsnode.h b/source/blender/depsgraph/intern/depsnode.h
index 53826ae8e71..4a464955384 100644
--- a/source/blender/depsgraph/intern/depsnode.h
+++ b/source/blender/depsgraph/intern/depsnode.h
@@ -73,7 +73,7 @@ struct DepsNode {
 	 * from basic serialization benefits - from the typeinfo) is that we can have
 	 * relationships between these nodes!
 	 */
-	typedef unordered_set<DepsRelation *> Relations;
+	typedef vector<DepsRelation *> Relations;
 
 	/* Nodes which this one depends on. */
 	Relations inlinks;