[Bf-blender-cvs] [4fe8d0419c2] master: Functions: refactor virtual array data structures
Jacques Lucke
noreply at git.blender.org
Sun Mar 21 19:42:54 CET 2021
Commit: 4fe8d0419c2f080a248f52b3924ce2a4e897e5cb
Author: Jacques Lucke
Date: Sun Mar 21 19:31:24 2021 +0100
Branches: master
https://developer.blender.org/rB4fe8d0419c2f080a248f52b3924ce2a4e897e5cb
Functions: refactor virtual array data structures
When a function is executed for many elements (e.g. per point) it is often the case
that some parameters are different for every element and other parameters are
the same (there are some more less common cases). To simplify writing such
functions one can use a "virtual array". This is a data structure that has a value
for every index, but might not be stored as an actual array internally. Instead, it
might be just a single value or is computed on the fly. There are various tradeoffs
involved when using this data structure which are mentioned in `BLI_virtual_array.hh`.
It is called "virtual", because it uses inheritance and virtual methods.
Furthermore, there is a new virtual vector array data structure, which is an array
of vectors. Both these types have corresponding generic variants, which can be used
when the data type is not known at compile time. This is typically the case when
building a somewhat generic execution system. The function system used these virtual
data structures before, but now they are more versatile.
I've done this refactor in preparation for the attribute processor and other features of
geometry nodes. I moved the typed virtual arrays to blenlib, so that they can be used
independent of the function system.
One open question for me is whether all the generic data structures (and `CPPType`)
should be moved to blenlib as well. They are well isolated and don't really contain
any business logic. That can be done later if necessary.
===================================================================
M source/blender/blenkernel/BKE_attribute_access.hh
A source/blender/blenlib/BLI_virtual_array.hh
A source/blender/blenlib/BLI_virtual_vector_array.hh
M source/blender/blenlib/CMakeLists.txt
A source/blender/blenlib/tests/BLI_virtual_array_test.cc
M source/blender/functions/CMakeLists.txt
D source/blender/functions/FN_array_spans.hh
A source/blender/functions/FN_generic_span.hh
M source/blender/functions/FN_generic_vector_array.hh
A source/blender/functions/FN_generic_virtual_array.hh
A source/blender/functions/FN_generic_virtual_vector_array.hh
M source/blender/functions/FN_multi_function_builder.hh
M source/blender/functions/FN_multi_function_params.hh
M source/blender/functions/FN_multi_function_signature.hh
D source/blender/functions/FN_spans.hh
A source/blender/functions/intern/generic_vector_array.cc
A source/blender/functions/intern/generic_virtual_array.cc
A source/blender/functions/intern/generic_virtual_vector_array.cc
M source/blender/functions/intern/multi_function_network_evaluation.cc
D source/blender/functions/tests/FN_array_spans_test.cc
A source/blender/functions/tests/FN_generic_span_test.cc
M source/blender/functions/tests/FN_generic_vector_array_test.cc
M source/blender/functions/tests/FN_multi_function_network_test.cc
M source/blender/functions/tests/FN_multi_function_test.cc
D source/blender/functions/tests/FN_spans_test.cc
M source/blender/nodes/function/nodes/node_fn_object_transforms.cc
M source/blender/nodes/function/nodes/node_fn_random_float.cc
M source/blender/nodes/shader/nodes/node_shader_map_range.cc
M source/blender/nodes/shader/nodes/node_shader_sepcombRGB.cc
M source/blender/nodes/shader/nodes/node_shader_sepcombXYZ.cc
M source/blender/nodes/shader/nodes/node_shader_valToRgb.cc
===================================================================
diff --git a/source/blender/blenkernel/BKE_attribute_access.hh b/source/blender/blenkernel/BKE_attribute_access.hh
index 653c0f0d85d..120b4e08b9c 100644
--- a/source/blender/blenkernel/BKE_attribute_access.hh
+++ b/source/blender/blenkernel/BKE_attribute_access.hh
@@ -19,7 +19,7 @@
#include <mutex>
#include "FN_cpp_type.hh"
-#include "FN_spans.hh"
+#include "FN_generic_span.hh"
#include "BKE_attribute.h"
diff --git a/source/blender/blenlib/BLI_virtual_array.hh b/source/blender/blenlib/BLI_virtual_array.hh
new file mode 100644
index 00000000000..51d2e820504
--- /dev/null
+++ b/source/blender/blenlib/BLI_virtual_array.hh
@@ -0,0 +1,211 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ *
+ * A virtual array is a data structure that behaves similar to an array, but its elements are
+ * accessed through virtual methods. This improves the decoupling of a function from its callers,
+ * because it does not have to know exactly how the data is layed out in memory, or if it is stored
+ * in memory at all. It could just as well be computed on the fly.
+ *
+ * Taking a virtual array as parameter instead of a more specific non-virtual type has some
+ * tradeoffs. Access to individual elements of the individual elements is higher due to function
+ * call overhead. On the other hand, potential callers don't have to convert the data into the
+ * specific format required for the function. This can be a costly conversion if only few of the
+ * elements are accessed in the end.
+ *
+ * Functions taking a virtual array as input can still optimize for different data layouts. For
+ * example, they can check if the array is stored as an array internally or if it is the same
+ * element for all indices. Whether it is worth to optimize for different data layouts in a
+ * function has to be decided on a case by case basis. One should always do some benchmarking to
+ * see of the increased compile time and binary size is worth it.
+ */
+
+#include "BLI_span.hh"
+
+namespace blender {
+
+/* An immutable virtual array. */
+template<typename T> class VArray {
+ protected:
+ int64_t size_;
+
+ public:
+ VArray(const int64_t size) : size_(size)
+ {
+ BLI_assert(size_ >= 0);
+ }
+
+ virtual ~VArray() = default;
+
+ T get(const int64_t index) const
+ {
+ BLI_assert(index >= 0);
+ BLI_assert(index < size_);
+ return this->get_impl(index);
+ }
+
+ int64_t size() const
+ {
+ return size_;
+ }
+
+ bool is_empty() const
+ {
+ return size_ == 0;
+ }
+
+ /* Returns true when the virtual array is stored as a span internally. */
+ bool is_span() const
+ {
+ if (size_ == 0) {
+ return true;
+ }
+ return this->is_span_impl();
+ }
+
+ /* Returns the internally used span of the virtual array. This invokes undefined behavior is the
+ * virtual array is not stored as a span internally. */
+ Span<T> get_span() const
+ {
+ BLI_assert(this->is_span());
+ if (size_ == 0) {
+ return {};
+ }
+ return this->get_span_impl();
+ }
+
+ /* Returns true when the virtual array returns the same value for every index. */
+ bool is_single() const
+ {
+ if (size_ == 1) {
+ return true;
+ }
+ return this->is_single_impl();
+ }
+
+ /* Returns the value that is returned for every index. This invokes undefined behavior if the
+ * virtual array would not return the same value for every index. */
+ T get_single() const
+ {
+ BLI_assert(this->is_single());
+ if (size_ == 1) {
+ return this->get(0);
+ }
+ return this->get_single_impl();
+ }
+
+ T operator[](const int64_t index) const
+ {
+ return this->get(index);
+ }
+
+ protected:
+ virtual T get_impl(const int64_t index) const = 0;
+
+ virtual bool is_span_impl() const
+ {
+ return false;
+ }
+
+ virtual Span<T> get_span_impl() const
+ {
+ BLI_assert(false);
+ return {};
+ }
+
+ virtual bool is_single_impl() const
+ {
+ return false;
+ }
+
+ virtual T get_single_impl() const
+ {
+ /* Provide a default implementation, so that subclasses don't have to provide it. This method
+ * should never be called because `is_single_impl` returns false by default. */
+ BLI_assert(false);
+ return T();
+ }
+};
+
+/* A virtual array implementation for a span. */
+template<typename T> class VArrayForSpan : public VArray<T> {
+ private:
+ const T *data_;
+
+ public:
+ VArrayForSpan(const Span<T> data) : VArray<T>(data.size()), data_(data.data())
+ {
+ }
+
+ protected:
+ T get_impl(const int64_t index) const override
+ {
+ return data_[index];
+ }
+
+ bool is_span_impl() const override
+ {
+ return true;
+ }
+
+ Span<T> get_span_impl() const override
+ {
+ return Span<T>(data_, this->size_);
+ }
+};
+
+/* A virtual array implementation that returns the same value for every index. */
+template<typename T> class VArrayForSingle : public VArray<T> {
+ private:
+ T value_;
+
+ public:
+ VArrayForSingle(T value, const int64_t size) : VArray<T>(size), value_(std::move(value))
+ {
+ }
+
+ protected:
+ T get_impl(const int64_t UNUSED(index)) const override
+ {
+ return value_;
+ }
+
+ bool is_span_impl() const override
+ {
+ return this->size_ == 1;
+ }
+
+ Span<T> get_span_impl() const override
+ {
+ return Span<T>(&value_, 1);
+ }
+
+ bool is_single_impl() const override
+ {
+ return true;
+ }
+
+ T get_single_impl() const override
+ {
+ return value_;
+ }
+};
+
+} // namespace blender
diff --git a/source/blender/blenlib/BLI_virtual_vector_array.hh b/source/blender/blenlib/BLI_virtual_vector_array.hh
new file mode 100644
index 00000000000..ab5afd2d80a
--- /dev/null
+++ b/source/blender/blenlib/BLI_virtual_vector_array.hh
@@ -0,0 +1,95 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#pragma once
+
+/** \file
+ * \ingroup bli
+ *
+ * A virtual vector array gives access to an array of vectors. The individual vectors in the array
+ * can have different sizes.
+ *
+ * The tradeoffs here are similar to virtual arrays.
+ */
+
+#include "BLI_virtual_array.hh"
+
+namespace blender {
+
+/* A readonly virtual array of vectors. */
+template<typename T> class VVectorArray {
+ protected:
+ int64_t size_;
+
+ public:
+ VVectorArray(const int64_t size) : size_(size)
+ {
+ BLI_assert(size >= 0);
+ }
+
+ virtual ~VVectorArray() = default;
+
+ /* Returns the number of vectors in the vector array. */
+ int64_t size() const
+ {
+ return size_;
+ }
+
+ /* Returns true when there is no vector in the vector array. */
+ bool is_empty() const
+ {
+ return size_ == 0;
+ }
+
+ /* Returns the size of the vector at the given index. */
+ int64_t get_vector_size(const int64_t index) const
+ {
+ BLI_assert(index >= 0);
+ BLI_assert(index < size_);
+ return this->get_vector_size_impl(index);
+ }
+
+ /* Returns an element from one of the vectors. */
+ T get_vector_element(const int64_t index, const int64_t index_in_vector) const
+ {
+ BLI_assert(index >= 0);
+ BLI_assert(index < size_);
+ BLI_assert(index_in_vector >= 0);
+ BLI_assert(index_in_vector < this->get_vector_size(index));
+ return this->get_vector_element_impl(index, index_in_vector);
+ }
+
+ /* Returns true when the same vector is used at every index. */
+ bool is_single_vector() const
+ {
+ if (size_ == 1) {
+ return true;
+ }
+ return this->is_single_vector_impl();
+ }
+
+ protected:
+ virtual int64_t get_vector_size_impl(const int64_t index) const = 0;
+
+ virtual T get_vector_element_impl(const int64_t index, const int64_t index_in_vetor) const = 0;
+
+ virtual bool is_single_vector_impl() const
+ {
+ return false;
+ }
+};
+
+} // namespace blender
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index 5a851b7b2cb..37b0f742b8b 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -296,6 +296,8 @@ set(SRC
BLI_vector_set.hh
BLI_vector_set_slots.hh
BLI_vfontdata.h
+ BLI_virtual_array.hh
+ BLI_virtual_vector_array.hh
BLI_voronoi_2d.h
BLI_voxel.h
BLI_winstuff.h
@@ -432,6 +434,7 @@ if(WITH_GTESTS)
tests/BLI_task_test.cc
tests/BLI_vector_set_test.cc
tests/BLI_vector_test.cc
+ tests/BLI_virtual_array_test.cc
tests/BLI_exception_safety_test_utils.hh
)
diff --git a/source/blender/blenlib/tests/BLI_virtual_array_test.cc b/source/blender/blenlib/tests/BLI_virtual_array_test.cc
new file mode 100644
index 00000000000..ac25229cd69
--- /dev/null
+++ b/source/blender/blenlib/tests/BLI_virtual_array_test.cc
@@ -0,0 +1,31 @@
+/* Apache License, Version 2.0 */
+
+#include "BLI_strict_flags.h"
+#include "BLI_virtual_array.hh"
+#include "testing/testing.h"
+
+namespace blender::tests {
+
+TEST(virtual_array, ForSpan)
+{
+ std::array<int,
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list