diff options
-rw-r--r-- | source/blender/blenkernel/intern/outliner_treehash.c | 20 |
1 files changed, 19 insertions, 1 deletions
diff --git a/source/blender/blenkernel/intern/outliner_treehash.c b/source/blender/blenkernel/intern/outliner_treehash.c index 03c327bec2f..09e2baf2be1 100644 --- a/source/blender/blenkernel/intern/outliner_treehash.c +++ b/source/blender/blenkernel/intern/outliner_treehash.c @@ -21,11 +21,20 @@ typedef struct TseGroup { TreeStoreElem **elems; + /* Index of last used #TreeStoreElem item, to speed up search for another one. */ int lastused; + /* Counter used to reduce the amount of 'rests' of `lastused` index, otherwise search for unused + * item is exponential and becomes critically slow when there are a lot of items in the group. */ + int lastused_reset_count; + /* Number of items currently in use. */ int size; + /* Number of items currently allocated. */ int allocated; } TseGroup; +/* Only allow reset of #TseGroup.lastused counter to 0 once every 1k search. */ +#define TSEGROUP_LASTUSED_RESET_VALUE 10000 + /* Allocate structure for TreeStoreElements; * Most of elements in treestore have no duplicates, * so there is no need to preallocate memory for more than one pointer */ @@ -47,6 +56,7 @@ static void tse_group_add_element(TseGroup *tse_group, TreeStoreElem *elem) sizeof(TreeStoreElem *) * tse_group->allocated); } tse_group->elems[tse_group->size] = elem; + tse_group->lastused = tse_group->size; tse_group->size++; } @@ -136,6 +146,7 @@ void BKE_outliner_treehash_clear_used(void *treehash) GHASH_ITER (gh_iter, treehash) { TseGroup *group = BLI_ghashIterator_getValue(&gh_iter); group->lastused = 0; + group->lastused_reset_count = 0; } } @@ -157,7 +168,6 @@ void BKE_outliner_treehash_add_element(void *treehash, TreeStoreElem *elem) *val_p = tse_group_create(); } group = *val_p; - group->lastused = 0; tse_group_add_element(group, elem); } @@ -204,7 +214,15 @@ TreeStoreElem *BKE_outliner_treehash_lookup_unused(void *treehash, int offset = group->lastused; for (int i = 0; i < size; i++, offset++) { + /* Once at the end of the array of items, in most cases it just means that all items are + * used, so only check the whole array once every TSEGROUP_LASTUSED_RESET_VALUE times. */ if (offset >= size) { + if (LIKELY(group->lastused_reset_count <= TSEGROUP_LASTUSED_RESET_VALUE)) { + group->lastused_reset_count++; + group->lastused = group->size - 1; + break; + } + group->lastused_reset_count = 0; offset = 0; } |