Performance: Remap multiple items in UI

During sprite fright loading of complex scenes would spend a long time in remapping ID's
The remapping process is done on a per ID instance that resulted in a very time consuming
process that goes over every possible ID reference to find out if it needs to be updated.

If there are N of references to ID blocks and there are M ID blocks that needed to be remapped
it would take N*M checks. These checks are scattered around the place and memory.
Each reference would only be updated at most once, but most of the time no update is needed at all.

Idea: By grouping the changes together will reduce the number of checks resulting in improved performance.
This would only require N checks. Additional benefits is improved data locality as data is only loaded once
in the L2 cache.

It has be implemented for the resyncing process and UI editors.
On an Intel(R) Core(TM) i7-6700 CPU @ 3.40GHz 16Gig the resyncing process went
from 170 seconds to 145 seconds (during hotspot recording).

After this patch has been applied we could add similar approach
to references (references between data blocks) and functionality (tagged deletion).
In my understanding this could reduce the resyncing process to less than a second.
Opening the village production file between 10 and 20 seconds.

Flame graphs showing that UI remapping isn't visible anymore (`WM_main_remap_editor_id_reference`)
* Master {F12769210 size=full}
* This patch {F12769211 size=full}

Reviewed By: mont29

Maniphest Tasks: T94185

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

5 files changed, 380 insertions, 49 deletions

diff --git a/source/blender/blenkernel/intern/lib_id_delete.c b/source/blender/blenkernel/intern/lib_id_delete.c
index 6d2e89187f7..f4dd67cac28 100644
--- a/source/blender/blenkernel/intern/lib_id_delete.c
+++ b/source/blender/blenkernel/intern/lib_id_delete.c
@@ -154,7 +154,10 @@ void BKE_id_free_ex(Main *bmain, void *idv, int flag, const bool use_flag_from_i
     }
 
     if (remap_editor_id_reference_cb) {
-      remap_editor_id_reference_cb(id, NULL);
+      struct IDRemapper *remapper = BKE_id_remapper_create();
+      BKE_id_remapper_add(remapper, id, NULL);
+      remap_editor_id_reference_cb(remapper);
+      BKE_id_remapper_free(remapper);
     }
   }
 
@@ -292,32 +295,40 @@ static size_t id_delete(Main *bmain, const bool do_tagged_deletion)
      * Note that we go forward here, since we want to check dependencies before users
      * (e.g. meshes before objects).
      * Avoids to have to loop twice. */
+    struct IDRemapper *remapper = BKE_id_remapper_create();
     for (i = 0; i < base_count; i++) {
       ListBase *lb = lbarray[i];
       ID *id, *id_next;
+      BKE_id_remapper_clear(remapper);
 
       for (id = lb->first; id; id = id_next) {
         id_next = id->next;
         /* NOTE: in case we delete a library, we also delete all its datablocks! */
         if ((id->tag & tag) || (id->lib != NULL && (id->lib->id.tag & tag))) {
           id->tag |= tag;
-
-          /* Will tag 'never NULL' users of this ID too.
-           * Note that we cannot use BKE_libblock_unlink() here, since it would ignore indirect
-           * (and proxy!) links, this can lead to nasty crashing here in second,
-           * actual deleting loop.
-           * Also, this will also flag users of deleted data that cannot be unlinked
-           * (object using deleted obdata, etc.), so that they also get deleted. */
-          BKE_libblock_remap_locked(bmain,
-                                    id,
-                                    NULL,
-                                    (ID_REMAP_FLAG_NEVER_NULL_USAGE |
-                                     ID_REMAP_FORCE_NEVER_NULL_USAGE |
-                                     ID_REMAP_FORCE_INTERNAL_RUNTIME_POINTERS));
+          BKE_id_remapper_add(remapper, id, NULL);
         }
       }
+
+      if (BKE_id_remapper_is_empty(remapper)) {
+        continue;
+      }
+
+      /* Will tag 'never NULL' users of this ID too.
+       * Note that we cannot use BKE_libblock_unlink() here, since it would ignore indirect
+       * (and proxy!) links, this can lead to nasty crashing here in second,
+       * actual deleting loop.
+       * Also, this will also flag users of deleted data that cannot be unlinked
+       * (object using deleted obdata, etc.), so that they also get deleted. */
+      BKE_libblock_remap_multiple_locked(bmain,
+                                         remapper,
+                                         (ID_REMAP_FLAG_NEVER_NULL_USAGE |
+                                          ID_REMAP_FORCE_NEVER_NULL_USAGE |
+                                          ID_REMAP_FORCE_INTERNAL_RUNTIME_POINTERS));
     }
