Geometry Nodes: multi threaded field evaluation

This adds a new `ParallelMultiFunction` which wraps another multi-function
and evaluates it with multiple threads. The speeds up field evaluation
quite a bit (the effect is most noticeable when the number of evaluations
and the field is large).

There are still other single-threaded performance bottlenecks in field
evaluation that will need to be solved separately. Most notably here
is the process of copying the computed data into the position attribute
in the Set Position node.

Differential Revision: https://developer.blender.org/D12457

4 files changed, 85 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_index_mask.hh b/source/blender/blenlib/BLI_index_mask.hh
index 7a3169520ca..ad030e127fe 100644
--- a/source/blender/blenlib/BLI_index_mask.hh
+++ b/source/blender/blenlib/BLI_index_mask.hh
@@ -39,6 +39,7 @@
 
 #include "BLI_index_range.hh"
 #include "BLI_span.hh"
+#include "BLI_vector.hh"
 
 namespace blender {
 
@@ -221,6 +222,8 @@ class IndexMask {
   {
     return indices_.is_empty();
   }
+
+  IndexMask slice_and_offset(IndexRange slice, Vector<int64_t> &r_new_indices) const;
 };
 
 }  // namespace blender
diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt
index fc058793d11..f607285c4d0 100644
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@ -86,6 +86,7 @@ set(SRC
   intern/hash_md5.c
   intern/hash_mm2a.c
   intern/hash_mm3.c
+  intern/index_mask.cc
   intern/jitter_2d.c
   intern/kdtree_1d.c
   intern/kdtree_2d.c
diff --git a/source/blender/blenlib/intern/index_mask.cc b/source/blender/blenlib/intern/index_mask.cc
new file mode 100644
index 00000000000..cba985b8a44
--- /dev/null
+++ b/source/blender/blenlib/intern/index_mask.cc
@@ -0,0 +1,57 @@
+/*
+ * 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.
+ */
+
+#include "BLI_index_mask.hh"
+
+namespace blender {
+
+/**
+ * Create a sub-mask that is also shifted to the beginning. The shifting to the beginning allows
+ * code to work with smaller indices, which is more memory efficient.
+ *
+ * \return New index mask with the size of #slice. It is either empty or starts with 0. It might
+ * reference indices that have been appended to #r_new_indices.
+ *
+ * Example:
+ *  this:   [2, 3, 5, 7, 8, 9, 10]
+ *  slice:      ^--------^
+ *  output: [0, 2, 4, 5]
+ *
+ *  All the indices in the sub-mask are shifted by 3 towards zero, so that the first index in the
+ *  output is zero.
+ */
+IndexMask IndexMask::slice_and_offset(const IndexRange slice, Vector<int64_t> &r_new_indices) const
+{
+  const int slice_size = slice.size();
+  if (slice_size == 0) {
+    return {};
+  }
+  IndexMask sliced_mask{indices_.slice(slice)};
+  if (sliced_mask.is_range()) {
+    return IndexMask(slice_size);
+  }
+  const int64_t offset = sliced_mask.indices().first();
+  if (offset == 0) {
+    return sliced_mask;
+  }
+  r_new_indices.resize(slice_size);
+  for (const int i : IndexRange(slice_size)) {
+    r_new_indices[i] = sliced_mask[i] - offset;
+  }
+  return IndexMask(r_new_indices.as_span());
+}
+
+}  // namespace blender
diff --git a/source/blender/blenlib/tests/BLI_index_mask_test.cc b/source/blender/blenlib/tests/BLI_index_mask_test.cc
index 4d6060e51c9..0778d71df01 100644
--- a/source/blender/blenlib/tests/BLI_index_mask_test.cc
+++ b/source/blender/blenlib/tests/BLI_index_mask_test.cc
@@ -40,4 +40,28 @@ TEST(index_mask, RangeConstructor)
   EXPECT_EQ(indices[2], 5);
 }
 
+TEST(index_mask, SliceAndOffset)
+{
+  Vector<int64_t> indices;
+  {
+    IndexMask mask{IndexRange(10)};
+    IndexMask new_mask = mask.slice_and_offset(IndexRange(3, 5), indices);
+    EXPECT_TRUE(new_mask.is_range());
+    EXPECT_EQ(new_mask.size(), 5);
+    EXPECT_EQ(new_mask[0], 0);
+    EXPECT_EQ(new_mask[1], 1);
+  }
+  {
+    Vector<int64_t> original_indices = {2, 3, 5, 7, 8, 9, 10};
+    IndexMask mask{original_indices.as_span()};
+    IndexMask new_mask = mask.slice_and_offset(IndexRange(1, 4), indices);
+    EXPECT_FALSE(new_mask.is_range());
+    EXPECT_EQ(new_mask.size(), 4);
+    EXPECT_EQ(new_mask[0], 0);
+    EXPECT_EQ(new_mask[1], 2);
+    EXPECT_EQ(new_mask[2], 4);
+    EXPECT_EQ(new_mask[3], 5);
+  }
+}
+
 }  // namespace blender::tests