VSE: prefetching

When enabled prefetching(preview panel>view settings), a pernament running job
is created, that will render frames in the background until the cache is full.
If the cache is not filled fast enough, prefetch job suspends itself
at the last moment and will wait until it has chance to "catch up".
Effectively this will decouple rendering to separate thread, so rendering
itself is a bit faster.
Cache recycling behavior will be changed to "free furthest frame to the left
of playhead if possible, otherwise rightmost frame".

Reviewed By: brecht

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

9 files changed, 610 insertions, 26 deletions

diff --git a/source/blender/blenkernel/BKE_sequencer.h b/source/blender/blenkernel/BKE_sequencer.h
index e1bc16702d5..16f766ae8bb 100644
--- a/source/blender/blenkernel/BKE_sequencer.h
+++ b/source/blender/blenkernel/BKE_sequencer.h
@@ -82,6 +82,11 @@ void BKE_sequence_iterator_end(SeqIterator *iter);
   } \
   ((void)0)
 
+typedef enum eSeqTaskId {
+  SEQ_TASK_MAIN_RENDER,
+  SEQ_TASK_PREFETCH_RENDER,
+} eSeqTaskId;
+
 typedef struct SeqRenderData {
   struct Main *bmain;
   struct Depsgraph *depsgraph;
@@ -94,7 +99,10 @@ typedef struct SeqRenderData {
   float motion_blur_shutter;
   bool skip_cache;
   bool is_proxy_render;
+  bool is_prefetch_render;
   int view_id;
+  /* ID of task for asigning temp cache entries to particular task(thread, etc.) */
+  eSeqTaskId task_id;
 
   /* special case for OpenGL render */
   struct GPUOffScreen *gpu_offscreen;
@@ -290,7 +298,7 @@ void BKE_sequencer_proxy_rebuild_context(struct Main *bmain,
 void BKE_sequencer_proxy_rebuild(struct SeqIndexBuildContext *context,
                                  short *stop,
                                  short *do_update,
-                                 float *progress);
+                                 float *num_frames_prefetched);
 void BKE_sequencer_proxy_rebuild_finish(struct SeqIndexBuildContext *context, bool stop);
 
 void BKE_sequencer_proxy_set(struct Sequence *seq, bool value);
@@ -318,6 +326,7 @@ bool BKE_sequencer_cache_put_if_possible(const SeqRenderData *context,
                                          int type,
                                          struct ImBuf *nval,
                                          float cost);
+bool BKE_sequencer_cache_recycle_item(struct Scene *scene);
 void BKE_sequencer_cache_free_temp_cache(struct Scene *scene, short id, int cfra);
 void BKE_sequencer_cache_destruct(struct Scene *scene);
 void BKE_sequencer_cache_cleanup_all(struct Main *bmain);
@@ -330,6 +339,22 @@ void BKE_sequencer_cache_iterate(
     struct Scene *scene,
     void *userdata,
     bool callback(void *userdata, struct Sequence *seq, int cfra, int cache_type, float cost));
+bool BKE_sequencer_cache_is_full(struct Scene *scene);
+
+/* **********************************************************************
+ * seqprefetch.c
+ *
+ * Sequencer frame prefetching
+ * ********************************************************************** */
+
+void BKE_sequencer_prefetch_start(const SeqRenderData *context, float cfra, float cost);
+void BKE_sequencer_prefetch_stop(struct Scene *scene);
+void BKE_sequencer_prefetch_free(struct Scene *scene);
+bool BKE_sequencer_prefetch_need_redraw(struct Main *bmain, struct Scene *scene);
+void BKE_sequencer_prefetch_get_time_range(struct Scene *scene, int *start, int *end);
+SeqRenderData *BKE_sequencer_prefetch_get_original_context(const SeqRenderData *context);
+struct Sequence *BKE_sequencer_prefetch_get_original_sequence(struct Sequence *seq,
+                                                              struct Scene *scene);
 
 /* **********************************************************************
  * seqeffects.c
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index 053e5435925..16074cd3e37 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -188,6 +188,7 @@ set(SRC
   intern/scene.c
   intern/screen.c
   intern/seqcache.c
+  intern/seqprefetch.c
   intern/seqeffects.c
   intern/seqmodifier.c
   intern/sequencer.c
diff --git a/source/blender/blenkernel/intern/seqcache.c b/source/blender/blenkernel/intern/seqcache.c
index ff54327e406..eb4fc6994a9 100644
--- a/source/blender/blenkernel/intern/seqcache.c
+++ b/source/blender/blenkernel/intern/seqcache.c
@@ -44,17 +44,6 @@
  * Sequencer Cache Design Notes
  * ============================
  *
- * Cache key members:
- * is_temp_cache - this cache entry will be freed before rendering next frame
- * creator_id - ID of thread that created entry
- * cost - In short: render time divided by playback frame rate
- * link_prev/next - link to another entry created during rendering of the frame
- *
- * Linking: We use links to reduce number of iterations needed to manage cache.
- * Entries are linked in order as they are put into cache.
- * Only permanent (is_temp_cache = 0) cache entries are linked.
- * Putting #SEQ_CACHE_STORE_FINAL_OUT will reset linking
- *
  * Function:
  * All images created during rendering are added to cache, even if the cache is already full.
  * This is because:
@@ -64,6 +53,11 @@
  *    "holes" in the cache, which can be annoying
  * If the cache is full all entries for pending frame will have is_temp_cache set.
  *
+ * Linking: We use links to reduce number of iterations over entries needed to manage cache.
+ * Entries are linked in order as they are put into cache.
+ * Only permanent (is_temp_cache = 0) cache entries are linked.
+ * Putting #SEQ_CACHE_STORE_FINAL_OUT will reset linking
+ *
  * Only entire frame can be freed to release resources for new entries (recycling).
  * Once again, this is to reduce number of iterations, but also more controllable than removing
  * entries one by one in reverse order to their creation.
@@ -93,9 +87,10 @@ typedef struct SeqCacheKey {
   struct Sequence *seq;
   SeqRenderData context;
   float nfra;
-  float cost;
-  bool is_temp_cache;
-  short creator_id;
+  float cost;         /* In short: render time(s) divided by playback frame duration(s) */
+  bool is_temp_cache; /* this cache entry will be freed before rendering next frame */
+  /* ID of task for asigning temp cache entries to particular task(thread, etc.) */
+  eSeqTaskId task_id;
   int type;
 } SeqCacheKey;
 
@@ -172,6 +167,11 @@ static void seq_cache_unlock(Scene *scene)
   }
 }
 
