IO: speed up import of large amounts of objects in USD/OBJ by pre-sorting objects by name

Previously, when creating "very large" (tens-hundreds of thousands)
amounts of objects, the Blender code that was ensuring name
uniqueness was the bottleneck. That got recently addressed (D14162),
however now sorting of IDs by their names is the remaining bottleneck.

Name sorting code in Blender is optimized for the pattern where names
are inserted in already sorted order (i.e. objects expect to get added
near the end of the list). By doing this pre-sorting of objects
intended to get created by an importer (USD and OBJ, in this patch),
this sorting bottleneck can be largely removed, especially with very
high object counts.

Windows, Ryzen 5950X, import times:

- OBJ, splash screen scene (26k objects): 22.0s -> 20.7s
- USD, Disney Moana scene (250k objects): 585s -> 82.2s (10 minutes -> 1.5 minutes)

Reviewed By: Michael Kowalski, Howard Trickey
Differential Revision: https://developer.blender.org/D15506

5 files changed, 196 insertions, 153 deletions

diff --git a/source/blender/io/usd/intern/usd_capi_import.cc b/source/blender/io/usd/intern/usd_capi_import.cc
index 13ae6f4d4c0..03af3aed2d0 100644
--- a/source/blender/io/usd/intern/usd_capi_import.cc
+++ b/source/blender/io/usd/intern/usd_capi_import.cc
@@ -218,6 +218,7 @@ static void import_startjob(void *customdata, short *stop, short *do_update, flo
     data->scene->r.efra = stage->GetEndTimeCode();
   }
 
+  *data->do_update = true;
   *data->progress = 0.15f;
 
   USDStageReader *archive = new USDStageReader(stage, data->params, data->settings);
