diff options
author | Campbell Barton <ideasman42@gmail.com> | 2015-08-18 04:22:07 +0300 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2015-08-18 04:39:23 +0300 |
commit | a08f8a4708379290e69ba74ae7abf78e813e0978 (patch) | |
tree | 4c28582068a59e004389404262dd6ace6c35397e | |
parent | ac62d44e4f570173d2094612c31615b5ff4acc7f (diff) |
Readfile: more efficient OldNewMap lookups
Even when lasthit can't be used to find the next address,
use it as a starting point for the full array search.
Gives approx 1/3 less array searching in own tests.
-rw-r--r-- | source/blender/blenloader/intern/readfile.c | 83 |
1 files changed, 64 insertions, 19 deletions
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c index ccb389bdcb2..32b736bc687 100644 --- a/source/blender/blenloader/intern/readfile.c +++ b/source/blender/blenloader/intern/readfile.c @@ -313,6 +313,56 @@ void blo_do_versions_oldnewmap_insert(OldNewMap *onm, void *oldaddr, void *newad oldnewmap_insert(onm, oldaddr, newaddr, nr); } +/** + * 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) +{ + 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; + } + } + } + + return -1; +} + static void *oldnewmap_lookup_and_inc(OldNewMap *onm, void *addr, bool increase_users) { int i; @@ -329,16 +379,14 @@ static void *oldnewmap_lookup_and_inc(OldNewMap *onm, void *addr, bool increase_ } } - for (i = 0; i < onm->nentries; i++) { + i = oldnewmap_lookup_entry_full(onm, addr, onm->lasthit); + if (i != -1) { OldNew *entry = &onm->entries[i]; - - if (entry->old == addr) { - onm->lasthit = i; - - if (increase_users) - entry->nr++; - return entry->newp; - } + BLI_assert(entry->old == addr); + onm->lasthit = i; + if (increase_users) + entry->nr++; + return entry->newp; } return NULL; @@ -368,16 +416,13 @@ static void *oldnewmap_liblookup(OldNewMap *onm, void *addr, void *lib) } else { /* note, this can be a bottle neck when loading some files */ - unsigned int nentries = (unsigned int)onm->nentries; - unsigned int i; - OldNew *entry; - - for (i = 0, entry = onm->entries; i < nentries; i++, entry++) { - if (entry->old == addr) { - ID *id = entry->newp; - if (id && (!lib || id->lib)) { - return id; - } + 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; } } } |