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

source/blender/editors/animation/anim_draw.c

@@ -521,6 +521,7 @@ static bool find_prev_next_keyframes(struct bContext *C, int *r_nextfra, int *r_
     MaskLayer *masklay = BKE_mask_layer_active(mask);
     mask_to_keylist(&ads, masklay, keylist);
   }
+  ED_keylist_prepare_for_direct_access(keylist);
 
   /* TODO(jbakker): Keylists are ordered, no need to do any searching at all. */
   /* find matching keyframe in the right direction */

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;

source/blender/editors/animation/keyframes_draw.c

@@ -346,10 +346,12 @@ static void draw_keylist_block(const DrawKeylistUIData *ctx, const ActKeyColumn
 }
 
 static void draw_keylist_blocks(const DrawKeylistUIData *ctx,
-                                const ListBase * /*ActKeyColumn*/ columns,
+                                const ActKeyColumn *keys,
+                                const int key_len,
                                 float ypos)
 {
-  LISTBASE_FOREACH (ActKeyColumn *, ab, columns) {
+  for (int i = 0; i < key_len; i++) {
+    const ActKeyColumn *ab = &keys[i];
     draw_keylist_block(ctx, ab, ypos);
   }
 }
@@ -362,13 +364,15 @@ static bool draw_keylist_is_visible_key(const View2D *v2d, const ActKeyColumn *a
 static void draw_keylist_keys(const DrawKeylistUIData *ctx,
                               View2D *v2d,
                               const KeyframeShaderBindings *sh_bindings,
-                              const ListBase * /*ActKeyColumn*/ keys,
+                              const ActKeyColumn *keys,
+                              const int key_len,
                               float ypos,
                               eSAction_Flag saction_flag)
 {
   short handle_type = KEYFRAME_HANDLE_NONE, extreme_type = KEYFRAME_EXTREME_NONE;
 
-  LISTBASE_FOREACH (ActKeyColumn *, ak, keys) {
+  for (int i = 0; i < key_len; i++) {
+    const ActKeyColumn *ak = &keys[i];
     if (draw_keylist_is_visible_key(v2d, ak)) {
       if (ctx->show_ipo) {
         handle_type = ak->handle_type;
@@ -469,8 +473,9 @@ static void ED_keylist_draw_list_elem_draw_blocks(AnimKeylistDrawListElem *elem,
   DrawKeylistUIData ctx;
   draw_keylist_ui_data_init(&ctx, v2d, elem->yscale_fac, elem->channel_locked, elem->saction_flag);
 
-  const ListBase *keys = ED_keylist_listbase(elem->keylist);
-  draw_keylist_blocks(&ctx, keys, elem->ypos);
+  const int key_len = ED_keylist_array_len(elem->keylist);
+  const ActKeyColumn *keys = ED_keylist_array(elem->keylist);
+  draw_keylist_blocks(&ctx, keys, key_len, elem->ypos);
 }
 
 static void ED_keylist_draw_list_elem_draw_keys(AnimKeylistDrawListElem *elem,
@@ -479,8 +484,15 @@ static void ED_keylist_draw_list_elem_draw_keys(AnimKeylistDrawListElem *elem,
 {
   DrawKeylistUIData ctx;
   draw_keylist_ui_data_init(&ctx, v2d, elem->yscale_fac, elem->channel_locked, elem->saction_flag);
-  const ListBase *keys = ED_keylist_listbase(elem->keylist);
-  draw_keylist_keys(&ctx, v2d, sh_bindings, keys, elem->ypos, elem->saction_flag);
+
+  const int key_len = ED_keylist_array_len(elem->keylist);
+  const ActKeyColumn *keys = ED_keylist_array(elem->keylist);
+  draw_keylist_keys(&ctx, v2d, sh_bindings, keys, key_len, elem->ypos, elem->saction_flag);
+}
+
+static void ED_keylist_draw_list_elem_prepare_for_drawing(AnimKeylistDrawListElem *elem)
+{
+  ED_keylist_prepare_for_direct_access(elem->keylist);
 }
 
 typedef struct AnimKeylistDrawList {
@@ -496,6 +508,7 @@ static void ED_keylist_draw_list_build_keylists(AnimKeylistDrawList *draw_list)
 {
   LISTBASE_FOREACH (AnimKeylistDrawListElem *, elem, &draw_list->channels) {
     ED_keylist_draw_list_elem_build_keylist(elem);
+    ED_keylist_draw_list_elem_prepare_for_drawing(elem);
   }
 }
 

source/blender/editors/animation/keyframes_keylist.cc

@@ -23,15 +23,20 @@
 
 /* System includes ----------------------------------------------------- */
 
+#include <algorithm>
 #include <cfloat>
 #include <cmath>
 #include <cstdlib>
 #include <cstring>
+#include <functional>
+#include <optional>
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_array.hh"
 #include "BLI_dlrbTree.h"
 #include "BLI_listbase.h"
+#include "BLI_math.h"
 #include "BLI_range.h"
 #include "BLI_utildefines.h"
 
@@ -50,86 +55,6 @@
 extern "C" {
 /* *************************** Keyframe Processing *************************** */
 
-struct AnimKeylist {
-  DLRBT_Tree keys;
-};
-
-static void ED_keylist_init(AnimKeylist *keylist)
-{
-  BLI_dlrbTree_init(&keylist->keys);
-}
-
-AnimKeylist *ED_keylist_create(void)
-{
-  AnimKeylist *keylist = static_cast<AnimKeylist *>(MEM_callocN(sizeof(AnimKeylist), __func__));
-  ED_keylist_init(keylist);
-  return keylist;
-}
-
-void ED_keylist_free(AnimKeylist *keylist)
-{
-  BLI_assert(keylist);
-  BLI_dlrbTree_free(&keylist->keys);
-  MEM_freeN(keylist);
-}
-
-const ActKeyColumn *ED_keylist_find_exact(const AnimKeylist *keylist, float cfra)
-{
-  return (const ActKeyColumn *)BLI_dlrbTree_search_exact(
-      &keylist->keys, compare_ak_cfraPtr, &cfra);
-}
-
-const ActKeyColumn *ED_keylist_find_next(const AnimKeylist *keylist, float cfra)
-{
-  return (const ActKeyColumn *)BLI_dlrbTree_search_next(&keylist->keys, compare_ak_cfraPtr, &cfra);
-}
-
-const ActKeyColumn *ED_keylist_find_prev(const AnimKeylist *keylist, float cfra)
-{
-  return (const ActKeyColumn *)BLI_dlrbTree_search_prev(&keylist->keys, compare_ak_cfraPtr, &cfra);
-}
-
-/* TODO(jbakker): Should we change this to use `ED_keylist_find_next(keys, min_fra)` and only check
- * boundary of `max_fra`. */
-const ActKeyColumn *ED_keylist_find_any_between(const AnimKeylist *keylist,
-                                                const Range2f frame_range)
-{
-  for (const ActKeyColumn *ak = static_cast<const ActKeyColumn *>(keylist->keys.root); ak;
-       ak = static_cast<const ActKeyColumn *>((ak->cfra < frame_range.min) ? ak->right :
-                                                                             ak->left)) {
-    if (range2f_in_range(&frame_range, ak->cfra)) {
-      return ak;
-    }
-  }
-  return nullptr;
-}
-
-bool ED_keylist_is_empty(const struct AnimKeylist *keylist)
-{
-  return keylist->keys.root == nullptr;
-}
-
-const struct ListBase *ED_keylist_listbase(const AnimKeylist *keylist)
-{
-  return (ListBase *)&keylist->keys;
-}
-
-bool ED_keylist_frame_range(const struct AnimKeylist *keylist, Range2f *r_frame_range)
-{
-  BLI_assert(r_frame_range);
-
-  if (ED_keylist_is_empty(keylist)) {
-    return false;
-  }
-
-  const ActKeyColumn *first_column = (const ActKeyColumn *)keylist->keys.first;
-  r_frame_range->min = first_column->cfra;
-
-  const ActKeyColumn *last_column = (const ActKeyColumn *)keylist->keys.last;
-  r_frame_range->max = last_column->cfra;
-
-  return true;
-}
 /* ActKeyColumns (Keyframe Columns) ------------------------------------------ */
 
 BLI_INLINE bool is_cfra_eq(const float a, const float b)
@@ -142,25 +67,282 @@ BLI_INLINE bool is_cfra_lt(const float a, const float b)
   return (b - a) > BEZT_BINARYSEARCH_THRESH;
 }
 
-/* Comparator callback used for ActKeyColumns and cframe float-value pointer */
-/* NOTE: this is exported to other modules that use the ActKeyColumns for finding keyframes */
-short compare_ak_cfraPtr(void *node, void *data)
+/* --------------- */
+
+struct AnimKeylist {
+  /* Number of ActKeyColumn's in the keylist. */
+  size_t column_len = 0;
+
+  bool is_runtime_initialized = false;
+
+  /* Before initializing the runtime, the key_columns list base is used to quickly add columns.
+   * Contains `ActKeyColumn`. Should not be used after runtime is initialized. */
+  ListBase /* ActKeyColumn */ key_columns;
+  /* Last accessed column in the key_columns list base. Inserting columns are typically done in
+   * order. The last accessed column is used as starting point to search for a location to add or
+   * update the next column.*/
+  std::optional<ActKeyColumn *> last_accessed_column = std::nullopt;
+
+  struct {
+    /* When initializing the runtime the columns from the list base `AnimKeyList.key_columns` are
+     * transferred to an array to support binary searching and index based access. */
+    blender::Array<ActKeyColumn> key_columns;
+    /* Wrapper around runtime.key_columns so it can still be accessed as a ListBase. Elements are
+     * owned by runtime.key_columns. */
+    ListBase /* ActKeyColumn */ list_wrapper;
+  } runtime;
+
+  AnimKeylist()
+  {
+    BLI_listbase_clear(&this->key_columns);
+    BLI_listbase_clear(&this->runtime.list_wrapper);
+  }
+
+  ~AnimKeylist()
+  {
+    BLI_freelistN(&this->key_columns);
+    BLI_listbase_clear(&this->runtime.list_wrapper);
+  }
+
+#ifdef WITH_CXX_GUARDEDALLOC
+  MEM_CXX_CLASS_ALLOC_FUNCS("editors:AnimKeylist")
+#endif
+};
+
+AnimKeylist *ED_keylist_create(void)
 {
-  ActKeyColumn *ak = (ActKeyColumn *)node;
-  const float *cframe = static_cast<const float *>(data);
-  const float val = *cframe;
-
-  if (is_cfra_eq(val, ak->cfra)) {
-    return 0;
-  }
-
-  if (val < ak->cfra) {
-    return -1;
-  }
-  return 1;
+  AnimKeylist *keylist = new AnimKeylist();
+  return keylist;
 }
 
-/* --------------- */
+void ED_keylist_free(AnimKeylist *keylist)
+{
+  BLI_assert(keylist);
+  delete keylist;
+}
+
+static void ED_keylist_convert_key_columns_to_array(AnimKeylist *keylist)
+{
+  size_t index;
+  LISTBASE_FOREACH_INDEX (ActKeyColumn *, key, &keylist->key_columns, index) {
+    keylist->runtime.key_columns[index] = *key;
+  }
+}
+
+static void ED_keylist_runtime_update_key_column_next_prev(AnimKeylist *keylist)
+{
+  for (size_t index = 0; index < keylist->column_len; index++) {
+    const bool is_first = (index == 0);
+    keylist->runtime.key_columns[index].prev = is_first ? nullptr :
+                                                          &keylist->runtime.key_columns[index - 1];
+    const bool is_last = (index == keylist->column_len - 1);
+    keylist->runtime.key_columns[index].next = is_last ? nullptr :
+                                                         &keylist->runtime.key_columns[index + 1];
+  }
+}
+
+static void ED_keylist_runtime_init_listbase(AnimKeylist *keylist)
+{
+  if (ED_keylist_is_empty(keylist)) {
+    BLI_listbase_clear(&keylist->runtime.list_wrapper);
+    return;
+  }
+
+  keylist->runtime.list_wrapper.first = &keylist->runtime.key_columns[0];
+  keylist->runtime.list_wrapper.last = &keylist->runtime.key_columns[keylist->column_len - 1];
+}
+
+static void ED_keylist_runtime_init(AnimKeylist *keylist)
+{
+  BLI_assert(!keylist->is_runtime_initialized);
+
+  keylist->runtime.key_columns = blender::Array<ActKeyColumn>(keylist->column_len);
+
+  /* Convert linked list to array to support fast searching. */
+  ED_keylist_convert_key_columns_to_array(keylist);
+  /* Ensure that the array can also be used as a listbase for external usages. */
+  ED_keylist_runtime_update_key_column_next_prev(keylist);
+  ED_keylist_runtime_init_listbase(keylist);
+
+  keylist->is_runtime_initialized = true;
+}
+
+static void ED_keylist_reset_last_accessed(AnimKeylist *keylist)
+{
+  BLI_assert(!keylist->is_runtime_initialized);
+  keylist->last_accessed_column.reset();
+}
+
+void ED_keylist_prepare_for_direct_access(AnimKeylist *keylist)
+{
+  if (keylist->is_runtime_initialized) {
+    return;
+  }
+  ED_keylist_runtime_init(keylist);
+}
+
+static const ActKeyColumn *ED_keylist_find_lower_bound(const AnimKeylist *keylist,
+                                                       const float cfra)
+{
+  BLI_assert(!ED_keylist_is_empty(keylist));
+  const ActKeyColumn *begin = std::begin(keylist->runtime.key_columns);
+  const ActKeyColumn *end = std::end(keylist->runtime.key_columns);
+  ActKeyColumn value;
+  value.cfra = cfra;
+
+  const ActKeyColumn *found_column = std::lower_bound(
+      begin, end, value, [](const ActKeyColumn &column, const ActKeyColumn &other) {
+        return is_cfra_lt(column.cfra, other.cfra);
+      });
+  return found_column;
+}
+
+static const ActKeyColumn *ED_keylist_find_upper_bound(const AnimKeylist *keylist,
+                                                       const float cfra)
+{
+  BLI_assert(!ED_keylist_is_empty(keylist));
+  const ActKeyColumn *begin = std::begin(keylist->runtime.key_columns);
+  const ActKeyColumn *end = std::end(keylist->runtime.key_columns);
+  ActKeyColumn value;
+  value.cfra = cfra;
+
+  const ActKeyColumn *found_column = std::upper_bound(
+      begin, end, value, [](const ActKeyColumn &column, const ActKeyColumn &other) {
+        return is_cfra_lt(column.cfra, other.cfra);
+      });
+  return found_column;
+}
+
+const ActKeyColumn *ED_keylist_find_exact(const AnimKeylist *keylist, const float cfra)
+{
+  BLI_assert_msg(keylist->is_runtime_initialized,
+                 "ED_keylist_prepare_for_direct_access needs to be called before searching.");
+
+  if (ED_keylist_is_empty(keylist)) {
+    return nullptr;
+  }
+
+  const ActKeyColumn *found_column = ED_keylist_find_lower_bound(keylist, cfra);
+
+  const ActKeyColumn *end = std::end(keylist->runtime.key_columns);
+  if (found_column == end) {
+    return nullptr;
+  }
+  if (is_cfra_eq(found_column->cfra, cfra)) {
+    return found_column;
+  }
+  return nullptr;
+}
+
+const ActKeyColumn *ED_keylist_find_next(const AnimKeylist *keylist, const float cfra)
+{
+  BLI_assert_msg(keylist->is_runtime_initialized,
+                 "ED_keylist_prepare_for_direct_access needs to be called before searching.");
+
+  if (ED_keylist_is_empty(keylist)) {
+    return nullptr;
+  }
+
+  const ActKeyColumn *found_column = ED_keylist_find_upper_bound(keylist, cfra);
+
+  const ActKeyColumn *end = std::end(keylist->runtime.key_columns);
+  if (found_column == end) {
+    return nullptr;
+  }
+  return found_column;
+}
+
+const ActKeyColumn *ED_keylist_find_prev(const AnimKeylist *keylist, const float cfra)
+{
+  BLI_assert_msg(keylist->is_runtime_initialized,
+                 "ED_keylist_prepare_for_direct_access needs to be called before searching.");
+
+  if (ED_keylist_is_empty(keylist)) {
+    return nullptr;
+  }
+
+  const ActKeyColumn *end = std::end(keylist->runtime.key_columns);
+  const ActKeyColumn *found_column = ED_keylist_find_lower_bound(keylist, cfra);
+
+  if (found_column == end) {
+    /* Nothing found, return the last item. */
+    return end - 1;
+  }
+
+  const ActKeyColumn *prev_column = found_column->prev;
+  return prev_column;
+}
+
+const ActKeyColumn *ED_keylist_find_any_between(const AnimKeylist *keylist,
+                                                const Range2f frame_range)
+{
+  BLI_assert_msg(keylist->is_runtime_initialized,
+                 "ED_keylist_prepare_for_direct_access needs to be called before searching.");
+
+  if (ED_keylist_is_empty(keylist)) {
+    return nullptr;
+  }
+
+  const ActKeyColumn *column = ED_keylist_find_lower_bound(keylist, frame_range.min);
+  const ActKeyColumn *end = std::end(keylist->runtime.key_columns);
+  if (column == end) {
+    return nullptr;
+  }
+  if (column->cfra >= frame_range.max) {
+    return nullptr;
+  }
+  return column;
+}
+
+const ActKeyColumn *ED_keylist_array(const struct AnimKeylist *keylist)
+{
+  BLI_assert_msg(
+      keylist->is_runtime_initialized,
+      "ED_keylist_prepare_for_direct_access needs to be called before accessing array.");
+  return keylist->runtime.key_columns.data();
+}
+
+int64_t ED_keylist_array_len(const struct AnimKeylist *keylist)
+{
+  return keylist->column_len;
+}
+
+bool ED_keylist_is_empty(const struct AnimKeylist *keylist)
+{
+  return keylist->column_len == 0;
+}
+
+const struct ListBase *ED_keylist_listbase(const AnimKeylist *keylist)
+{
+  if (keylist->is_runtime_initialized) {
+    return &keylist->runtime.list_wrapper;
+  }
+  return &keylist->key_columns;
+}
+
+bool ED_keylist_frame_range(const struct AnimKeylist *keylist, Range2f *r_frame_range)
+{
+  BLI_assert(r_frame_range);
+
+  if (ED_keylist_is_empty(keylist)) {
+    return false;
+  }
+
+  const ActKeyColumn *first_column;
+  const ActKeyColumn *last_column;
+  if (keylist->is_runtime_initialized) {
+    first_column = &keylist->runtime.key_columns[0];
+    last_column = &keylist->runtime.key_columns[keylist->column_len - 1];
+  }
+  else {
+    first_column = static_cast<const ActKeyColumn *>(keylist->key_columns.first);
+    last_column = static_cast<const ActKeyColumn *>(keylist->key_columns.last);
+  }
+  r_frame_range->min = first_column->cfra;
+  r_frame_range->max = last_column->cfra;
+
+  return true;
+}
 
 /* Set of references to three logically adjacent keys. */
 struct BezTripleChain {
@@ -243,16 +425,8 @@ static eKeyframeExtremeDrawOpts bezt_extreme_type(const BezTripleChain *chain)
   return KEYFRAME_EXTREME_NONE;
 }
 
-/* Comparator callback used for ActKeyColumns and BezTripleChain */
-static short compare_ak_bezt(void *node, void *data)
-{
-  BezTripleChain *chain = static_cast<BezTripleChain *>(data);
-
-  return compare_ak_cfraPtr(node, &chain->cur->vec[1][0]);
-}
-
 /* New node callback used for building ActKeyColumns from BezTripleChain */
-static DLRBT_Node *nalloc_ak_bezt(void *data)
+static ActKeyColumn *nalloc_ak_bezt(void *data)
 {
   ActKeyColumn *ak = static_cast<ActKeyColumn *>(
       MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumn"));
@@ -269,13 +443,12 @@ static DLRBT_Node *nalloc_ak_bezt(void *data)
   /* count keyframes in this column */
   ak->totkey = 1;
 
-  return (DLRBT_Node *)ak;
+  return ak;
 }
 
 /* Node updater callback used for building ActKeyColumns from BezTripleChain */
-static void nupdate_ak_bezt(void *node, void *data)
+static void nupdate_ak_bezt(ActKeyColumn *ak, void *data)
 {
-  ActKeyColumn *ak = static_cast<ActKeyColumn *>(node);
   const BezTripleChain *chain = static_cast<const BezTripleChain *>(data);
   const BezTriple *bezt = chain->cur;
 
@@ -312,17 +485,8 @@ static void nupdate_ak_bezt(void *node, void *data)
 
 /* ......... */
 
-/* Comparator callback used for ActKeyColumns and GPencil frame */
-static short compare_ak_gpframe(void *node, void *data)
-{
-  const bGPDframe *gpf = (bGPDframe *)data;
-
-  float frame = gpf->framenum;
-  return compare_ak_cfraPtr(node, &frame);
-}
-
 /* New node callback used for building ActKeyColumns from GPencil frames */
-static DLRBT_Node *nalloc_ak_gpframe(void *data)
+static ActKeyColumn *nalloc_ak_gpframe(void *data)
 {
   ActKeyColumn *ak = static_cast<ActKeyColumn *>(
       MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumnGPF"));
@@ -340,14 +504,13 @@ static DLRBT_Node *nalloc_ak_gpframe(void *data)
   ak->block.sel = ak->sel;
   ak->block.flag |= ACTKEYBLOCK_FLAG_GPENCIL;
 
-  return (DLRBT_Node *)ak;
+  return ak;
 }
 
 /* Node updater callback used for building ActKeyColumns from GPencil frames */
-static void nupdate_ak_gpframe(void *node, void *data)
+static void nupdate_ak_gpframe(ActKeyColumn *ak, void *data)
 {
-  ActKeyColumn *ak = (ActKeyColumn *)node;
-  const bGPDframe *gpf = (bGPDframe *)data;
+  bGPDframe *gpf = (bGPDframe *)data;
 
   /* set selection status and 'touched' status */
   if (gpf->flag & GP_FRAME_SELECT) {
@@ -366,17 +529,8 @@ static void nupdate_ak_gpframe(void *node, void *data)
 
 /* ......... */
 
-/* Comparator callback used for ActKeyColumns and GPencil frame */
-static short compare_ak_masklayshape(void *node, void *data)
-{
-  const MaskLayerShape *masklay_shape = (const MaskLayerShape *)data;
-
-  float frame = masklay_shape->frame;
-  return compare_ak_cfraPtr(node, &frame);
-}
-
 /* New node callback used for building ActKeyColumns from GPencil frames */
-static DLRBT_Node *nalloc_ak_masklayshape(void *data)
+static ActKeyColumn *nalloc_ak_masklayshape(void *data)
 {
   ActKeyColumn *ak = static_cast<ActKeyColumn *>(
       MEM_callocN(sizeof(ActKeyColumn), "ActKeyColumnGPF"));
@@ -389,14 +543,13 @@ static DLRBT_Node *nalloc_ak_masklayshape(void *data)
   /* count keyframes in this column */
   ak->totkey = 1;
 
-  return (DLRBT_Node *)ak;
+  return ak;
 }
 
 /* Node updater callback used for building ActKeyColumns from GPencil frames */
-static void nupdate_ak_masklayshape(void *node, void *data)
+static void nupdate_ak_masklayshape(ActKeyColumn *ak, void *data)
 {
-  ActKeyColumn *ak = (ActKeyColumn *)node;
-  const MaskLayerShape *masklay_shape = (const MaskLayerShape *)data;
+  MaskLayerShape *masklay_shape = (MaskLayerShape *)data;
 
   /* set selection status and 'touched' status */
   if (masklay_shape->flag & MASK_SHAPE_SELECT) {
@@ -408,6 +561,95 @@ static void nupdate_ak_masklayshape(void *node, void *data)
 }
 
 /* --------------- */
+using KeylistCreateColumnFunction = std::function<ActKeyColumn *(void *userdata)>;
+using KeylistUpdateColumnFunction = std::function<void(ActKeyColumn *, void *)>;
+
+/* `ED_keylist_find_neighbour_front_to_back` is called before the runtime can be initialized so we
+ * cannot use bin searching. */
+static ActKeyColumn *ED_keylist_find_neighbour_front_to_back(ActKeyColumn *cursor, float cfra)
+{
+  while (cursor->next && cursor->next->cfra <= cfra) {
+    cursor = cursor->next;
+  }
+  return cursor;
+}
+
+/* `ED_keylist_find_neighbour_back_to_front` is called before the runtime can be initialized so we
+ * cannot use bin searching. */
+static ActKeyColumn *ED_keylist_find_neighbour_back_to_front(ActKeyColumn *cursor, float cfra)
+{
+  while (cursor->prev && cursor->prev->cfra >= cfra) {
+    cursor = cursor->prev;
+  }
+  return cursor;
+}
+
+/*
+ * `ED_keylist_find_exact_or_neighbour_column` is called before the runtime can be initialized so
+ * we cannot use bin searching.
+ *
+ * This function is called to add or update columns in the keylist.
+ * Typically columns are sorted by frame number so keeping track of the last_accessed_column
+ * reduces searching.
+ */
+static ActKeyColumn *ED_keylist_find_exact_or_neighbour_column(AnimKeylist *keylist, float cfra)
+{
+  BLI_assert(!keylist->is_runtime_initialized);
+  if (ED_keylist_is_empty(keylist)) {
+    return nullptr;
+  }
+
+  ActKeyColumn *cursor = keylist->last_accessed_column.value_or(
+      static_cast<ActKeyColumn *>(keylist->key_columns.first));
+  if (!is_cfra_eq(cursor->cfra, cfra)) {
+    const bool walking_direction_front_to_back = cursor->cfra <= cfra;
+    if (walking_direction_front_to_back) {
+      cursor = ED_keylist_find_neighbour_front_to_back(cursor, cfra);
+    }
+    else {
+      cursor = ED_keylist_find_neighbour_back_to_front(cursor, cfra);
+    }
+  }
+
+  keylist->last_accessed_column = cursor;
+  return cursor;
+}
+
+static void ED_keylist_add_or_update_column(AnimKeylist *keylist,
+                                            float cfra,
+                                            KeylistCreateColumnFunction create_func,
+                                            KeylistUpdateColumnFunction update_func,
+                                            void *userdata)
+{
+  BLI_assert_msg(
+      !keylist->is_runtime_initialized,
+      "Modifying AnimKeylist isn't allowed after runtime is initialized "
+      "keylist->key_columns/columns_len will get out of sync with runtime.key_columns.");
+  if (ED_keylist_is_empty(keylist)) {
+    ActKeyColumn *key_column = create_func(userdata);
+    BLI_addhead(&keylist->key_columns, key_column);
+    keylist->column_len += 1;
+    keylist->last_accessed_column = key_column;
+    return;
+  }
+
+  ActKeyColumn *nearest = ED_keylist_find_exact_or_neighbour_column(keylist, cfra);
+  if (is_cfra_eq(nearest->cfra, cfra)) {
+    update_func(nearest, userdata);
+  }
+  else if (is_cfra_lt(nearest->cfra, cfra)) {
+    ActKeyColumn *key_column = create_func(userdata);
+    BLI_insertlinkafter(&keylist->key_columns, nearest, key_column);
+    keylist->column_len += 1;
+    keylist->last_accessed_column = key_column;
+  }
+  else {
+    ActKeyColumn *key_column = create_func(userdata);
+    BLI_insertlinkbefore(&keylist->key_columns, nearest, key_column);
+    keylist->column_len += 1;
+    keylist->last_accessed_column = key_column;
+  }
+}
 
 /* Add the given BezTriple to the given 'list' of Keyframes */
 static void add_bezt_to_keycolumns_list(AnimKeylist *keylist, BezTripleChain *bezt)
@@ -416,7 +658,8 @@ static void add_bezt_to_keycolumns_list(AnimKeylist *keylist, BezTripleChain *be
     return;
   }
 
-  BLI_dlrbTree_add(&keylist->keys, compare_ak_bezt, nalloc_ak_bezt, nupdate_ak_bezt, bezt);
+  float cfra = bezt->cur->vec[1][0];
+  ED_keylist_add_or_update_column(keylist, cfra, nalloc_ak_bezt, nupdate_ak_bezt, bezt);
 }
 
 /* Add the given GPencil Frame to the given 'list' of Keyframes */
@@ -426,7 +669,8 @@ static void add_gpframe_to_keycolumns_list(AnimKeylist *keylist, bGPDframe *gpf)
     return;
   }
 
-  BLI_dlrbTree_add(&keylist->keys, compare_ak_gpframe, nalloc_ak_gpframe, nupdate_ak_gpframe, gpf);
+  float cfra = gpf->framenum;
+  ED_keylist_add_or_update_column(keylist, cfra, nalloc_ak_gpframe, nupdate_ak_gpframe, gpf);
 }
 
 /* Add the given MaskLayerShape Frame to the given 'list' of Keyframes */
@@ -436,11 +680,9 @@ static void add_masklay_to_keycolumns_list(AnimKeylist *keylist, MaskLayerShape
     return;
   }
 
-  BLI_dlrbTree_add(&keylist->keys,
-                   compare_ak_masklayshape,
-                   nalloc_ak_masklayshape,
-                   nupdate_ak_masklayshape,
-                   masklay_shape);
+  float cfra = masklay_shape->frame;
+  ED_keylist_add_or_update_column(
+      keylist, cfra, nalloc_ak_masklayshape, nupdate_ak_masklayshape, masklay_shape);
 }
 
 /* ActKeyBlocks (Long Keyframes) ------------------------------------------ */
@@ -476,7 +718,7 @@ static void compute_keyblock_data(ActKeyBlockInfo *info,
       hold = IS_EQF(beztn->vec[1][1], beztn->vec[0][1]) &&
              IS_EQF(prev->vec[1][1], prev->vec[2][1]);
     }
-    /* This interpolation type induces movement even between identical keys. */
+    /* This interpolation type induces movement even between identical columns. */
     else {
       hold = !ELEM(prev->ipo, BEZT_IPO_ELASTIC);
     }
@@ -514,7 +756,7 @@ static void add_keyblock_info(ActKeyColumn *col, const ActKeyBlockInfo *block)
 
 static void add_bezt_to_keyblocks_list(AnimKeylist *keylist, BezTriple *bezt, const int bezt_len)
 {
-  ActKeyColumn *col = static_cast<ActKeyColumn *>(keylist->keys.first);
+  ActKeyColumn *col = static_cast<ActKeyColumn *>(keylist->key_columns.first);
 
   if (bezt && bezt_len >= 2) {
     ActKeyBlockInfo block;
@@ -532,19 +774,15 @@ static void add_bezt_to_keyblocks_list(AnimKeylist *keylist, BezTriple *bezt, co
       if (is_cfra_lt(bezt[1].vec[1][0], bezt[0].vec[1][0])) {
         /* Backtrack to find the right location. */
         if (is_cfra_lt(bezt[1].vec[1][0], col->cfra)) {
-          ActKeyColumn *newcol = (ActKeyColumn *)BLI_dlrbTree_search_exact(
-              &keylist->keys, compare_ak_cfraPtr, &bezt[1].vec[1][0]);
+          ActKeyColumn *newcol = ED_keylist_find_exact_or_neighbour_column(keylist, col->cfra);
 
-          if (newcol != nullptr) {
-            col = newcol;
+          BLI_assert(newcol);
+          BLI_assert(newcol->cfra == col->cfra);
 
-            /* The previous keyblock is garbage too. */
-            if (col->prev != nullptr) {
-              add_keyblock_info(col->prev, &dummy_keyblock);
-            }
-          }
-          else {
-            BLI_assert(false);
+          col = newcol;
+          /* The previous keyblock is garbage too. */
+          if (col->prev != nullptr) {
+            add_keyblock_info(col->prev, &dummy_keyblock);
           }
         }
 
@@ -577,20 +815,17 @@ static void add_bezt_to_keyblocks_list(AnimKeylist *keylist, BezTriple *bezt, co
  */
 static void update_keyblocks(AnimKeylist *keylist, BezTriple *bezt, const int bezt_len)
 {
-  /* Recompute the prev/next linked list. */
-  BLI_dlrbTree_linkedlist_sync(&keylist->keys);
-
   /* Find the curve count */
   int max_curve = 0;
 
-  LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->keys) {
+  LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->key_columns) {
     max_curve = MAX2(max_curve, col->totcurve);
   }
 
   /* Propagate blocks to inserted keys */
   ActKeyColumn *prev_ready = nullptr;
 
-  LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->keys) {
+  LISTBASE_FOREACH (ActKeyColumn *, col, &keylist->key_columns) {
     /* Pre-existing column. */
     if (col->totcurve > 0) {
       prev_ready = col;
@@ -775,6 +1010,7 @@ void cachefile_to_keylist(bDopeSheet *ads,
 void fcurve_to_keylist(AnimData *adt, FCurve *fcu, AnimKeylist *keylist, const int saction_flag)
 {
   if (fcu && fcu->totvert && fcu->bezt) {
+    ED_keylist_reset_last_accessed(keylist);
     /* apply NLA-mapping (if applicable) */
     if (adt) {
       ANIM_nla_mapping_apply_fcurve(adt, fcu, false, false);
@@ -790,7 +1026,7 @@ void fcurve_to_keylist(AnimData *adt, FCurve *fcu, AnimKeylist *keylist, const i
     for (int v = 0; v < fcu->totvert; v++) {
       chain.cur = &fcu->bezt[v];
 
-      /* Neighbor keys, accounting for being cyclic. */
+      /* Neighbor columns, accounting for being cyclic. */
       if (do_extremes) {
         chain.prev = (v > 0)   ? &fcu->bezt[v - 1] :
                      is_cyclic ? &fcu->bezt[fcu->totvert - 2] :
@@ -856,6 +1092,7 @@ void gpencil_to_keylist(bDopeSheet *ads, bGPdata *gpd, AnimKeylist *keylist, con
 void gpl_to_keylist(bDopeSheet *UNUSED(ads), bGPDlayer *gpl, AnimKeylist *keylist)
 {
   if (gpl && keylist) {
+    ED_keylist_reset_last_accessed(keylist);
     /* Although the frames should already be in an ordered list,
      * they are not suitable for displaying yet. */
     LISTBASE_FOREACH (bGPDframe *, gpf, &gpl->frames) {
@@ -869,6 +1106,7 @@ void gpl_to_keylist(bDopeSheet *UNUSED(ads), bGPDlayer *gpl, AnimKeylist *keylis
 void mask_to_keylist(bDopeSheet *UNUSED(ads), MaskLayer *masklay, AnimKeylist *keylist)
 {
   if (masklay && keylist) {
+    ED_keylist_reset_last_accessed(keylist);
     LISTBASE_FOREACH (MaskLayerShape *, masklay_shape, &masklay->splines_shapes) {
       add_masklay_to_keycolumns_list(keylist, masklay_shape);
     }

source/blender/editors/armature/pose_slide.c

@@ -976,6 +976,7 @@ static int pose_slide_invoke_common(bContext *C, wmOperator *op, const wmEvent *
   }
 
   /* Cancel if no keyframes found. */
+  ED_keylist_prepare_for_direct_access(pso->keylist);
   if (ED_keylist_is_empty(pso->keylist)) {
     BKE_report(op->reports, RPT_ERROR, "No keyframes to slide between");
     pose_slide_exit(C, op);
@@ -1712,6 +1713,7 @@ static float pose_propagate_get_boneHoldEndFrame(tPChanFCurveLink *pfl, float st
     FCurve *fcu = (FCurve *)ld->data;
     fcurve_to_keylist(adt, fcu, keylist, 0);
   }
+  ED_keylist_prepare_for_direct_access(keylist);
 
   /* Find the long keyframe (i.e. hold), and hence obtain the endFrame value
    * - the best case would be one that starts on the frame itself

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);

source/blender/editors/screen/screen_ops.c

@@ -3107,6 +3107,7 @@ static int keyframe_jump_exec(bContext *C, wmOperator *op)
       mask_to_keylist(&ads, masklay, keylist);
     }
   }
+  ED_keylist_prepare_for_direct_access(keylist);
 
   /* find matching keyframe in the right direction */
   const ActKeyColumn *ak;

source/blender/editors/space_action/action_select.c

@@ -162,6 +162,7 @@ static void actkeys_find_key_in_list_element(bAnimContext *ac,
 
   struct AnimKeylist *keylist = ED_keylist_create();
   actkeys_list_element_to_keylist(ac, keylist, ale);
+  ED_keylist_prepare_for_direct_access(keylist);
 
   AnimData *adt = ANIM_nla_mapping_get(ac, ale);