From 7b88a4a3ba7eb9b839afa6c42d070812a3af7997 Mon Sep 17 00:00:00 2001 From: Jacques Lucke Date: Sat, 11 Dec 2021 11:25:32 +0100 Subject: Geometry Nodes: remove accidental exponential time algorithm Calling `foreach_field_input` on a highly nested field (we do that often) has an exponential running time in the number of nodes. That is because the same node may be visited many times. This made Blender freeze on some setups that should work just fine. Now every field keeps track of its inputs all the time. That replaces the exponential algorithm with constant time access. --- source/blender/functions/FN_field.hh | 49 ++++++++++++-------- source/blender/functions/intern/field.cc | 76 +++++++++++++++++++++++--------- 2 files changed, 87 insertions(+), 38 deletions(-) (limited to 'source/blender/functions') diff --git a/source/blender/functions/FN_field.hh b/source/blender/functions/FN_field.hh index d82f685e7ea..289ced8929f 100644 --- a/source/blender/functions/FN_field.hh +++ b/source/blender/functions/FN_field.hh @@ -49,6 +49,7 @@ #include "BLI_function_ref.hh" #include "BLI_string_ref.hh" #include "BLI_vector.hh" +#include "BLI_vector_set.hh" #include "FN_generic_virtual_array.hh" #include "FN_multi_function_builder.hh" @@ -59,6 +60,7 @@ namespace blender::fn { class FieldInput; +class FieldInputs; /** * A node in a field-tree. It has at least one output that can be referenced by fields. @@ -66,18 +68,18 @@ class FieldInput; class FieldNode { private: bool is_input_; + + protected: /** - * True when this node is a #FieldInput or (potentially indirectly) depends on one. This could - * always be derived again later by traversing the field-tree, but keeping track of it while the - * field is built is cheaper. - * - * If this is false, the field is constant. Note that even when this is true, the field may be - * constant when all inputs are constant. + * Keeps track of the inputs that this node depends on. This avoids recomputing it every time the + * data is required. It is a shared pointer, because very often multiple nodes depend on the same + * inputs. + * Might contain null. */ - bool depends_on_input_; + std::shared_ptr field_inputs_; public: - FieldNode(bool is_input, bool depends_on_input); + FieldNode(bool is_input); virtual ~FieldNode() = default; @@ -87,11 +89,7 @@ class FieldNode { bool is_operation() const; bool depends_on_input() const; - /** - * Invoke callback for every field input. It might be called multiple times for the same input. - * The caller is responsible for deduplication if required. - */ - virtual void foreach_field_input(FunctionRef foreach_fn) const = 0; + const std::shared_ptr &field_inputs() const; virtual uint64_t hash() const; virtual bool is_equal_to(const FieldNode &other) const; @@ -231,7 +229,6 @@ class FieldOperation : public FieldNode { const MultiFunction &multi_function() const; const CPPType &output_cpp_type(int output_index) const override; - void foreach_field_input(FunctionRef foreach_fn) const override; }; class FieldContext; @@ -271,7 +268,19 @@ class FieldInput : public FieldNode { Category category() const; const CPPType &output_cpp_type(int output_index) const override; - void foreach_field_input(FunctionRef foreach_fn) const override; +}; + +/** + * Keeps track of the inputs of a field. + */ +struct FieldInputs { + /** All #FieldInput nodes that a field (possibly indirectly) depends on. */ + VectorSet nodes; + /** + * Same as above but the inputs are deduplicated. For example, when there are two separate index + * input nodes, only one will show up in this list. + */ + VectorSet> deduplicated_nodes; }; /** @@ -529,8 +538,7 @@ template struct ValueOrField { /** \name #FieldNode Inline Methods * \{ */ -inline FieldNode::FieldNode(bool is_input, bool depends_on_input) - : is_input_(is_input), depends_on_input_(depends_on_input) +inline FieldNode::FieldNode(bool is_input) : is_input_(is_input) { } @@ -546,7 +554,12 @@ inline bool FieldNode::is_operation() const inline bool FieldNode::depends_on_input() const { - return depends_on_input_; + return field_inputs_ && !field_inputs_->nodes.is_empty(); +} + +inline const std::shared_ptr &FieldNode::field_inputs() const +{ + return field_inputs_; } inline uint64_t FieldNode::hash() const diff --git a/source/blender/functions/intern/field.cc b/source/blender/functions/intern/field.cc index f55b9cd92ff..3274af4a7be 100644 --- a/source/blender/functions/intern/field.cc +++ b/source/blender/functions/intern/field.cc @@ -540,28 +540,65 @@ FieldOperation::FieldOperation(std::shared_ptr function, owned_function_ = std::move(function); } -static bool any_field_depends_on_input(Span fields) +/** + * Returns the field inputs used by all the provided fields. + * This tries to reuse an existing #FieldInputs whenever possible to avoid copying it. + */ +static std::shared_ptr combine_field_inputs(Span fields) { + /* The #FieldInputs that we try to reuse if possible. */ + const std::shared_ptr *field_inputs_candidate = nullptr; for (const GField &field : fields) { - if (field.node().depends_on_input()) { - return true; + const std::shared_ptr &field_inputs = field.node().field_inputs(); + /* Only try to reuse non-empty #FieldInputs. */ + if (field_inputs && !field_inputs->nodes.is_empty()) { + if (field_inputs_candidate == nullptr) { + field_inputs_candidate = &field_inputs; + } + else if ((*field_inputs_candidate)->nodes.size() < field_inputs->nodes.size()) { + /* Always try to reuse the #FieldInputs that has the most nodes already. */ + field_inputs_candidate = &field_inputs; + } + } + } + if (field_inputs_candidate == nullptr) { + /* None of the field depends on an input. */ + return {}; + } + /* Check if all inputs are in the */ + Vector inputs_not_in_candidate; + for (const GField &field : fields) { + const std::shared_ptr &field_inputs = field.node().field_inputs(); + if (!field_inputs) { + continue; + } + if (&field_inputs == field_inputs_candidate) { + continue; } + for (const FieldInput *field_input : field_inputs->nodes) { + if (!(*field_inputs_candidate)->nodes.contains(field_input)) { + inputs_not_in_candidate.append(field_input); + } + } + } + if (inputs_not_in_candidate.is_empty()) { + /* The existing #FieldInputs can be reused, because no other field has additional inputs. */ + return *field_inputs_candidate; } - return false; + /* Create new #FieldInputs that contains all of the inputs that the fields depend on. */ + std::shared_ptr new_field_inputs = std::make_shared( + **field_inputs_candidate); + for (const FieldInput *field_input : inputs_not_in_candidate) { + new_field_inputs->nodes.add(field_input); + new_field_inputs->deduplicated_nodes.add(*field_input); + } + return new_field_inputs; } FieldOperation::FieldOperation(const MultiFunction &function, Vector inputs) - : FieldNode(false, any_field_depends_on_input(inputs)), - function_(&function), - inputs_(std::move(inputs)) + : FieldNode(false), function_(&function), inputs_(std::move(inputs)) { -} - -void FieldOperation::foreach_field_input(FunctionRef foreach_fn) const -{ - for (const GField &field : inputs_) { - field.node().foreach_field_input(foreach_fn); - } + field_inputs_ = combine_field_inputs(inputs); } /* -------------------------------------------------------------------- @@ -569,13 +606,12 @@ void FieldOperation::foreach_field_input(FunctionRef f */ FieldInput::FieldInput(const CPPType &type, std::string debug_name) - : FieldNode(true, true), type_(&type), debug_name_(std::move(debug_name)) -{ -} - -void FieldInput::foreach_field_input(FunctionRef foreach_fn) const + : FieldNode(true), type_(&type), debug_name_(std::move(debug_name)) { - foreach_fn(*this); + std::shared_ptr field_inputs = std::make_shared(); + field_inputs->nodes.add_new(this); + field_inputs->deduplicated_nodes.add_new(*this); + field_inputs_ = std::move(field_inputs); } /* -------------------------------------------------------------------- -- cgit v1.2.3