fix for [#36260] 2,300 Objects Makes Blender Unresponsive

- performance of outliner was low because of unoptimal data structures.
- now it uses BLI_mempool instead of custom mempool and GHash to make searches for duplicates faster.
- also fix undesired behaviour of BLI_mempool_as_arrayN

thanks to Campbell Barton and Lukas Tönne for helping me get a better fix put together.

2 files changed, 73 insertions, 23 deletions

diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 0ff3392ad00..72b426a155a 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -108,6 +108,7 @@
 #include "BLI_math.h"
 #include "BLI_edgehash.h"
 #include "BLI_threads.h"
+#include "BLI_mempool.h"
 
 #include "BLF_translation.h"
 
@@ -5684,16 +5685,24 @@ static void lib_link_screen(FileData *fd, Main *main)
 					}
 					else if (sl->spacetype == SPACE_OUTLINER) {
 						SpaceOops *so= (SpaceOops *)sl;
-						TreeStoreElem *tselem;
-						int a;
-						
 						so->search_tse.id = newlibadr(fd, NULL, so->search_tse.id);
 						
 						if (so->treestore) {
-							tselem = so->treestore->data;
-							for (a=0; a < so->treestore->usedelem; a++, tselem++) {
+							TreeStoreElem *tselem;
+							BLI_mempool_iter iter;
+
+							BLI_mempool_iternew(so->treestore, &iter);
+							while ((tselem = BLI_mempool_iterstep(&iter))) {
 								tselem->id = newlibadr(fd, NULL, tselem->id);
 							}
+							if (so->treehash) {
+								/* update hash table, because it depends on ids too */
+								BLI_ghash_clear(so->treehash, NULL, NULL);
+								BLI_mempool_iternew(so->treestore, &iter);
+								while ((tselem = BLI_mempool_iterstep(&iter))) {
+									BLI_ghash_insert(so->treehash, tselem, tselem);
+								}
+							}
 						}
 					}
 					else if (sl->spacetype == SPACE_NODE) {
@@ -6016,16 +6025,25 @@ void blo_lib_link_screen_restore(Main *newmain, bScreen *curscreen, Scene *cursc
 				}
 				else if (sl->spacetype == SPACE_OUTLINER) {
 					SpaceOops *so= (SpaceOops *)sl;
-					int a;
 					
 					so->search_tse.id = restore_pointer_by_name(newmain, so->search_tse.id, 0);
 					
 					if (so->treestore) {
-						TreeStore *ts = so->treestore;
-						TreeStoreElem *tselem = ts->data;
-						for (a = 0; a < ts->usedelem; a++, tselem++) {
+						TreeStoreElem *tselem;
+						BLI_mempool_iter iter;
+
+						BLI_mempool_iternew(so->treestore, &iter);
+						while ((tselem = BLI_mempool_iterstep(&iter))) {
 							tselem->id = restore_pointer_by_name(newmain, tselem->id, 0);
 						}
+						if (so->treehash) {
+							/* update hash table, because it depends on ids too */
+							BLI_ghash_clear(so->treehash, NULL, NULL);
+							BLI_mempool_iternew(so->treestore, &iter);
+							while ((tselem = BLI_mempool_iterstep(&iter))) {
+								BLI_ghash_insert(so->treehash, tselem, tselem);
+							}
+						}
 					}
 				}
 				else if (sl->spacetype == SPACE_NODE) {
@@ -6283,13 +6301,27 @@ static bool direct_link_screen(FileData *fd, bScreen *sc)
 			else if (sl->spacetype == SPACE_OUTLINER) {
 				SpaceOops *soops = (SpaceOops *) sl;
 				
-				soops->treestore = newdataadr(fd, soops->treestore);
-				if (soops->treestore) {
-					soops->treestore->data = newdataadr(fd, soops->treestore->data);
+				TreeStore *ts = newdataadr(fd, soops->treestore);
+				soops->treestore = NULL;
+				if (ts) {
+					TreeStoreElem *elems = newdataadr(fd, ts->data);
+					
+					soops->treestore = BLI_mempool_create(sizeof(TreeStoreElem), ts->usedelem,
+					                                      512, BLI_MEMPOOL_ALLOW_ITER);
+					if (ts->usedelem && elems) {
+						int i;
+						for (i = 0; i < ts->usedelem; i++) {
+							TreeStoreElem *new_elem = BLI_mempool_alloc(soops->treestore);
+							*new_elem = elems[i];
+						}
+						MEM_freeN(elems);
+					}
 					/* we only saved what was used */
-					soops->treestore->totelem = soops->treestore->usedelem;
 					soops->storeflag |= SO_TREESTORE_CLEANUP;	// at first draw
+					
+					MEM_freeN(ts);
 				}
+				soops->treehash = NULL;
 				soops->tree.first = soops->tree.last= NULL;
 			}
 			else if (sl->spacetype == SPACE_IMAGE) {
diff --git a/source/blender/blenloader/intern/writefile.c b/source/blender/blenloader/intern/writefile.c
index e170107713c..12804e8042d 100644
--- a/source/blender/blenloader/intern/writefile.c
+++ b/source/blender/blenloader/intern/writefile.c
@@ -144,12 +144,13 @@
 #include "BLI_bitmap.h"
 #include "BLI_blenlib.h"
 #include "BLI_linklist.h"
-#include "BKE_bpath.h"
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
+#include "BLI_mempool.h"
 
 #include "BKE_action.h"
 #include "BKE_blender.h"
+#include "BKE_bpath.h"
 #include "BKE_curve.h"
 #include "BKE_constraint.h"
 #include "BKE_global.h" // for G
@@ -2393,6 +2394,31 @@ static void write_region(WriteData *wd, ARegion *ar, int spacetype)
 	}
 }
 
+static void write_soops(WriteData *wd, SpaceOops *so)
+{
+	BLI_mempool *ts = so->treestore;
+	
+	if (ts) {
+		int elems = BLI_mempool_count(ts);
+		/* linearize mempool to array */
+		TreeStoreElem *data = elems ? BLI_mempool_as_arrayN(ts, "TreeStoreElem") : NULL;
+		TreeStore ts_flat = {elems, elems, data};
+		
+		/* temporarily replace mempool-treestore by flat-treestore */
+		so->treestore = (BLI_mempool *)&ts_flat;
+		writestruct(wd, DATA, "SpaceOops", 1, so);
+		/* restore old treestore */
+		so->treestore = ts;
+		writestruct(wd, DATA, "TreeStore", 1, &ts_flat);
+		if (data) {
+			writestruct(wd, DATA, "TreeStoreElem", elems, data);
+			MEM_freeN(data);
+		}
+	} else {
+		writestruct(wd, DATA, "SpaceOops", 1, so);
+	}
+}
+
 static void write_screens(WriteData *wd, ListBase *scrbase)
 {
 	bScreen *sc;
@@ -2475,15 +2501,7 @@ static void write_screens(WriteData *wd, ListBase *scrbase)
 				}
 				else if (sl->spacetype==SPACE_OUTLINER) {
 					SpaceOops *so= (SpaceOops *)sl;
-					
-					writestruct(wd, DATA, "SpaceOops", 1, so);
-
-					/* outliner */
-					if (so->treestore) {
-						writestruct(wd, DATA, "TreeStore", 1, so->treestore);
-						if (so->treestore->data)
-							writestruct(wd, DATA, "TreeStoreElem", so->treestore->usedelem, so->treestore->data);
-					}
+					write_soops(wd, so);
 				}
 				else if (sl->spacetype==SPACE_IMAGE) {
 					SpaceImage *sima= (SpaceImage *)sl;