From 0624fad0f3ffa1167c8d807d991aa5788236925b Mon Sep 17 00:00:00 2001 From: Bastien Montagne Date: Thu, 16 Dec 2021 10:45:28 +0100 Subject: 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. --- source/blender/blenkernel/intern/lib_override.c | 74 +++++++++++++++++++++---- 1 file 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) { -- cgit v1.2.3