[Bf-blender-cvs] [46607bc09d5] master: ID Management: Improve speed of code used when creating/renaming and ID.

Bastien Montagne noreply at git.blender.org
Fri Dec 20 14:46:36 CET 2019


Commit: 46607bc09d5cd9fa3570e5ad4b01ea4ea7adaffc
Author: Bastien Montagne
Date:   Thu Dec 19 21:58:59 2019 +0100
Branches: master
https://developer.blender.org/rB46607bc09d5cd9fa3570e5ad4b01ea4ea7adaffc

ID Management: Improve speed of code used when creating/renaming and ID.

This commit affects `id_sort_by_name()` and `check_for_dupid()` helper:
* Add a new parameter, `ID *id_sorting_hint`, to `id_sort_by_name()`,
  and when non-NULL, check if we can insert `id` immediately before or
  after it. This can dramatically reduce time spent in that function.
* Use loop over whole list in `check_for_dupid()` to also define the
  likely ID pointer that will be neighbor with our new one.

This gives another decent speedup to all massive addition cases:

| Number and type of names of IDs  | old code | new code | speed improvement |
| -------------------------------- | -------- | -------- | ----------------- |
| 40K, mixed (14k rand, 26k const) |      39s |      33s |               18% |
| 40K, fully random                |      51s |      42s |               21% |
| 40K, fully constant              |      40s |      34s |               18% |

Combined with the previous commits, this makes massive addition of IDs more
than twice as fast as previously.

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

M	source/blender/blenkernel/BKE_library.h
M	source/blender/blenkernel/intern/blendfile.c
M	source/blender/blenkernel/intern/library.c
M	source/blender/blenloader/intern/readfile.c
M	source/blender/windowmanager/intern/wm_files_link.c

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

diff --git a/source/blender/blenkernel/BKE_library.h b/source/blender/blenkernel/BKE_library.h
index 71799bf74f6..c41cd50eba5 100644
--- a/source/blender/blenkernel/BKE_library.h
+++ b/source/blender/blenkernel/BKE_library.h
@@ -199,7 +199,7 @@ bool BKE_id_copy_is_allowed(const struct ID *id);
 bool BKE_id_copy(struct Main *bmain, const struct ID *id, struct ID **newid);
 bool BKE_id_copy_ex(struct Main *bmain, const struct ID *id, struct ID **r_newid, const int flag);
 void BKE_id_swap(struct Main *bmain, struct ID *id_a, struct ID *id_b);
-void id_sort_by_name(struct ListBase *lb, struct ID *id);
+void id_sort_by_name(struct ListBase *lb, struct ID *id, struct ID *id_sorting_hint);
 void BKE_id_expand_local(struct Main *bmain, struct ID *id);
 void BKE_id_copy_ensure_local(struct Main *bmain, const struct ID *old_id, struct ID *new_id);
 
diff --git a/source/blender/blenkernel/intern/blendfile.c b/source/blender/blenkernel/intern/blendfile.c
index 36f0950cd08..62173393256 100644
--- a/source/blender/blenkernel/intern/blendfile.c
+++ b/source/blender/blenkernel/intern/blendfile.c
@@ -873,7 +873,7 @@ bool BKE_blendfile_write_partial(Main *bmain_src,
 
     while ((id = BLI_pophead(lb_src))) {
       BLI_addtail(lb_dst, id);
-      id_sort_by_name(lb_dst, id);
+      id_sort_by_name(lb_dst, id, NULL);
     }
   }
 
diff --git a/source/blender/blenkernel/intern/library.c b/source/blender/blenkernel/intern/library.c
index 2006c5af6f0..8a4814e1a92 100644
--- a/source/blender/blenkernel/intern/library.c
+++ b/source/blender/blenkernel/intern/library.c
@@ -1547,70 +1547,99 @@ ID *BKE_libblock_find_name(struct Main *bmain, const short type, const char *nam
   return BLI_findstring(lb, name, offsetof(ID, name) + 2);
 }
 
