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, 2 insertions, 0 deletions

diff --git a/source/blender/editors/animation/anim_motion_paths.c b/source/blender/editors/animation/anim_motion_paths.c
index d976f5f72ad..d130941b9bc 100644
--- a/source/blender/editors/animation/anim_motion_paths.c
+++ b/source/blender/editors/animation/anim_motion_paths.c
@@ -329,6 +329,7 @@ static void motionpath_calculate_update_range(MPathTarget *mpt,
   for (FCurve *fcu = fcurve_list->first; fcu != NULL; fcu = fcu->next) {
     struct AnimKeylist *keylist = ED_keylist_create();
     fcurve_to_keylist(adt, fcu, keylist, 0);
+    ED_keylist_prepare_for_direct_access(keylist);
 
     int fcu_sfra = motionpath_get_prev_prev_keyframe(mpt, keylist, current_frame);
     int fcu_efra = motionpath_get_next_next_keyframe(mpt, keylist, current_frame);
@@ -443,6 +444,7 @@ void animviz_calc_motionpaths(Depsgraph *depsgraph,
         action_to_keylist(adt, adt->action, mpt->keylist, 0);
       }
     }
+    ED_keylist_prepare_for_direct_access(mpt->keylist);
 
     if (range == ANIMVIZ_CALC_RANGE_CHANGED) {
       int mpt_sfra, mpt_efra;