Page MenuHome
Differential D15775

Nodes: Add persistent identifier to nodes
ClosedPublic
Actions

Authored by Hans Goudey (HooglyBoogly) on Aug 24 2022, 3:15 PM.

Details

Reviewers
Jacques Lucke (JacquesLucke)
Commits
rB90ea1b76434f: Nodes: Use persistent integer to identify to nodes
Summary

This patch adds an integer identifier to nodes that doesn't change when
the node name changes. This identifier can be used by different systems
to reference a node. This may be important to store caches and simulation
states per node, because otherwise those would always be invalidated
when a node name changes.

Additionally, this kind of identifier could make some things more efficient,
because with it an integer is enough to identify a node and one does not
have to store the node name.

This gives a 10% improvement in evaluation time in a file with an extreme
amount of simple math nodes, due to reduced logging overhead-- from
0.226s to 0.205s.

Note:

  • bNode.runtime.index_in_tree is can be accessed with the VectorSet now, it could be removed.

Diff Detail

Repository
rB Blender

Event Timeline

Jacques Lucke (JacquesLucke) requested review of this revision.Aug 24 2022, 3:15 PM
Jacques Lucke (JacquesLucke) created this revision.
Harbormaster completed remote builds in B23473: Diff 54947.Aug 24 2022, 3:15 PM
Paul Larson (GeorgiaPacific) added a subscriber: Paul Larson (GeorgiaPacific).Aug 29 2022, 6:41 PM
Hans Goudey (HooglyBoogly) added a subscriber: Hans Goudey (HooglyBoogly).Sep 17 2022, 1:29 AM

Seems like a nice approach. The added complexity isn't bad so this looks like it could be worth it

source/blender/blenkernel/intern/node.cc
2290

Shouldn't this copy the identifier from the original node? Or are these meant to continually reset to start at zero when the tree is copied?
Also, this might not work with the constant node sorting from the editor.

source/blender/makesdna/DNA_node_types.h
338

I'm curious why you used an unsigned integer here, any particular reason?

550

Could reference the field in bNode in a comment

Hans Goudey (HooglyBoogly) mentioned this in rB46c40d7fa1ec: Fix: Use after free in geometry node group logger.Oct 6 2022, 6:59 PM
Hans Goudey (HooglyBoogly) commandeered this revision.Nov 30 2022, 4:15 AM
Hans Goudey (HooglyBoogly) added a reviewer: Jacques Lucke (JacquesLucke).
Hans Goudey (HooglyBoogly) updated this revision to Diff 58166.Nov 30 2022, 4:17 AM
Hans Goudey (HooglyBoogly) retitled this revision from Nodes: Add persistent identifier to nodes (WIP). to Nodes: Add persistent identifier to nodes (WIP).
Hans Goudey (HooglyBoogly) edited the summary of this revision. (Show Details)

Use identifier in more areas, fix copying node trees and inserting nodes.

Hans Goudey (HooglyBoogly) edited the summary of this revision. (Show Details)Nov 30 2022, 4:18 AM
Iliya Katueshenock (Moder) added a subscriber: Iliya Katueshenock (Moder).Nov 30 2022, 5:35 AM
Jacques Lucke (JacquesLucke) requested changes to this revision.Nov 30 2022, 2:07 PM

Thanks for picking this up.

source/blender/blenkernel/BKE_compute_contexts.hh
52

Probably still helps to store a debug_node_name.

source/blender/blenkernel/BKE_node.h
698

Maybe something like dst_tree_is_subset_of_src_tree? Maybe that can be shortened somehow.

source/blender/blenkernel/intern/node.cc
2019

That's obviously not very useful yet.

2214

I kind of changed my mind on the use of identifier_counter, as in, we shouldn't use it. Instead it would be better to generate random identifiers and keep a set of existing identifiers in the node tree runtime data (eagerly updated, not part of the topology cache).

Main reason against identifier_counter is that it can overflow and we have no way to recover from that. While it's unlikely, I can totally see it happen when people use scripts that continuously update node trees over and over again.

Would also be good to enforce valid identifiers to be positive.