+    BKE_id_remapper_free(remapper);
   }
+
   BKE_main_unlock(bmain);
 
   /* In usual reversed order, such that all usage of a given ID, even 'never NULL' ones,
diff --git a/source/blender/blenkernel/intern/lib_id_remapper.cc b/source/blender/blenkernel/intern/lib_id_remapper.cc
new file mode 100644
index 00000000000..c1734c9826a
--- /dev/null
+++ b/source/blender/blenkernel/intern/lib_id_remapper.cc
@@ -0,0 +1,175 @@
+/*
+ * 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.
+ *
+ * The Original Code is Copyright (C) 2022 by Blender Foundation.
+ */
+
+#include "DNA_ID.h"
+
+#include "BKE_idtype.h"
+#include "BKE_lib_id.h"
+#include "BKE_lib_remap.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_map.hh"
+
+using IDTypeFilter = uint64_t;
+
+namespace blender::bke::id::remapper {
+struct IDRemapper {
+ private:
+  Map<ID *, ID *> mappings;
+  IDTypeFilter source_types = 0;
+
+ public:
+  void clear()
+  {
+    mappings.clear();
+    source_types = 0;
+  }
+
+  bool is_empty() const
+  {
+    return mappings.is_empty();
+  }
+
+  void add(ID *old_id, ID *new_id)
+  {
+    BLI_assert(old_id != nullptr);
+    BLI_assert(new_id == nullptr || (GS(old_id->name) == GS(new_id->name)));
+    mappings.add(old_id, new_id);
+    source_types |= BKE_idtype_idcode_to_idfilter(GS(old_id->name));
+  }
+
+  bool contains_mappings_for_any(IDTypeFilter filter) const
+  {
+    return (source_types & filter) != 0;
+  }
+
+  IDRemapperApplyResult apply(ID **r_id_ptr, IDRemapperApplyOptions options) const
+  {
+    BLI_assert(r_id_ptr != nullptr);
+    if (*r_id_ptr == nullptr) {
+      return ID_REMAP_RESULT_SOURCE_NOT_MAPPABLE;
+    }
+
+    if (!mappings.contains(*r_id_ptr)) {
+      return ID_REMAP_RESULT_SOURCE_UNAVAILABLE;
+    }
+
+    if (options & ID_REMAP_APPLY_UPDATE_REFCOUNT) {
+      id_us_min(*r_id_ptr);
+    }
+
+    *r_id_ptr = mappings.lookup(*r_id_ptr);
+    if (*r_id_ptr == nullptr) {
+      return ID_REMAP_RESULT_SOURCE_UNASSIGNED;
+    }
+
+    if (options & ID_REMAP_APPLY_UPDATE_REFCOUNT) {
+      id_us_plus(*r_id_ptr);
+    }
+
+    if (options & ID_REMAP_APPLY_ENSURE_REAL) {
+      id_us_ensure_real(*r_id_ptr);
+    }
+    return ID_REMAP_RESULT_SOURCE_REMAPPED;
+  }
+
+  void iter(IDRemapperIterFunction func, void *user_data) const
+  {
+    for (auto item : mappings.items()) {
+      func(item.key, item.value, user_data);
+    }
+  }
+};
+
+}  // namespace blender::bke::id::remapper
+
+/** \brief wrap CPP IDRemapper to a C handle. */
+static IDRemapper *wrap(blender::bke::id::remapper::IDRemapper *remapper)
+{
+  return static_cast<IDRemapper *>(static_cast<void *>(remapper));
+}
+
+/** \brief wrap C handle to a CPP IDRemapper. */
+static blender::bke::id::remapper::IDRemapper *unwrap(IDRemapper *remapper)
+{
+  return static_cast<blender::bke::id::remapper::IDRemapper *>(static_cast<void *>(remapper));
+}
+
+/** \brief wrap C handle to a CPP IDRemapper. */
+static const blender::bke::id::remapper::IDRemapper *unwrap(const IDRemapper *remapper)
+{
+  return static_cast<const blender::bke::id::remapper::IDRemapper *>(
+      static_cast<const void *>(remapper));
+}
+
+extern "C" {
+
+IDRemapper *BKE_id_remapper_create(void)
+{
+  blender::bke::id::remapper::IDRemapper *remapper =
+      MEM_new<blender::bke::id::remapper::IDRemapper>(__func__);
+  return wrap(remapper);
+}
+
+void BKE_id_remapper_free(IDRemapper *id_remapper)
+{
+  blender::bke::id::remapper::IDRemapper *remapper = unwrap(id_remapper);
+  MEM_delete<blender::bke::id::remapper::IDRemapper>(remapper);
+}
+
+void BKE_id_remapper_clear(struct IDRemapper *id_remapper)
+{
+  blender::bke::id::remapper::IDRemapper *remapper = unwrap(id_remapper);
+  remapper->clear();
+}
+
+bool BKE_id_remapper_is_empty(const struct IDRemapper *id_remapper)
+{
+  const blender::bke::id::remapper::IDRemapper *remapper = unwrap(id_remapper);
+  return remapper->is_empty();
+}
+
+void BKE_id_remapper_add(IDRemapper *id_remapper, ID *old_id, ID *new_id)
+{
+  blender::bke::id::remapper::IDRemapper *remapper = unwrap(id_remapper);
+  remapper->add(old_id, new_id);
+}
+
+bool BKE_id_remapper_has_mapping_for(const struct IDRemapper *id_remapper, uint64_t type_filter)
+{
+  const blender::bke::id::remapper::IDRemapper *remapper = unwrap(id_remapper);
+  return remapper->contains_mappings_for_any(type_filter);
+}
+
+IDRemapperApplyResult BKE_id_remapper_apply(const IDRemapper *id_remapper,
+                                            ID **r_id_ptr,
+                                            const IDRemapperApplyOptions options)
+{
+  const blender::bke::id::remapper::IDRemapper *remapper = unwrap(id_remapper);
+  return remapper->apply(r_id_ptr, options);
+}
+
+void BKE_id_remapper_iter(const struct IDRemapper *id_remapper,
+                          IDRemapperIterFunction func,
+                          void *user_data)
+{
+  const blender::bke::id::remapper::IDRemapper *remapper = unwrap(id_remapper);
+  remapper->iter(func, user_data);
+}
+}
diff --git a/source/blender/blenkernel/intern/lib_id_remapper_test.cc b/source/blender/blenkernel/intern/lib_id_remapper_test.cc
new file mode 100644
index 00000000000..594f64dac73
--- /dev/null
+++ b/source/blender/blenkernel/intern/lib_id_remapper_test.cc
@@ -0,0 +1,83 @@
+/*
+ * 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.
+ *
+ * The Original Code is Copyright (C) 2022 by Blender Foundation.
+ */
+
+#include "testing/testing.h"
+
+#include "BKE_lib_remap.h"
+
+#include "BLI_string.h"
+
+#include "DNA_ID.h"
+
+namespace blender::bke::id::remapper::tests {
+
+TEST(lib_id_remapper, unavailable)
+{
+  ID id1;
+  ID *idp = &id1;
+
+  IDRemapper *remapper = BKE_id_remapper_create();
+  IDRemapperApplyResult result = BKE_id_remapper_apply(remapper, &idp, ID_REMAP_APPLY_DEFAULT);
+  EXPECT_EQ(result, ID_REMAP_RESULT_SOURCE_UNAVAILABLE);
+
+  BKE_id_remapper_free(remapper);
+}
+
+TEST(lib_id_remapper, not_mappable)
+{
+  ID *idp = nullptr;
+
+  IDRemapper *remapper = BKE_id_remapper_create();
+  IDRemapperApplyResult result = BKE_id_remapper_apply(remapper, &idp, ID_REMAP_APPLY_DEFAULT);
+  EXPECT_EQ(result, ID_REMAP_RESULT_SOURCE_NOT_MAPPABLE);
+
+  BKE_id_remapper_free(remapper);
+}
+
+TEST(lib_id_remapper, mapped)
+{
+  ID id1;
+  ID id2;
+  ID *idp = &id1;
+  BLI_strncpy(id1.name, "OB1", sizeof(id1.name));
+  BLI_strncpy(id2.name, "OB2", sizeof(id2.name));
+
+  IDRemapper *remapper = BKE_id_remapper_create();
+  BKE_id_remapper_add(remapper, &id1, &id2);
+  IDRemapperApplyResult result = BKE_id_remapper_apply(remapper, &idp, ID_REMAP_APPLY_DEFAULT);
+  EXPECT_EQ(result, ID_REMAP_RESULT_SOURCE_REMAPPED);
+  EXPECT_EQ(idp, &id2);
+
+  BKE_id_remapper_free(remapper);
+}
+
+TEST(lib_id_remapper, unassigned)
+{
+  ID id1;
+  ID *idp = &id1;
+
+  IDRemapper *remapper = BKE_id_remapper_create();
+  BKE_id_remapper_add(remapper, &id1, nullptr);
+  IDRemapperApplyResult result = BKE_id_remapper_apply(remapper, &idp, ID_REMAP_APPLY_DEFAULT);
+  EXPECT_EQ(result, ID_REMAP_RESULT_SOURCE_UNASSIGNED);
+  EXPECT_EQ(idp, nullptr);
+
+  BKE_id_remapper_free(remapper);
+}
+
+}  // namespace blender::bke::id::remapper::tests
diff --git a/source/blender/blenkernel/intern/lib_override.c b/source/blender/blenkernel/intern/lib_override.c
index 38ce8ea88b9..bc897e9075b 100644
--- a/source/blender/blenkernel/intern/lib_override.c
+++ b/source/blender/blenkernel/intern/lib_override.c
@@ -1121,6 +1121,45 @@ void BKE_lib_override_library_main_proxy_convert(Main *bmain, BlendFileReadRepor
   }
 }
 
