Further speedup of new obj exporter.

This change from Aras further parallelizes wihin large meshes (the previous one
just parallelized over objects).

Some stats: on A Windows machine, AMD Ryzen (32 threads):

(one mesh) Monkey subdivided to level 6: 4.9s -> 1.2s (blender 3.1 was 6.3s; 3.0 was 49.4s).
(one mesh) "Rungholt" minecraft level: 8.5s -> 2.9s (3.1 was 10.5s; 3.0 was 73.7s).
(lots of meshes) Blender 3 splash: 6.2s -> 5.2s (3.1 was 48.9s; 3.0 was 392.3s).

On a Linux machine (Threadripper, 48 threads, writing to SSD):
Monkey - 5.08s -> 1.18s (4.2x speedup)
Rungholt - 9.52s -> 3.22s (2.95x speedup)
Blender 3 splash - 5.91s -> 4.61s (1.28x speedup)

For details see patch D14028.

3 files changed, 131 insertions, 121 deletions

diff --git a/source/blender/io/wavefront_obj/exporter/obj_export_file_writer.cc b/source/blender/io/wavefront_obj/exporter/obj_export_file_writer.cc
index 13d1a4fdde6..87f87e37a7e 100644
--- a/source/blender/io/wavefront_obj/exporter/obj_export_file_writer.cc
+++ b/source/blender/io/wavefront_obj/exporter/obj_export_file_writer.cc
@@ -24,6 +24,7 @@
 #include "BKE_blender_version.h"
 
 #include "BLI_path_util.h"
+#include "BLI_task.hh"
 
 #include "obj_export_mesh.hh"
 #include "obj_export_mtl.hh"
@@ -167,108 +168,85 @@ void OBJWriter::write_object_name(FormatHandler<eFileType::OBJ> &fh,
   fh.write<eOBJSyntaxElement::object_name>(object_name);
 }
 
-void OBJWriter::write_vertex_coords(FormatHandler<eFileType::OBJ> &fh,
-                                    const OBJMesh &obj_mesh_data) const
+/* Split up large meshes into multi-threaded jobs; each job processes
+ * this amount of items. */
+static const int chunk_size = 32768;
+static int calc_chunk_count(int count)
 {
-  const int tot_vertices = obj_mesh_data.tot_vertices();
-  for (int i = 0; i < tot_vertices; i++) {
-    float3 vertex = obj_mesh_data.calc_vertex_coords(i, export_params_.scaling_factor);
-    fh.write<eOBJSyntaxElement::vertex_coords>(vertex[0], vertex[1], vertex[2]);
-  }
+  return (count + chunk_size - 1) / chunk_size;
 }
 
