LibOverride: Improve speed of resync and creation of liboverrides.

`BKE_collection_object_find` has extremely bad performances (very high
time complexity). While ideally this should be fixed in that API, for
now cache its results once at the beginning of the resync/creation
process.

This makes loading of complex production files with a lot of
liboverrides to resync three to four times faster.

Thanks to @brecht for the profiling in T94059.

1 files changed, 64 insertions, 10 deletions

diff --git a/source/blender/blenkernel/intern/lib_override.c b/source/blender/blenkernel/intern/lib_override.c
index 52bfeb4b4d3..b4a0b2c35e4 100644
--- a/source/blender/blenkernel/intern/lib_override.c
+++ b/source/blender/blenkernel/intern/lib_override.c
@@ -57,6 +57,7 @@
 #include "BLI_ghash.h"
 #include "BLI_linklist.h"
 #include "BLI_listbase.h"
+#include "BLI_memarena.h"
 #include "BLI_string.h"
 #include "BLI_task.h"
 #include "BLI_utildefines.h"
@@ -452,8 +453,49 @@ typedef struct LibOverrideGroupTagData {
   bool is_override;
   /* Whether we are creating new override, or resyncing existing one. */
   bool is_resync;
+
+  /* Mapping linked objects to all their instantiating collections (as a linked list).
+   * Avoids calling #BKE_collection_object_find over and over, this function is very expansive. */
+  GHash *linked_object_to_instantiating_collections;
+  MemArena *mem_arena;
 } LibOverrideGroupTagData;
 
+/* Initialize complex data, `data` is expected to be already initialized with basic pointers and
+ * other simple data.
+ *
+ * NOTE: Currently creates a mapping from linked object to all of their instantiating collections
+ * (as returned by #BKE_collection_object_find). */
+static void lib_override_group_tag_data_object_to_collection_init(LibOverrideGroupTagData *data)
+{
+  data->mem_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__);
+
+  data->linked_object_to_instantiating_collections = BLI_ghash_new(
+      BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, __func__);
+  LISTBASE_FOREACH (Object *, ob, &data->bmain->objects) {
+    if (!ID_IS_LINKED(ob)) {
+      continue;
+    }
+
+    LinkNodePair collections_linkedlist = {NULL};
+    Collection *instantiating_collection = NULL;
+    while ((instantiating_collection = BKE_collection_object_find(
+                data->bmain, data->scene, instantiating_collection, ob)) != NULL) {
+      BLI_linklist_append_arena(
+          &collections_linkedlist, instantiating_collection, data->mem_arena);
+    }
+
+    BLI_ghash_insert(
+        data->linked_object_to_instantiating_collections, ob, collections_linkedlist.list);
+  }
+}
+
+static void lib_override_group_tag_data_clear(LibOverrideGroupTagData *data)
+{
+  BLI_ghash_free(data->linked_object_to_instantiating_collections, NULL, NULL);
+  BLI_memarena_free(data->mem_arena);
+  memset(data, 0, sizeof(*data));
+}
+
 /* Tag all IDs in dependency relationships within an override hierarchy/group.
  *
  * Requires existing `Main.relations`.
@@ -572,7 +614,6 @@ static void lib_override_linked_group_tag_recursive(LibOverrideGroupTagData *dat
 static void lib_override_linked_group_tag(LibOverrideGroupTagData *data)
 {
   Main *bmain = data->bmain;
-  Scene *scene = data->scene;
   ID *id_root = data->id_root;
   const bool is_resync = data->is_resync;
   BLI_assert(!data->is_override);
@@ -610,8 +651,11 @@ static void lib_override_linked_group_tag(LibOverrideGroupTagData *data)
         Collection *instantiating_collection_override_candidate = NULL;
         /* Loop over all collections instantiating the object, if we already have a 'locale' one we
          * have nothing to do, otherwise try to find a 'linked' one that we can override too. */
