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

[Bastien Montagne]

Commit: d84065807810d008ea57de39bd90ac417537c488
Author: Bastien Montagne
Date:   Fri Dec 13 19:18:01 2019 +0100
Branches: master
https://developer.blender.org/rBd84065807810d008ea57de39bd90ac417537c488

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

This alone can make e.g. adding 40k IDs with default name (i.e. 'fully
constant' case in table below) about 15-20% faster:

| Number and type of names of IDs  | old code | new code | speed improvement |
| -------------------------------- | -------- | -------- | ----------------- |
| 40K, mixed (14k rand, 26k const) |      75s |      62s |               21% |
| 40K, fully random                |      90s |      76s |               18% |
| 40K, fully constant              |      94s |      77s |               22% |

Idea is to use a first pass, where we just check one item every nth ones,
until we have found the chunk in which we want to insert the new item,
then do a basic linear comparison with all items in that chunk as before.

Also, list is now walked backward, as in most common 'massive insertion'
cases new ID's names have higher number, hence ends up towards the end of
the list.

This new sorting function can be between a few percents and 50% quicker than
original code, depending on various factors (like length of common parts of
ID names, whether new IDs should be added towards the end or not, how high
in numbering we are, etc.).

Note: another, full bisecting approach was also tried, which gives a massive
reduction of comparisons (from n items to log2(n)), but it only gave minor
improvements of speed from original fully linear code, while adding a fair
amount of complexity to the logic. Only case it was shining was the unlikely
'very long, almost similar ID names' case (since `strcasecmp()` is rather
costly then).

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

M	source/blender/blenkernel/intern/library.c

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

diff --git a/source/blender/blenkernel/intern/library.c b/source/blender/blenkernel/intern/library.c
index e312522b508..5edc349de74 100644
--- a/source/blender/blenkernel/intern/library.c
+++ b/source/blender/blenkernel/intern/library.c
@@ -1545,6 +1545,7 @@ 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)
 {
   ID *idtest;
@@ -1553,20 +1554,61 @@ void id_sort_by_name(ListBase *lb, ID *id)
   if (lb->first != lb->last) {
     BLI_remlink(lb, id);
 
-    idtest = lb->first;
-    while (idtest) {
-      if (BLI_strcasecmp(idtest->name, id->name) > 0 || (idtest->lib && !id->lib)) {
+    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;
+      }
+    }
+
+    /* 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;
       }
-      idtest = idtest->next;
     }
-    /* as last */
-    if (idtest == NULL) {
-      BLI_addtail(lb, id);
+    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
 
 /**
  * Check to see if there is an ID with the same name as 'name'.