Mesh: Parallelize vertex and edge to corner topology map creation #110707

Iliya Katushenock · 2023-08-02T00:53:40+02:00

Iliya Katushenock commented

2023-08-02 00:53:40 +02:00

Make the algorithm more parallelizable. For 8.000.000 edges,
this function has become 4.5x times faster (509.1 ms -> 136.2 ms).
*Called from Edge Split node for cuboid [1].

https://hackmd.io/@s0TMIS4lTAGwHVO20ECwpw/build_edge_to_loop_map_tests.

Make the algorithm more parallelizable. For 8.000.000 edges, this function has become 4.5x times faster (509.1 ms -> 136.2 ms). *Called from Edge Split node for cuboid [1]. 1. https://hackmd.io/@s0TMIS4lTAGwHVO20ECwpw/build_edge_to_loop_map_tests.

👍 3 ❤️ 1 🎉 2

Iliya Katushenock added 7 commits 2023-08-02 00:53:51 +02:00

Iliya Katushenock requested review from Hans Goudey 2023-08-02 00:53:58 +02:00

Hans Goudey commented

2023-08-02 14:05:52 +02:00

2x faster is quite nice! This looks very clever. But I wonder if parallel sorting is the best solution, since it's so global-- it starts by acting on the entire domain.

I didn't do my own performance testing of this PR though, with 32 threads the benefit might be larger.

Here's my guess for another approach (not tested, just a sketch!):

diff --git a/source/blender/blenkernel/intern/mesh_mapping.cc b/source/blender/blenkernel/intern/mesh_mapping.cc
index 53a8200dc4d..c1d9a16d3a6 100644
--- a/source/blender/blenkernel/intern/mesh_mapping.cc
+++ b/source/blender/blenkernel/intern/mesh_mapping.cc
@@ -29,6 +29,8 @@
 
 #include "BLI_strict_flags.h"
 
+#include "atomic_ops.h"
+
 /* -------------------------------------------------------------------- */
 /** \name Mesh Connectivity Mapping
  * \{ */
@@ -374,12 +376,27 @@ GroupedSpan<int> build_edge_to_loop_map(const Span<int> corner_edges,
   r_offsets = create_reverse_offsets(corner_edges, edges_num);
   r_indices.reinitialize(r_offsets.last());
   Array<int> counts(edges_num, 0);
-
-  for (const int64_t corner : corner_edges.index_range()) {
-    const int edge = corner_edges[corner];
-    r_indices[r_offsets[edge] + counts[edge]] = int(corner);
-    counts[edge]++;
-  }
+  const OffsetIndices offsets(r_offsets.as_span());
+
+  threading::parallel_for(IndexRange(edges_num), 4096, [&](const IndexRange range) {
+    for (const int64_t corner : range) {
+      const int edge = corner_edges[corner];
+      const IndexRange range = offsets[edge];
+
+      int old_count = counts[edge];
+      while (true) {
+        old_count = counts[edge];
+        if (atomic_cas_int32(&counts[edge], old_count, old_count + 1)) {
+          r_indices[range[counts[edge]]] = int(corner);
+          break;
+        }
+      }
+      if (old_count + 1 == range.size()) {
+        MutableSpan edge_corners = r_indices.as_mutable_span().slice(range);
+        std::sort(edge_corners.begin(), edge_corners.end());
+      }
+    }
+  });
   return {OffsetIndices<int>(r_offsets), r_indices};
 }
 
 }

The downside is that it still needs the "counts" array, and the offsets and indices can't be built in parallel. But at least each chunk of work is smaller. Maybe worth looking into-- not sure.