@@ -226,13 +227,32 @@ static void import_startjob(void *customdata, short *stop, short *do_update, flo
 
   archive->collect_readers(data->bmain);
 
+  *data->do_update = true;
   *data->progress = 0.2f;
 
   const float size = static_cast<float>(archive->readers().size());
   size_t i = 0;
 
-  /* Setup parenthood */
+  /* Sort readers by name: when creating a lot of objects in Blender,
+   * it is much faster if the order is sorted by name. */
+  archive->sort_readers();
+  *data->do_update = true;
+  *data->progress = 0.25f;
+
+  /* Create blender objects. */
+  for (USDPrimReader *reader : archive->readers()) {
+    if (!reader) {
+      continue;
+    }
+    reader->create_object(data->bmain, 0.0);
+    if ((++i & 1023) == 0) {
+      *data->do_update = true;
+      *data->progress = 0.25f + 0.25f * (i / size);
+    }
+  }
 
+  /* Setup parenthood and read actual object data. */
+  i = 0;
   for (USDPrimReader *reader : archive->readers()) {
 
     if (!reader) {
@@ -252,7 +272,7 @@ static void import_startjob(void *customdata, short *stop, short *do_update, flo
       ob->parent = parent->object();
     }
 
-    *data->progress = 0.2f + 0.8f * (++i / size);
+    *data->progress = 0.5f + 0.5f * (++i / size);
     *data->do_update = true;
 
     if (G.is_break) {
diff --git a/source/blender/io/usd/intern/usd_reader_stage.cc b/source/blender/io/usd/intern/usd_reader_stage.cc
index 583c58a1356..df75be849e2 100644
--- a/source/blender/io/usd/intern/usd_reader_stage.cc
+++ b/source/blender/io/usd/intern/usd_reader_stage.cc
@@ -28,6 +28,9 @@
 
 #include <iostream>
 
+#include "BLI_sort.hh"
+#include "BLI_string.h"
+
 namespace blender::io::usd {
 
 USDStageReader::USDStageReader(pxr::UsdStageRefPtr stage,
@@ -252,8 +255,6 @@ USDPrimReader *USDStageReader::collect_readers(Main *bmain, const pxr::UsdPrim &
     return nullptr;
   }
 
-  reader->create_object(bmain, 0.0);
-
   readers_.push_back(reader);
   reader->incref();
 
@@ -310,4 +311,14 @@ void USDStageReader::clear_readers()
   readers_.clear();
 }
 
+void USDStageReader::sort_readers()
+{
+  blender::parallel_sort(
+      readers_.begin(), readers_.end(), [](const USDPrimReader *a, const USDPrimReader *b) {
+        const char *na = a ? a->name().c_str() : "";
+        const char *nb = b ? b->name().c_str() : "";
+        return BLI_strcasecmp(na, nb) < 0;
+      });
+}
+
 }  // Namespace blender::io::usd
diff --git a/source/blender/io/usd/intern/usd_reader_stage.h b/source/blender/io/usd/intern/usd_reader_stage.h
index 0ed964c7679..5f4a343f874 100644
--- a/source/blender/io/usd/intern/usd_reader_stage.h
+++ b/source/blender/io/usd/intern/usd_reader_stage.h
@@ -63,6 +63,8 @@ class USDStageReader {
     return readers_;
   };
 
+  void sort_readers();
+
  private:
   USDPrimReader *collect_readers(Main *bmain, const pxr::UsdPrim &prim);
 
diff --git a/source/blender/io/wavefront_obj/importer/obj_importer.cc b/source/blender/io/wavefront_obj/importer/obj_importer.cc
index f2051d195c8..bb32776d2be 100644
--- a/source/blender/io/wavefront_obj/importer/obj_importer.cc
+++ b/source/blender/io/wavefront_obj/importer/obj_importer.cc
@@ -9,6 +9,7 @@
 #include "BLI_map.hh"
 #include "BLI_math_vec_types.hh"
 #include "BLI_set.hh"
+#include "BLI_sort.hh"
 #include "BLI_string_ref.hh"
 
 #include "BKE_layer.h"
@@ -44,6 +45,15 @@ static void geometry_to_blender_objects(Main *bmain,
   /* Don't do collection syncs for each object, will do once after the loop. */
   BKE_layer_collection_resync_forbid();
 
+  /* Sort objects by name: creating many objects is much faster if the creation
+   * order is sorted by name. */
+  blender::parallel_sort(
+      all_geometries.begin(), all_geometries.end(), [](const auto &a, const auto &b) {
+        const char *na = a ? a->geometry_name_.c_str() : "";
+        const char *nb = b ? b->geometry_name_.c_str() : "";
+        return BLI_strcasecmp(na, nb) < 0;
+      });
+
   /* Create all the objects. */
   Vector<Object *> objects;
   objects.reserve(all_geometries.size());
diff --git a/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc b/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc
index 02565556c37..c59269f5a7d 100644
--- a/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc
+++ b/source/blender/io/wavefront_obj/tests/obj_importer_tests.cc
@@ -226,7 +226,9 @@ TEST_F(obj_importer_test, import_nurbs_curves)
 {
   Expectation expect[] = {
       {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)},
+      {"OBCurveDeg3", OB_CURVES_LEGACY, 4, 0, 3, 0, float3(10, -2, 0), float3(6, -2, 0)},
       {"OBnurbs_curves", OB_CURVES_LEGACY, 4, 0, 4, 0, float3(2, -2, 0), float3(-2, -2, 0)},
+      {"OBNurbsCurveCyclic", OB_CURVES_LEGACY, 7, 0, 4, 1, float3(-2, -2, 0), float3(-6, 2, 0)},
       {"OBNurbsCurveDiffWeights",
        OB_CURVES_LEGACY,
        4,
@@ -235,7 +237,6 @@ TEST_F(obj_importer_test, import_nurbs_curves)
        0,
        float3(6, -2, 0),
        float3(2, -2, 0)},
-      {"OBNurbsCurveCyclic", OB_CURVES_LEGACY, 7, 0, 4, 1, float3(-2, -2, 0), float3(-6, 2, 0)},
       {"OBNurbsCurveEndpoint",
        OB_CURVES_LEGACY,
        4,
@@ -244,7 +245,6 @@ TEST_F(obj_importer_test, import_nurbs_curves)
        0,
        float3(-6, -2, 0),
        float3(-10, -2, 0)},
-      {"OBCurveDeg3", OB_CURVES_LEGACY, 4, 0, 3, 0, float3(10, -2, 0), float3(6, -2, 0)},
   };
   import_and_check("nurbs_curves.obj", expect, std::size(expect), 0);
 }
@@ -269,7 +269,8 @@ TEST_F(obj_importer_test, import_nurbs_manual)
 {
   Expectation expect[] = {
       {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)},
-      {"OBCurve_Uniform_Parm", OB_CURVES_LEGACY, 5, 0, 4, 0, float3(-2, 0, 2), float3(-2, 0, 2)},
+      {"OBCurve_Cyclic", OB_CURVES_LEGACY, 7, 0, 4, 1, float3(-2, 0, 2), float3(2, 0, -2)},
+      {"OBCurve_Endpoints", OB_CURVES_LEGACY, 5, 1, 4, 0, float3(-2, 0, 2), float3(-2, 0, 2)},
       {"OBCurve_NonUniform_Parm",
        OB_CURVES_LEGACY,
        5,
@@ -278,8 +279,7 @@ TEST_F(obj_importer_test, import_nurbs_manual)
        0,
        float3(-2, 0, 2),
        float3(-2, 0, 2)},
-      {"OBCurve_Endpoints", OB_CURVES_LEGACY, 5, 1, 4, 0, float3(-2, 0, 2), float3(-2, 0, 2)},
-      {"OBCurve_Cyclic", OB_CURVES_LEGACY, 7, 0, 4, 1, float3(-2, 0, 2), float3(2, 0, -2)},
+      {"OBCurve_Uniform_Parm", OB_CURVES_LEGACY, 5, 0, 4, 0, float3(-2, 0, 2), float3(-2, 0, 2)},
   };
   import_and_check("nurbs_manual.obj", expect, std::size(expect), 0);
 }
@@ -313,23 +313,14 @@ TEST_F(obj_importer_test, import_faces_invalid_or_with_holes)
 {
   Expectation expect[] = {
       {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)},
-      {"OBFaceWithHole_BecomesTwoFacesFormingAHole",
+      {"OBFaceAllVerts_BecomesOneOverlappingFaceUsingAllVerts",
        OB_MESH,
        8,
-       10,
-       2,
-       12,
-       float3(-2, 0, -2),
-       float3(1, 0, -1)},
-      {"OBFaceQuadDupSomeVerts_BecomesOneQuadUsing4Verts",
-       OB_MESH,
-       4,
-       4,
+       8,
        1,
-       4,
-       float3(3, 0, -2),
-       float3(7, 0, -2)},
-      {"OBFaceTriDupVert_Becomes1Tri", OB_MESH, 3, 3, 1, 3, float3(-2, 0, 3), float3(2, 0, 7)},
+       8,
+       float3(8, 0, -2),
+       float3(11, 0, -1)},
       {"OBFaceAllVertsDup_BecomesOneOverlappingFaceUsingAllVerts",
        OB_MESH,
        8,
@@ -338,15 +329,24 @@ TEST_F(obj_importer_test, import_faces_invalid_or_with_holes)
        8,
        float3(3, 0, 3),
        float3(6, 0, 4)},
-      {"OBFaceAllVerts_BecomesOneOverlappingFaceUsingAllVerts",
+      {"OBFaceJustTwoVerts_IsSkipped", OB_MESH, 2, 0, 0, 0, float3(8, 0, 3), float3(8, 0, 7)},
+      {"OBFaceQuadDupSomeVerts_BecomesOneQuadUsing4Verts",
        OB_MESH,
-       8,
-       8,
+       4,
+       4,
        1,
+       4,
+       float3(3, 0, -2),
+       float3(7, 0, -2)},
+      {"OBFaceTriDupVert_Becomes1Tri", OB_MESH, 3, 3, 1, 3, float3(-2, 0, 3), float3(2, 0, 7)},
+      {"OBFaceWithHole_BecomesTwoFacesFormingAHole",
+       OB_MESH,
        8,
-       float3(8, 0, -2),
-       float3(11, 0, -1)},
-      {"OBFaceJustTwoVerts_IsSkipped", OB_MESH, 2, 0, 0, 0, float3(8, 0, 3), float3(8, 0, 7)},
+       10,
+       2,
+       12,
+       float3(-2, 0, -2),
+       float3(1, 0, -1)},
   };
   import_and_check("faces_invalid_or_with_holes.obj", expect, std::size(expect), 0);
 }
@@ -392,6 +392,63 @@ TEST_F(obj_importer_test, import_all_objects)
   Expectation expect[] = {
       {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)},
       /* .obj file has empty EmptyText and EmptyMesh objects; these are ignored and skipped */
+      {"OBBezierCurve", OB_MESH, 13, 12, 0, 0, float3(-1, -2, 0), float3(1, -2, 0)},
+      {"OBBlankCube", OB_MESH, 8, 13, 7, 26, float3(1, 1, -1), float3(-1, 1, 1), float3(0, 0, 1)},
+      {"OBMaterialCube",
+       OB_MESH,
+       8,
+       13,
+       7,
+       26,
+       float3(28, 1, -1),
+       float3(26, 1, 1),
+       float3(-1, 0, 0)},
+      {"OBNurbsCircle",
+       OB_MESH,
+       96,
+       96,
+       0,
+       0,
+       float3(3.292893f, -2.707107f, 0),
+       float3(3.369084f, -2.77607f, 0)},
+      {"OBNurbsCircle.001", OB_MESH, 4, 4, 0, 0, float3(2, -3, 0), float3(3, -2, 0)},
+      {"OBParticleCube",
+       OB_MESH,
+       8,
+       13,
+       7,
+       26,
+       float3(22, 1, -1),
+       float3(20, 1, 1),
+       float3(0, 0, 1)},
+      {"OBShapeKeyCube",
+       OB_MESH,
+       8,
+       13,
+       7,
+       26,
+       float3(19, 1, -1),
+       float3(17, 1, 1),
+       float3(-0.4082f, -0.4082f, 0.8165f)},
+      {"OBSmoothCube",
+       OB_MESH,
+       8,
+       13,
+       7,
+       26,
+       float3(4, 1, -1),
+       float3(2, 1, 1),
+       float3(0.5774f, 0.5773f, 0.5774f)},
+      {"OBSurface",
+       OB_MESH,
+       256,
+       480,
+       224,
+       896,
+       float3(7.292893f, -2.707107f, -1),
+       float3(7.525872f, -2.883338f, 1),
+       float3(-0.7071f, -0.7071f, 0),
+       float2(0, 0.142857f)},
       {"OBSurfPatch",
        OB_MESH,
        256,
@@ -412,24 +469,16 @@ TEST_F(obj_importer_test, import_all_objects)
        float3(11, -2, 1),
        float3(-0.0541f, -0.0541f, -0.9971f),
        float2(0, 1)},
-      {"OBSmoothCube",
-       OB_MESH,
-       8,
-       13,
-       7,
-       26,
-       float3(4, 1, -1),
-       float3(2, 1, 1),
-       float3(0.5774f, 0.5773f, 0.5774f)},
-      {"OBMaterialCube",
+      {"OBSurfTorus.001",
        OB_MESH,
-       8,
-       13,
-       7,
-       26,
-       float3(28, 1, -1),
-       float3(26, 1, 1),
-       float3(-1, 0, 0)},
+       1024,
+       2048,
+       1024,
+       4096,
+       float3(5.34467f, -2.65533f, -0.176777f),
+       float3(5.232792f, -2.411795f, -0.220835f),
+       float3(-0.5042f, -0.5042f, -0.7011f),
+       float2(0, 1)},
       {"OBTaperCube",
        OB_MESH,
        106,
@@ -439,24 +488,26 @@ TEST_F(obj_importer_test, import_all_objects)
        float3(24.444445f, 0.502543f, -0.753814f),
        float3(23.790743f, 0.460522f, -0.766546f),
        float3(-0.0546f, 0.1716f, 0.9837f)},
-      {"OBParticleCube",
+      {"OBText",
        OB_MESH,
-       8,
-       13,
-       7,
-       26,
-       float3(22, 1, -1),
-       float3(20, 1, 1),
-       float3(0, 0, 1)},
-      {"OBShapeKeyCube",
+       177,
+       345,
+       171,
+       513,
+       float3(1.75f, -9.458f, 0),
+       float3(0.587f, -9.406f, 0),
+       float3(0, 0, 1),
+       float2(0.017544f, 0)},
+      {"OBUVCube",
        OB_MESH,
        8,
        13,
        7,
        26,
-       float3(19, 1, -1),
-       float3(17, 1, 1),
-       float3(-0.4082f, -0.4082f, 0.8165f)},
+       float3(7, 1, -1),
+       float3(5, 1, 1),
+       float3(0, 0, 1),
+       float2(0.654526f, 0.579873f)},
       {"OBUVImageCube",
        OB_MESH,
        8,
@@ -467,15 +518,6 @@ TEST_F(obj_importer_test, import_all_objects)
        float3(8, 1, 1),
        float3(0, 0, 1),
        float2(0.654526f, 0.579873f)},
-      {"OBVGroupCube",
-       OB_MESH,
-       8,
-       13,
-       7,
-       26,
-       float3(16, 1, -1),
-       float3(14, 1, 1),
-       float3(0, 0, 1)},
       {"OBVColCube",
        OB_MESH,
        8,
@@ -487,57 +529,15 @@ TEST_F(obj_importer_test, import_all_objects)
        float3(0, 0, 1),
        float2(0, 0),
        float4(0.0f, 0.002125f, 1.0f, 1.0f)},
-      {"OBUVCube",
+      {"OBVGroupCube",
        OB_MESH,
        8,
        13,
        7,
        26,
-       float3(7, 1, -1),
-       float3(5, 1, 1),
-       float3(0, 0, 1),
-       float2(0.654526f, 0.579873f)},
-      {"OBNurbsCircle.001", OB_MESH, 4, 4, 0, 0, float3(2, -3, 0), float3(3, -2, 0)},
-      {"OBSurface",
-       OB_MESH,
-       256,
-       480,
-       224,
-       896,
-       float3(7.292893f, -2.707107f, -1),
-       float3(7.525872f, -2.883338f, 1),
-       float3(-0.7071f, -0.7071f, 0),
-       float2(0, 0.142857f)},
-      {"OBText",
-       OB_MESH,
-       177,
-       345,
-       171,
-       513,
-       float3(1.75f, -9.458f, 0),
-       float3(0.587f, -9.406f, 0),
-       float3(0, 0, 1),
-       float2(0.017544f, 0)},
-      {"OBSurfTorus.001",
-       OB_MESH,
-       1024,
-       2048,
-       1024,
-       4096,
-       float3(5.34467f, -2.65533f, -0.176777f),
-       float3(5.232792f, -2.411795f, -0.220835f),
-       float3(-0.5042f, -0.5042f, -0.7011f),
-       float2(0, 1)},
-      {"OBNurbsCircle",
-       OB_MESH,
-       96,
-       96,
-       0,
-       0,
-       float3(3.292893f, -2.707107f, 0),
-       float3(3.369084f, -2.77607f, 0)},
-      {"OBBezierCurve", OB_MESH, 13, 12, 0, 0, float3(-1, -2, 0), float3(1, -2, 0)},
-      {"OBBlankCube", OB_MESH, 8, 13, 7, 26, float3(1, 1, -1), float3(-1, 1, 1), float3(0, 0, 1)},
+       float3(16, 1, -1),
+       float3(14, 1, 1),
+       float3(0, 0, 1)},
   };
   import_and_check("all_objects.obj", expect, std::size(expect), 7);
 }