source/blender/makesrna/intern/rna_space.c
8012 ↗(On Diff #58166)

Think it's reasonable to make the node id accessible from the python api as readonly.

This revision now requires changes to proceed.Nov 30 2022, 2:07 PM
Hans Goudey (HooglyBoogly) updated this revision to Diff 58199.Dec 1 2022, 4:28 AM
Hans Goudey (HooglyBoogly) marked 3 inline comments as done.
Hans Goudey (HooglyBoogly) edited the summary of this revision. (Show Details)

Add eagerly calculated cache of node ids. This has the following benefits:

  • Looking up a node by an ID is always very fast
  • Using VectorSet, it can be merged with the array of nodes to give an always-valid nodes span
  • Not using a counter to build IDs means we can add and remove a node from a tree more than 2 billion times

It has some downsides too:

  • Maintaining the IDs takes some effort when removing/adding/sorting nodes
  • It doesn't solve the "problem" of invalid identifiers for "localized" node trees (not that it has to!)
  • Removing a node requires rebuilding the VectorSet (not noticeable even on gigantic trees in my testing)

Overall I like the solution though. Maybe we can even not use the ListBase at all at runtime in the future, it's a nice step in that direction.
I also added back the node name to the viewer path.

Hans Goudey (HooglyBoogly) updated this revision to Diff 58222.Dec 1 2022, 6:21 PM
Hans Goudey (HooglyBoogly) retitled this revision from Nodes: Add persistent identifier to nodes (WIP) to Nodes: Add persistent identifier to nodes.
Hans Goudey (HooglyBoogly) edited the summary of this revision. (Show Details)
  • Seed the random number generator with time
  • Move fixing of bad IDs from versioning to file reading code
Jacques Lucke (JacquesLucke) requested changes to this revision.Dec 1 2022, 6:39 PM
Jacques Lucke (JacquesLucke) added inline comments.
source/blender/blenkernel/BKE_node.h
698

This didn't change, or did it?

source/blender/blenkernel/BKE_node_runtime.hh
342

const

source/blender/blenkernel/intern/compute_contexts.cc
39–45

Print the name.

source/blender/blenkernel/intern/node.cc
2196

Needs a seed.

2200

Feels weird to check if the node is in there. Maybe better check if it contains the id and only set node->identifier when a good id is found.

2954

Why does this have to be rebuild exactly? VectorSet supports removing elements.

source/blender/makesdna/DNA_node_types.h
322

sounds gramatically wrong (more efficient references)

326

Guess it would be good to make sure that identifiers are always positive. (also add a debug check for that in the tree update)

source/blender/nodes/shader/node_shader_tree.cc
581

It's not clear to me that we can allow identifiers to be invalid. When the node tree is used later, things like all_nodes() couldn't be used if I'm not mistaken.

This revision now requires changes to proceed.Dec 1 2022, 6:39 PM
Hans Goudey (HooglyBoogly) marked 10 inline comments as done.Dec 1 2022, 7:12 PM
Hans Goudey (HooglyBoogly) added inline comments.
source/blender/blenkernel/BKE_node.h
698

Maybe, that doesn't really feel more helpful though. The name is difficult.
For example, if copying 10 nodes of one tree into a new tree, this can be false. But if the tree already had a node, this must be true.
In the end it's about making sure identifiers and names are unique, and that they don't change unnecessarily.

I'll go with "use_unique" since that avoids the abstraction a bit. I also improved the comment a bit.

698

Oops, got lost in a git stash!

source/blender/blenkernel/intern/node.cc
2214

Agreed, I was questioning that when working on this.

2954

We want the order to match the order of the ListBase.

source/blender/nodes/shader/node_shader_tree.cc
581

Good point. The identifiers have to be created at least. I clarified this a bit.

Hans Goudey (HooglyBoogly) updated this revision to Diff 58223.Dec 1 2022, 7:15 PM
Hans Goudey (HooglyBoogly) marked 3 inline comments as done.
Hans Goudey (HooglyBoogly) edited the summary of this revision. (Show Details)
  • Improve handling of identifiers in shader node evaluation
  • Assert that identifier is always positive
  • Simplify comment on bNode
  • Tweak lookup when creating new unique ID
  • Print node name in compute context (for debugging)
  • Use const
  • Add missing improvement to comment and parameter name
  • Seed the random generator properly, move identifier creation to file read
source/blender/blenkernel/BKE_node.h
698

Oops, I forgot to submit that last time

Jacques Lucke (JacquesLucke) added inline comments.Dec 1 2022, 7:35 PM
source/blender/blenkernel/BKE_node.h
691–693

Wrong name in comment.

Hans Goudey (HooglyBoogly) updated this revision to Diff 58229.Dec 1 2022, 7:54 PM
Hans Goudey (HooglyBoogly) marked an inline comment as done.

Fix name in comment

Jacques Lucke (JacquesLucke) accepted this revision.Dec 1 2022, 7:55 PM

bNode.runtime.index_in_tree is can be accessed with the VectorSet now, it could be removed.

I think this is fairly important to keep to implement graph algorithms (it's used so that an Array can be used as Map without the lookup cost).

This revision is now accepted and ready to land.Dec 1 2022, 7:55 PM
Hans Goudey (HooglyBoogly) added a comment.EditedDec 1 2022, 8:00 PM

Thanks for the review.

In D15775#453737, @Jacques Lucke (JacquesLucke) wrote:

bNode.runtime.index_in_tree is can be accessed with the VectorSet now, it could be removed.

I think this is fairly important to keep to implement graph algorithms (it's used so that an Array can be used as Map without the lookup cost).

I only meant that it could be implemented with VectorSet::index_of() if we wanted. Agree that it's very helpful in general.

Closed by commit rB90ea1b76434f: Nodes: Use persistent integer to identify to nodes (authored by Hans Goudey (HooglyBoogly)). · Explain WhyDec 1 2022, 10:11 PM
This revision was automatically updated to reflect the committed changes.
Hans Goudey (HooglyBoogly) added a commit: rB90ea1b76434f: Nodes: Use persistent integer to identify to nodes.

Revision Contents
Changeset List

PathSize
source/
blender/
blenkernel/
16 lines
10 lines
73 lines
intern/
24 lines
50 lines
51 lines
9 lines
3 lines
editors/
include/
4 lines
space_node/
73 lines
10 lines
15 lines
util/
70 lines
makesdna/
21 lines
8 lines
modifiers/
intern/
20 lines
nodes/
18 lines
intern/
9 lines
62 lines
9 lines
shader/
5 lines

Diff 58229

View Options

source/blender/blenkernel/BKE_compute_contexts.hh

Loading...
View Options

source/blender/blenkernel/BKE_node.h

Loading...
View Options

source/blender/blenkernel/BKE_node_runtime.hh

Loading...
View Options

source/blender/blenkernel/intern/compute_contexts.cc

Loading...
View Options

source/blender/blenkernel/intern/node.cc

Loading...
View Options

source/blender/blenkernel/intern/node_runtime.cc

Loading...
View Options

source/blender/blenkernel/intern/node_tree_update.cc

Loading...
View Options

source/blender/blenkernel/intern/viewer_path.cc

Loading...
View Options

source/blender/editors/include/ED_viewer_path.hh

Loading...
View Options

source/blender/editors/space_node/node_draw.cc

Loading...
View Options

source/blender/editors/space_node/node_geometry_attribute_search.cc

Loading...
View Options

source/blender/editors/space_node/node_group.cc

Loading...
View Options

source/blender/editors/util/ed_viewer_path.cc

Loading...
View Options

source/blender/makesdna/DNA_node_types.h

Loading...
View Options

source/blender/makesdna/DNA_viewer_path_types.h

Loading...
View Options

source/blender/modifiers/intern/MOD_nodes.cc

Loading...
View Options

source/blender/nodes/NOD_geometry_nodes_log.hh

Loading...
View Options

source/blender/nodes/intern/geometry_nodes_lazy_function.cc

Loading...
View Options

source/blender/nodes/intern/geometry_nodes_log.cc

Loading...
View Options

source/blender/nodes/intern/node_geometry_exec.cc

Loading...
View Options

source/blender/nodes/shader/node_shader_tree.cc

Loading...