Add experimental batch IDs deletion.

Main idea is to remove IDs to be deleted from Main, to avoid looping on
them to remove other deleted IDs usage (this is the most expensive
process in ID deletion, by far).

Speed improvements when deleting a large amount of IDs from a Main
containing a lot of them is quite significant, some examples for Objects:
* Removing 1k from 10k: 32% quicker (2.5s to 1.7s).
* Removing 10k from 20k: 60% quicker (59s to 23s).
* Removing 20k from 20k: 99.5% quicker (82s to 0.4s)!

Note however that this process is more risky/touchy, since we by-pass
some safety checks from regular ID removal here.
So will only give access to that code from python API for now (in
separate commit), so that it gets really tested. Also still need to
think about how to hook it up in UI (probably mostly for Outliner),
since we often do higher-level operations there...

1 files changed, 114 insertions, 18 deletions

diff --git a/source/blender/blenkernel/intern/library_remap.c b/source/blender/blenkernel/intern/library_remap.c
index 39d7b690447..28d949a4f91 100644
--- a/source/blender/blenkernel/intern/library_remap.c
+++ b/source/blender/blenkernel/intern/library_remap.c
@@ -946,53 +946,149 @@ void BKE_id_free_us(Main *bmain, void *idv)      /* test users */
 	}
 }
 
