Fix (unreported) infinite tie building Outliner liboverride hierarchy tree.

In complex scenes featuring thousands of connections between IDs in
their liboverride hierarchies (e.g. Heist files), the time required to
check if tree items were available (before allocated a new one) would
become insanely long (O(n^2)).

This commit brings it back to roughly a constant time, only re-checking
the whole array for unused items once in a while (once every 10k times
currently), since in almost all cases is the index after `lastused`
value is not unused, and you have reached the end of the currently used
array of items, you actually need to 'allocate' a new one anyway.

It also improves the handling of `lastused` index, in particular in
`tse_group_add_element`.

This makes switching to the Outliner override hierarchy view in Heist
scenes from virtually infinite time (more than 30mins for sure) to about
20 seconds on my machine. Still far from being effectively usable.

Note that this is only a bandaid fix anyway, root of the issue is that
this view has to deal with way too many items in its tree, current code
is not designed for that. Either outliner has to improve its tree
handling (by only building subsets of the whole tree maybe?), or we have
to cull/filter out some of the ID relationships between overridden IDs
to make this view actually usable. Maybe limit the depth of the tree?

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;
       }