Anim: Keylist drawing optimization by using arrays.

Change data structure of keylists. Reducing the balancing overhead and therefore increases performance.

| **Function** | **Master** | **Patch** |
|`draw_summary_channel`| 0.202105s| 0.083874s |

When adding items to the keylist it will store it in a linked list. This linked list is
accompanied with the length (key_len) and a `last_accessed_column`. last_accessed_column is a cursor
that improve the performance when adding new items as they are mostly ordered by frame numbers.
last_accessed_column is reset when a new fcurve/mask/... is added to the keylist.

Before searching or array access. the listbase needs to be converted to an array.
`ED_keylist_prepare_for_direct_access`. After that the caller can use
`ED_keylist_find_*` or `ED_keylist_array*` functions.

The internal array can also be accessed via the `ED_keylist_listbase` function.
The items inside the array link to the previous/next item in the list.

Reviewed By: sybren

Differential Revision: https://developer.blender.org/D12052

1 files changed, 9 insertions, 5 deletions

diff --git a/source/blender/editors/include/ED_keyframes_keylist.h b/source/blender/editors/include/ED_keyframes_keylist.h
index 3a9750c1206..4194444ca0f 100644
--- a/source/blender/editors/include/ED_keyframes_keylist.h
+++ b/source/blender/editors/include/ED_keyframes_keylist.h
@@ -139,14 +139,20 @@ typedef enum eKeyframeExtremeDrawOpts {
 
 struct AnimKeylist *ED_keylist_create(void);
 void ED_keylist_free(struct AnimKeylist *keylist);
-const struct ActKeyColumn *ED_keylist_find_exact(const struct AnimKeylist *keylist, float cfra);
-const struct ActKeyColumn *ED_keylist_find_next(const struct AnimKeylist *keylist, float cfra);
-const struct ActKeyColumn *ED_keylist_find_prev(const struct AnimKeylist *keylist, float cfra);
+void ED_keylist_prepare_for_direct_access(struct AnimKeylist *keylist);
+const struct ActKeyColumn *ED_keylist_find_exact(const struct AnimKeylist *keylist,
+                                                 const float cfra);
+const struct ActKeyColumn *ED_keylist_find_next(const struct AnimKeylist *keylist,
+                                                const float cfra);
+const struct ActKeyColumn *ED_keylist_find_prev(const struct AnimKeylist *keylist,
+                                                const float cfra);
 const struct ActKeyColumn *ED_keylist_find_any_between(const struct AnimKeylist *keylist,
                                                        const Range2f frame_range);
 bool ED_keylist_is_empty(const struct AnimKeylist *keylist);
 const struct ListBase /* ActKeyColumn */ *ED_keylist_listbase(const struct AnimKeylist *keylist);
 bool ED_keylist_frame_range(const struct AnimKeylist *keylist, Range2f *r_frame_range);
+const ActKeyColumn *ED_keylist_array(const struct AnimKeylist *keylist);
+int64_t ED_keylist_array_len(const struct AnimKeylist *keylist);
 
 /* Key-data Generation --------------- */
 
@@ -197,8 +203,6 @@ void mask_to_keylist(struct bDopeSheet *ads,
                      struct AnimKeylist *keylist);
 
 /* ActKeyColumn API ---------------- */
-/* Comparator callback used for ActKeyColumns and cframe float-value pointer */
-short compare_ak_cfraPtr(void *node, void *data);
 
 /* Checks if ActKeyColumn has any block data */
 bool actkeyblock_is_valid(const ActKeyColumn *ac);