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

1 files changed, 16 insertions, 6 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 -------------------------------------- */