2x faster is quite nice! This looks very clever. But I wonder if parallel sorting is the best solution, since it's so global-- it starts by acting on the entire domain. I didn't do my own performance testing of this PR though, with 32 threads the benefit might be larger. Here's my guess for another approach (not tested, just a sketch!): ```diff diff --git a/source/blender/blenkernel/intern/mesh_mapping.cc b/source/blender/blenkernel/intern/mesh_mapping.cc index 53a8200dc4d..c1d9a16d3a6 100644 --- a/source/blender/blenkernel/intern/mesh_mapping.cc +++ b/source/blender/blenkernel/intern/mesh_mapping.cc @@ -29,6 +29,8 @@ #include "BLI_strict_flags.h" +#include "atomic_ops.h" + /* -------------------------------------------------------------------- */ /** \name Mesh Connectivity Mapping * \{ */ @@ -374,12 +376,27 @@ GroupedSpan<int> build_edge_to_loop_map(const Span<int> corner_edges, r_offsets = create_reverse_offsets(corner_edges, edges_num); r_indices.reinitialize(r_offsets.last()); Array<int> counts(edges_num, 0); - - for (const int64_t corner : corner_edges.index_range()) { - const int edge = corner_edges[corner]; - r_indices[r_offsets[edge] + counts[edge]] = int(corner); - counts[edge]++; - } + const OffsetIndices offsets(r_offsets.as_span()); + + threading::parallel_for(IndexRange(edges_num), 4096, [&](const IndexRange range) { + for (const int64_t corner : range) { + const int edge = corner_edges[corner]; + const IndexRange range = offsets[edge]; + + int old_count = counts[edge]; + while (true) { + old_count = counts[edge]; + if (atomic_cas_int32(&counts[edge], old_count, old_count + 1)) { + r_indices[range[counts[edge]]] = int(corner); + break; + } + } + if (old_count + 1 == range.size()) { + MutableSpan edge_corners = r_indices.as_mutable_span().slice(range); + std::sort(edge_corners.begin(), edge_corners.end()); + } + } + }); return {OffsetIndices<int>(r_offsets), r_indices}; } } ``` The downside is that it still needs the "counts" array, and the offsets and indices can't be built in parallel. But at least each chunk of work is smaller. Maybe worth looking into-- not sure.

Iliya Katushenock commented

2023-08-02 14:23:10 +02:00

Thanks for the other option, I'll try it out as well.
Small addition: I improved the Point to Curve node today, and also applied this technique with sorting iota-groups. Apparently, separating create_reverse_offsets and gather_reverse into different threads is not such a good idea.
And following the conclusions, i can assume that sorting itself is 2 times faster than loop with random-memory incrementation. It's just that create_reverse_offsets and the gather_reverse are parallelized well enough to interfere with each other. It will be necessary to make their calls sequential ....

Thanks for the other option, I'll try it out as well. Small addition: I improved the Point to Curve node today, and also applied this technique with sorting iota-groups. Apparently, separating `create_reverse_offsets` and `gather_reverse` into different threads is not such a good idea. And following the conclusions, i can assume that sorting itself is 2 times faster than loop with random-memory incrementation. It's just that `create_reverse_offsets` and the `gather_reverse` are parallelized well enough to interfere with each other. It will be necessary to make their calls sequential ....

Hans Goudey commented

2023-08-02 14:28:42 +02:00

Interesting! parallel_invoke might make sense in a sweet spot where the individual callbacks don't have quite enough work to be worth parallelizing, but that probably doesn't make sense here yet.

Interesting! `parallel_invoke` might make sense in a sweet spot where the individual callbacks don't have quite enough work to be worth parallelizing, but that probably doesn't make sense here yet.

Hans Goudey referenced this pull request

2023-08-02 14:55:46 +02:00

Mesh: Rewrite split edges algorithm #110661

Iliya Katushenock commented

2023-08-02 16:38:19 +02:00

I was able to achieve a 2.4 gain with only multi-step sorts. Probably, if memory was dear to us, then this would be a solution.
But we want speed (since the speed of cpu grows more slowly than the amount of ram). So in the end, having an array of indices, your variant turned out to be 1.7 times faster than the best my sort result!
So the end result is 509.1 ms -> 136.2 ms!

All tests: https://hackmd.io/@s0TMIS4lTAGwHVO20ECwpw/build_edge_to_loop_map_tests

I was able to achieve a 2.4 gain with only multi-step sorts. Probably, if memory was dear to us, then this would be a solution. But we want speed (since the speed of cpu grows more slowly than the amount of ram). So in the end, having an array of indices, your variant turned out to be 1.7 times faster than the best my sort result! So the end result is 509.1 ms -> 136.2 ms! All tests: https://hackmd.io/@s0TMIS4lTAGwHVO20ECwpw/build_edge_to_loop_map_tests

Iliya Katushenock added 1 commit 2023-08-02 16:40:28 +02:00

027780d7ec progress

Iliya Katushenock added 1 commit 2023-08-02 16:45:08 +02:00

a1c579063e cleanup

Hans Goudey reviewed 2023-08-02 17:03:00 +02:00