+static size_t seq_cache_get_mem_total(void)
+{
+  return ((size_t)U.memcachelimit) * 1024 * 1024;
+}
+
 static void seq_cache_keyfree(void *val)
 {
   SeqCacheKey *key = val;
@@ -228,10 +228,43 @@ static void seq_cache_relink_keys(SeqCacheKey *link_next, SeqCacheKey *link_prev
   }
 }
 
+/* Choose a key out of 2 candidates(leftmost and rightmost items)
+ * to recycle based on currently used strategy */
 static SeqCacheKey *seq_cache_choose_key(Scene *scene, SeqCacheKey *lkey, SeqCacheKey *rkey)
 {
   SeqCacheKey *finalkey = NULL;
 
+  /* Ideally, cache would not need to check the state of prefetching task
+   * that is tricky to do however, because prefetch would need to know,
+   * if a key, that is about to be created would be removed by itself.
+   *
+   * This can happen because only FINAL_OUT item insertion will trigger recycling
+   * but that is also the point, where prefetch can be suspended.
+   *
+   * We could use temp cache as a shield and later untemp entry,
+   * but it is not worth of increasing system complexity.
+   */
+  if (scene->ed->cache_flag & SEQ_CACHE_PREFETCH_ENABLE) {
+    int pfjob_start, pfjob_end;
+    BKE_sequencer_prefetch_get_time_range(scene, &pfjob_start, &pfjob_end);
+
+    if (lkey) {
+      int lkey_cfra = lkey->seq->start + lkey->nfra;
+      if (lkey_cfra < pfjob_start || lkey_cfra > pfjob_end) {
+        return lkey;
+      }
+    }
+
+    if (rkey) {
+      int rkey_cfra = rkey->seq->start + rkey->nfra;
+      if (rkey_cfra < pfjob_start || rkey_cfra > pfjob_end) {
+        return rkey;
+      }
+    }
+
+    return NULL;
+  }
+
   if (rkey && lkey) {
     int lkey_cfra = lkey->seq->start + lkey->nfra;
     int rkey_cfra = rkey->seq->start + rkey->nfra;
@@ -286,7 +319,7 @@ static void seq_cache_recycle_linked(Scene *scene, SeqCacheKey *base)
   }
 }
 
-static SeqCacheKey *seq_cache_get_item_for_removal(Scene *scene)
+SeqCacheKey *seq_cache_get_item_for_removal(Scene *scene)
 {
   SeqCache *cache = seq_cache_get_from_scene(scene);
   SeqCacheKey *finalkey = NULL;
@@ -342,15 +375,16 @@ static SeqCacheKey *seq_cache_get_item_for_removal(Scene *scene)
   }
 
   finalkey = seq_cache_choose_key(scene, lkey, rkey);
+
   return finalkey;
 }
 
 /* Find only "base" keys
  * Sources(other types) for a frame must be freed all at once
  */
