From db4fe8e3223b36615e53cf64f4a55f6d974c4597 Mon Sep 17 00:00:00 2001 From: Bastien Montagne Date: Wed, 30 Jun 2021 15:19:35 +0200 Subject: BlenRead: Add GHash-based search for already read linked IDs. Ths commit adds a new `IDNameLibMap` to `Main`, used during file reading to quickly find already read linked IDs. Without that, search would use string-based search over list of linked data, which becomes extremely slow and inneficient in cases where a lot of IDs are linked from a same library. See also {T89194}. Extrem-usecase reported in T89194 is now about 4 times faster in linked data reading (about 2 times faster for the whole .blend file loading). More normal cases (like Sprites studio production files) have barely measurable speed improvements, a few percents at best. NOTE: `main_idmap` API was extended to support insertion and removal of IDs from the mapping, avoids having to re-create the whole thing several time during libraries expansion in readcode. Differential Revision: https://developer.blender.org/D11757 --- source/blender/blenkernel/BKE_main.h | 4 ++ source/blender/blenkernel/BKE_main_idmap.h | 5 ++ source/blender/blenkernel/intern/main.c | 5 ++ source/blender/blenkernel/intern/main_idmap.c | 87 ++++++++++++++++++++++----- source/blender/blenloader/intern/readfile.c | 57 +++++++++++++++++- 5 files changed, 142 insertions(+), 16 deletions(-) (limited to 'source/blender') diff --git a/source/blender/blenkernel/BKE_main.h b/source/blender/blenkernel/BKE_main.h index ed930fe539d..ae60a5563b5 100644 --- a/source/blender/blenkernel/BKE_main.h +++ b/source/blender/blenkernel/BKE_main.h @@ -48,6 +48,7 @@ struct BLI_mempool; struct BlendThumbnail; struct GHash; struct GSet; +struct IDNameLib_Map; struct ImBuf; struct Library; struct MainLock; @@ -191,6 +192,9 @@ typedef struct Main { */ struct MainIDRelations *relations; + /* IDMap of IDs. Currently used when reading (expanding) libraries. */ + struct IDNameLib_Map *id_map; + struct MainLock *lock; } Main; diff --git a/source/blender/blenkernel/BKE_main_idmap.h b/source/blender/blenkernel/BKE_main_idmap.h index bffb12a5136..ff69883f0fb 100644 --- a/source/blender/blenkernel/BKE_main_idmap.h +++ b/source/blender/blenkernel/BKE_main_idmap.h @@ -50,8 +50,13 @@ struct IDNameLib_Map *BKE_main_idmap_create(struct Main *bmain, const int idmap_types) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1); void BKE_main_idmap_destroy(struct IDNameLib_Map *id_map) ATTR_NONNULL(); + +void BKE_main_idmap_insert_id(struct IDNameLib_Map *id_map, struct ID *id) ATTR_NONNULL(); +void BKE_main_idmap_remove_id(struct IDNameLib_Map *id_map, struct ID *id) ATTR_NONNULL(); + struct Main *BKE_main_idmap_main_get(struct IDNameLib_Map *id_map) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); + struct ID *BKE_main_idmap_lookup_name(struct IDNameLib_Map *id_map, short id_type, const char *name, diff --git a/source/blender/blenkernel/intern/main.c b/source/blender/blenkernel/intern/main.c index 655b6d3732c..bb33f5f9f87 100644 --- a/source/blender/blenkernel/intern/main.c +++ b/source/blender/blenkernel/intern/main.c @@ -38,6 +38,7 @@ #include "BKE_lib_id.h" #include "BKE_lib_query.h" #include "BKE_main.h" +#include "BKE_main_idmap.h" #include "IMB_imbuf.h" #include "IMB_imbuf_types.h" @@ -194,6 +195,10 @@ void BKE_main_free(Main *mainvar) BKE_main_relations_free(mainvar); } + if (mainvar->id_map) { + BKE_main_idmap_destroy(mainvar->id_map); + } + BLI_spin_end((SpinLock *)mainvar->lock); MEM_freeN(mainvar->lock); MEM_freeN(mainvar); diff --git a/source/blender/blenkernel/intern/main_idmap.c b/source/blender/blenkernel/intern/main_idmap.c index 1421d456883..8f462f814e5 100644 --- a/source/blender/blenkernel/intern/main_idmap.c +++ b/source/blender/blenkernel/intern/main_idmap.c @@ -21,6 +21,7 @@ #include "BLI_ghash.h" #include "BLI_listbase.h" +#include "BLI_mempool.h" #include "BLI_utildefines.h" #include "DNA_ID.h" @@ -58,8 +59,6 @@ struct IDNameLib_Key { struct IDNameLib_TypeMap { GHash *map; short id_type; - /* only for storage of keys in the ghash, avoid many single allocs */ - struct IDNameLib_Key *keys; }; /** @@ -71,6 +70,9 @@ struct IDNameLib_Map { struct Main *bmain; struct GSet *valid_id_pointers; int idmap_types; + + /* For storage of keys for the TypeMap ghash, avoids many single allocs. */ + BLI_mempool *type_maps_keys_pool; }; static struct IDNameLib_TypeMap *main_idmap_from_idcode(struct IDNameLib_Map *id_map, @@ -115,6 +117,7 @@ struct IDNameLib_Map *BKE_main_idmap_create(struct Main *bmain, BLI_assert(type_map->id_type != 0); } BLI_assert(index == INDEX_ID_MAX); + id_map->type_maps_keys_pool = NULL; if (idmap_types & MAIN_IDMAP_TYPE_UUID) { ID *id; @@ -148,6 +151,60 @@ struct IDNameLib_Map *BKE_main_idmap_create(struct Main *bmain, return id_map; } +void BKE_main_idmap_insert_id(struct IDNameLib_Map *id_map, ID *id) +{ + if (id_map->idmap_types & MAIN_IDMAP_TYPE_NAME) { + const short id_type = GS(id->name); + struct IDNameLib_TypeMap *type_map = main_idmap_from_idcode(id_map, id_type); + + /* No need to do anything if map has not been lazyly created yet. */ + if (LIKELY(type_map != NULL) && type_map->map != NULL) { + BLI_assert(id_map->type_maps_keys_pool != NULL); + + struct IDNameLib_Key *key = BLI_mempool_alloc(id_map->type_maps_keys_pool); + key->name = id->name + 2; + key->lib = id->lib; + BLI_ghash_insert(type_map->map, key, id); + } + } + + if (id_map->idmap_types & MAIN_IDMAP_TYPE_UUID) { + BLI_assert(id_map->uuid_map != NULL); + BLI_assert(id->session_uuid != MAIN_ID_SESSION_UUID_UNSET); + void **id_ptr_v; + const bool existing_key = BLI_ghash_ensure_p( + id_map->uuid_map, POINTER_FROM_UINT(id->session_uuid), &id_ptr_v); + BLI_assert(existing_key == false); + UNUSED_VARS_NDEBUG(existing_key); + + *id_ptr_v = id; + } +} + +void BKE_main_idmap_remove_id(struct IDNameLib_Map *id_map, ID *id) +{ + if (id_map->idmap_types & MAIN_IDMAP_TYPE_NAME) { + const short id_type = GS(id->name); + struct IDNameLib_TypeMap *type_map = main_idmap_from_idcode(id_map, id_type); + + /* No need to do anything if map has not been lazyly created yet. */ + if (LIKELY(type_map != NULL) && type_map->map != NULL) { + BLI_assert(id_map->type_maps_keys_pool != NULL); + + /* NOTE: We cannot free the key from the MemPool here, would need new API from GHash to also + * retrieve key pointer. Not a big deal for now */ + BLI_ghash_remove(type_map->map, &(struct IDNameLib_Key){id->name + 2, id->lib}, NULL, NULL); + } + } + + if (id_map->idmap_types & MAIN_IDMAP_TYPE_UUID) { + BLI_assert(id_map->uuid_map != NULL); + BLI_assert(id->session_uuid != MAIN_ID_SESSION_UUID_UNSET); + + BLI_ghash_remove(id_map->uuid_map, POINTER_FROM_UINT(id->session_uuid), NULL, NULL); + } +} + struct Main *BKE_main_idmap_main_get(struct IDNameLib_Map *id_map) { return id_map->bmain; @@ -181,20 +238,17 @@ ID *BKE_main_idmap_lookup_name(struct IDNameLib_Map *id_map, return NULL; } - /* lazy init */ + /* Lazy init. */ if (type_map->map == NULL) { - ListBase *lb = which_libbase(id_map->bmain, id_type); - const int lb_len = BLI_listbase_count(lb); - if (lb_len == 0) { - return NULL; + if (id_map->type_maps_keys_pool == NULL) { + id_map->type_maps_keys_pool = BLI_mempool_create( + sizeof(struct IDNameLib_Key), 1024, 1024, BLI_MEMPOOL_NOP); } - type_map->map = BLI_ghash_new_ex(idkey_hash, idkey_cmp, __func__, lb_len); - type_map->keys = MEM_mallocN(sizeof(struct IDNameLib_Key) * lb_len, __func__); - - GHash *map = type_map->map; - struct IDNameLib_Key *key = type_map->keys; - for (ID *id = lb->first; id; id = id->next, key++) { + GHash *map = type_map->map = BLI_ghash_new(idkey_hash, idkey_cmp, __func__); + ListBase *lb = which_libbase(id_map->bmain, id_type); + for (ID *id = lb->first; id; id = id->next) { + struct IDNameLib_Key *key = BLI_mempool_alloc(id_map->type_maps_keys_pool); key->name = id->name + 2; key->lib = id->lib; BLI_ghash_insert(map, key, id); @@ -235,14 +289,19 @@ void BKE_main_idmap_destroy(struct IDNameLib_Map *id_map) if (type_map->map) { BLI_ghash_free(type_map->map, NULL, NULL); type_map->map = NULL; - MEM_freeN(type_map->keys); } } + if (id_map->type_maps_keys_pool != NULL) { + BLI_mempool_destroy(id_map->type_maps_keys_pool); + id_map->type_maps_keys_pool = NULL; + } } if (id_map->idmap_types & MAIN_IDMAP_TYPE_UUID) { BLI_ghash_free(id_map->uuid_map, NULL, NULL); } + BLI_assert(id_map->type_maps_keys_pool == NULL); + if (id_map->valid_id_pointers != NULL) { BLI_gset_free(id_map->valid_id_pointers, NULL); } diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c index 11986f11fea..e48c305fc4b 100644 --- a/source/blender/blenloader/intern/readfile.c +++ b/source/blender/blenloader/intern/readfile.c @@ -464,6 +464,13 @@ void blo_join_main(ListBase *mainlist) Main *tojoin, *mainl; mainl = mainlist->first; + + if (mainl->id_map != NULL) { + /* Cannot keep this since we add some IDs from joined mains. */ + BKE_main_idmap_destroy(mainl->id_map); + mainl->id_map = NULL; + } + while ((tojoin = mainl->next)) { add_main_to_main(mainl, tojoin); BLI_remlink(mainlist, tojoin); @@ -502,6 +509,12 @@ void blo_split_main(ListBase *mainlist, Main *main) return; } + if (main->id_map != NULL) { + /* Cannot keep this since we remove some IDs from given main. */ + BKE_main_idmap_destroy(main->id_map); + main->id_map = NULL; + } + /* (Library.temp_index -> Main), lookup table */ const uint lib_main_array_len = BLI_listbase_count(&main->libraries); Main **lib_main_array = MEM_malloc_arrayN(lib_main_array_len, sizeof(*lib_main_array), __func__); @@ -3209,6 +3222,10 @@ static ID *create_placeholder(Main *mainvar, const short idcode, const char *idn BLI_addtail(lb, ph_id); id_sort_by_name(lb, ph_id, NULL); + if (mainvar->id_map != NULL) { + BKE_main_idmap_insert_id(mainvar->id_map, ph_id); + } + if ((tag & LIB_TAG_TEMP_MAIN) == 0) { BKE_lib_libblock_session_uuid_ensure(ph_id); } @@ -3667,6 +3684,10 @@ static BHead *read_libblock(FileData *fd, if (r_id) { *r_id = id_old; } + if (main->id_map != NULL) { + BKE_main_idmap_insert_id(main->id_map, id_old); + } + return blo_bhead_next(fd, bhead); } } @@ -3725,6 +3746,11 @@ static BHead *read_libblock(FileData *fd, } direct_link_id(fd, main, id_tag, id, id_old); + + if (main->id_map != NULL) { + BKE_main_idmap_insert_id(main->id_map, id); + } + return blo_bhead_next(fd, bhead); } @@ -3748,6 +3774,13 @@ static BHead *read_libblock(FileData *fd, else if (id_old) { /* For undo, store contents read into id at id_old. */ read_libblock_undo_restore_at_old_address(fd, main, id, id_old); + + if (main->id_map != NULL) { + BKE_main_idmap_insert_id(main->id_map, id_old); + } + } + else if (main->id_map != NULL) { + BKE_main_idmap_insert_id(main->id_map, id); } return bhead; @@ -4299,6 +4332,8 @@ BlendFileData *blo_read_file_internal(FileData *fd, const char *filepath) fd->mainlist = NULL; /* Safety, this is local variable, shall not be used afterward. */ + BLI_assert(bfd->main->id_map == NULL); + return bfd; } @@ -4443,9 +4478,16 @@ static BHead *find_bhead_from_idname(FileData *fd, const char *idname) static ID *is_yet_read(FileData *fd, Main *mainvar, BHead *bhead) { + if (mainvar->id_map == NULL) { + mainvar->id_map = BKE_main_idmap_create(mainvar, false, NULL, MAIN_IDMAP_TYPE_NAME); + } + BLI_assert(BKE_main_idmap_main_get(mainvar->id_map) == mainvar); + const char *idname = blo_bhead_id_name(fd, bhead); - /* which_libbase can be NULL, intentionally not using idname+2 */ - return BLI_findstring(which_libbase(mainvar, GS(idname)), idname, offsetof(ID, name)); + + ID *id = BKE_main_idmap_lookup_name(mainvar->id_map, GS(idname), idname + 2, mainvar->curlib); + BLI_assert(id == BLI_findstring(which_libbase(mainvar, GS(idname)), idname, offsetof(ID, name))); + return id; } /** \} */ @@ -5196,6 +5238,10 @@ static void library_link_end(Main *mainl, Main *mainvar; Library *curlib; + if (mainl->id_map == NULL) { + mainl->id_map = BKE_main_idmap_create(mainl, false, NULL, MAIN_IDMAP_TYPE_NAME); + } + /* expander now is callback function */ BLO_main_expander(expand_doit_library); @@ -5401,6 +5447,9 @@ static void read_library_linked_ids(FileData *basefd, ID *id_next = id->next; if ((id->tag & LIB_TAG_ID_LINK_PLACEHOLDER) && !(id->flag & LIB_INDIRECT_WEAK_LINK)) { BLI_remlink(lbarray[a], id); + if (mainvar->id_map != NULL) { + BKE_main_idmap_remove_id(mainvar->id_map, id); + } /* When playing with lib renaming and such, you may end with cases where * you have more than one linked ID of the same data-block from same @@ -5569,6 +5618,10 @@ static void read_libraries(FileData *basefd, ListBase *mainlist) if (fd) { do_it = true; + + if (mainptr->id_map == NULL) { + mainptr->id_map = BKE_main_idmap_create(mainptr, false, NULL, MAIN_IDMAP_TYPE_NAME); + } } /* Read linked data-locks for each link placeholder, and replace -- cgit v1.2.3