-void BKE_id_delete(Main *bmain, void *idv)
+static void id_delete(Main *bmain, const bool do_tagged_deletion)
 {
+	const int tag = LIB_TAG_DOIT;
 	ListBase *lbarray[MAX_LIBARRAY];
 	int base_count, i;
 
-	base_count = set_listbasepointers(bmain, lbarray);
-	BKE_main_id_tag_all(bmain, LIB_TAG_DOIT, false);
+	/* Used by batch tagged deletion, when we call BKE_id_free then, id is no more in Main database,
+	 * and has already properly unlinked its other IDs usages.
+	 * UI users are always cleared in BKE_libblock_remap_locked() call, so we can always skip it. */
+	const int free_flag = LIB_ID_FREE_NO_UI_USER |
+	                      (do_tagged_deletion ? LIB_ID_FREE_NO_MAIN | LIB_ID_FREE_NO_USER_REFCOUNT : 0);
+	ListBase tagged_deleted_ids = {NULL};
 
-	/* First tag all datablocks directly from target lib.
-	 * Note that we go forward here, since we want to check dependencies before users (e.g. meshes before objects).
-	 * Avoids to have to loop twice. */
-	for (i = 0; i < base_count; i++) {
-		ListBase *lb = lbarray[i];
-		ID *id;
+	base_count = set_listbasepointers(bmain, lbarray);
 
-		for (id = lb->first; id; id = id->next) {
-			/* Note: in case we delete a library, we also delete all its datablocks! */
-			if ((id == (ID *)idv) || (id->lib == (Library *)idv) || (id->tag & LIB_TAG_DOIT)) {
-				id->tag |= LIB_TAG_DOIT;
+	BKE_main_lock(bmain);
+	if (do_tagged_deletion) {
+		/* Main idea of batch deletion is to remove all IDs to be deleted from Main database.
+		 * This means that we won't have to loop over all deleted IDs to remove usages
+		 * of other deleted IDs.
+		 * This gives tremendous speed-up when deleting a large amount of IDs from a Main
+		 * countaining thousands of those.
+		 * This also means that we have to be very careful here, as we by-pass many 'common'
+		 * processing, hence risking to 'corrupt' at least user counts, if not IDs themselves. */
+		bool keep_looping = true;
+		while (keep_looping) {
+			ID *id, *id_next;
+			ID *last_remapped_id = tagged_deleted_ids.last;
+			keep_looping = false;
+
+			/* First tag and remove from Main all datablocks directly from target lib.
+			 * Note that we go forward here, since we want to check dependencies before users
+			 * (e.g. meshes before objects). Avoids to have to loop twice. */
+			for (i = 0; i < base_count; i++) {
+				ListBase *lb = lbarray[i];
+
+				for (id = lb->first; id; id = id_next) {
+					id_next = id->next;
+					/* Note: in case we delete a library, we also delete all its datablocks! */
+					if ((id->tag & tag) || (id->lib != NULL && (id->lib->id.tag & tag))) {
+						BLI_remlink(lb, id);
+						BLI_addtail(&tagged_deleted_ids, id);
+						id->tag |= tag | LIB_TAG_NO_MAIN;
+						keep_looping = true;
+					}
+				}
+			}
+			if (last_remapped_id == NULL) {
+				last_remapped_id = tagged_deleted_ids.first;
+				if (last_remapped_id == NULL) {
+					BLI_assert(!keep_looping);
+					break;
+				}
+			}
+			for (id = last_remapped_id->next; id; id = id->next) {
 				/* Will tag 'never NULL' users of this ID too.
 				 * Note that we cannot use BKE_libblock_unlink() here, since it would ignore indirect (and proxy!)
 				 * links, this can lead to nasty crashing here in second, actual deleting loop.
 				 * Also, this will also flag users of deleted data that cannot be unlinked
 				 * (object using deleted obdata, etc.), so that they also get deleted. */
-				BKE_libblock_remap(bmain, id, NULL, ID_REMAP_FLAG_NEVER_NULL_USAGE | ID_REMAP_FORCE_NEVER_NULL_USAGE);
+				BKE_libblock_remap_locked(
+				            bmain, id, NULL,
+				            ID_REMAP_FLAG_NEVER_NULL_USAGE | ID_REMAP_FORCE_NEVER_NULL_USAGE);
+				/* Since we removed ID from Main, we also need to unlink its own other IDs usages ourself. */
+				BKE_libblock_relink_ex(bmain, id, NULL, NULL, true);
+				/* This is needed because we may not have remapped usages of that ID by other deleted ones. */
+//				id->us = 0;  /* Is it actually? */
+			}
+		}
+	}
+	else {
+		/* First tag all datablocks directly from target lib.
+		 * Note that we go forward here, since we want to check dependencies before users (e.g. meshes before objects).
+		 * Avoids to have to loop twice. */
+		for (i = 0; i < base_count; i++) {
+			ListBase *lb = lbarray[i];
+			ID *id, *id_next;
+
+			for (id = lb->first; id; id = id_next) {
+				id_next = id->next;
+				/* Note: in case we delete a library, we also delete all its datablocks! */
+				if ((id->tag & tag) || (id->lib != NULL && (id->lib->id.tag & tag))) {
+					id->tag |= tag;
+
+					/* Will tag 'never NULL' users of this ID too.
+					 * Note that we cannot use BKE_libblock_unlink() here, since it would ignore indirect (and proxy!)
+					 * links, this can lead to nasty crashing here in second, actual deleting loop.
+					 * Also, this will also flag users of deleted data that cannot be unlinked
+					 * (object using deleted obdata, etc.), so that they also get deleted. */
+					BKE_libblock_remap_locked(
+					            bmain, id, NULL,
+					            ID_REMAP_FLAG_NEVER_NULL_USAGE | ID_REMAP_FORCE_NEVER_NULL_USAGE);
+				}
 			}
 		}
 	}
+	BKE_main_unlock(bmain);
 
 	/* In usual reversed order, such that all usage of a given ID, even 'never NULL' ones, have been already cleared
 	 * when we reach it (e.g. Objects being processed before meshes, they'll have already released their 'reference'
 	 * over meshes when we come to freeing obdata). */
-	for (i = base_count; i--; ) {
+	for (i = do_tagged_deletion ? 1 : base_count; i--; ) {
 		ListBase *lb = lbarray[i];
 		ID *id, *id_next;
 
-		for (id = lb->first; id; id = id_next) {
+		for (id = do_tagged_deletion ? tagged_deleted_ids.first : lb->first; id; id = id_next) {
 			id_next = id->next;
-			if (id->tag & LIB_TAG_DOIT) {
+			if (id->tag & tag) {
 				if (id->us != 0) {
 #ifdef DEBUG_PRINT
 					printf("%s: deleting %s (%d)\n", __func__, id->name, id->us);
 #endif
 					BLI_assert(id->us == 0);
 				}
-				BKE_id_free(bmain, id);
+				BKE_id_free_ex(bmain, id, free_flag, !do_tagged_deletion);
 			}
 		}
 	}
+
+	bmain->is_memfile_undo_written = false;
+}
+
+/**
+ * Properly delete a single ID from given \a bmain database.
+ */
+void BKE_id_delete(Main *bmain, void *idv)
+{
+	BKE_main_id_tag_all(bmain, LIB_TAG_DOIT, false);
+	((ID *)idv)->tag |= LIB_TAG_DOIT;
+
+	id_delete(bmain, false);
+}
+
+/**
+ * Properly delete all IDs tagged with \a LIB_TAG_DOIT, in given \a bmain database.
+ *
+ * This is more efficient than calling #BKE_id_delete repitively on a large set of IDs
+ * (several times faster when deleting most of the IDs at once)...
+ *
+ * \warning Considered experimental for now, seems to be working OK but this is
+ *          risky code in a complicated area.
+ */
+void BKE_id_multi_tagged_delete(Main *bmain)
+{
+	id_delete(bmain, true);
 }