[Bf-blender-cvs] [be1745425ca] master: Nodes: Remove "level" building pass on update

[Hans Goudey]

Commit: be1745425cad0a87f6ea35aaacf78bf4404a91ac
Author: Hans Goudey
Date:   Mon Nov 21 11:34:22 2022 -0600
Branches: master
https://developer.blender.org/rBbe1745425cad0a87f6ea35aaacf78bf4404a91ac

Nodes: Remove "level" building pass on update

The node level was an indication of how deep the node was in the tree.
It was only used for detecting link cycles. Now that the node topology
cache from 25e307d725d0b9 exists, this calculation can be removed
completely.

The level calculation was quadratic and very slow on larger node trees.
In the mouse house file with a few thousand nodes, it took 23ms on
every single update. Another benefit is storing slightly less runtime
data, though this was only 2 bytes per node.

Differential Revision: https://developer.blender.org/D16566

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

M	source/blender/blenkernel/BKE_node.h
M	source/blender/blenkernel/BKE_node_runtime.hh
M	source/blender/blenkernel/intern/node.cc
M	source/blender/blenkernel/intern/node_tree_update.cc

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

diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h
index 680cf4c283d..dd035dbf537 100644
--- a/source/blender/blenkernel/BKE_node.h
+++ b/source/blender/blenkernel/BKE_node.h
@@ -512,8 +512,6 @@ bool ntreeHasTree(const struct bNodeTree *ntree, const struct bNodeTree *lookup)
 void ntreeUpdateAllNew(struct Main *main);
 void ntreeUpdateAllUsers(struct Main *main, struct ID *id);
 
-void ntreeUpdateNodeLevels(struct bNodeTree *ntree);
-
 /**
  * XXX: old trees handle output flags automatically based on special output
  * node types and last active selection.
diff --git a/source/blender/blenkernel/BKE_node_runtime.hh b/source/blender/blenkernel/BKE_node_runtime.hh
index 48c6c7d3643..ea523da0c55 100644
--- a/source/blender/blenkernel/BKE_node_runtime.hh
+++ b/source/blender/blenkernel/BKE_node_runtime.hh
@@ -146,9 +146,8 @@ class bNodeRuntime : NonCopyable, NonMovable {
   /** #eNodeTreeChangedFlag. */
   uint32_t changed_flag = 0;
 
-  /** Both for dependency and sorting. */
+  /** For dependency and sorting. */
   short done = 0;
-  short level = 0;
 
   /** Used as a boolean for execution. */
   uint8_t need_exec = 0;
diff --git a/source/blender/blenkernel/intern/node.cc b/source/blender/blenkernel/intern/node.cc
index 17fc4b51b95..d8451cab0f5 100644
--- a/source/blender/blenkernel/intern/node.cc
+++ b/source/blender/blenkernel/intern/node.cc
@@ -4078,62 +4078,6 @@ void BKE_node_instance_hash_remove_untagged(bNodeInstanceHash *hash,
   MEM_freeN(untagged);
 }
 
-/* ************** dependency stuff *********** */
-
-/* node is guaranteed to be not checked before */
-static int node_get_deplist_recurs(bNodeTree *ntree, bNode *node, bNode ***nsort)
-{
-  int level = 0xFFF;
-
-  node->runtime->done = true;
-
-  /* check linked nodes */
-  LISTBASE_FOREACH (bNodeLink *, link, &ntree->links) {
-    if (link->tonode == node) {
-      bNode *fromnode = link->fromnode;
-      if (fromnode->runtime->done == 0) {
-        fromnode->runtime->level = node_get_deplist_recurs(ntree, fromnode, nsort);
-      }
-      if (fromnode->runtime->level <= level) {
-        level = fromnode->runtime->level - 1;
-      }
-    }
-  }
-
-  /* check parent node */
-  if (node->parent) {
-    if (node->parent->runtime->done == 0) {
-      node->parent->runtime->level = node_get_deplist_recurs(ntree, node->parent, nsort);
-    }
-    if (node->parent->runtime->level <= level) {
-      level = node->parent->runtime->level - 1;
-    }
-  }
-
-  if (nsort) {
-    **nsort = node;
-    (*nsort)++;
-  }
-
-  return level;
-}
-
-/* only updates node->level for detecting cycles links */
-void ntreeUpdateNodeLevels(bNodeTree *ntree)
-{
-  /* first clear tag */
-  LISTBASE_FOREACH (bNode *, node, &ntree->nodes) {
-    node->runtime->done = false;
-  }
-
-  /* recursive check */
-  LISTBASE_FOREACH (bNode *, node, &ntree->nodes) {
-    if (node->runtime->done == 0) {
-      node->runtime->level = node_get_deplist_recurs(ntree, node, nullptr);
-    }
-  }
-}
-
 void ntreeUpdateAllNew(Main *main)
 {
   Vector<bNodeTree *> new_ntrees;
diff --git a/source/blender/blenkernel/intern/node_tree_update.cc b/source/blender/blenkernel/intern/node_tree_update.cc
index 75ae8b8e0c1..f204e8fbddc 100644
--- a/source/blender/blenkernel/intern/node_tree_update.cc
+++ b/source/blender/blenkernel/intern/node_tree_update.cc
@@ -998,7 +998,6 @@ class NodeTreeMainUpdater {
     result.output_changed = this->check_if_output_changed(ntree);
 
     this->update_socket_link_and_use(ntree);
-    this->update_node_levels(ntree);
     this->update_link_validation(ntree);
 
     if (ntree.type == NTREE_TEXTURE) {
@@ -1269,25 +1268,32 @@ class NodeTreeMainUpdater {
     }
   }
 
-  void update_node_levels(bNodeTree &ntree)
-  {
-    ntreeUpdateNodeLevels(&ntree);
-  }
-
   void update_link_validation(bNodeTree &ntree)
   {
+    const Span<const bNode *> toposort = ntree.toposort_left_to_right();
+
+    /* Build an array of toposort indices to allow retrieving the "depth" for each node. */
+    Array<int> toposort_indices(toposort.size());
+    for (const int i : toposort.index_range()) {
+      const bNode &node = *toposort[i];
+      toposort_indices[node.runtime->index_in_tree] = i;
+    }
+
     LISTBASE_FOREACH (bNodeLink *, link, &ntree.links) {
       link->flag |= NODE_LINK_VALID;
-      if (link->fromnode && link->tonode &&
-          link->fromnode->runtime->level <= link->tonode->runtime->level) {
+      const bNode &from_node = *link->fromnode;
+      const bNode &to_node = *link->tonode;
+      if (toposort_indices[from_node.runtime->index_in_tree] >
+          toposort_indices[to_node.runtime->index_in_tree]) {
         link->flag &= ~NODE_LINK_VALID;
+        continue;
       }
-      else if (ntree.typeinfo->validate_link) {
-        const eNodeSocketDatatype from_type = static_cast<eNodeSocketDatatype>(
-            link->fromsock->type);
-        const eNodeSocketDatatype to_type = static_cast<eNodeSocketDatatype>(link->tosock->type);
+      if (ntree.typeinfo->validate_link) {
+        const eNodeSocketDatatype from_type = eNodeSocketDatatype(link->fromsock->type);
+        const eNodeSocketDatatype to_type = eNodeSocketDatatype(link->tosock->type);
         if (!ntree.typeinfo->validate_link(from_type, to_type)) {
           link->flag &= ~NODE_LINK_VALID;
+          continue;
         }
       }
     }