[Bf-blender-cvs] [b084b57fbf6] master: Geometry Nodes: new geometry nodes evaluator
Jacques Lucke
noreply at git.blender.org
Thu May 20 11:39:56 CEST 2021
Commit: b084b57fbf6d2b6c2a1adb2192f5d82581cede5c
Author: Jacques Lucke
Date: Thu May 20 11:34:47 2021 +0200
Branches: master
https://developer.blender.org/rBb084b57fbf6d2b6c2a1adb2192f5d82581cede5c
Geometry Nodes: new geometry nodes evaluator
The old geometry nodes evaluator was quite basic and missed many features.
It was useful to get the geometry nodes project started. However, nowadays
we run into its limitations from time to time.
The new evaluator is more complex, but comes with new capabilities.
The two most important capabilities are that it can now execute nodes in
parallel and it supports lazy evaluation.
The performance improvement by multi-threading depends a lot on the specific
node tree. In our demo files, the speedup is measurable but not huge. This
is mainly because they are bottlenecked by one or two nodes that have to be
executed one after the other (often the Boolean or Attribute Proximity nodes)
or because the bottleneck is multi-threaded already (often openvdb nodes).
Lazy evaluation of inputs is only supported by the Switch node for now.
Previously, geometry nodes would always compute both inputs and then just
discard the one that is not used. Now, only the input that is required
is computed.
For some more details read D11191, T87620 and the in-code documentation.
Differential Revision: https://developer.blender.org/D11191
===================================================================
M source/blender/blenkernel/BKE_node.h
M source/blender/modifiers/intern/MOD_nodes_evaluator.cc
M source/blender/nodes/NOD_geometry_exec.hh
M source/blender/nodes/geometry/nodes/node_geo_point_separate.cc
M source/blender/nodes/geometry/nodes/node_geo_switch.cc
===================================================================
diff --git a/source/blender/blenkernel/BKE_node.h b/source/blender/blenkernel/BKE_node.h
index fbe7e91e985..8824ffc5695 100644
--- a/source/blender/blenkernel/BKE_node.h
+++ b/source/blender/blenkernel/BKE_node.h
@@ -325,6 +325,7 @@ typedef struct bNodeType {
/* Execute a geometry node. */
NodeGeometryExecFunction geometry_node_execute;
+ bool geometry_node_execute_supports_lazyness;
/* RNA integration */
ExtensionRNA rna_ext;
diff --git a/source/blender/modifiers/intern/MOD_nodes_evaluator.cc b/source/blender/modifiers/intern/MOD_nodes_evaluator.cc
index 2637c7db0fc..ac5249b40a2 100644
--- a/source/blender/modifiers/intern/MOD_nodes_evaluator.cc
+++ b/source/blender/modifiers/intern/MOD_nodes_evaluator.cc
@@ -24,6 +24,12 @@
#include "FN_generic_value_map.hh"
#include "FN_multi_function.hh"
+#include "BLI_enumerable_thread_specific.hh"
+#include "BLI_stack.hh"
+#include "BLI_task.h"
+#include "BLI_task.hh"
+#include "BLI_vector_set.hh"
+
namespace blender::modifiers::geometry_nodes {
using fn::CPPType;
@@ -31,404 +37,1531 @@ using fn::GValueMap;
using nodes::GeoNodeExecParams;
using namespace fn::multi_function_types;
-class NodeParamsProvider : public nodes::GeoNodeExecParamsProvider {
- public:
- LinearAllocator<> *allocator;
- GValueMap<StringRef> *input_values;
- GValueMap<StringRef> *output_values;
+enum class ValueUsage : uint8_t {
+ /* The value is definitely used. */
+ Required,
+ /* The value may be used. */
+ Maybe,
+ /* The value will definitely not be used. */
+ Unused,
+};
+
+struct SingleInputValue {
+ /**
+ * Points either to null or to a value of the type of input.
+ */
+ void *value = nullptr;
+};
+
+struct MultiInputValueItem {
+ /**
+ * The socket where this value is coming from. This is required to sort the inputs correctly
+ * based on the link order later on.
+ */
+ DSocket origin;
+ /**
+ * Should only be null directly after construction. After that it should always point to a value
+ * of the correct type.
+ */
+ void *value = nullptr;
+};
+
+struct MultiInputValue {
+ /**
+ * Collection of all the inputs that have been provided already. Note, the same origin can occur
+ * multiple times. However, it is guaranteed that if two items have the same origin, they will
+ * also have the same value (the pointer is different, but they point to values that would
+ * compare equal).
+ */
+ Vector<MultiInputValueItem> items;
+ /**
+ * Number of items that need to be added until all inputs have been provided.
+ */
+ int expected_size = 0;
+};
+
+struct InputState {
+
+ /**
+ * Type of the socket. If this is null, the socket should just be ignored.
+ */
+ const CPPType *type = nullptr;
+
+ /**
+ * Value of this input socket. By default, the value is empty. When other nodes are done
+ * computing their outputs, the computed values will be forwarded to linked input sockets.
+ * The value will then live here until it is consumed by the node or it was found that the value
+ * is not needed anymore.
+ * Whether the `single` or `multi` value is used depends on the socket.
+ */
+ union {
+ SingleInputValue *single;
+ MultiInputValue *multi;
+ } value;
+
+ /**
+ * How the node intends to use this input. By default all inputs may be used. Based on which
+ * outputs are used, a node can tell the evaluator that an input will definitely be used or is
+ * never used. This allows the evaluator to free values early, avoid copies and other unnecessary
+ * computations.
+ */
+ ValueUsage usage = ValueUsage::Maybe;
+
+ /**
+ * True when this input is/was used for an execution. While a node is running, only the inputs
+ * that have this set to true are allowed to be used. This makes sure that inputs created while
+ * the node is running correctly trigger the node to run again. Furthermore, it gives the node a
+ * consistent view of which inputs are available that does not change unexpectedly.
+ *
+ * While the node is running, this can be checked without a lock, because no one is writing to
+ * it. If this is true, the value can be read without a lock as well, because the value is not
+ * changed by others anymore.
+ */
+ bool was_ready_for_execution = false;
+};
+
+struct OutputState {
+ /**
+ * If this output has been computed and forwarded already. If this is true, the value is not
+ * computed/forwarded again.
+ */
+ bool has_been_computed = false;
+
+ /**
+ * Keeps track of how the output value is used. If a connected input becomes required, this
+ * output has to become required as well. The output becomes ignored when it has zero potential
+ * users that are counted below.
+ */
+ ValueUsage output_usage = ValueUsage::Maybe;
+
+ /**
+ * This is a copy of `output_usage` that is done right before node execution starts. This is
+ * done so that the node gets a consistent view of what outputs are used, even when this changes
+ * while the node is running (the node might be reevaluated in that case).
+ *
+ * While the node is running, this can be checked without a lock, because no one is writing to
+ * it.
+ */
+ ValueUsage output_usage_for_execution = ValueUsage::Maybe;
+
+ /**
+ * Counts how many times the value from this output might be used. If this number reaches zero,
+ * the output is not needed anymore.
+ */
+ int potential_users = 0;
+};
+
+enum class NodeScheduleState {
+ /**
+ * Default state of every node.
+ */
+ NotScheduled,
+ /**
+ * The node has been added to the task group and will be executed by it in the future.
+ */
+ Scheduled,
+ /**
+ * The node is currently running.
+ */
+ Running,
+ /**
+ * The node is running and has been rescheduled while running. In this case the node will run
+ * again. However, we don't add it to the task group immediately, because then the node might run
+ * twice at the same time, which is not allowed. Instead, once the node is done running, it will
+ * reschedule itself.
+ */
+ RunningAndRescheduled,
+};
+
+struct NodeState {
+ /**
+ * Needs to be locked when any data in this state is accessed that is not explicitely marked as
+ * otherwise.
+ */
+ std::mutex mutex;
+
+ /**
+ * States of the individual input and output sockets. One can index into these arrays without
+ * locking. However, to access the data inside a lock is generally necessary.
+ *
+ * These spans have to be indexed with the socket index. Unavailable sockets have a state as
+ * well. Maybe we can handle unavailable sockets differently in Blender in general, so I did not
+ * want to add complexity around it here.
+ */
+ MutableSpan<InputState> inputs;
+ MutableSpan<OutputState> outputs;
- bool can_get_input(StringRef identifier) const override
+ /**
+ * Nodes that don't support lazyness have some special handling the first time they are executed.
+ */
+ bool non_lazy_node_is_initialized = false;
+
+ /**
+ * Used to check that nodes that don't support lazyness do not run more than once.
+ */
+ bool has_been_executed = false;
+
+ /**
+ * Becomes true when the node will never be executed again and its inputs are destructed.
+ * Generally, a node has finished once all of its outputs with (potential) users have been
+ * computed.
+ */
+ bool node_has_finished = false;
+
+ /**
+ * Counts the number of values that still have to be forwarded to this node until it should run
+ * again. It counts values from a multi input socket separately.
+ * This is used as an optimization so that nodes are not scheduled unnecessarily in many cases.
+ */
+ int missing_required_inputs = 0;
+
+ /**
+ * A node is always in one specific schedule state. This helps to ensure that the same node does
+ * not run twice at the same time accidentally.
+ */
+ NodeScheduleState schedule_state = NodeScheduleState::NotScheduled;
+};
+
+/**
+ * Container for a node and its state. Packing them into a single struct allows the use of
+ * `VectorSet` instead of a `Map` for `node_states_` which simplifies parallel loops over all
+ * states.
+ *
+ * Equality operators and a hash function for `DNode` are provided so that one can lookup this type
+ * in `node_states_` just with a `DNode`.
+ */
+struct NodeWithState {
+ DNode node;
+ /* Store a pointer instead of `NodeState` directly to keep it small and movable. */
+ NodeState *state = nullptr;
+
+ friend bool operator==(const NodeWithState &a, const NodeWithState &b)
{
- return input_values->contains(identifier);
+ return a.node == b.node;
}
- bool can_set_output(StringRef identifier) const override
+ friend bool operator==(const NodeWithState &a, const DNode &b)
{
- return !output_values->contains(identifier);
+ return a.node == b;
}
- GMutablePointer extract_input(StringRef identifier) override
+ friend bool operator==(const DNode &a, const NodeWithState &b)
{
- return this->input_values->extract(identifier);
+ return a == b.node;
}
- Vector<GMutablePointer> extract_multi_input(StringRef identifier) override
+ uint64_t hash() const
{
- Vector<GMutablePointer> values;
- int index = 0;
- while (true) {
- std::string sub_identifier = identifier;
- if (index > 0) {
- sub_identifier += "[" + std::to_string(index) + "]";
- }
- if (!this->input_values->contains(sub_identifier)) {
- break;
- }
- values.append(input_values->extract(sub_identifier));
- index++;
- }
- return values;
+ return node.hash();
}
- GPointer get_input(StringRef identifier) const override
+ static uint64_t hash_as(const DNode &node)
{
- return this->input_values->lookup(identifier);
+ return node.hash();
}
+};
+
+class GeometryNodesEvaluator;
+
+/**
+ * Utility class that locks the state of a node. Having this is a separate class is useful because
+ * it allows methods to communicate that they expect the node to be locked.
+ */
+class LockedNode : NonCopyable, NonMovable {
+ private:
+ GeometryNodesEvaluator &evaluator_;
- GMutablePointer alloc_output_value(StringRef identifier, const CPPType &type) override
+ public:
+ /**
+ * This is the node that i
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list