From 5c79f2d0fba7360488e591922f91aa858bd8d603 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Cl=C3=A9ment=20Foucault?= Date: Mon, 30 Sep 2019 13:09:39 +0200 Subject: Fix T70325 EEVEE: Performance regression with large nodetrees This was caused by nodeChainIter which is not linear complexity. Introduce nodeChainIterBackwards to iterate backwards faster. --- source/blender/blenkernel/BKE_node.h | 4 ++ source/blender/blenkernel/intern/node.c | 51 ++++++++++++++++++++++++++ source/blender/makesdna/DNA_node_types.h | 4 +- source/blender/nodes/shader/node_shader_tree.c | 32 +++------------- 4 files changed, 64 insertions(+), 27 deletions(-) (limited to 'source/blender') diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h index f88aebd312c..06fd7915476 100644 --- a/source/blender/blenkernel/BKE_node.h +++ b/source/blender/blenkernel/BKE_node.h @@ -591,6 +591,10 @@ void nodeChainIter(const bNodeTree *ntree, bool (*callback)(bNode *, bNode *, void *, const bool), void *userdata, const bool reversed); +void nodeChainIterBackwards(const bNodeTree *ntree, + const bNode *node_start, + bool (*callback)(bNode *, bNode *, void *), + void *userdata); void nodeParentsIter(bNode *node, bool (*callback)(bNode *, void *), void *userdata); struct bNodeLink *nodeFindLink(struct bNodeTree *ntree, diff --git a/source/blender/blenkernel/intern/node.c b/source/blender/blenkernel/intern/node.c index 92c15e05aee..0ef35bd3d06 100644 --- a/source/blender/blenkernel/intern/node.c +++ b/source/blender/blenkernel/intern/node.c @@ -947,6 +947,57 @@ void nodeChainIter(const bNodeTree *ntree, } } +static void iter_backwards_ex(const bNodeTree *ntree, + const bNode *node_start, + bool (*callback)(bNode *, bNode *, void *), + void *userdata) +{ + LISTBASE_FOREACH (bNodeSocket *, sock, &node_start->inputs) { + bNodeLink *link = sock->link; + if (link == NULL) { + continue; + } + if ((link->flag & NODE_LINK_VALID) == 0) { + /* Skip links marked as cyclic. */ + continue; + } + if (link->fromnode->iter_flag) { + /* Only iter on nodes once. */ + continue; + } + else { + link->fromnode->iter_flag = 1; + } + + if (!callback(link->fromnode, link->tonode, userdata)) { + return; + } + iter_backwards_ex(ntree, link->fromnode, callback, userdata); + } +} + +/** + * Iterate over a chain of nodes, starting with \a node_start, executing + * \a callback for each node (which can return false to end iterator). + * + * Faster than nodeChainIter. Iter only once per node. + * + * \note Needs updated socket links (ntreeUpdateTree). + * \note Recursive + */ +void nodeChainIterBackwards(const bNodeTree *ntree, + const bNode *node_start, + bool (*callback)(bNode *, bNode *, void *), + void *userdata) +{ + /* Reset flag. */ + LISTBASE_FOREACH (bNode *, node, &ntree->nodes) { + node->iter_flag = 0; + } + + iter_backwards_ex(ntree, node_start, callback, userdata); +} + /** * Iterate over all parents of \a node, executing \a callback for each parent * (which can return false to end iterator) diff --git a/source/blender/makesdna/DNA_node_types.h b/source/blender/makesdna/DNA_node_types.h index 702758b51ec..7eecf23195a 100644 --- a/source/blender/makesdna/DNA_node_types.h +++ b/source/blender/makesdna/DNA_node_types.h @@ -277,7 +277,9 @@ typedef struct bNode { /** Used at runtime when going through the tree. Initialize before use. */ short tmp_flag; /** Used at runtime to tag derivatives branches. EEVEE only. */ - short branch_tag; + char branch_tag; + /** Used at runtime when iterating over node branches. */ + char iter_flag; /** Runtime during drawing. */ struct uiBlock *block; diff --git a/source/blender/nodes/shader/node_shader_tree.c b/source/blender/nodes/shader/node_shader_tree.c index aaab3572b8e..92266600612 100644 --- a/source/blender/nodes/shader/node_shader_tree.c +++ b/source/blender/nodes/shader/node_shader_tree.c @@ -597,10 +597,7 @@ static void ntree_shader_bypass_tagged_bump_nodes(bNodeTree *ntree) ntreeUpdateTree(G.main, ntree); } -static bool ntree_branch_count_and_tag_nodes(bNode *fromnode, - bNode *tonode, - void *userdata, - const bool UNUSED(reversed)) +static bool ntree_branch_count_and_tag_nodes(bNode *fromnode, bNode *tonode, void *userdata) { int *node_count = (int *)userdata; if (fromnode->tmp_flag == -1) { @@ -629,7 +626,7 @@ static bNode *ntree_shader_copy_branch(bNodeTree *ntree, /* Count and tag all nodes inside the displacement branch of the tree. */ start_node->tmp_flag = 0; int node_count = 1; - nodeChainIter(ntree, start_node, ntree_branch_count_and_tag_nodes, &node_count, true); + nodeChainIterBackwards(ntree, start_node, ntree_branch_count_and_tag_nodes, &node_count); /* Make a full copy of the branch */ bNode **nodes_copy = MEM_mallocN(sizeof(bNode *) * node_count, __func__); LISTBASE_FOREACH (bNode *, node, &ntree->nodes) { @@ -763,10 +760,7 @@ static void node_tag_branch_as_derivative(bNode *node, int dx) } } -static bool ntree_shader_bump_branches(bNode *UNUSED(fromnode), - bNode *tonode, - void *userdata, - const bool UNUSED(reversed)) +static bool ntree_shader_bump_branches(bNode *UNUSED(fromnode), bNode *tonode, void *userdata) { bNodeTree *ntree = (bNodeTree *)userdata; @@ -794,17 +788,8 @@ static bool ntree_shader_bump_branches(bNode *UNUSED(fromnode), return true; } -static bool ntree_tag_bsdf_cb(bNode *fromnode, - bNode *UNUSED(tonode), - void *userdata, - const bool UNUSED(reversed)) +static bool ntree_tag_bsdf_cb(bNode *fromnode, bNode *UNUSED(tonode), void *userdata) { - /* Don't evaluate nodes more than once. */ - if (fromnode->tmp_flag) { - return true; - } - fromnode->tmp_flag = 1; - switch (fromnode->type) { case SH_NODE_BSDF_ANISOTROPIC: case SH_NODE_EEVEE_SPECULAR: @@ -844,12 +829,7 @@ void ntree_shader_tag_nodes(bNodeTree *ntree, bNode *output_node, nTreeTags *tag /* Make sure sockets links pointers are correct. */ ntreeUpdateTree(G.main, ntree); - /* Reset visit flag. */ - for (bNode *node = ntree->nodes.first; node; node = node->next) { - node->tmp_flag = 0; - } - - nodeChainIter(ntree, output_node, ntree_tag_bsdf_cb, tags, true); + nodeChainIterBackwards(ntree, output_node, ntree_tag_bsdf_cb, tags); } /* This one needs to work on a local tree. */ @@ -878,7 +858,7 @@ void ntreeGPUMaterialNodes(bNodeTree *localtree, /* Duplicate bump height branches for manual derivatives. */ - nodeChainIter(localtree, output, ntree_shader_bump_branches, localtree, true); + nodeChainIterBackwards(localtree, output, ntree_shader_bump_branches, localtree); /* TODO(fclem): consider moving this to the gpu shader tree evaluation. */ nTreeTags tags = { -- cgit v1.2.3