IDManagement: Speedup ID unique name assignment by tracking used names/basenames/suffixes

An implementation of T73412, roughly as outlined there:

Track the names that are in use, as well as base names (before
numeric suffix) plus a bit map for each base name, indicating which
numeric suffixes are already used. This is done per-Main/Library,
per-object-type.

Timings (Windows, VS2022 Release build, AMD Ryzen 5950X):

- Scene with 10k cubes, Shift+D to duplicate them all: 8.7s -> 1.9s.
  Name map memory usage for resulting 20k objects: 4.3MB.
- Importing a 2.5GB .obj file of exported Blender 3.0 splash scene
  (24k objects), using the new C++ importer: 34.2s-> 22.0s. Name map
  memory usage for resulting scene: 8.6MB.
- Importing Disney Moana USD scene (almost half a million objects):
  56min -> 10min. Name map usage: ~100MB. Blender crashes later on
  when trying to render it, in the same place in both cases, but
  that's for another day.

Reviewed By: Bastien Montagne
Differential Revision: https://developer.blender.org/D14162

1 files changed, 8 insertions, 0 deletions

diff --git a/source/blender/makesdna/DNA_ID.h b/source/blender/makesdna/DNA_ID.h
index d3fc279381f..a77b7034241 100644
--- a/source/blender/makesdna/DNA_ID.h
+++ b/source/blender/makesdna/DNA_ID.h
@@ -22,6 +22,7 @@ struct GPUTexture;
 struct ID;
 struct Library;
 struct PackedFile;
+struct UniqueName_Map;
 
 /* Runtime display data */
 struct DrawData;
@@ -444,6 +445,11 @@ typedef struct ID {
   struct ID_Runtime runtime;
 } ID;
 
+typedef struct Library_Runtime {
+  /* Used for efficient calculations of unique names. */
+  struct UniqueName_Map *name_map;
+} Library_Runtime;
+
 /**
  * For each library file used, a Library struct is added to Main
  * WARNING: readfile.c, expand_doit() reads this struct without DNA check!
@@ -476,6 +482,8 @@ typedef struct Library {
   int temp_index;
   /** See BLENDER_FILE_VERSION, BLENDER_FILE_SUBVERSION, needed for do_versions. */
   short versionfile, subversionfile;
+
+  struct Library_Runtime runtime;
 } Library;
 
 /** #Library.tag */