VSE: Improve animation evaluation performance

Use lookup string callback function for `sequences_all` RNA property
`rna_SequenceEditor_sequences_all_lookup_string` using a GHash for faster lookups.

When names are changed or strips are added/removed the lookup is tagged invalid.
The next time the lookup is used it will rebuild it.

Reviewed By: sergey, jbakker

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

source/blender/blenkernel/intern/scene.c

@@ -1145,6 +1145,7 @@ static void scene_blend_read_data(BlendDataReader *reader, ID *id)
     BLO_read_data_address(reader, &ed->act_seq);
     ed->cache = NULL;
     ed->prefetch_job = NULL;
+    ed->runtime.sequence_lookup = NULL;
 
     /* recursive link sequences, lb will be correctly initialized */
     link_recurs_seq(reader, &ed->seqbase);

source/blender/blenloader/intern/versioning_280.c

@@ -1785,7 +1785,7 @@ void do_versions_after_linking_280(Main *bmain, ReportList *UNUSED(reports))
 static void do_versions_seq_unique_name_all_strips(Scene *sce, ListBase *seqbasep)
 {
   for (Sequence *seq = seqbasep->first; seq != NULL; seq = seq->next) {
-    SEQ_sequence_base_unique_name_recursive(&sce->ed->seqbase, seq);
+    SEQ_sequence_base_unique_name_recursive(sce, &sce->ed->seqbase, seq);
     if (seq->seqbase.first != NULL) {
       do_versions_seq_unique_name_all_strips(sce, &seq->seqbase);
     }

source/blender/editors/space_sequencer/sequencer_edit.c

@@ -1983,7 +1983,7 @@ static int sequencer_meta_make_exec(bContext *C, wmOperator *op)
 
   seqm->machine = active_seq ? active_seq->machine : channel_max;
   strcpy(seqm->name + 2, "MetaStrip");
-  SEQ_sequence_base_unique_name_recursive(&ed->seqbase, seqm);
+  SEQ_sequence_base_unique_name_recursive(scene, &ed->seqbase, seqm);
   seqm->start = meta_start_frame;
   seqm->len = meta_end_frame - meta_start_frame;
   SEQ_time_update_sequence(scene, seqm);

source/blender/makesdna/DNA_sequence_types.h

@@ -45,6 +45,7 @@ struct MovieClip;
 struct Scene;
 struct VFont;
 struct bSound;
+struct SequenceLookup;
 
 /* strlens; 256= FILE_MAXFILE, 768= FILE_MAXDIR */
 
@@ -257,6 +258,10 @@ typedef struct MetaStack {
   int disp_range[2];
 } MetaStack;
 
+typedef struct EditingRuntime {
+  struct SequenceLookup *sequence_lookup;
+} EditingRuntime;
+
 typedef struct Editing {
   /** Pointer to the current list of seq's being edited (can be within a meta strip). */
   ListBase *seqbasep;
@@ -287,6 +292,8 @@ typedef struct Editing {
 
   /* Must be initialized only by seq_cache_create() */
   int64_t disk_cache_timestamp;
+
+  EditingRuntime runtime;
 } Editing;
 
 /* ************* Effect Variable Structs ********* */

source/blender/makesrna/intern/rna_sequencer.c

@@ -94,6 +94,8 @@ const EnumPropertyItem rna_enum_sequence_modifier_type_items[] = {
 
 #  include "IMB_imbuf.h"
 
+#  include "SEQ_edit.h"
+
 typedef struct SequenceSearchData {
   Sequence *seq;
   void *data;
@@ -243,6 +245,21 @@ static void rna_SequenceEditor_sequences_all_next(CollectionPropertyIterator *it
   iter->valid = (internal->link != NULL);
 }
 
+static int rna_SequenceEditor_sequences_all_lookup_string(PointerRNA *ptr,
+                                                          const char *key,
+                                                          PointerRNA *r_ptr)
+{
+  ID *id = ptr->owner_id;
+  Scene *scene = (Scene *)id;
+
+  Sequence *seq = SEQ_sequence_lookup_by_name(scene, key);
+  if (seq) {
+    RNA_pointer_create(ptr->owner_id, &RNA_Sequence, seq, r_ptr);
+    return true;
+  }
+  return false;
+}
+
 /* internal use */
 static int rna_SequenceEditor_elements_length(PointerRNA *ptr)
 {
@@ -627,11 +644,10 @@ static void rna_Sequence_name_set(PointerRNA *ptr, const char *value)
   BLI_strncpy(oldname, seq->name + 2, sizeof(seq->name) - 2);
 
   /* copy the new name into the name slot */
-  BLI_strncpy_utf8(seq->name + 2, value, sizeof(seq->name) - 2);
+  SEQ_edit_sequence_name_set(scene, seq, value);
 
   /* make sure the name is unique */
-  SEQ_sequence_base_unique_name_recursive(&scene->ed->seqbase, seq);
-
+  SEQ_sequence_base_unique_name_recursive(scene, &scene->ed->seqbase, seq);
   /* fix all the animation data which may link to this */
 
   /* Don't rename everywhere because these are per scene. */
@@ -1997,7 +2013,7 @@ static void rna_def_editor(BlenderRNA *brna)
                                     NULL,
                                     NULL,
                                     NULL,
-                                    NULL,
+                                    "rna_SequenceEditor_sequences_all_lookup_string",
                                     NULL);
 
   prop = RNA_def_property(srna, "meta_stack", PROP_COLLECTION, PROP_NONE);

source/blender/sequencer/CMakeLists.txt

@@ -79,6 +79,7 @@ set(SRC
   intern/render.h
   intern/sequencer.c
   intern/sequencer.h
+  intern/sequence_lookup.c
   intern/sound.c
   intern/strip_add.c
   intern/strip_edit.c

source/blender/sequencer/SEQ_edit.h

@@ -58,6 +58,8 @@ bool SEQ_edit_remove_gaps(struct Scene *scene,
                           struct ListBase *seqbase,
                           const int initial_frame,
                           const bool remove_all_gaps);
+void SEQ_edit_sequence_name_set(struct Scene *scene, struct Sequence *seq, const char *new_name);
+
 #ifdef __cplusplus
 }
 #endif

source/blender/sequencer/SEQ_sequencer.h

@@ -33,6 +33,7 @@ struct Editing;
 struct Scene;
 struct Sequence;
 struct SequencerToolSettings;
+struct SequenceLookup;
 
 /* RNA enums, just to be more readable */
 enum {
@@ -79,6 +80,16 @@ void SEQ_sequence_base_dupli_recursive(const struct Scene *scene_src,
                                        int dupe_flag,
                                        const int flag);
 
+/* Defined in sequence_lookup.c */
+
+typedef enum eSequenceLookupTag {
+  SEQ_LOOKUP_TAG_INVALID = (1 << 0),
+} eSequenceLookupTag;
+
+struct Sequence *SEQ_sequence_lookup_by_name(const struct Scene *scene, const char *key);
+void SEQ_sequence_lookup_free(const struct Scene *scene);
+void SEQ_sequence_lookup_tag(const struct Scene *scene, eSequenceLookupTag tag);
+
 #ifdef __cplusplus
 }
 #endif

source/blender/sequencer/SEQ_utils.h

@@ -36,7 +36,9 @@ struct Sequence;
 struct StripElem;
 
 void SEQ_sort(struct ListBase *seqbase);
-void SEQ_sequence_base_unique_name_recursive(struct ListBase *seqbasep, struct Sequence *seq);
+void SEQ_sequence_base_unique_name_recursive(struct Scene *scene,
+                                             struct ListBase *seqbasep,
+                                             struct Sequence *seq);
 const char *SEQ_sequence_give_name(struct Sequence *seq);
 struct ListBase *SEQ_get_seqbase_from_sequence(struct Sequence *seq, int *r_offset);
 const struct Sequence *SEQ_get_topmost_sequence(const struct Scene *scene, int frame);

source/blender/sequencer/intern/sequence_lookup.c

@@ -0,0 +1,161 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * The Original Code is Copyright (C) 2021 Blender Foundation.
+ * All rights reserved.
+ */
+
+/** \file
+ * \ingroup sequencer
+ */
+
+#include "SEQ_sequencer.h"
+
+#include "DNA_listBase.h"
+#include "DNA_scene_types.h"
+#include "DNA_sequence_types.h"
+
+#include "SEQ_iterator.h"
+
+#include "BLI_ghash.h"
+#include "BLI_string.h"
+#include "BLI_sys_types.h"
+#include "BLI_threads.h"
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+static ThreadMutex lookup_lock = BLI_MUTEX_INITIALIZER;
+
+typedef struct SequenceLookup {
+  GHash *by_name;
+  eSequenceLookupTag tag;
+} SequenceLookup;
+
+static void seq_sequence_lookup_init(struct SequenceLookup *lookup)
+{
+  lookup->by_name = BLI_ghash_str_new(__func__);
+  lookup->tag |= SEQ_LOOKUP_TAG_INVALID;
+}
+
+static void seq_sequence_lookup_build(const struct Scene *scene, struct SequenceLookup *lookup)
+{
+  SeqCollection *all_strips = SEQ_query_all_strips_recursive(&scene->ed->seqbase);
+  Sequence *seq;
+  SEQ_ITERATOR_FOREACH (seq, all_strips) {
+    BLI_ghash_insert(lookup->by_name, seq->name + 2, seq);
+  }
+  SEQ_collection_free(all_strips);
+  lookup->tag &= ~SEQ_LOOKUP_TAG_INVALID;
+}
+
+static SequenceLookup *seq_sequence_lookup_new(void)
+{
+  SequenceLookup *lookup = MEM_callocN(sizeof(SequenceLookup), __func__);
+  seq_sequence_lookup_init(lookup);
+  return lookup;
+}
+
+static void seq_sequence_lookup_free(struct SequenceLookup **lookup)
+{
+  if (*lookup == NULL) {
+    return;
+  }
+
+  BLI_ghash_free((*lookup)->by_name, NULL, NULL);
+  (*lookup)->by_name = NULL;
+  MEM_freeN(*lookup);
+  *lookup = NULL;
+}
+
+static void seq_sequence_lookup_rebuild(const struct Scene *scene, struct SequenceLookup **lookup)
+{
+  seq_sequence_lookup_free(lookup);
+  *lookup = seq_sequence_lookup_new();
+  seq_sequence_lookup_build(scene, *lookup);
+}
+
+static bool seq_sequence_lookup_is_valid(struct SequenceLookup *lookup)
+{
+  return (lookup->tag & SEQ_LOOKUP_TAG_INVALID) == 0;
+}
+
+static void seq_sequence_lookup_update_if_needed(const struct Scene *scene,
+                                                 struct SequenceLookup **lookup)
+{
+  if (!scene->ed) {
+    return;
+  }
+  if (*lookup && seq_sequence_lookup_is_valid(*lookup)) {
+    return;
+  }
+
+  seq_sequence_lookup_rebuild(scene, lookup);
+}
+
+/**
+ * Free lookup hash data.
+ *
+ * \param scene: scene that owns lookup hash
+ */
+void SEQ_sequence_lookup_free(const Scene *scene)
+{
+  BLI_assert(scene->ed);
+  BLI_mutex_lock(&lookup_lock);
+  SequenceLookup *lookup = scene->ed->runtime.sequence_lookup;
+  seq_sequence_lookup_free(&lookup);
+  BLI_mutex_unlock(&lookup_lock);
+}
+
+/**
+ * Find a sequence with a given name.
+ * If lookup hash doesn't exist, it will be created. If hash is tagged as invalid, it will be
+ * rebuilt.
+ *
+ * \param scene: scene that owns lookup hash
+ * \param key: Sequence name without SQ prefix (seq->name + 2)
+ *
+ * \return pointer to Sequence
+ */
+Sequence *SEQ_sequence_lookup_by_name(const Scene *scene, const char *key)
+{
+  BLI_assert(scene->ed);
+  BLI_mutex_lock(&lookup_lock);
+  seq_sequence_lookup_update_if_needed(scene, &scene->ed->runtime.sequence_lookup);
+  SequenceLookup *lookup = scene->ed->runtime.sequence_lookup;
+  Sequence *seq = BLI_ghash_lookup(lookup->by_name, key);
+  BLI_mutex_unlock(&lookup_lock);
+  return seq;
+}
+
+/**
+ * Find a sequence with a given name.
+ *
+ * \param scene: scene that owns lookup hash
+ * \param tag: tag to set
+ */
+void SEQ_sequence_lookup_tag(const Scene *scene, eSequenceLookupTag tag)
+{
+  if (!scene->ed) {
+    return;
+  }
+
+  BLI_mutex_lock(&lookup_lock);
+  SequenceLookup *lookup = scene->ed->runtime.sequence_lookup;
+  if (lookup != NULL) {
+    lookup->tag |= tag;
+  }
+  BLI_mutex_unlock(&lookup_lock);
+}

source/blender/sequencer/intern/sequencer.c

@@ -271,6 +271,7 @@ void SEQ_editing_free(Scene *scene, const bool do_id_user)
   SEQ_ALL_END;
 
   BLI_freelistN(&ed->metastack);
+  SEQ_sequence_lookup_free(scene);
   MEM_freeN(ed);
 
   scene->ed = NULL;
@@ -514,7 +515,7 @@ static Sequence *seq_dupli(const Scene *scene_src,
 
   if (scene_src == scene_dst) {
     if (dupe_flag & SEQ_DUPE_UNIQUE_NAME) {
-      SEQ_sequence_base_unique_name_recursive(&scene_dst->ed->seqbase, seqn);
+      SEQ_sequence_base_unique_name_recursive(scene_dst, &scene_dst->ed->seqbase, seqn);
     }
   }
 

source/blender/sequencer/intern/strip_add.c

@@ -56,6 +56,7 @@
 #include "IMB_metadata.h"
 
 #include "SEQ_add.h"
+#include "SEQ_edit.h"
 #include "SEQ_effects.h"
 #include "SEQ_relations.h"
 #include "SEQ_render.h"
@@ -98,33 +99,32 @@ void SEQ_add_load_data_init(SeqLoadData *load_data,
 
 static void seq_add_generic_update(Scene *scene, ListBase *seqbase, Sequence *seq)
 {
-  SEQ_sequence_base_unique_name_recursive(seqbase, seq);
+  SEQ_sequence_base_unique_name_recursive(scene, seqbase, seq);
   SEQ_time_update_sequence_bounds(scene, seq);
   SEQ_sort(seqbase);
   SEQ_relations_invalidate_cache_composite(scene, seq);
 }
 
-static void seq_add_set_name(Sequence *seq, SeqLoadData *load_data)
+static void seq_add_set_name(Scene *scene, Sequence *seq, SeqLoadData *load_data)
 {
   if (load_data->name[0] != '\0') {
-    BLI_strncpy(seq->name + 2, load_data->name, sizeof(seq->name) - 2);
+    SEQ_edit_sequence_name_set(scene, seq, load_data->name);
   }
   else {
     if (seq->type == SEQ_TYPE_SCENE) {
-      BLI_strncpy(seq->name + 2, load_data->scene->id.name + 2, sizeof(seq->name) - 2);
+      SEQ_edit_sequence_name_set(scene, seq, load_data->scene->id.name + 2);
     }
     else if (seq->type == SEQ_TYPE_MOVIECLIP) {
-      BLI_strncpy(seq->name + 2, load_data->clip->id.name + 2, sizeof(seq->name) - 2);
+      SEQ_edit_sequence_name_set(scene, seq, load_data->clip->id.name + 2);
     }
     else if (seq->type == SEQ_TYPE_MASK) {
-      BLI_strncpy(seq->name + 2, load_data->mask->id.name + 2, sizeof(seq->name) - 2);
+      SEQ_edit_sequence_name_set(scene, seq, load_data->mask->id.name + 2);
     }
     else if ((seq->type & SEQ_TYPE_EFFECT) != 0) {
-      BLI_strncpy(seq->name + 2, SEQ_sequence_give_name(seq), sizeof(seq->name) - 2);
+      SEQ_edit_sequence_name_set(scene, seq, SEQ_sequence_give_name(seq));
     }
     else { /* Image, sound and movie. */
-      BLI_strncpy_utf8(seq->name + 2, load_data->name, sizeof(seq->name) - 2);
-      BLI_utf8_invalid_strip(seq->name + 2, strlen(seq->name + 2));
+      SEQ_edit_sequence_name_set(scene, seq, load_data->name);
     }
   }
 }
@@ -163,7 +163,7 @@ Sequence *SEQ_add_scene_strip(Scene *scene, ListBase *seqbase, struct SeqLoadDat
   seq->scene = load_data->scene;
   seq->len = load_data->scene->r.efra - load_data->scene->r.sfra + 1;
   id_us_ensure_real((ID *)load_data->scene);
-  seq_add_set_name(seq, load_data);
+  seq_add_set_name(scene, seq, load_data);
   seq_add_generic_update(scene, seqbase, seq);
   return seq;
 }
@@ -184,7 +184,7 @@ Sequence *SEQ_add_movieclip_strip(Scene *scene, ListBase *seqbase, struct SeqLoa
   seq->clip = load_data->clip;
   seq->len = BKE_movieclip_get_duration(load_data->clip);
   id_us_ensure_real((ID *)load_data->clip);
-  seq_add_set_name(seq, load_data);
+  seq_add_set_name(scene, seq, load_data);
   seq_add_generic_update(scene, seqbase, seq);
   return seq;
 }
@@ -205,7 +205,7 @@ Sequence *SEQ_add_mask_strip(Scene *scene, ListBase *seqbase, struct SeqLoadData
   seq->mask = load_data->mask;
   seq->len = BKE_mask_get_duration(load_data->mask);
   id_us_ensure_real((ID *)load_data->mask);
-  seq_add_set_name(seq, load_data);
+  seq_add_set_name(scene, seq, load_data);
   seq_add_generic_update(scene, seqbase, seq);
   return seq;
 }
@@ -249,7 +249,7 @@ Sequence *SEQ_add_effect_strip(Scene *scene, ListBase *seqbase, struct SeqLoadDa
   }
 
   SEQ_relations_update_changed_seq_and_deps(scene, seq, 1, 1); /* Runs SEQ_time_update_sequence. */
-  seq_add_set_name(seq, load_data);
+  seq_add_set_name(scene, seq, load_data);
   seq_add_generic_update(scene, seqbase, seq);
 
   return seq;
@@ -364,7 +364,7 @@ Sequence *SEQ_add_image_strip(Main *bmain, Scene *scene, ListBase *seqbase, SeqL
   /* Set Last active directory. */
   BLI_strncpy(scene->ed->act_imagedir, seq->strip->dir, sizeof(scene->ed->act_imagedir));
   seq_add_set_view_transform(scene, seq, load_data);
-  seq_add_set_name(seq, load_data);
+  seq_add_set_name(scene, seq, load_data);
   seq_add_generic_update(scene, seqbase, seq);
 
   return seq;
@@ -426,7 +426,7 @@ Sequence *SEQ_add_sound_strip(Main *bmain, Scene *scene, ListBase *seqbase, SeqL
 
   /* Set Last active directory. */
   BLI_strncpy(scene->ed->act_sounddir, strip->dir, FILE_MAXDIR);
-  seq_add_set_name(seq, load_data);
+  seq_add_set_name(scene, seq, load_data);
   seq_add_generic_update(scene, seqbase, seq);
 
   return seq;
@@ -458,7 +458,7 @@ Sequence *SEQ_add_meta_strip(Scene *scene, ListBase *seqbase, SeqLoadData *load_
       seqbase, load_data->start_frame, load_data->channel, SEQ_TYPE_META);
 
   /* Set name. */
-  seq_add_set_name(seqm, load_data);
+  seq_add_set_name(scene, seqm, load_data);
 
   /* Set frames start and length. */
   seqm->start = load_data->start_frame;
@@ -590,7 +590,7 @@ Sequence *SEQ_add_movie_strip(Main *bmain, Scene *scene, ListBase *seqbase, SeqL
   BLI_split_dirfile(load_data->path, strip->dir, se->name, sizeof(strip->dir), sizeof(se->name));
 
   seq_add_set_view_transform(scene, seq, load_data);
-  seq_add_set_name(seq, load_data);
+  seq_add_set_name(scene, seq, load_data);
   seq_add_generic_update(scene, seqbase, seq);
 
   MEM_freeN(anim_arr);

source/blender/sequencer/intern/strip_edit.c

@@ -30,6 +30,7 @@
 #include "BLI_listbase.h"
 #include "BLI_math.h"
 #include "BLI_string.h"
+#include "BLI_string_utf8.h"
 
 #include "BLT_translation.h"
 
@@ -202,6 +203,7 @@ void SEQ_edit_remove_flagged_sequences(Scene *scene, ListBase *seqbase)
       }
       BLI_remlink(seqbase, seq);
       SEQ_sequence_free(scene, seq, true);
+      SEQ_sequence_lookup_tag(scene, SEQ_LOOKUP_TAG_INVALID);
     }
   }
 }
@@ -468,3 +470,10 @@ bool SEQ_edit_remove_gaps(Scene *scene,
   }
   return true;
 }
+
+void SEQ_edit_sequence_name_set(Scene *scene, Sequence *seq, const char *new_name)
+{
+  BLI_strncpy_utf8(seq->name + 2, new_name, MAX_NAME - 2);
+  BLI_utf8_invalid_strip(seq->name + 2, strlen(seq->name + 2));
+  SEQ_sequence_lookup_tag(scene, SEQ_LOOKUP_TAG_INVALID);
+}

source/blender/sequencer/intern/utils.c

@@ -39,6 +39,7 @@
 #include "BKE_main.h"
 #include "BKE_scene.h"
 
+#include "SEQ_edit.h"
 #include "SEQ_iterator.h"
 #include "SEQ_relations.h"
 #include "SEQ_select.h"
@@ -140,7 +141,9 @@ static int seqbase_unique_name_recursive_fn(Sequence *seq, void *arg_pt)
   return 1;
 }
 
-void SEQ_sequence_base_unique_name_recursive(ListBase *seqbasep, Sequence *seq)
+void SEQ_sequence_base_unique_name_recursive(struct Scene *scene,
+                                             ListBase *seqbasep,
+                                             Sequence *seq)
 {
   SeqUniqueInfo sui;
   char *dot;
@@ -167,7 +170,7 @@ void SEQ_sequence_base_unique_name_recursive(ListBase *seqbasep, Sequence *seq)
     SEQ_seqbase_recursive_apply(seqbasep, seqbase_unique_name_recursive_fn, &sui);
   }
 
-  BLI_strncpy(seq->name + 2, sui.name_dest, sizeof(seq->name) - 2);
+  SEQ_edit_sequence_name_set(scene, seq, sui.name_dest);
 }
 
 static const char *give_seqname_by_type(int type)
@@ -629,7 +632,7 @@ void SEQ_ensure_unique_name(Sequence *seq, Scene *scene)
   char name[SEQ_NAME_MAXSTR];
 
   BLI_strncpy_utf8(name, seq->name + 2, sizeof(name));
-  SEQ_sequence_base_unique_name_recursive(&scene->ed->seqbase, seq);
+  SEQ_sequence_base_unique_name_recursive(scene, &scene->ed->seqbase, seq);
   SEQ_dupe_animdata(scene, name, seq->name + 2);
 
   if (seq->type == SEQ_TYPE_META) {