[Bf-blender-cvs] [86a57b0] master: Depsgraph: Store node input/output links in a vector rather than in set

[Sergey Sharybin]

Commit: 86a57b04bfa6730298dc8fafe0545f6929ee64a6
Author: Sergey Sharybin
Date:   Mon May 9 12:42:53 2016 +0200
Branches: master
https://developer.blender.org/rB86a57b04bfa6730298dc8fafe0545f6929ee64a6

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 ;)

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

M	source/blender/depsgraph/intern/depsgraph.cc
M	source/blender/depsgraph/intern/depsgraph_eval.cc
M	source/blender/depsgraph/intern/depsnode.cc
M	source/blender/depsgraph/intern/depsnode.h

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

diff --git a/source/blender/depsgraph/intern/depsgraph.cc b/source/blender/depsgraph/intern/depsgraph.cc
index 18c7c5b..d293d03 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 15c8b1a..febea7d 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 7d4d689..8aa1059 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 53826ae..4a46495 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;