Commit: 33993c056a557d8c51ff9d01ff3666ab81d40c29 Author: Jacques Lucke Date: Thu Dec 13 15:29:54 2018 +0100 Branches: blender2.8 https://developer.blender.org/rB33993c056a557d8c51ff9d01ff3666ab81d40c29
Speedup: new OldNewMap implementation for file loading In production files that use a lot of linking I measured loading speedups between 5% and 18%. In files that use less linking the speedup might not be noticeable at all, but it should not be slower. Reviewer: brecht Differential Revision: https://developer.blender.org/D4038 =================================================================== M source/blender/blenloader/intern/readfile.c =================================================================== diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c index 2f66f9707d9..6aff6f6506f 100644 --- a/source/blender/blenloader/intern/readfile.c +++ b/source/blender/blenloader/intern/readfile.c @@ -117,6 +117,7 @@ #include "BLI_math.h" #include "BLI_threads.h" #include "BLI_mempool.h" +#include "BLI_ghash.h" #include "BLT_translation.h" @@ -178,7 +179,6 @@ #include "readfile.h" - #include <errno.h> /** @@ -246,21 +246,6 @@ # define DEBUG_PRINTF(...) #endif -/***/ - -typedef struct OldNew { - const void *old; - void *newp; - int nr; -} OldNew; - -typedef struct OldNewMap { - OldNew *entries; - int nentries, entriessize; - bool sorted; - int lasthit; -} OldNewMap; - /* local prototypes */ static void *read_struct(FileData *fd, BHead *bh, const char *blockname); @@ -306,175 +291,155 @@ static const char *library_parent_filepath(Library *lib) return lib->parent ? lib->parent->filepath : "<direct>"; } -static OldNewMap *oldnewmap_new(void) -{ - OldNewMap *onm = MEM_callocN(sizeof(*onm), "OldNewMap"); - onm->entriessize = 1024; - onm->entries = MEM_malloc_arrayN(onm->entriessize, sizeof(*onm->entries), "OldNewMap.entries"); +/* ************** OldNewMap ******************* */ - return onm; -} +typedef struct OldNew { + const void *oldp; + void *newp; + /* `nr` is "user count" for data, and ID code for libdata. */ + int nr; +} OldNew; -static int verg_oldnewmap(const void *v1, const void *v2) -{ - const struct OldNew *x1 = v1, *x2 = v2; +typedef struct OldNewMap { + /* Array that stores the actual entries. */ + OldNew *entries; + int nentries; + /* Hashmap that stores indices into the `entries` array. */ + int32_t *map; - if (x1->old > x2->old) return 1; - else if (x1->old < x2->old) return -1; - return 0; -} + int capacity_exp; +} OldNewMap; +#define ENTRIES_CAPACITY(onm) (1 << (onm)->capacity_exp) +#define MAP_CAPACITY(onm) (1 << ((onm)->capacity_exp + 1)) +#define SLOT_MASK(onm) (MAP_CAPACITY(onm) - 1) +#define DEFAULT_SIZE_EXP 6 +#define PERTURB_SHIFT 5 + +/* based on the probing algorithm used in Python dicts. */ +#define ITER_SLOTS(onm, KEY, SLOT_NAME, INDEX_NAME) \ + uint32_t hash = BLI_ghashutil_ptrhash(KEY); \ + uint32_t mask = SLOT_MASK(onm); \ + uint perturb = hash; \ + int SLOT_NAME = mask & hash; \ + int INDEX_NAME = onm->map[SLOT_NAME]; \ + for (;;SLOT_NAME = mask & ((5 * SLOT_NAME) + 1 + perturb), perturb >>= PERTURB_SHIFT, INDEX_NAME = onm->map[SLOT_NAME]) + +static void oldnewmap_insert_index_in_map(OldNewMap *onm, const void *ptr, int index) +{ + ITER_SLOTS(onm, ptr, slot, stored_index) { + if (stored_index == -1) { + onm->map[slot] = index; + break; + } + } +} -static void oldnewmap_sort(FileData *fd) +static void oldnewmap_insert_or_replace(OldNewMap *onm, OldNew entry) { - BLI_assert(fd->libmap->sorted == false); - qsort(fd->libmap->entries, fd->libmap->nentries, sizeof(OldNew), verg_oldnewmap); - fd->libmap->sorted = 1; + ITER_SLOTS(onm, entry.oldp, slot, index) { + if (index == -1) { + onm->entries[onm->nentries] = entry; + onm->map[slot] = onm->nentries; + onm->nentries++; + break; + } + else if (onm->entries[index].oldp == entry.oldp) { + onm->entries[index] = entry; + break; + } + } } -/* nr is zero for data, and ID code for libdata */ -static void oldnewmap_insert(OldNewMap *onm, const void *oldaddr, void *newaddr, int nr) +static OldNew *oldnewmap_lookup_entry(const OldNewMap *onm, const void *addr) { - OldNew *entry; - - if (oldaddr == NULL || newaddr == NULL) return; - - if (UNLIKELY(onm->nentries == onm->entriessize)) { - onm->entriessize *= 2; - onm->entries = MEM_reallocN(onm->entries, sizeof(*onm->entries) * onm->entriessize); + ITER_SLOTS(onm, addr, slot, index) { + if (index >= 0) { + OldNew *entry = &onm->entries[index]; + if (entry->oldp == addr) { + return entry; + } + } + else { + return NULL; + } } - - entry = &onm->entries[onm->nentries++]; - entry->old = oldaddr; - entry->newp = newaddr; - entry->nr = nr; } -void blo_do_versions_oldnewmap_insert(OldNewMap *onm, const void *oldaddr, void *newaddr, int nr) +static void oldnewmap_clear_map(OldNewMap *onm) { - oldnewmap_insert(onm, oldaddr, newaddr, nr); + memset(onm->map, 0xFF, MAP_CAPACITY(onm) * sizeof(*onm->map)); } -/** - * Do a full search (no state). - * - * \param lasthit: Use as a reference position to avoid a full search - * from either end of the array, giving more efficient lookups. - * - * \note This would seem an ideal case for hash or btree lookups. - * However the data is written in-order, using the \a lasthit will normally avoid calling this function. - * Creating a btree/hash structure adds overhead for the common-case to optimize the corner-case - * (since most entries will never be retrieved). - * So just keep full lookups as a fall-back. - */ -static int oldnewmap_lookup_entry_full(const OldNewMap *onm, const void *addr, int lasthit) +static void oldnewmap_increase_size(OldNewMap *onm) { - const int nentries = onm->nentries; - const OldNew *entries = onm->entries; - int i; - - /* search relative to lasthit where possible */ - if (lasthit >= 0 && lasthit < nentries) { - - /* search forwards */ - i = lasthit; - while (++i != nentries) { - if (entries[i].old == addr) { - return i; - } - } - - /* search backwards */ - i = lasthit + 1; - while (i--) { - if (entries[i].old == addr) { - return i; - } - } - } - else { - /* search backwards (full) */ - i = nentries; - while (i--) { - if (entries[i].old == addr) { - return i; - } - } + onm->capacity_exp++; + onm->entries = MEM_reallocN(onm->entries, sizeof(*onm->entries) * ENTRIES_CAPACITY(onm)); + onm->map = MEM_reallocN(onm->map, sizeof(*onm->map) * MAP_CAPACITY(onm)); + oldnewmap_clear_map(onm); + for (int i = 0; i < onm->nentries; i++) { + oldnewmap_insert_index_in_map(onm, onm->entries[i].oldp, i); } - - return -1; } -static void *oldnewmap_lookup_and_inc(OldNewMap *onm, const void *addr, bool increase_users) + +/* Public OldNewMap API */ + +static OldNewMap *oldnewmap_new(void) { - int i; + OldNewMap *onm = MEM_callocN(sizeof(*onm), "OldNewMap"); - if (addr == NULL) return NULL; + onm->capacity_exp = DEFAULT_SIZE_EXP; + onm->entries = MEM_malloc_arrayN(ENTRIES_CAPACITY(onm), sizeof(*onm->entries), "OldNewMap.entries"); + onm->map = MEM_malloc_arrayN(MAP_CAPACITY(onm), sizeof(*onm->map), "OldNewMap.map"); + oldnewmap_clear_map(onm); - if (onm->lasthit < onm->nentries - 1) { - OldNew *entry = &onm->entries[++onm->lasthit]; + return onm; +} - if (entry->old == addr) { - if (increase_users) - entry->nr++; - return entry->newp; - } - } +static void oldnewmap_insert(OldNewMap *onm, const void *oldaddr, void *newaddr, int nr) +{ + if (oldaddr == NULL || newaddr == NULL) return; - i = oldnewmap_lookup_entry_full(onm, addr, onm->lasthit); - if (i != -1) { - OldNew *entry = &onm->entries[i]; - BLI_assert(entry->old == addr); - onm->lasthit = i; - if (increase_users) - entry->nr++; - return entry->newp; + if (UNLIKELY(onm->nentries == ENTRIES_CAPACITY(onm))) { + oldnewmap_increase_size(onm); } - return NULL; + OldNew entry; + entry.oldp = oldaddr; + entry.newp = newaddr; + entry.nr = nr; + oldnewmap_insert_or_replace(onm, entry); } -/* for libdata, nr has ID code, no increment */ -static void *oldnewmap_liblookup(OldNewMap *onm, const void *addr, const void *lib) +void blo_do_versions_oldnewmap_insert(OldNewMap *onm, const void *oldaddr, void *newaddr, int nr) { - if (addr == NULL) { - return NULL; - } + oldnewmap_insert(onm, oldaddr, newaddr, nr); +} - /* lasthit works fine for non-libdata, linking there is done in same sequence as writing */ - if (onm->sorted) { - const OldNew entry_s = {.old = addr}; - OldNew *entry = bsearch(&entry_s, onm->entries, onm->nentries, sizeof(OldNew), verg_oldnewmap); - if (entry) { - ID *id = entry->newp; +static void *oldnewmap_lookup_and_inc(OldNewMap *onm, const void *addr, bool increase_users) +{ + OldNew *entry = oldnewmap_lookup_entry(onm, addr); + if (entry == NULL) return NULL; + if (increase_users) entry->nr++; + return entry->newp; +} - if (id && (!lib || id->lib)) { - return id; - } - } - } - else { - /* note, this can be a bottle neck when loading some files */ - const int i = oldnewmap_lookup_entry_full(onm, addr, -1); - if (i != -1) { - OldNew *entry = &onm->entries[i]; - ID *id = entry->newp; - BLI_assert(entry->old == addr); - if (id && (!lib || id->lib)) { - return id; - } - } - } +/* for libdata, OldNew.nr has ID code, no increment */ +static void *oldnewmap_liblookup(OldNewMap *onm, const void *addr, const void *lib) +{ + if (addr == NULL) return NULL; + ID *id = oldnewmap_lookup_and_inc(onm, addr, false); + if (id == NULL) return NULL; + if (!lib || id->lib) return id; return NULL; } static void oldnewmap_free_unused(OldNewMap *onm) { - int i; - - for (i = 0; i < onm->nentries; i++) { + for (int i = 0; i < onm->nentries; i++) { OldNew *entry = &onm->entries[i]; if (entry->nr == 0) { MEM_freeN(entry->newp); @@ -485,16 +450,25 @@ static void oldnewmap_free_unused(OldNewMap *onm) static void oldnewmap_clear(OldNewMap *onm) { + onm->capacity_exp = DEFAULT_SIZE_EXP; + oldnewmap_clear_map(onm); onm->nentries = 0; - onm->lasthit = 0; } static void oldnewmap_free(OldNewMap *onm) { MEM_freeN(onm->entries); + MEM_freeN(onm->map); MEM_freeN(onm); } +#undef ENTRIES_CAPACITY +#undef MAP_CAPACITY +#undef SLOT_MASK +#undef DEFAULT_SIZE_EXP +#undef PERTURB_SHIFT +#undef ITER_SLOTS + /***/ static void read_libraries(FileData *basefd, ListBase *mainlist); @@ -1486,31 +1460,6 @@ static void *newdataadr(FileData *fd, const void *adr) /* only direct datab return oldnewmap_lookup_and_inc(fd->datamap, adr, true); } -/* This is a special version of newdataadr() which allows us to keep lasthit of - * map unchanged. In certain cases this makes file loading time significantly - * faster. - * - * Use this function in cases like restoring pointer from one list element to - * another list element, but keep lasthit value so we can continue restoring - * pointers efficiently. - * - * Examp @@ Diff output truncated at 10240 characters. @@ _______________________________________________ Bf-blender-cvs mailing list [email protected] https://lists.blender.org/mailman/listinfo/bf-blender-cvs