-        while ((instantiating_collection = BKE_collection_object_find(
-                    bmain, scene, instantiating_collection, ob)) != NULL) {
+        LinkNode *instantiating_collection_linknode = BLI_ghash_lookup(
+            data->linked_object_to_instantiating_collections, ob);
+        for (; instantiating_collection_linknode != NULL;
+             instantiating_collection_linknode = instantiating_collection_linknode->next) {
+          instantiating_collection = instantiating_collection_linknode->link;
           /* In (recursive) resync case, if a collection of a 'parent' lib instantiates the linked
            * object, it is also fine. */
           if (!ID_IS_LINKED(instantiating_collection) ||
@@ -623,6 +667,7 @@ static void lib_override_linked_group_tag(LibOverrideGroupTagData *data)
               (!is_resync || instantiating_collection->id.lib == id_root->lib)) {
             instantiating_collection_override_candidate = instantiating_collection;
           }
+          instantiating_collection = NULL;
         }
 
         if (instantiating_collection == NULL &&
@@ -724,12 +769,14 @@ static bool lib_override_library_create_do(Main *bmain, Scene *scene, ID *id_roo
                                   .missing_tag = LIB_TAG_MISSING,
                                   .is_override = false,
                                   .is_resync = false};
+  lib_override_group_tag_data_object_to_collection_init(&data);
   lib_override_linked_group_tag(&data);
 
   BKE_main_relations_tag_set(bmain, MAINIDRELATIONS_ENTRY_TAGS_PROCESSED, false);
   lib_override_hierarchy_dependencies_recursive_tag(&data);
 
   BKE_main_relations_free(bmain);
+  lib_override_group_tag_data_clear(&data);
 
   return BKE_lib_override_library_create_from_tag(bmain, id_root->lib, false);
 }
@@ -1050,6 +1097,7 @@ bool BKE_lib_override_library_resync(Main *bmain,
                                   .missing_tag = LIB_TAG_MISSING,
                                   .is_override = true,
                                   .is_resync = true};
+  lib_override_group_tag_data_object_to_collection_init(&data);
   lib_override_overrides_group_tag(&data);
 
   BKE_main_relations_tag_set(bmain, MAINIDRELATIONS_ENTRY_TAGS_PROCESSED, false);
@@ -1140,6 +1188,7 @@ bool BKE_lib_override_library_resync(Main *bmain,
   lib_override_hierarchy_dependencies_recursive_tag(&data);
 
   BKE_main_relations_free(bmain);
+  lib_override_group_tag_data_clear(&data);
 
   /* Make new override from linked data. */
   /* Note that this call also remaps all pointers of tagged IDs from old override IDs to new
@@ -1532,6 +1581,14 @@ static void lib_override_library_main_resync_on_library_indirect_level(
 
   /* Detect all linked data that would need to be overridden if we had to create an override from
    * those used by current existing overrides. */
+  LibOverrideGroupTagData data = {.bmain = bmain,
+                                  .scene = scene,
+                                  .id_root = NULL,
+                                  .tag = LIB_TAG_DOIT,
+                                  .missing_tag = LIB_TAG_MISSING,
+                                  .is_override = false,
+                                  .is_resync = true};
+  lib_override_group_tag_data_object_to_collection_init(&data);
   ID *id;
   FOREACH_MAIN_ID_BEGIN (bmain, id) {
     if (!ID_IS_OVERRIDE_LIBRARY_REAL(id)) {
@@ -1542,19 +1599,14 @@ static void lib_override_library_main_resync_on_library_indirect_level(
       continue;
     }
 
-    LibOverrideGroupTagData data = {.bmain = bmain,
-                                    .scene = scene,
-                                    .id_root = id->override_library->reference,
-                                    .tag = LIB_TAG_DOIT,
-                                    .missing_tag = LIB_TAG_MISSING,
-                                    .is_override = false,
-                                    .is_resync = true};
+    data.id_root = id->override_library->reference;
     lib_override_linked_group_tag(&data);
     BKE_main_relations_tag_set(bmain, MAINIDRELATIONS_ENTRY_TAGS_PROCESSED, false);
     lib_override_hierarchy_dependencies_recursive_tag(&data);
     BKE_main_relations_tag_set(bmain, MAINIDRELATIONS_ENTRY_TAGS_PROCESSED, false);
   }
   FOREACH_MAIN_ID_END;
+  lib_override_group_tag_data_clear(&data);
 
   /* Now check existing overrides, those needing resync will be the one either already tagged as
    * such, or the one using linked data that is now tagged as needing override. */
@@ -1787,9 +1839,11 @@ void BKE_lib_override_library_delete(Main *bmain, ID *id_root)
                                   .missing_tag = LIB_TAG_MISSING,
                                   .is_override = true,
                                   .is_resync = false};
+  lib_override_group_tag_data_object_to_collection_init(&data);
   lib_override_overrides_group_tag(&data);
 
   BKE_main_relations_free(bmain);
+  lib_override_group_tag_data_clear(&data);
 
   ID *id;
   FOREACH_MAIN_ID_BEGIN (bmain, id) {