-void OBJWriter::write_uv_coords(FormatHandler<eFileType::OBJ> &fh, OBJMesh &r_obj_mesh_data) const
+/* Write /tot_count/ items to OBJ file output. Each item is written
+ * by a /function/ that should be independent from other items.
+ * If the amount of items is large enough (> chunk_size), then writing
+ * will be done in parallel, into temporary FormatHandler buffers that
+ * will be written into the final /fh/ buffer at the end.
+ */
+template<typename Function>
+void obj_parallel_chunked_output(FormatHandler<eFileType::OBJ> &fh,
+                                 int tot_count,
+                                 const Function &function)
 {
-  for (const float2 &uv_vertex : r_obj_mesh_data.get_uv_coords()) {
-    fh.write<eOBJSyntaxElement::uv_vertex_coords>(uv_vertex[0], uv_vertex[1]);
+  if (tot_count <= 0) {
+    return;
   }
-}
-
-void OBJWriter::write_poly_normals(FormatHandler<eFileType::OBJ> &fh, OBJMesh &obj_mesh_data)
-{
-  /* Poly normals should be calculated earlier via store_normal_coords_and_indices. */
-  for (const float3 &normal : obj_mesh_data.get_normal_coords()) {
-    fh.write<eOBJSyntaxElement::normal>(normal[0], normal[1], normal[2]);
+  /* If we have just one chunk, process it directly into the output
+   * buffer - avoids all the job scheduling and temporary vector allocation
+   * overhead. */
+  const int chunk_count = calc_chunk_count(tot_count);
+  if (chunk_count == 1) {
+    for (int i = 0; i < tot_count; i++) {
+      function(fh, i);
+    }
+    return;
+  }
+  /* Give each chunk its own temporary output buffer, and process them in parallel. */
+  std::vector<FormatHandler<eFileType::OBJ>> buffers(chunk_count);
+  blender::threading::parallel_for(IndexRange(chunk_count), 1, [&](IndexRange range) {
+    for (const int r : range) {
+      int i_start = r * chunk_size;
+      int i_end = std::min(i_start + chunk_size, tot_count);
+      auto &buf = buffers[r];
+      for (int i = i_start; i < i_end; i++) {
+        function(buf, i);
+      }
+    }
+  });
+  /* Emit all temporary output buffers into the destination buffer. */
+  for (auto &buf : buffers) {
+    fh.append_from(buf);
   }
 }
 
-int OBJWriter::write_smooth_group(FormatHandler<eFileType::OBJ> &fh,
-                                  const OBJMesh &obj_mesh_data,
-                                  const int poly_index,
-                                  const int last_poly_smooth_group) const
+void OBJWriter::write_vertex_coords(FormatHandler<eFileType::OBJ> &fh,
+                                    const OBJMesh &obj_mesh_data) const
 {
-  int current_group = SMOOTH_GROUP_DISABLED;
-  if (!export_params_.export_smooth_groups && obj_mesh_data.is_ith_poly_smooth(poly_index)) {
-    /* Smooth group calculation is disabled, but polygon is smooth-shaded. */
-    current_group = SMOOTH_GROUP_DEFAULT;
-  }
-  else if (obj_mesh_data.is_ith_poly_smooth(poly_index)) {
-    /* Smooth group calc is enabled and polygon is smooth–shaded, so find the group. */
-    current_group = obj_mesh_data.ith_smooth_group(poly_index);
-  }
-
-  if (current_group == last_poly_smooth_group) {
-    /* Group has already been written, even if it is "s 0". */
-    return current_group;
-  }
-  fh.write<eOBJSyntaxElement::smooth_group>(current_group);
-  return current_group;
+  const int tot_count = obj_mesh_data.tot_vertices();
+  obj_parallel_chunked_output(fh, tot_count, [&](FormatHandler<eFileType::OBJ> &buf, int i) {
+    float3 vertex = obj_mesh_data.calc_vertex_coords(i, export_params_.scaling_factor);
+    buf.write<eOBJSyntaxElement::vertex_coords>(vertex[0], vertex[1], vertex[2]);
+  });
 }
 
-int16_t OBJWriter::write_poly_material(FormatHandler<eFileType::OBJ> &fh,
-                                       const OBJMesh &obj_mesh_data,
-                                       const int poly_index,
-                                       const int16_t last_poly_mat_nr,
-                                       std::function<const char *(int)> matname_fn) const
+void OBJWriter::write_uv_coords(FormatHandler<eFileType::OBJ> &fh, OBJMesh &r_obj_mesh_data) const
 {
-  if (!export_params_.export_materials || obj_mesh_data.tot_materials() <= 0) {
-    return last_poly_mat_nr;
-  }
-  const int16_t current_mat_nr = obj_mesh_data.ith_poly_matnr(poly_index);
-  /* Whenever a polygon with a new material is encountered, write its material
-   * and/or group, otherwise pass. */
-  if (last_poly_mat_nr == current_mat_nr) {
-    return current_mat_nr;
-  }
-
-  if (current_mat_nr == NOT_FOUND) {
-    fh.write<eOBJSyntaxElement::poly_usemtl>(MATERIAL_GROUP_DISABLED);
-    return current_mat_nr;
-  }
-  if (export_params_.export_object_groups) {
-    write_object_group(fh, obj_mesh_data);
-  }
-  const char *mat_name = matname_fn(current_mat_nr);
-  if (!mat_name) {
-    mat_name = MATERIAL_GROUP_DISABLED;
-  }
-  fh.write<eOBJSyntaxElement::poly_usemtl>(mat_name);
-
-  return current_mat_nr;
+  const Vector<float2> &uv_coords = r_obj_mesh_data.get_uv_coords();
+  const int tot_count = uv_coords.size();
+  obj_parallel_chunked_output(fh, tot_count, [&](FormatHandler<eFileType::OBJ> &buf, int i) {
+    const float2 &uv_vertex = uv_coords[i];
+    buf.write<eOBJSyntaxElement::uv_vertex_coords>(uv_vertex[0], uv_vertex[1]);
+  });
 }
 
-int16_t OBJWriter::write_vertex_group(FormatHandler<eFileType::OBJ> &fh,
-                                      const OBJMesh &obj_mesh_data,
-                                      const int poly_index,
-                                      const int16_t last_poly_vertex_group) const
+void OBJWriter::write_poly_normals(FormatHandler<eFileType::OBJ> &fh, OBJMesh &obj_mesh_data)
 {
-  if (!export_params_.export_vertex_groups) {
-    return last_poly_vertex_group;
-  }
-  const int16_t current_group = obj_mesh_data.get_poly_deform_group_index(poly_index);
-
-  if (current_group == last_poly_vertex_group) {
-    /* No vertex group found in this polygon, just like in the last iteration. */
-    return current_group;
-  }
-  if (current_group == NOT_FOUND) {
-    fh.write<eOBJSyntaxElement::object_group>(DEFORM_GROUP_DISABLED);
-  }
-  else {
-    fh.write<eOBJSyntaxElement::object_group>(
-        obj_mesh_data.get_poly_deform_group_name(current_group));
-  }
-  return current_group;
+  /* Poly normals should be calculated earlier via store_normal_coords_and_indices. */
+  const Vector<float3> &normal_coords = obj_mesh_data.get_normal_coords();
+  const int tot_count = normal_coords.size();
+  obj_parallel_chunked_output(fh, tot_count, [&](FormatHandler<eFileType::OBJ> &buf, int i) {
+    const float3 &normal = normal_coords[i];
+    buf.write<eOBJSyntaxElement::normal>(normal[0], normal[1], normal[2]);
+  });
 }
 
 OBJWriter::func_vert_uv_normal_indices OBJWriter::get_poly_element_writer(
@@ -290,30 +268,78 @@ OBJWriter::func_vert_uv_normal_indices OBJWriter::get_poly_element_writer(
   return &OBJWriter::write_vert_indices;
 }
 
+static int get_smooth_group(const OBJMesh &mesh, const OBJExportParams &params, int poly_idx)
+{
+  if (poly_idx < 0) {
+    return NEGATIVE_INIT;
+  }
+  int group = SMOOTH_GROUP_DISABLED;
+  if (mesh.is_ith_poly_smooth(poly_idx)) {
+    group = !params.export_smooth_groups ? SMOOTH_GROUP_DEFAULT : mesh.ith_smooth_group(poly_idx);
+  }
+  return group;
+}
+
 void OBJWriter::write_poly_elements(FormatHandler<eFileType::OBJ> &fh,
                                     const IndexOffsets &offsets,
                                     const OBJMesh &obj_mesh_data,
                                     std::function<const char *(int)> matname_fn)
 {
-  int last_poly_smooth_group = NEGATIVE_INIT;
-  int16_t last_poly_vertex_group = NEGATIVE_INIT;
-  int16_t last_poly_mat_nr = NEGATIVE_INIT;
-
   const func_vert_uv_normal_indices poly_element_writer = get_poly_element_writer(
       obj_mesh_data.tot_uv_vertices());
 
   const int tot_polygons = obj_mesh_data.tot_polygons();
-  for (int i = 0; i < tot_polygons; i++) {
+  obj_parallel_chunked_output(fh, tot_polygons, [&](FormatHandler<eFileType::OBJ> &buf, int i) {
     Vector<int> poly_vertex_indices = obj_mesh_data.calc_poly_vertex_indices(i);
     Span<int> poly_uv_indices = obj_mesh_data.calc_poly_uv_indices(i);
     Vector<int> poly_normal_indices = obj_mesh_data.calc_poly_normal_indices(i);
 
-    last_poly_smooth_group = write_smooth_group(fh, obj_mesh_data, i, last_poly_smooth_group);
-    last_poly_vertex_group = write_vertex_group(fh, obj_mesh_data, i, last_poly_vertex_group);
-    last_poly_mat_nr = write_poly_material(fh, obj_mesh_data, i, last_poly_mat_nr, matname_fn);
+    /* Write smoothing group if different from previous. */
+    {
+      const int prev_group = get_smooth_group(obj_mesh_data, export_params_, i - 1);
+      const int group = get_smooth_group(obj_mesh_data, export_params_, i);
+      if (group != prev_group) {
+        buf.write<eOBJSyntaxElement::smooth_group>(group);
+      }
+    }
+
+    /* Write vertex group if different from previous. */
+    if (export_params_.export_vertex_groups) {
+      const int16_t prev_group = i == 0 ? NEGATIVE_INIT :
+                                          obj_mesh_data.get_poly_deform_group_index(i - 1);
+      const int16_t group = obj_mesh_data.get_poly_deform_group_index(i);
+      if (group != prev_group) {
+        buf.write<eOBJSyntaxElement::object_group>(
+            group == NOT_FOUND ? DEFORM_GROUP_DISABLED :
+                                 obj_mesh_data.get_poly_deform_group_name(group));
+      }
+    }
+
+    /* Write material name and material group if different from previous. */
+    if (export_params_.export_materials && obj_mesh_data.tot_materials() > 0) {
+      const int16_t prev_mat = i == 0 ? NEGATIVE_INIT : obj_mesh_data.ith_poly_matnr(i - 1);
+      const int16_t mat = obj_mesh_data.ith_poly_matnr(i);
+      if (mat != prev_mat) {
+        if (mat == NOT_FOUND) {
+          buf.write<eOBJSyntaxElement::poly_usemtl>(MATERIAL_GROUP_DISABLED);
+        }
+        else {
+          if (export_params_.export_object_groups) {
+            write_object_group(buf, obj_mesh_data);
+          }
+          const char *mat_name = matname_fn(mat);
+          if (!mat_name) {
+            mat_name = MATERIAL_GROUP_DISABLED;
+          }
+          buf.write<eOBJSyntaxElement::poly_usemtl>(mat_name);
+        }
+      }
+    }
+
+    /* Write polygon elements. */
     (this->*poly_element_writer)(
-        fh, offsets, poly_vertex_indices, poly_uv_indices, poly_normal_indices);
-  }
+        buf, offsets, poly_vertex_indices, poly_uv_indices, poly_normal_indices);
+  });
 }
 
 void OBJWriter::write_edges_indices(FormatHandler<eFileType::OBJ> &fh,
diff --git a/source/blender/io/wavefront_obj/exporter/obj_export_file_writer.hh b/source/blender/io/wavefront_obj/exporter/obj_export_file_writer.hh
index 2620d65f28c..c88955e5090 100644
--- a/source/blender/io/wavefront_obj/exporter/obj_export_file_writer.hh
+++ b/source/blender/io/wavefront_obj/exporter/obj_export_file_writer.hh
@@ -103,30 +103,6 @@ class OBJWriter : NonMovable, NonCopyable {
    */
   void write_poly_normals(FormatHandler<eFileType::OBJ> &fh, OBJMesh &obj_mesh_data);
   /**
-   * Write smooth group if polygon at the given index is shaded smooth else "s 0"
-   */
-  int write_smooth_group(FormatHandler<eFileType::OBJ> &fh,
-                         const OBJMesh &obj_mesh_data,
-                         int poly_index,
-                         int last_poly_smooth_group) const;
-  /**
-   * Write material name and material group of a polygon in the .OBJ file.
-   * \return #mat_nr of the polygon at the given index.
-   * \note It doesn't write to the material library.
-   */
-  int16_t write_poly_material(FormatHandler<eFileType::OBJ> &fh,
-                              const OBJMesh &obj_mesh_data,
-                              int poly_index,
-                              int16_t last_poly_mat_nr,
-                              std::function<const char *(int)> matname_fn) const;
-  /**
-   * Write the name of the deform group of a polygon.
-   */
-  int16_t write_vertex_group(FormatHandler<eFileType::OBJ> &fh,
-                             const OBJMesh &obj_mesh_data,
-                             int poly_index,
-                             int16_t last_poly_vertex_group) const;
-  /**
    * Write polygon elements with at least vertex indices, and conditionally with UV vertex
    * indices and polygon normal indices. Also write groups: smooth, vertex, material.
    * The matname_fn turns a 0-indexed material slot number in an Object into the
diff --git a/source/blender/io/wavefront_obj/exporter/obj_export_io.hh b/source/blender/io/wavefront_obj/exporter/obj_export_io.hh
index e5b731aa51d..7d8427a8980 100644
--- a/source/blender/io/wavefront_obj/exporter/obj_export_io.hh
+++ b/source/blender/io/wavefront_obj/exporter/obj_export_io.hh
@@ -313,6 +313,14 @@ class FormatHandler : NonCopyable, NonMovable {
     return blocks_.size();
   }
 
+  void append_from(FormatHandler<filetype, buffer_chunk_size, write_local_buffer_size> &v)
+  {
+    blocks_.insert(blocks_.end(),
+                   std::make_move_iterator(v.blocks_.begin()),
+                   std::make_move_iterator(v.blocks_.end()));
+    v.blocks_.clear();
+  }
+
   /**
    * Example invocation: `writer->write<eMTLSyntaxElement::newmtl>("foo")`.
    *