source/blender/blenkernel/intern/mesh_mapping.cc Outdated

						
				@ -366,20 +368,39 @@ GroupedSpan<int> build_vert_to_loop_map(const Span<int> corner_verts,

				  return {OffsetIndices<int>(r_offsets), r_indices};

				}

				static void sort_groups(const OffsetIndices<int> groups, MutableSpan<int> indices)

Hans Goudey commented

2023-08-02 17:02:57 +02:00

Did you find it better to sort the entire array once at the end?
I imagined that sorting the moment each group was full would make better use of caches, since the small group of data would already be in L1 or L2 cache of that thread

Did you find it better to sort the entire array once at the end? I imagined that sorting the moment each group was full would make better use of caches, since the small group of data would already be in L1 or L2 cache of that thread

Iliya Katushenock commented

2023-08-02 17:19:04 +02:00

The problem is that we don't have a group from the start. By iterating over the corner edge indices, we can have random edges rather than already grouped ones. This means that only at the end it can be done.

Hans Goudey commented

2023-08-02 17:20:27 +02:00

Okay, right, applying the same logic from my other comment, this makes sense. Thanks.

HooglyBoogly marked this conversation as resolved

source/blender/blenkernel/intern/mesh_mapping.cc Outdated

						
				@ -383,0 +397,4 @@

				      const int edge = corner_edges[corner];

				      const IndexRange range = offsets[edge];

				      const int index = atomic_add_and_fetch_int32(&counts[edge], 1);

				      r_indices[range[index]] = int(corner);

Hans Goudey commented

2023-08-02 17:01:44 +02:00

Not sure this works-- imagine that each thread might pause for an unknown about of time between these two lines:

const int index = atomic_add_and_fetch_int32(&counts[edge], 1);
r_indices[range[index]] = int(corner);

So there needs to be some mechanism to prevent multiple threads from reaching r_indices[...] = for the same index at the same time. I think that's what I was doing with the while (true) loop in my example

Not sure this works-- imagine that each thread might pause for an unknown about of time between these two lines: ``` const int index = atomic_add_and_fetch_int32(&counts[edge], 1); r_indices[range[index]] = int(corner); ``` So there needs to be some mechanism to prevent multiple threads from reaching `r_indices[...] = ` for the same index at the same time. I _think_ that's what I was doing with the `while (true)` loop in my example

Iliya Katushenock commented

2023-08-02 17:17:23 +02:00

Imagine that counts is an array of iterators.
Each thread can make a step and get the value of the random iterator. This means that each iterator will reach its end in the end of all.
And each thread will only see its own value of each iterator. That is, only one line (atomic_add_and_fetch_int32) works with a lock. And its result is a unique index in the group.

Imagine that `counts` is an array of iterators. Each thread can make a step and get the value of the random iterator. This means that each iterator will reach its end in the end of all. And each thread will only see its own value of each iterator. That is, only one line (`atomic_add_and_fetch_int32`) works with a lock. And its result is a unique index in the group.

Hans Goudey commented

2023-08-02 17:19:17 +02:00

Ah, makes sense, since the order doesn't matter here, since they're sorted later. Very nice!

HooglyBoogly marked this conversation as resolved

Hans Goudey reviewed 2023-08-02 17:21:49 +02:00