@@ -546,28 +546,6 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors)
 {
   Expectation expect[] = {
       {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)},
-      {"OBCubeVertexByte",
-       OB_MESH,
-       8,
-       12,
-       6,
-       24,
-       float3(1.0f, 1.0f, -1.0f),
-       float3(-1.0f, -1.0f, 1.0f),
-       float3(0, 0, 0),
-       float2(0, 0),
-       float4(0.846873f, 0.027321f, 0.982123f, 1.0f)},
-      {"OBCubeVertexFloat",
-       OB_MESH,
-       8,
-       12,
-       6,
-       24,
-       float3(3.392028f, 1.0f, -1.0f),
-       float3(1.392028f, -1.0f, 1.0f),
-       float3(0, 0, 0),
-       float2(0, 0),
-       float4(49.99467f, 0.027321f, 0.982123f, 1.0f)},
       {"OBCubeCornerByte",
        OB_MESH,
        8,
@@ -609,6 +587,28 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors)
        24,
        float3(-4.550208f, -1.0f, -1.918042f),
        float3(-2.550208f, 1.0f, -3.918042f)},
+      {"OBCubeVertexByte",
+       OB_MESH,
+       8,
+       12,
+       6,
+       24,
+       float3(1.0f, 1.0f, -1.0f),
+       float3(-1.0f, -1.0f, 1.0f),
+       float3(0, 0, 0),
+       float2(0, 0),
+       float4(0.846873f, 0.027321f, 0.982123f, 1.0f)},
+      {"OBCubeVertexFloat",
+       OB_MESH,
+       8,
+       12,
+       6,
+       24,
+       float3(3.392028f, 1.0f, -1.0f),
+       float3(1.392028f, -1.0f, 1.0f),
+       float3(0, 0, 0),
+       float2(0, 0),
+       float4(49.99467f, 0.027321f, 0.982123f, 1.0f)},
   };
   import_and_check("cubes_vertex_colors.obj", expect, std::size(expect), 0);
 }
