[Bf-blender-cvs] [ce6d20b54e3] master: Add experimental batch IDs deletion.

Bastien Montagne noreply at git.blender.org
Wed Jan 16 12:03:01 CET 2019


Commit: ce6d20b54e3077e8d57103de3e7933069a2d54e7
Author: Bastien Montagne
Date:   Wed Jan 16 11:50:20 2019 +0100
Branches: master
https://developer.blender.org/rBce6d20b54e3077e8d57103de3e7933069a2d54e7

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...

===================================================================

M	source/blender/blenkernel/BKE_library.h
M	source/blender/blenkernel/intern/library_remap.c

===================================================================

diff --git a/source/blender/blenkernel/BKE_library.h b/source/blender/blenkernel/BKE_library.h
index d03834d2995..0560646c49b 100644
--- a/source/blender/blenkernel/BKE_library.h
+++ b/source/blender/blenkernel/BKE_library.h
@@ -140,15 +140,16 @@ enum {
 	LIB_ID_FREE_NO_UI_USER         = 1 << 9,  /* Do not attempt to remove freed ID from UI data/notifiers/... */
 };
 
-void  BKE_libblock_free_datablock(struct ID *id, const int flag) ATTR_NONNULL();
-void  BKE_libblock_free_data(struct ID *id, const bool do_id_user) ATTR_NONNULL();
+void BKE_libblock_free_datablock(struct ID *id, const int flag) ATTR_NONNULL();
+void BKE_libblock_free_data(struct ID *id, const bool do_id_user) ATTR_NONNULL();
 
 void BKE_id_free_ex(struct Main *bmain, void *idv, int flag, const bool use_flag_from_idtag);
 void BKE_id_free(struct Main *bmain, void *idv);
 
-void  BKE_id_free_us(struct Main *bmain, void *idv) ATTR_NONNULL();
+void BKE_id_free_us(struct Main *bmain, void *idv) ATTR_NONNULL();
 
-void  BKE_id_delete(struct Main *bmain, void *idv) ATTR_NONNULL();
+void BKE_id_delete(struct Main *bmain, void *idv) ATTR_NONNULL();
+void BKE_id_multi_tagged_delete(struct Main *bmain) ATTR_NONNULL();
 
 void BKE_libblock_management_main_add(struct Main *bmain, void *idv);
 void BKE_libblock_management_main_remove(struct Main *bmain, void *idv);
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);
 }



More information about the Bf-blender-cvs mailing list