+static void lib_override_library_remap(Main *bmain,
+                                       const ID *id_root_reference,
+                                       GHash *linkedref_to_old_override)
+{
+  ID *id;
+  struct IDRemapper *remapper = BKE_id_remapper_create();
+  FOREACH_MAIN_ID_BEGIN (bmain, id) {
+
+    if (id->tag & LIB_TAG_DOIT && id->newid != NULL && id->lib == id_root_reference->lib) {
+      ID *id_override_new = id->newid;
+      ID *id_override_old = BLI_ghash_lookup(linkedref_to_old_override, id);
+      if (id_override_old == NULL) {
+        continue;
+      }
+
+      BKE_id_remapper_add(remapper, id_override_old, id_override_new);
+      /* Remap no-main override IDs we just created too. */
+      GHashIterator linkedref_to_old_override_iter;
+      GHASH_ITER (linkedref_to_old_override_iter, linkedref_to_old_override) {
+        ID *id_override_old_iter = BLI_ghashIterator_getValue(&linkedref_to_old_override_iter);
+        if ((id_override_old_iter->tag & LIB_TAG_NO_MAIN) == 0) {
+          continue;
+        }
+
+        BKE_libblock_relink_ex(bmain,
+                               id_override_old_iter,
+                               id_override_old,
+                               id_override_new,
+                               ID_REMAP_FORCE_USER_REFCOUNT | ID_REMAP_FORCE_NEVER_NULL_USAGE);
+      }
+    }
+  }
+  FOREACH_MAIN_ID_END;
+
+  /* Remap all IDs to use the new override. */
+  BKE_libblock_remap_multiple(bmain, remapper, 0);
+  BKE_id_remapper_free(remapper);
+}
+
 static bool lib_override_library_resync(Main *bmain,
                                         Scene *scene,
                                         ViewLayer *view_layer,
@@ -1312,32 +1351,9 @@ static bool lib_override_library_resync(Main *bmain,
   }
   FOREACH_MAIN_LISTBASE_END;
 
-  /* We need to remap old to new override usages in a separate loop, after all new overrides have
+  /* We remap old to new override usages in a separate loop, after all new overrides have
    * been added to Main. */
-  FOREACH_MAIN_ID_BEGIN (bmain, id) {
-    if (id->tag & LIB_TAG_DOIT && id->newid != NULL && id->lib == id_root_reference->lib) {
-      ID *id_override_new = id->newid;
-      ID *id_override_old = BLI_ghash_lookup(linkedref_to_old_override, id);
-
-      if (id_override_old != NULL) {
-        /* Remap all IDs to use the new override. */
-        BKE_libblock_remap(bmain, id_override_old, id_override_new, 0);
-        /* Remap no-main override IDs we just created too. */
-        GHashIterator linkedref_to_old_override_iter;
-        GHASH_ITER (linkedref_to_old_override_iter, linkedref_to_old_override) {
-          ID *id_override_old_iter = BLI_ghashIterator_getValue(&linkedref_to_old_override_iter);
-          if (id_override_old_iter->tag & LIB_TAG_NO_MAIN) {
-            BKE_libblock_relink_ex(bmain,
-                                   id_override_old_iter,
-                                   id_override_old,
-                                   id_override_new,
-                                   ID_REMAP_FORCE_USER_REFCOUNT | ID_REMAP_FORCE_NEVER_NULL_USAGE);
-          }
-        }
-      }
-    }
-  }
-  FOREACH_MAIN_ID_END;
+  lib_override_library_remap(bmain, id_root_reference, linkedref_to_old_override);
 
   BKE_main_collection_sync(bmain);
 
diff --git a/source/blender/blenkernel/intern/lib_remap.c b/source/blender/blenkernel/intern/lib_remap.c
index ec97ca83703..c3ccedb9608 100644
--- a/source/blender/blenkernel/intern/lib_remap.c
+++ b/source/blender/blenkernel/intern/lib_remap.c
@@ -510,11 +510,18 @@ static void libblock_remap_data(
 #endif
 }
 
-void BKE_libblock_remap_locked(Main *bmain, void *old_idv, void *new_idv, const short remap_flags)
+typedef struct LibblockRemapMultipleUserData {
+  Main *bmain;
+  short remap_flags;
+} LibBlockRemapMultipleUserData;
+
+static void libblock_remap_foreach_idpair_cb(ID *old_id, ID *new_id, void *user_data)
 {
+  LibBlockRemapMultipleUserData *data = user_data;
+  Main *bmain = data->bmain;
+  const short remap_flags = data->remap_flags;
+
   IDRemap id_remap_data;
-  ID *old_id = old_idv;
-  ID *new_id = new_idv;
   int skipped_direct, skipped_refcounted;
 
   BLI_assert(old_id != NULL);
@@ -527,13 +534,6 @@ void BKE_libblock_remap_locked(Main *bmain, void *old_idv, void *new_idv, const
     free_notifier_reference_cb(old_id);
   }
 
-  /* We assume editors do not hold references to their IDs... This is false in some cases
-   * (Image is especially tricky here),
-   * editors' code is to handle refcount (id->us) itself then. */
-  if (remap_editor_id_reference_cb) {
-    remap_editor_id_reference_cb(old_id, new_id);
-  }
-
   skipped_direct = id_remap_data.skipped_direct;
   skipped_refcounted = id_remap_data.skipped_refcounted;
 
@@ -606,6 +606,41 @@ void BKE_libblock_remap_locked(Main *bmain, void *old_idv, void *new_idv, const
   DEG_relations_tag_update(bmain);
 }
 
+void BKE_libblock_remap_multiple_locked(Main *bmain,
+                                        const struct IDRemapper *mappings,
+                                        const short remap_flags)
+{
+  if (BKE_id_remapper_is_empty(mappings)) {
+    /* Early exit nothing to do. */
+    return;
+  }
+
+  LibBlockRemapMultipleUserData user_data;
+  user_data.bmain = bmain;
+  user_data.remap_flags = remap_flags;
+  BKE_id_remapper_iter(mappings, libblock_remap_foreach_idpair_cb, &user_data);
+
+  /* We assume editors do not hold references to their IDs... This is false in some cases
+   * (Image is especially tricky here),
+   * editors' code is to handle refcount (id->us) itself then. */
+  if (remap_editor_id_reference_cb) {
+    remap_editor_id_reference_cb(mappings);
+  }
+
+  /* Full rebuild of DEG! */
+  DEG_relations_tag_update(bmain);
+}
+
+void BKE_libblock_remap_locked(Main *bmain, void *old_idv, void *new_idv, const short remap_flags)
+{
+  struct IDRemapper *remapper = BKE_id_remapper_create();
+  ID *old_id = old_idv;
+  ID *new_id = new_idv;
+  BKE_id_remapper_add(remapper, old_id, new_id);
+  BKE_libblock_remap_multiple_locked(bmain, remapper, remap_flags);
+  BKE_id_remapper_free(remapper);
+}
+
 void BKE_libblock_remap(Main *bmain, void *old_idv, void *new_idv, const short remap_flags)
 {
   BKE_main_lock(bmain);
@@ -615,6 +650,17 @@ void BKE_libblock_remap(Main *bmain, void *old_idv, void *new_idv, const short r
   BKE_main_unlock(bmain);
 }
 
+void BKE_libblock_remap_multiple(Main *bmain,
+                                 const struct IDRemapper *mappings,
+                                 const short remap_flags)
+{
+  BKE_main_lock(bmain);
+
+  BKE_libblock_remap_multiple_locked(bmain, mappings, remap_flags);
+
+  BKE_main_unlock(bmain);
+}
+
 void BKE_libblock_unlink(Main *bmain,
                          void *idv,
                          const bool do_flag_never_null,