-static bool seq_cache_recycle_item(Scene *scene)
+bool BKE_sequencer_cache_recycle_item(Scene *scene)
 {
-  size_t memory_total = ((size_t)U.memcachelimit) * 1024 * 1024;
+  size_t memory_total = seq_cache_get_mem_total();
   SeqCache *cache = seq_cache_get_from_scene(scene);
   if (!cache) {
     return false;
@@ -429,7 +463,7 @@ void BKE_sequencer_cache_free_temp_cache(Scene *scene, short id, int cfra)
     SeqCacheKey *key = BLI_ghashIterator_getKey(&gh_iter);
     BLI_ghashIterator_step(&gh_iter);
 
-    if (key->is_temp_cache && key->creator_id == id && key->seq->start + key->nfra != cfra) {
+    if (key->is_temp_cache && key->task_id == id && key->seq->start + key->nfra != cfra) {
       BLI_ghash_remove(cache->hash, key, seq_cache_keyfree, seq_cache_valfree);
     }
   }
@@ -459,6 +493,8 @@ void BKE_sequencer_cache_cleanup_all(Main *bmain)
 }
 void BKE_sequencer_cache_cleanup(Scene *scene)
 {
+  BKE_sequencer_prefetch_stop(scene);
+
   SeqCache *cache = seq_cache_get_from_scene(scene);
   if (!cache) {
     return;
@@ -542,6 +578,12 @@ struct ImBuf *BKE_sequencer_cache_get(const SeqRenderData *context,
 {
   Scene *scene = context->scene;
 
+  if (context->is_prefetch_render) {
+    context = BKE_sequencer_prefetch_get_original_context(context);
+    scene = context->scene;
+    seq = BKE_sequencer_prefetch_get_original_sequence(seq, scene);
+  }
+
   if (!scene->ed->cache) {
     BKE_sequencer_cache_create(scene);
     return NULL;
@@ -571,7 +613,13 @@ bool BKE_sequencer_cache_put_if_possible(
 {
   Scene *scene = context->scene;
 
-  if (seq_cache_recycle_item(scene)) {
+  if (context->is_prefetch_render) {
+    context = BKE_sequencer_prefetch_get_original_context(context);
+    scene = context->scene;
+    seq = BKE_sequencer_prefetch_get_original_sequence(seq, scene);
+  }
+
+  if (BKE_sequencer_cache_recycle_item(scene)) {
     BKE_sequencer_cache_put(context, seq, cfra, type, ibuf, cost);
     return true;
   }
@@ -586,7 +634,12 @@ void BKE_sequencer_cache_put(
     const SeqRenderData *context, Sequence *seq, float cfra, int type, ImBuf *i, float cost)
 {
   Scene *scene = context->scene;
-  short creator_id = 0;
+
+  if (context->is_prefetch_render) {
+    context = BKE_sequencer_prefetch_get_original_context(context);
+    scene = context->scene;
+    seq = BKE_sequencer_prefetch_get_original_sequence(seq, scene);
+  }
 
   if (i == NULL || context->skip_cache || context->is_proxy_render || !seq) {
     return;
@@ -632,7 +685,7 @@ void BKE_sequencer_cache_put(
   key->link_prev = NULL;
   key->link_next = NULL;
   key->is_temp_cache = true;
-  key->creator_id = creator_id;
+  key->task_id = context->task_id;
 
   /* Item stored for later use */
   if (flag & type) {
@@ -688,3 +741,14 @@ void BKE_sequencer_cache_iterate(
   cache->last_key = NULL;
   seq_cache_unlock(scene);
 }
+
+bool BKE_sequencer_cache_is_full(Scene *scene)
+{
+  size_t memory_total = seq_cache_get_mem_total();
+  SeqCache *cache = seq_cache_get_from_scene(scene);
+  if (!cache) {
+    return false;
+  }
+
+  return memory_total < cache->memory_used;
+}
diff --git a/source/blender/blenkernel/intern/seqprefetch.c b/source/blender/blenkernel/intern/seqprefetch.c
new file mode 100644
index 00000000000..172db70823a
--- /dev/null
+++ b/source/blender/blenkernel/intern/seqprefetch.c
@@ -0,0 +1,453 @@
+/*
+ * 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) 2001-2002 by NaN Holding BV.
+ * All rights reserved.
+ */
+
+/** \file
+ * \ingroup bke
+ */
+
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "MEM_guardedalloc.h"
+
+#include "DNA_sequence_types.h"
+#include "DNA_scene_types.h"
+#include "DNA_screen_types.h"
+#include "DNA_windowmanager_types.h"
+
+#include "BLI_listbase.h"
+#include "BLI_threads.h"
+
+#include "IMB_imbuf.h"
+#include "IMB_imbuf_types.h"
+
+#include "BKE_animsys.h"
+#include "BKE_library.h"
+#include "BKE_scene.h"
+#include "BKE_main.h"
+#include "BKE_context.h"
+#include "BKE_sequencer.h"
+#include "BKE_layer.h"
+
+#include "DEG_depsgraph.h"
+#include "DEG_depsgraph_build.h"
+#include "DEG_depsgraph_debug.h"
+#include "DEG_depsgraph_query.h"
+
+typedef struct PrefetchJob {
+  struct PrefetchJob *next, *prev;
+
+  struct Main *bmain;
+  struct Scene *scene;
+  struct Scene *scene_eval;
+  struct Depsgraph *depsgraph;
+
+  ThreadMutex prefetch_suspend_mutex;
+  ThreadCondition prefetch_suspend_cond;
+
+  ListBase threads;
+
+  /* context */
+  struct SeqRenderData context;
+  struct SeqRenderData context_cpy;
+  struct ListBase *seqbasep;
+  struct ListBase *seqbasep_cpy;
+
+  /* prefetch area */
+  float cfra;
+  int num_frames_prefetched;
+
+  /* control */
+  bool running;
+  bool waiting;
+  bool stop;
+} PrefetchJob;
+
+static bool seq_prefetch_is_playing(Main *bmain)
+{
+  for (bScreen *screen = bmain->screens.first; screen; screen = screen->id.next) {
+    if (screen->animtimer) {
+      return true;
+    }
+  }
+  return false;
+}
+
+static bool seq_prefetch_is_scrubbing(Main *bmain)
+{
+
+  for (bScreen *screen = bmain->screens.first; screen; screen = screen->id.next) {
+    if (screen->scrubbing) {
+      return true;
+    }
+  }
+  return false;
+}
+
+static PrefetchJob *seq_prefetch_job_get(Scene *scene)
+{
+  if (scene && scene->ed) {
+    return scene->ed->prefetch_job;
+  }
+  return NULL;
+}
+
+static bool seq_prefetch_job_is_running(Scene *scene)
+{
+  PrefetchJob *pfjob = seq_prefetch_job_get(scene);
+
+  if (!pfjob) {
+    return false;
+  }
+
+  return pfjob->running;
+}
+
+static bool seq_prefetch_job_is_waiting(Scene *scene)
+{
+  PrefetchJob *pfjob = seq_prefetch_job_get(scene);
+
+  if (!pfjob) {
+    return false;
+  }
+
+  return pfjob->waiting;
+}
+
+/* for cache context swapping */
+Sequence *BKE_sequencer_prefetch_get_original_sequence(Sequence *seq, Scene *scene)
+{
+  Editing *ed = scene->ed;
+  ListBase *seqbase = &ed->seqbase;
+  Sequence *seq_orig = NULL;
+
+  for (seq_orig = (Sequence *)seqbase->first; seq_orig; seq_orig = seq_orig->next) {
+    if (strcmp(seq->name, seq_orig->name) == 0) {
+      break;
+    }
+  }
+  return seq_orig;
+}
+
+/* for cache context swapping */
+SeqRenderData *BKE_sequencer_prefetch_get_original_context(const SeqRenderData *context)
+{
+  PrefetchJob *pfjob = seq_prefetch_job_get(context->scene);
+
+  return &pfjob->context;
+}
+
+static bool seq_prefetch_is_cache_full(Scene *scene)
+{
+  PrefetchJob *pfjob = seq_prefetch_job_get(scene);
+
+  if (!BKE_sequencer_cache_is_full(pfjob->scene)) {
+    return false;
+  }
+
+  return BKE_sequencer_cache_recycle_item(pfjob->scene) == false;
+}
+
+void BKE_sequencer_prefetch_get_time_range(Scene *scene, int *start, int *end)
+{
+  PrefetchJob *pfjob = seq_prefetch_job_get(scene);
+
+  *start = pfjob->cfra;
+  *end = pfjob->cfra + pfjob->num_frames_prefetched;
+}
+
+static void seq_prefetch_free_depsgraph(PrefetchJob *pfjob)
+{
+  if (pfjob->depsgraph != NULL) {
+    DEG_graph_free(pfjob->depsgraph);
+  }
+  pfjob->depsgraph = NULL;
+  pfjob->scene_eval = NULL;
+}
+
+static void seq_prefetch_update_depsgraph(PrefetchJob *pfjob)
+{
+  DEG_evaluate_on_framechange(
+      pfjob->bmain, pfjob->depsgraph, pfjob->cfra + pfjob->num_frames_prefetched);
+}
+
+static void seq_prefetch_init_depsgraph(PrefetchJob *pfjob)
+{
+  Main *bmain = pfjob->bmain;
+  Scene *scene = pfjob->scene;
+  ViewLayer *view_layer = BKE_view_layer_default_render(scene);
+
+  pfjob->depsgraph = DEG_graph_new(bmain, scene, view_layer, DAG_EVAL_RENDER);
+  DEG_debug_name_set(pfjob->depsgraph, "SEQUENCER PREFETCH");
+
+  /* Make sure there is a correct evaluated scene pointer. */
+  DEG_graph_build_for_render_pipeline(pfjob->depsgraph, pfjob->bmain, scene, view_layer);
+
+  /* Update immediately so we have proper evaluated scene. */
+  seq_prefetch_update_depsgraph(pfjob);
+
+  pfjob->scene_eval = DEG_get_evaluated_scene(pfjob->depsgraph);
+  pfjob->scene_eval->ed->cache_flag = 0;
+}
+
+static void seq_prefetch_update_area(PrefetchJob *pfjob)
+{
+  int cfra = pfjob->scene->r.cfra;
+
+  /* rebase */
+  if (cfra > pfjob->cfra) {
+    int delta = cfra - pfjob->cfra;
+    pfjob->cfra = cfra;
+    pfjob->num_frames_prefetched -= delta;
+
+    if (pfjob->num_frames_prefetched <= 1) {
+      pfjob->num_frames_prefetched = 1;
+    }
+  }
+
+  /* reset */
+  if (cfra < pfjob->cfra) {
+    pfjob->cfra = cfra;
+    pfjob->num_frames_prefetched = 1;
+  }
+}
+
+/* Use also to update scene and context changes */
+void BKE_sequencer_prefetch_stop(Scene *scene)
+{
+  PrefetchJob *pfjob;
+  pfjob = seq_prefetch_job_get(scene);
+
+  if (!pfjob) {
+    return;
+  }
+
+  pfjob->stop = true;
+
+  while (pfjob->running) {
+    BLI_condition_notify_one(&pfjob->prefetch_suspend_cond);
+  }
+}
+
+static void seq_prefetch_update_context(const SeqRenderData *context)
+{
+  PrefetchJob *pfjob;
+  pfjob = seq_prefetch_job_get(context->scene);
+
+  BKE_sequencer_new_render_data(pfjob->bmain,
+                                pfjob->depsgraph,
+                                pfjob->scene_eval,
+                                context->rectx,
+                                context->recty,
+                                context->preview_render_size,
+                                false,
+                                &pfjob->context_cpy);
+  pfjob->context_cpy.is_prefetch_render = true;
+  pfjob->context_cpy.task_id = SEQ_TASK_PREFETCH_RENDER;
+
+  BKE_sequencer_new_render_data(pfjob->bmain,
+                                pfjob->depsgraph,
+                                pfjob->scene,
+                                context->rectx,
+                                context->recty,
+                                context->preview_render_size,
+                                false,
+                                &pfjob->context);
+  pfjob->context.is_prefetch_render = false;
+
+  /* Same ID as prefetch context, because context will be swapped, but we still
+   * want to assign this ID to cache entries created in this thread.
+   * This is to allow "temp cache" work correctly for both threads.
+   */
+  pfjob->context.task_id = SEQ_TASK_PREFETCH_RENDER;
+}
+
+static void seq_prefetch_update_scene(Scene *scene)
+{
+  PrefetchJob *pfjob = seq_prefetch_job_get(scene);
+
+  if (!pfjob) {
+    return;
+  }
+
+  seq_prefetch_free_depsgraph(pfjob);
+  seq_prefetch_init_depsgraph(pfjob);
+}
+
+static void seq_prefetch_resume(Scene *scene)
+{
+  PrefetchJob *pfjob = seq_prefetch_job_get(scene);
+
+  if (pfjob && pfjob->waiting) {
+    BLI_condition_notify_one(&pfjob->prefetch_suspend_cond);
+  }
+}
+
+void BKE_sequencer_prefetch_free(Scene *scene)
+{
+  PrefetchJob *pfjob = seq_prefetch_job_get(scene);
+  if (!pfjob) {
+    return;
+  }
+
+  BKE_sequencer_prefetch_stop(scene);
+
+  BLI_threadpool_remove(&pfjob->threads, pfjob);
+  BLI_threadpool_end(&pfjob->threads);
+  BLI_mutex_end(&pfjob->prefetch_suspend_mutex);
+  BLI_condition_end(&pfjob->prefetch_suspend_cond);
+  seq_prefetch_free_depsgraph(pfjob);
+  MEM_freeN(pfjob);
+  scene->ed->prefetch_job = NULL;
+}
+
+static void *seq_prefetch_frames(void *job)
+{
+  PrefetchJob *pfjob = (PrefetchJob *)job;
+
+  /* set to NULL before return! */
+  pfjob->scene_eval->ed->prefetch_job = pfjob;
+
+  while (pfjob->cfra + pfjob->num_frames_prefetched < pfjob->scene->r.efra) {
+    BKE_animsys_evaluate_all_animation(pfjob->context_cpy.bmain,
+                                       pfjob->context_cpy.depsgraph,
+                                       pfjob->context_cpy.scene,
+                                       pfjob->cfra + pfjob->num_frames_prefetched);
+    seq_prefetch_update_depsgraph(pfjob);
+
+    ImBuf *ibuf = BKE_sequencer_give_ibuf(
+        &pfjob->context_cpy, pfjob->cfra + pfjob->num_frames_prefetched, 0);
+    BKE_sequencer_cache_free_temp_cache(
+        pfjob->scene, pfjob->context.task_id, pfjob->cfra + pfjob->num_frames_prefetched);
+    IMB_freeImBuf(ibuf);
+
+    /* suspend thread */
+    BLI_mutex_lock(&pfjob->prefetch_suspend_mutex);
+    while ((seq_prefetch_is_cache_full(pfjob->scene) || seq_prefetch_is_scrubbing(pfjob->bmain)) &&
+           pfjob->scene->ed->cache_flag & SEQ_CACHE_PREFETCH_ENABLE && !pfjob->stop) {
+      pfjob->waiting = true;
+      BLI_condition_wait(&pfjob->prefetch_suspend_cond, &pfjob->prefetch_suspend_mutex);
+      seq_prefetch_update_area(pfjob);
+    }
+    pfjob->waiting = false;
+    BLI_mutex_unlock(&pfjob->prefetch_suspend_mutex);
+
+    /* Avoid "collision" with main thread, but make sure to fetch at least few frames */
+    if (pfjob->num_frames_prefetched > 5 &&
+        (pfjob->cfra + pfjob->num_frames_prefetched - pfjob->scene->r.cfra) < 2) {
+      break;
+    }
+
+    if (!(pfjob->scene->ed->cache_flag & SEQ_CACHE_PREFETCH_ENABLE) || pfjob->stop) {
+      break;
+    }
+
+    seq_prefetch_update_area(pfjob);
+    pfjob->num_frames_prefetched++;
+  }
+
+  BKE_sequencer_cache_free_temp_cache(
+      pfjob->scene, pfjob->context.task_id, pfjob->cfra + pfjob->num_frames_prefetched);
+  pfjob->running = false;
+  pfjob->scene_eval->ed->prefetch_job = NULL;
+
+  return 0;
+}
+
+PrefetchJob *seq_prefetch_start(const SeqRenderData *context, float cfra)
+{
+  PrefetchJob *pfjob;
+  pfjob = seq_prefetch_job_get(context->scene);
+
+  if (!pfjob) {
+    if (context->scene->ed) {
+      pfjob = (PrefetchJob *)MEM_callocN(sizeof(PrefetchJob), "PrefetchJob");
+      context->scene->ed->prefetch_job = pfjob;
+
+      BLI_threadpool_init(&pfjob->threads, seq_prefetch_frames, 1);
+      BLI_mutex_init(&pfjob->prefetch_suspend_mutex);
+      BLI_condition_init(&pfjob->prefetch_suspend_cond);
+
+      pfjob->bmain = context->bmain;
+
+      pfjob->scene = context->scene;
+      seq_prefetch_init_depsgraph(pfjob);
+    }
+  }
+  seq_prefetch_update_scene(context->scene);
+  seq_prefetch_update_context(context);
+
+  pfjob->cfra = cfra;
+  pfjob->num_frames_prefetched = 1;
+
+  pfjob->waiting = false;
+  pfjob->stop = false;
+  pfjob->running = true;
+
+  if (&pfjob->threads) {
+    BLI_threadpool_remove(&pfjob->threads, pfjob);
+  }
+  BLI_threadpool_insert(&pfjob->threads, pfjob);
+
+  return pfjob;
+}
+
+/* Start or resume prefetching*/
+void BKE_sequencer_prefetch_start(const SeqRenderData *context, float cfra, float cost)
+{
+  Scene *scene = context->scene;
+  Editing *ed = scene->ed;
+  bool has_strips = (bool)ed->seqbasep->first;
+
+  if (!context->is_prefetch_render && !context->is_proxy_render) {
+    bool playing = seq_prefetch_is_playing(context->bmain);
+    bool scrubbing = seq_prefetch_is_scrubbing(context->bmain);
+    bool running = seq_prefetch_job_is_running(scene);
+    seq_prefetch_resume(scene);
+    /* conditions to start:
+     * prefetch enabled, prefetch not running, not scrubbing,
+     * not playing and rendering-expensive footage, cache storage enabled, has strips to render
+     */
+    if ((ed->cache_flag & SEQ_CACHE_PREFETCH_ENABLE) && !running && !scrubbing &&
+        !(playing && cost > 0.9) && ed->cache_flag & SEQ_CACHE_ALL_TYPES && has_strips) {
+
+      seq_prefetch_start(context, cfra);
+    }
+  }
+}
+
+bool BKE_sequencer_prefetch_need_redraw(Main *bmain, Scene *scene)
+{
+  bool playing = seq_prefetch_is_playing(bmain);
+  bool scrubbing = seq_prefetch_is_scrubbing(bmain);
+  bool running = seq_prefetch_job_is_running(scene);
+  bool suspended = seq_prefetch_job_is_waiting(scene);
+
+  /* force redraw, when prefetching and using cache view. */
+  if (running && !playing && !suspended && scene->ed->cache_flag & SEQ_CACHE_VIEW_ENABLE) {
+    return true;
+  }
+  /* Sometimes scrubbing flag is set when not scrubbing. In that case I want to catch "event" of
+   * stopping scrubbing */
+  if (scrubbing) {
+    return true;
+  }
+  return false;
+}
diff --git a/source/blender/blenkernel/intern/sequencer.c b/source/blender/blenkernel/intern/sequencer.c
index 14096335626..2e36982f7d8 100644
--- a/source/blender/blenkernel/intern/sequencer.c
+++ b/source/blender/blenkernel/intern/sequencer.c
@@ -112,6 +112,8 @@ static ImBuf *seq_render_mask(const SeqRenderData *context, Mask *mask, float nr
 static int seq_num_files(Scene *scene, char views_format, const bool is_multiview);
 static void seq_anim_add_suffix(Scene *scene, struct anim *anim, const int view_id);
 
+static ThreadMutex seq_render_mutex = BLI_MUTEX_INITIALIZER;
+
 /* **** XXX ******** */
 #define SELECT 1
 ListBase seqbase_clipboard;
@@ -483,6 +485,7 @@ void BKE_sequencer_editing_free(Scene *scene, const bool do_id_user)
     return;
   }
 
+  BKE_sequencer_prefetch_free(scene);
   BKE_sequencer_cache_destruct(scene);
 
   SEQ_BEGIN (ed, seq) {
@@ -492,7 +495,6 @@ void BKE_sequencer_editing_free(Scene *scene, const bool do_id_user)
   SEQ_END;
 
   BLI_freelistN(&ed->metastack);
-
   MEM_freeN(ed);
 
   scene->ed = NULL;
@@ -635,6 +637,8 @@ void BKE_sequencer_new_render_data(Main *bmain,
   r_context->is_proxy_render = false;
   r_context->view_id = 0;
   r_context->gpu_offscreen = NULL;
+  r_context->task_id = SEQ_TASK_MAIN_RENDER;
+  r_context->is_prefetch_render = false;
 }
 
 /* ************************* iterator ************************** */
@@ -4092,18 +4096,29 @@ ImBuf *BKE_sequencer_give_ibuf(const SeqRenderData *context, float cfra, int cha
     out = BKE_sequencer_cache_get(context, seq_arr[count - 1], cfra, SEQ_CACHE_STORE_FINAL_OUT);
   }
 
-  BKE_sequencer_cache_free_temp_cache(context->scene, 0, cfra);
+  BKE_sequencer_cache_free_temp_cache(context->scene, context->task_id, cfra);
 
   clock_t begin = seq_estimate_render_cost_begin();
   float cost = 0;
 
   if (count && !out) {
+    BLI_mutex_lock(&seq_render_mutex);
     out = seq_render_strip_stack(context, &state, seqbasep, cfra, chanshown);
     cost = seq_estimate_render_cost_end(context->scene, begin);
-    BKE_sequencer_cache_put_if_possible(
-        context, seq_arr[count - 1], cfra, SEQ_CACHE_STORE_FINAL_OUT, out, cost);
+
+    if (context->is_prefetch_render) {
+      BKE_sequencer_cache_put(
+          context, seq_arr[count - 1], cfra, SEQ_CACHE_STORE_FINAL_OUT, out, cost);
+    }
+    else {
+      BKE_sequencer_cache_put_if_possible(
+          context, seq_arr[count - 1], cfra, SEQ_CACHE_STORE_FINAL_OUT, out, cost);
+    }
+    BLI_mutex_unlock(&seq_render_mutex);
   }
 
+  BKE_sequencer_prefetch_start(context, cfra, cost);
+
   return out;
 }
 
@@ -4334,6 +4349,7 @@ static void sequence_invalidate_cache(Scene *scene,
   }
 
   sequence_do_invalidate_dependent(scene, seq, &ed->seqbase);
+  BKE_sequencer_prefetch_stop(scene);
 }
 
 void BKE_sequence_invalidate_cache_raw(Scene *scene, Sequence *seq)
@@ -4419,6 +4435,7 @@ void BKE_sequencer_free_imbuf(Scene *scene, ListBase *seqbase, bool for_render)
   Sequence *seq;
 
   BKE_sequencer_cache_cleanup(scene);
+  BKE_sequencer_prefetch_stop(scene);
 
   for (seq = seqbase->first; seq; seq = seq->next) {
     if (for_render && CFRA >= seq->startdisp && CFRA <= seq->enddisp) {
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 9a4a12729a0..b0ea7ce2aef 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -6758,6 +6758,7 @@ static void direct_link_scene(FileData *fd, Scene *sce)
 
     ed->act_seq = newdataadr(fd, ed->act_seq);
     ed->cache = NULL;
+    ed->prefetch_job = NULL;
 
     /* recursive link sequences, lb will be correctly initialized */
     link_recurs_seq(fd, &ed->seqbase);
diff --git a/source/blender/editors/space_sequencer/sequencer_draw.c b/source/blender/editors/space_sequencer/sequencer_draw.c
index b15acb12d00..bf555e8fe09 100644
--- a/source/blender/editors/space_sequencer/sequencer_draw.c
+++ b/source/blender/editors/space_sequencer/sequencer_draw.c
@@ -72,6 +72,7 @@
 #include "UI_view2d.h"
 
 #include "WM_api.h"
+#include "WM_types.h"
 
 #include "MEM_guardedalloc.h"
 
@@ -1223,6 +1224,14 @@ void sequencer_draw_maskedit(const bContext *C, Scene *scene, ARegion *ar, Space
 }
 #endif
 
+/* Force redraw, when prefetching and using cache view. */
+static void seq_prefetch_wm_notify(const bContext *C, Scene *scene)
+{
+  if (BKE_sequencer_prefetch_need_redraw(CTX_data_main(C), scene)) {
+    WM_event_add_notifier(C, NC_SCENE | ND_SEQUENCER, NULL);
+  }
+}
+
 static void *sequencer_OCIO_transform_ibuf(
     const bContext *C, ImBuf *ibuf, bool *glsl_used, int *format, int *type)
 {
@@ -1612,6 +1621,7 @@ void sequencer_draw_preview(const bContext *C,
   }
 
   UI_view2d_view_restore(C);
+  seq_prefetch_wm_notify(C, scene);
 }
 
 #if 0
@@ -2004,6 +2014,8 @@ void draw_timeline_seq(const bContext *C, ARegion *ar)
   short cfra_flag = 0;
   float col[3];
 
+  seq_prefetch_wm_notify(C, scene);
+
   /* clear and setup matrix */
   UI_GetThemeColor3fv(TH_BACK, col);
   if (ed && ed->metastack.first) {
diff --git a/source/blender/makesdna/DNA_sequence_types.h b/source/blender/makesdna/DNA_sequence_types.h
index 087d30ce312..8d9dc77c49b 100644
--- a/source/blender/makesdna/DNA_sequence_types.h
+++ b/source/blender/makesdna/DNA_sequence_types.h
@@ -270,6 +270,8 @@ typedef struct Editing {
   /* Cache control */
   float recycle_max_cost;
   int cache_flag;
+
+  struct PrefetchJob *prefetch_job;
 } Editing;
 
 /* ************* Effect Variable Structs ********* */
@@ -674,6 +676,8 @@ enum {
   SEQ_CACHE_VIEW_PREPROCESSED = (1 << 7),
   SEQ_CACHE_VIEW_COMPOSITE = (1 << 8),
   SEQ_CACHE_VIEW_FINAL_OUT = (1 << 9),
+
+  SEQ_CACHE_PREFETCH_ENABLE = (1 << 10),
 };
 
 #endif /* __DNA_SEQUENCE_TYPES_H__ */
diff --git a/source/blender/makesrna/intern/rna_sequencer.c b/source/blender/makesrna/intern/rna_sequencer.c
index 1da29217db8..31bc9927026 100644
--- a/source/blender/makesrna/intern/rna_sequencer.c
+++ b/source/blender/makesrna/intern/rna_sequencer.c
@@ -1932,6 +1932,13 @@ static void rna_def_editor(BlenderRNA *brna)
   RNA_def_property_boolean_sdna(prop, NULL, "cache_flag", SEQ_CACHE_STORE_FINAL_OUT);
   RNA_def_property_ui_text(prop, "Cache Final", "Cache final image for each frame");
 
+  prop = RNA_def_property(srna, "use_prefetch", PROP_BOOLEAN, PROP_NONE);
+  RNA_def_property_boolean_sdna(prop, NULL, "cache_flag", SEQ_CACHE_PREFETCH_ENABLE);
+  RNA_def_property_ui_text(prop,
+                           "Prefetch frames",
+                           "Render frames ahead of playhead in background for faster playback");
+  RNA_def_property_update(prop, NC_SCENE | ND_SEQUENCER, NULL);
+
   prop = RNA_def_property(srna, "recycle_max_cost", PROP_FLOAT, PROP_NONE);
   RNA_def_property_range(prop, 0.0f, SEQ_CACHE_COST_MAX);
   RNA_def_property_ui_range(prop, 0.0f, SEQ_CACHE_COST_MAX, 0.1f, 1);