-#define ID_SORT_STEP_SIZE 512
-void id_sort_by_name(ListBase *lb, ID *id)
+/**
+ * Sort given \a id into given \a lb list, using case-insensitive comparison of the id names.
+ *
+ * \note All other IDs beside given one are assumed already properly sorted in the list.
+ *
+ * \param id_sorting_hint Ignored if NULL. Otherwise, used to check if we can insert \a id
+ * immediately before or after that pointer. It must always be into given \a lb list.
+ */
+void id_sort_by_name(ListBase *lb, ID *id, ID *id_sorting_hint)
 {
+#define ID_SORT_STEP_SIZE 512
+
   ID *idtest;
 
   /* insert alphabetically */
-  if (lb->first != lb->last) {
-    BLI_remlink(lb, id);
-
-    void *item_array[ID_SORT_STEP_SIZE];
-    int item_array_index;
-
-    /* Step one: We go backward over a whole chunk of items at once, until we find a limit item
-     * that is lower than, or equal (should never happen!) to the one we want to insert. */
-    /* Note: We start from the end, because in typical 'heavy' case (insertion of lots of IDs at
-     * once using the same base name), newly inserted items will generally be towards the end
-     * (higher extension numbers). */
-    for (idtest = lb->last, item_array_index = ID_SORT_STEP_SIZE - 1; idtest != NULL;
-         idtest = idtest->prev, item_array_index--) {
-      item_array[item_array_index] = idtest;
-      if (item_array_index == 0) {
-        if ((idtest->lib == NULL && id->lib != NULL) ||
-            BLI_strcasecmp(idtest->name, id->name) <= 0) {
-          /* Not directly related to this code, but having two IDs with same name is a hard
-           * catastrophic bug, so having checks for that here does not hurt... */
-          BLI_assert(BLI_strcasecmp(idtest->name, id->name) != 0 || idtest->lib != id->lib);
-
-          break;
-        }
-        item_array_index = ID_SORT_STEP_SIZE;
-      }
+  if (lb->first == lb->last) {
+    return;
+  }
+
+  BLI_remlink(lb, id);
+
+  /* Check if we can actually insert id before or after id_sorting_hint, if given. */
+  if (id_sorting_hint != NULL && id_sorting_hint != id) {
+    BLI_assert(BLI_findindex(lb, id_sorting_hint) >= 0);
+
+    ID *id_sorting_hint_next = id_sorting_hint->next;
+    if (BLI_strcasecmp(id_sorting_hint->name, id->name) < 0 &&
+        (id_sorting_hint_next == NULL ||
+         BLI_strcasecmp(id_sorting_hint_next->name, id->name) > 0)) {
+      BLI_insertlinkafter(lb, id_sorting_hint, id);
+      return;
     }
 
-    /* Step two: we go forward in the selected chunk of items and check all of them, as we know
-     * that our target is in there. */
+    ID *id_sorting_hint_prev = id_sorting_hint->prev;
+    if (BLI_strcasecmp(id_sorting_hint->name, id->name) > 0 &&
+        (id_sorting_hint_prev == NULL ||
+         BLI_strcasecmp(id_sorting_hint_prev->name, id->name) < 0)) {
+      BLI_insertlinkbefore(lb, id_sorting_hint, id);
+      return;
+    }
+  }
 
-    /* If we reached start of the list, current item_array_index is off-by-one.
-     * Otherwise, we already know that it points to an item lower-or-equal-than the one we want to
-     * insert, no need to redo the check for that one.
-     * So we can increment that index in any case. */
-    for (item_array_index++; item_array_index < ID_SORT_STEP_SIZE; item_array_index++) {
-      idtest = item_array[item_array_index];
-      if ((idtest->lib != NULL && id->lib == NULL) || BLI_strcasecmp(idtest->name, id->name) > 0) {
-        BLI_insertlinkbefore(lb, idtest, id);
+  void *item_array[ID_SORT_STEP_SIZE];
+  int item_array_index;
+
+  /* Step one: We go backward over a whole chunk of items at once, until we find a limit item
+   * that is lower than, or equal (should never happen!) to the one we want to insert. */
+  /* Note: We start from the end, because in typical 'heavy' case (insertion of lots of IDs at
+   * once using the same base name), newly inserted items will generally be towards the end
+   * (higher extension numbers). */
+  for (idtest = lb->last, item_array_index = ID_SORT_STEP_SIZE - 1; idtest != NULL;
+       idtest = idtest->prev, item_array_index--) {
+    item_array[item_array_index] = idtest;
+    if (item_array_index == 0) {
+      if ((idtest->lib == NULL && id->lib != NULL) ||
+          BLI_strcasecmp(idtest->name, id->name) <= 0) {
         break;
       }
+      item_array_index = ID_SORT_STEP_SIZE;
     }
-    if (item_array_index == ID_SORT_STEP_SIZE) {
-      if (idtest == NULL) {
-        /* If idtest is NULL here, it means that in the first loop, the last comparison was
-         * performed exactly on the first item of the list, and that it also failed. In other
-         * words, all items in the list are greater than inserted one, so we can put it at the
-         * start of the list. */
-        /* Note that BLI_insertlinkafter() would have same behavior in that case, but better be
-         * explicit here. */
-        BLI_addhead(lb, id);
-      }
-      else {
-        BLI_insertlinkafter(lb, idtest, id);
-      }
+  }
+
+  /* Step two: we go forward in the selected chunk of items and check all of them, as we know
+   * that our target is in there. */
+
+  /* If we reached start of the list, current item_array_index is off-by-one.
+   * Otherwise, we already know that it points to an item lower-or-equal-than the one we want to
+   * insert, no need to redo the check for that one.
+   * So we can increment that index in any case. */
+  for (item_array_index++; item_array_index < ID_SORT_STEP_SIZE; item_array_index++) {
+    idtest = item_array[item_array_index];
+    if ((idtest->lib != NULL && id->lib == NULL) || BLI_strcasecmp(idtest->name, id->name) > 0) {
+      BLI_insertlinkbefore(lb, idtest, id);
+      break;
     }
   }
-}
+  if (item_array_index == ID_SORT_STEP_SIZE) {
+    if (idtest == NULL) {
+      /* If idtest is NULL here, it means that in the first loop, the last comparison was
+       * performed exactly on the first item of the list, and that it also failed. In other
+       * words, all items in the list are greater than inserted one, so we can put it at the
+       * start of the list. */
+      /* Note that BLI_insertlinkafter() would have same behavior in that case, but better be
+       * explicit here. */
+      BLI_addhead(lb, id);
+    }
+    else {
+      BLI_insertlinkafter(lb, idtest, id);
+    }
+  }
+
 #undef ID_SORT_STEP_SIZE
+}
 
 /* Note: this code assumes and ensures that the suffix number can never go beyond 1 billion. */
 #define MAX_NUMBER 1000000000
@@ -1667,10 +1696,12 @@ static bool id_name_final_build(char *name, char *root_name, size_t root_name_le
  * entry. The Python Library module needs to know what the name of a data-block will be before it
  * is appended, in this case ID *id is NULL.
  */
-static bool check_for_dupid(ListBase *lb, ID *id, char *name)
+static bool check_for_dupid(ListBase *lb, ID *id, char *name, ID **r_id_sorting_hint)
 {
   BLI_assert(strlen(name) < MAX_ID_NAME - 2);
 
+  *r_id_sorting_hint = NULL;
+
   ID *id_test = lb->first;
   bool is_name_changed = false;
 
@@ -1730,6 +1761,7 @@ static bool check_for_dupid(ListBase *lb, ID *id, char *name)
             if (!is_valid && id_test->name[2] == prev_final_name[0] &&
                 STREQ(prev_final_name, id_test->name + 2)) {
               is_valid = true;
+              *r_id_sorting_hint = id_test;
             }
           }
         }
@@ -1748,7 +1780,7 @@ static bool check_for_dupid(ListBase *lb, ID *id, char *name)
 
   /* To speed up finding smallest unused number within [0 .. MAX_NUMBERS_IN_USE - 1].
    * We do not bother beyond that point. */
-  BLI_bitmap *numbers_in_use = BLI_BITMAP_NEW_ALLOCA(MAX_NUMBERS_IN_USE);
+  ID *ids_in_use[MAX_NUMBERS_IN_USE] = {NULL};
 
   bool is_first_run = true;
   while (true) {
@@ -1786,10 +1818,11 @@ static bool check_for_dupid(ListBase *lb, ID *id, char *name)
         }
         /* Mark number of current id_test name as used, if possible. */
         if (number_test < MAX_NUMBERS_IN_USE) {
-          BLI_BITMAP_SET(numbers_in_use, number_test, true);
+          ids_in_use[number_test] = id_test;
         }
         /* Keep track of first largest unused number. */
         if (number <= number_test) {
+          *r_id_sorting_hint = id_test;
           number = number_test + 1;
         }
       }
@@ -1805,14 +1838,20 @@ static bool check_for_dupid(ListBase *lb, ID *id, char *name)
       prev_final_root_name[0] = '\0';
       prev_number = MIN_NUMBER - 1;
 
+      /* Value set previou

@@ Diff output truncated at 10240 characters. @@



More information about the Bf-blender-cvs mailing list