@@ -617,38 +617,28 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors_mrgb)
 {
   Expectation expect[] = {
       {"OBCube", OB_MESH, 8, 12, 6, 24, float3(1, 1, -1), float3(-1, 1, 1)},
-      {"OBCubeXYZRGB",
+      {"OBCubeMRGB",
        OB_MESH,
        8,
        12,
        6,
        24,
-       float3(1, 1, -1),
-       float3(-1, -1, 1),
+       float3(4, 1, -1),
+       float3(2, -1, 1),
        float3(0, 0, 0),
        float2(0, 0),
-       float4(0.6038f, 0.3185f, 0.1329f, 1.0f)},
-      {"OBCubeMRGB",
+       float4(0.8714f, 0.6308f, 0.5271f, 1.0f)},
+      {"OBCubeXYZRGB",
        OB_MESH,
        8,
        12,
        6,
        24,
-       float3(4, 1, -1),
-       float3(2, -1, 1),
+       float3(1, 1, -1),
+       float3(-1, -1, 1),
        float3(0, 0, 0),
        float2(0, 0),
-       float4(0.8714f, 0.6308f, 0.5271f, 1.0f)},
-      {
-          "OBTriNoColors",
-          OB_MESH,
-          3,
-          3,
-          1,
-          3,
-          float3(8, 1, -1),
-          float3(6, 0, -1),
-      },
+       float4(0.6038f, 0.3185f, 0.1329f, 1.0f)},
       {"OBTriMRGB",
        OB_MESH,
        3,
@@ -660,6 +650,16 @@ TEST_F(obj_importer_test, import_cubes_vertex_colors_mrgb)
        float3(0, 0, 0),
        float2(0, 0),
        float4(1.0f, 0.0f, 0.0f, 1.0f)},
+      {
+          "OBTriNoColors",
+          OB_MESH,
+          3,
+          3,
+          1,
+          3,
+          float3(8, 1, -1),
+          float3(6, 0, -1),
+      },
   };
   import_and_check("cubes_vertex_colors_mrgb.obj", expect, std::size(expect), 0);
 }