BKE: parallelize BKE_mesh_calc_edges

`BKE_mesh_calc_edges` was the main performance bottleneck in D9141.
While openvdb only needed ~115ms, calculating the edges afterwards
took ~960ms. Now with some parallelization this is reduced to ~210ms.

Parallelizing `BKE_mesh_calc_edges` is not entirely trivial, because it
has to perform deduplication and some other things that have to happen
in a certain order. Even though the multithreading improves performance
with more threads, there are diminishing returns when too many threads
are used in this function.

The speedup is mainly achieved by having multiple hash tables that are
filled in parallel. The distribution of the edges to hash tables is based on
a hash (that is different from the hash used in the actual hash tables).

I moved the function to C++, because that made it easier for me to
optimize it. Furthermore, I added `BLI_task.hh` which contains some
light tbb wrappers for parallelization.

Reviewers: campbellbarton

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

1 files changed, 63 insertions, 0 deletions

diff --git a/source/blender/blenlib/BLI_task.hh b/source/blender/blenlib/BLI_task.hh
new file mode 100644
index 00000000000..7e60f271e9d
--- /dev/null
+++ b/source/blender/blenlib/BLI_task.hh
@@ -0,0 +1,63 @@
+/*
+ * 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
+ */
+
+#ifdef WITH_TBB
+/* Quiet top level deprecation message, unrelated to API usage here. */
+#  define TBB_SUPPRESS_DEPRECATED_MESSAGES 1
+#  include <tbb/tbb.h>
+#endif
+
+#include "BLI_index_range.hh"
+#include "BLI_utildefines.h"
+
+namespace blender {
+
+template<typename Range, typename Function>
+void parallel_for_each(Range &range, const Function &function)
+{
+#ifdef WITH_TBB
+  tbb::parallel_for_each(range, function);
+#else
+  for (auto &value : range) {
+    function(value);
+  }
+#endif
+}
+
+template<typename Function>
+void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
+{
+  if (range.size() == 0) {
+    return;
+  }
+#ifdef WITH_TBB
+  tbb::parallel_for(tbb::blocked_range<int64_t>(range.first(), range.one_after_last(), grain_size),
+                    [&](const tbb::blocked_range<int64_t> &subrange) {
+                      function(IndexRange(subrange.begin(), subrange.size()));
+                    });
+#else
+  UNUSED_VARS(grain_size);
+  function(range);
+#endif
+}
+
+}  // namespace blender