diff options
author | Bastien Montagne <montagne29@wanadoo.fr> | 2019-12-19 23:58:59 +0300 |
---|---|---|
committer | Bastien Montagne <montagne29@wanadoo.fr> | 2019-12-20 16:29:35 +0300 |
commit | 46607bc09d5cd9fa3570e5ad4b01ea4ea7adaffc (patch) | |
tree | 7a1b14466e1de6744031c7dfc3ca25711d363ea3 | |
parent | 4cc8201a651007b7308a4468a550dbbd97c6c346 (diff) |
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.
-rw-r--r-- | source/blender/blenkernel/BKE_library.h | 2 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/blendfile.c | 2 | ||||
-rw-r--r-- | source/blender/blenkernel/intern/library.c | 158 | ||||
-rw-r--r-- | source/blender/blenloader/intern/readfile.c | 6 | ||||
-rw-r--r-- | source/blender/windowmanager/intern/wm_files_link.c | 2 |
5 files changed, 105 insertions, 65 deletions
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 previously is meaningless in that case. */ + *r_id_sorting_hint = NULL; + return is_name_changed; } /* Decide which value of number to use, either the smallest unused one if possible, or default * to the first largest unused one we got from previous loop. */ for (int i = MIN_NUMBER; i < MAX_NUMBERS_IN_USE; i++) { - if (!BLI_BITMAP_TEST_BOOL(numbers_in_use, i)) { + if (ids_in_use[i] == NULL) { number = i; + if (i > 0) { + *r_id_sorting_hint = ids_in_use[i - 1]; + } break; } } @@ -1829,7 +1868,7 @@ static bool check_for_dupid(ListBase *lb, ID *id, char *name) * have to go over the whole check again. */ if (!id_name_final_build(name, root_name, root_name_len, number)) { /* We have to clear our list of small used numbers before we do the whole check again. */ - BLI_bitmap_set_all(numbers_in_use, false, MAX_NUMBERS_IN_USE); + memset(ids_in_use, 0, sizeof(ids_in_use)); continue; } @@ -1884,7 +1923,8 @@ bool BKE_id_new_name_validate(ListBase *lb, ID *id, const char *tname) BLI_utf8_invalid_strip(name, strlen(name)); } - result = check_for_dupid(lb, id, name); + ID *id_sorting_hint = NULL; + result = check_for_dupid(lb, id, name, &id_sorting_hint); strcpy(id->name + 2, name); /* This was in 2.43 and previous releases @@ -1893,11 +1933,11 @@ bool BKE_id_new_name_validate(ListBase *lb, ID *id, const char *tname) * functions work, so sort every time. */ #if 0 if (result) { - id_sort_by_name(lb, id); + id_sort_by_name(lb, id, id_sorting_hint); } #endif - id_sort_by_name(lb, id); + id_sort_by_name(lb, id, id_sorting_hint); return result; } diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c index 5b73a7521e2..8085beb6351 100644 --- a/source/blender/blenloader/intern/readfile.c +++ b/source/blender/blenloader/intern/readfile.c @@ -9189,7 +9189,7 @@ static ID *create_placeholder(Main *mainvar, const short idcode, const char *idn ph_id->icon_id = 0; BLI_addtail(lb, ph_id); - id_sort_by_name(lb, ph_id); + id_sort_by_name(lb, ph_id, NULL); return ph_id; } @@ -11590,7 +11590,7 @@ static ID *link_named_part( if (id) { /* sort by name in list */ ListBase *lb = which_libbase(mainl, idcode); - id_sort_by_name(lb, id); + id_sort_by_name(lb, id, NULL); } } else { @@ -11647,7 +11647,7 @@ int BLO_library_link_copypaste(Main *mainl, BlendHandle *bh, const unsigned int if (id) { /* sort by name in list */ ListBase *lb = which_libbase(mainl, GS(id->name)); - id_sort_by_name(lb, id); + id_sort_by_name(lb, id, NULL); if (bhead->code == ID_OB) { /* Instead of instancing Base's directly, postpone until after collections are loaded diff --git a/source/blender/windowmanager/intern/wm_files_link.c b/source/blender/windowmanager/intern/wm_files_link.c index 3374d17cbfd..f0b186761ce 100644 --- a/source/blender/windowmanager/intern/wm_files_link.c +++ b/source/blender/windowmanager/intern/wm_files_link.c @@ -828,7 +828,7 @@ static void lib_relocate_do(Main *bmain, BLI_strncpy(&old_id->name[len], "~000", 7); } - id_sort_by_name(which_libbase(bmain, GS(old_id->name)), old_id); + id_sort_by_name(which_libbase(bmain, GS(old_id->name)), old_id, NULL); BKE_reportf( reports, |