[Bf-blender-cvs] [b6ca942e477] master: Functions: support cycles in lazy-function graph
Jacques Lucke
noreply at git.blender.org
Thu Dec 29 16:39:56 CET 2022
Commit: b6ca942e47730a2ca4ca620e5c82df9f85d8b266
Author: Jacques Lucke
Date: Thu Dec 29 16:38:18 2022 +0100
Branches: master
https://developer.blender.org/rBb6ca942e47730a2ca4ca620e5c82df9f85d8b266
Functions: support cycles in lazy-function graph
Lazy-function graphs are now evaluated properly even if they contain
cycles. Note that cycles are only ok if there is no data dependency cycle.
For example, a node might output something that is fed back into itself.
As long as the output can be computed without the input that it feeds into,
everything is ok.
The code that builds the graph is responsible for making sure that there
are no actual data dependencies.
===================================================================
M source/blender/functions/FN_lazy_function.hh
M source/blender/functions/FN_lazy_function_execute.hh
M source/blender/functions/intern/lazy_function.cc
M source/blender/functions/intern/lazy_function_graph_executor.cc
M source/blender/functions/tests/FN_lazy_function_test.cc
===================================================================
diff --git a/source/blender/functions/FN_lazy_function.hh b/source/blender/functions/FN_lazy_function.hh
index 4a539e7cbd1..bc85c155c2e 100644
--- a/source/blender/functions/FN_lazy_function.hh
+++ b/source/blender/functions/FN_lazy_function.hh
@@ -39,6 +39,7 @@
*/
#include "BLI_cpp_type.hh"
+#include "BLI_function_ref.hh"
#include "BLI_generic_pointer.hh"
#include "BLI_linear_allocator.hh"
#include "BLI_vector.hh"
@@ -165,7 +166,8 @@ class Params {
* Typed utility methods that wrap the methods above.
*/
template<typename T> T extract_input(int index);
- template<typename T> const T &get_input(int index) const;
+ template<typename T> T &get_input(int index) const;
+ template<typename T> T *try_get_input_data_ptr(int index) const;
template<typename T> T *try_get_input_data_ptr_or_request(int index);
template<typename T> void set_output(int index, T &&value);
@@ -253,6 +255,10 @@ class LazyFunction {
const char *debug_name_ = "<unknown>";
Vector<Input> inputs_;
Vector<Output> outputs_;
+ /**
+ * Allow executing the function even if previously requested values are not yet available.
+ */
+ bool allow_missing_requested_inputs_ = false;
public:
virtual ~LazyFunction() = default;
@@ -277,6 +283,13 @@ class LazyFunction {
*/
virtual void destruct_storage(void *storage) const;
+ /**
+ * Calls `fn` with the input indices that the given `output_index` may depend on. By default
+ * every output depends on every input.
+ */
+ virtual void possible_output_dependencies(int output_index,
+ FunctionRef<void(Span<int>)> fn) const;
+
/**
* Inputs of the function.
*/
@@ -298,6 +311,17 @@ class LazyFunction {
*/
bool always_used_inputs_available(const Params ¶ms) const;
+ /**
+ * If true, the function can be executed even when some requested inputs are not available yet.
+ * This allows the function to make some progress and maybe to compute some outputs that are
+ * passed into this function again (lazy-function graphs may contain cycles as long as there
+ * aren't actually data dependencies).
+ */
+ bool allow_missing_requested_inputs() const
+ {
+ return allow_missing_requested_inputs_;
+ }
+
private:
/**
* Needs to be implemented by subclasses. This is separate from #execute so that additional
@@ -391,11 +415,17 @@ template<typename T> inline T Params::extract_input(const int index)
return return_value;
}
-template<typename T> inline const T &Params::get_input(const int index) const
+template<typename T> inline T &Params::get_input(const int index) const
{
- const void *data = this->try_get_input_data_ptr(index);
+ void *data = this->try_get_input_data_ptr(index);
BLI_assert(data != nullptr);
- return *static_cast<const T *>(data);
+ return *static_cast<T *>(data);
+}
+
+template<typename T> inline T *Params::try_get_input_data_ptr(const int index) const
+{
+ this->assert_valid_thread();
+ return static_cast<T *>(this->try_get_input_data_ptr(index));
}
template<typename T> inline T *Params::try_get_input_data_ptr_or_request(const int index)
diff --git a/source/blender/functions/FN_lazy_function_execute.hh b/source/blender/functions/FN_lazy_function_execute.hh
index 31bbddf5baf..1d82ac94ee8 100644
--- a/source/blender/functions/FN_lazy_function_execute.hh
+++ b/source/blender/functions/FN_lazy_function_execute.hh
@@ -93,6 +93,9 @@ inline void execute_lazy_function_eagerly_impl(
fn, input_pointers, output_pointers, input_usages, output_usages, set_outputs};
fn.execute(params, context);
fn.destruct_storage(context.storage);
+
+ /* Make sure all outputs have been computed. */
+ BLI_assert(!Span(set_outputs).contains(false));
}
} // namespace detail
diff --git a/source/blender/functions/intern/lazy_function.cc b/source/blender/functions/intern/lazy_function.cc
index f1c53a04b3f..d42b1889160 100644
--- a/source/blender/functions/intern/lazy_function.cc
+++ b/source/blender/functions/intern/lazy_function.cc
@@ -36,8 +36,22 @@ void LazyFunction::destruct_storage(void *storage) const
UNUSED_VARS_NDEBUG(storage);
}
+void LazyFunction::possible_output_dependencies(const int /*output_index*/,
+ const FunctionRef<void(Span<int>)> fn) const
+{
+ /* The output depends on all inputs by default. */
+ Vector<int, 16> indices(inputs_.size());
+ for (const int i : inputs_.index_range()) {
+ indices[i] = i;
+ }
+ fn(indices);
+}
+
bool LazyFunction::always_used_inputs_available(const Params ¶ms) const
{
+ if (allow_missing_requested_inputs_) {
+ return true;
+ }
for (const int i : inputs_.index_range()) {
const Input &fn_input = inputs_[i];
if (fn_input.usage == ValueUsage::Used) {
diff --git a/source/blender/functions/intern/lazy_function_graph_executor.cc b/source/blender/functions/intern/lazy_function_graph_executor.cc
index a5764e23468..21040bd4550 100644
--- a/source/blender/functions/intern/lazy_function_graph_executor.cc
+++ b/source/blender/functions/intern/lazy_function_graph_executor.cc
@@ -762,8 +762,10 @@ class Executor {
input_state.was_ready_for_execution = true;
continue;
}
- if (input_state.usage == ValueUsage::Used) {
- return;
+ if (!fn.allow_missing_requested_inputs()) {
+ if (input_state.usage == ValueUsage::Used) {
+ return;
+ }
}
}
@@ -1031,7 +1033,10 @@ class Executor {
if (input_state.usage == ValueUsage::Used) {
node_state.missing_required_inputs -= 1;
- if (node_state.missing_required_inputs == 0) {
+ if (node_state.missing_required_inputs == 0 ||
+ (locked_node.node.is_function() && static_cast<const FunctionNode &>(locked_node.node)
+ .function()
+ .allow_missing_requested_inputs())) {
this->schedule_node(locked_node, current_task);
}
}
@@ -1248,6 +1253,9 @@ GraphExecutor::GraphExecutor(const Graph &graph,
logger_(logger),
side_effect_provider_(side_effect_provider)
{
+ /* The graph executor can handle partial execution when there are still missing inputs. */
+ allow_missing_requested_inputs_ = true;
+
for (const OutputSocket *socket : graph_inputs_) {
BLI_assert(socket->node().is_dummy());
inputs_.append({"In", socket->type(), ValueUsage::Maybe});
diff --git a/source/blender/functions/tests/FN_lazy_function_test.cc b/source/blender/functions/tests/FN_lazy_function_test.cc
index dc1c698598d..54e1df00cdf 100644
--- a/source/blender/functions/tests/FN_lazy_function_test.cc
+++ b/source/blender/functions/tests/FN_lazy_function_test.cc
@@ -112,4 +112,68 @@ TEST(lazy_function, SideEffects)
EXPECT_EQ(dst2, 105);
}
+class PartialEvaluationTestFunction : public LazyFunction {
+ public:
+ PartialEvaluationTestFunction()
+ {
+ debug_name_ = "Partial Evaluation";
+ allow_missing_requested_inputs_ = true;
+
+ inputs_.append_as("A", CPPType::get<int>(), ValueUsage::Used);
+ inputs_.append_as("B", CPPType::get<int>(), ValueUsage::Used);
+
+ outputs_.append_as("A*2", CPPType::get<int>());
+ outputs_.append_as("B*5", CPPType::get<int>());
+ }
+
+ void execute_impl(Params ¶ms, const Context & /*context*/) const override
+ {
+ if (!params.output_was_set(0)) {
+ if (int *a = params.try_get_input_data_ptr<int>(0)) {
+ params.set_output(0, *a * 2);
+ }
+ }
+ if (!params.output_was_set(1)) {
+ if (int *b = params.try_get_input_data_ptr<int>(1)) {
+ params.set_output(1, *b * 5);
+ }
+ }
+ }
+
+ void possible_output_dependencies(const int output_index,
+ FunctionRef<void(Span<int>)> fn) const override
+ {
+ /* Each output only depends on the input with the same index. */
+ const int input_index = output_index;
+ fn({input_index});
+ }
+};
+
+TEST(lazy_function, GraphWithCycle)
+{
+ const PartialEvaluationTestFunction fn;
+
+ Graph graph;
+ FunctionNode &fn_node = graph.add_function(fn);
+
+ DummyNode &input_node = graph.add_dummy({}, {&CPPType::get<int>()});
+ DummyNode &output_node = graph.add_dummy({&CPPType::get<int>()}, {});
+
+ graph.add_link(input_node.output(0), fn_node.input(0));
+ /* Note: This creates a cycle in the graph. However, it should still be possible to evaluate it,
+ * because there is no actual data dependency in the cycle. */
+ graph.add_link(fn_node.output(0), fn_node.input(1));
+ graph.add_link(fn_node.output(1), output_node.input(0));
+
+ graph.update_node_indices();
+
+ GraphExecutor executor_fn{
+ graph, {&input_node.output(0)}, {&output_node.input(0)}, nullptr, nullptr};
+ int result = 0;
+ execute_lazy_function_eagerly(
+ executor_fn, nullptr, std::make_tuple(10), std::make_tuple(&result));
+
+ EXPECT_EQ(result, 10 * 2 * 5);
+}
+
} // namespace blender::fn::lazy_function::tests
More information about the Bf-blender-cvs
mailing list