source/blender/blenkernel/intern/mesh_mapping.cc Outdated

						
				@ -368,1 +370,4 @@

				static void sort_groups(const OffsetIndices<int> groups, MutableSpan<int> indices)

				{

				  const auto comparator = [&](const int index_a, const int index_b) { return index_a < index_b; };

Hans Goudey commented

2023-08-02 17:21:49 +02:00

Could you pass this lambda directly to std::sort? Also, no need for a capture, [] would be fine

Could you pass this lambda directly to `std::sort`? Also, no need for a capture, `[]` would be fine

😆 1

Jacques Lucke commented

2023-08-02 17:31:41 +02:00

Is the lambda necessary at all?

🚀 1

Iliya Katushenock commented

2023-08-02 17:34:23 +02:00

Yep, just noticed this.

mod_moder marked this conversation as resolved

Hans Goudey commented

2023-08-02 17:39:42 +02:00

Could you also look into changing the vertex to corner map in this PR? The code could be shared actually, similarly to mapped_corner_selection_from_face

Could you also look into changing the vertex to corner map in this PR? The code could be shared actually, similarly to `mapped_corner_selection_from_face`

👍 1

Iliya Katushenock added 2 commits 2023-08-02 19:11:07 +02:00

077a0b32f5 Merge branch 'main' into tmp_edge_to_loop_speedup

434c6e59ec debug check

Iliya Katushenock added 1 commit 2023-08-02 19:42:00 +02:00

491a21e7bb progress

Iliya Katushenock commented

2023-08-02 19:43:39 +02:00

Added some assertions and also genirilized the names. For the Point to Curves node, this function will be just as useful, it can be moved to another place later.

Iliya Katushenock changed title from ~~Geometry Nodes: Improvement of topology map function~~ to Geometry Nodes: Improvement of topology map function with gather_groups

2023-08-02 19:44:00 +02:00

Hans Goudey reviewed 2023-08-02 19:44:57 +02:00

source/blender/blenkernel/intern/mesh_mapping.cc Outdated

						
				@ -307,1 +309,4 @@

				static void sort_small_groups(const OffsetIndices<int> groups,

				                              MutableSpan<int> indices,

				                              const int grai_size = 1024)

Hans Goudey commented

2023-08-02 19:44:57 +02:00

typo: grai_size -> grain_size

typo: `grai_size` -> `grain_size`

mod_moder marked this conversation as resolved

Iliya Katushenock added 1 commit 2023-08-02 19:47:33 +02:00

70a1393a33 fix typo

Hans Goudey reviewed 2023-08-02 20:02:40 +02:00

source/blender/blenkernel/intern/mesh_mapping.cc Outdated

						
				@ -308,0 +331,4 @@

				    for (const int64_t i : range) {

				      const int group = group_indices[i];

				      const int index = atomic_add_and_fetch_int32(&counts[group], 1);

				      const IndexRange range = offsets[group];

Hans Goudey commented

2023-08-02 20:02:40 +02:00

/home/hans/blender-git/blender/source/blender/blenkernel/intern/mesh_mapping.cc:334:24: error: declaration of ‘const blender::IndexRange range’ shadows a parameter [-Werror=shadow]
  334 |       const IndexRange range = offsets[group];
      |                        ^~~~~

``` /home/hans/blender-git/blender/source/blender/blenkernel/intern/mesh_mapping.cc:334:24: error: declaration of ‘const blender::IndexRange range’ shadows a parameter [-Werror=shadow] 334 | const IndexRange range = offsets[group]; | ^~~~~ ```

mod_moder marked this conversation as resolved

Hans Goudey changed title from ~~Geometry Nodes: Improvement of topology map function with gather_groups~~ to Mesh: Parallelize vertex and edge to corner topology map creation

2023-08-02 20:08:16 +02:00

Iliya Katushenock added 1 commit 2023-08-02 20:23:43 +02:00

ae8a16c85f fix name re-error

Iliya Katushenock added 1 commit 2023-08-02 21:09:00 +02:00

buildbot/vexp-code-patch-coordinator Build done. Details

9715b0d74b progress

Hans Goudey approved these changes 2023-08-22 00:53:49 +02:00

Hans Goudey left a comment

I'd like to test this again on my desktop when I get back home this weekend, just to corroborate the performance numbers. Other than that, the code looks quite good now given your explorations of alternative solutions I'm fairly confident this is at least a good solution.

source/blender/blenkernel/intern/mesh_mapping.cc

						
				@ -308,0 +343,4 @@

				                                      Array<int> &r_offsets,

				                                      Array<int> &r_indices)

				{

				  if (group_indices.is_empty()) {

Hans Goudey commented

2023-08-03 14:57:38 +02:00

Is this is_empty() case necessary? I guess it's because of the asserts in reverse_indices_in_groups?

Is this `is_empty()` case necessary? I guess it's because of the asserts in `reverse_indices_in_groups`?

Iliya Katushenock commented

2023-08-22 01:03:11 +02:00

I found it a little odd that we are still allocating an array just for the sake of empty groups to work. I decided to formalize this state here. Maybe later it will be possible not to do this ...

Hans Goudey commented

2023-08-22 01:06:16 +02:00

I usually find it better to handle the "empty" case implicitly later in the code-- performance should be totally fine, especially with small buffer optimization and the fact that this code might not even get called in the "important" cases anyway.

Iliya Katushenock commented

2023-08-22 02:14:27 +02:00

Also, yes, new code can have problems with empty group indices, so it's also required to be intercepted.