Tomato: improved cache management for movie clips

Replace pseudo-LRU approach of determining which buffer
to remove when running out of space allowed for cache
with approach which would remove the frame which is most
far away from newly added frame.

This is still a bit tricky because it's impossible to
distinguish which frame to delete in situation of:

    CCCC...CC
        ^

it's either user wants to extend left segment of cached
frames and buffers from right segment should be removed
or he wants to join this two segments and in that case
buffers from right segment should be removed.

Would need a bit more investigation which situation
is more common in general usecase.

diff --git a/intern/memutil/MEM_CacheLimiter.h b/intern/memutil/MEM_CacheLimiter.h
index 9a36b67aa2f8c11ae1f9bd197edec89f295da6bf..80489a5f5739123f9c46f0c39fd3cf8f9b3f3b9c 100644 (file)
--- a/intern/memutil/MEM_CacheLimiter.h
+++ b/intern/memutil/MEM_CacheLimiter.h
@@ -58,6 +58,8 @@
  */
 
 #include <list>
+#include <queue>
+#include <vector>
 #include "MEM_Allocator.h"
 
 template<class T>
@@ -110,11 +112,18 @@ public:
        void touch() {
                parent->touch(this);
        }
+       void set_priority(int priority) {
+               this->priority = priority;
+       }
+       int get_priority(void) {
+               return this->priority;
+       }
 private:
        friend class MEM_CacheLimiter<T>;
 
        T * data;
        int refcount;
+       int priority;
        typename std::list<MEM_CacheLimiterHandle<T> *,
          MEM_Allocator<MEM_CacheLimiterHandle<T> *> >::iterator me;
        MEM_CacheLimiter<T> * parent;
@@ -123,9 +132,8 @@ private:
 template<class T>
 class MEM_CacheLimiter {
 public:
-       typedef typename std::list<MEM_CacheLimiterHandle<T> *,
-         MEM_Allocator<MEM_CacheLimiterHandle<T> *> >::iterator iterator;
        typedef size_t (*MEM_CacheLimiter_DataSize_Func) (void *data);
+       typedef int (*MEM_CacheLimiter_ItemPriority_Func) (void *item, int default_priority);
        MEM_CacheLimiter(MEM_CacheLimiter_DataSize_Func getDataSize_)
                : getDataSize(getDataSize_) {
        }
@@ -146,6 +154,7 @@ public:
                delete handle;
        }
        void enforce_limits() {
+               MEM_CachePriorityQueue priority_queue;
                size_t max = MEM_CacheLimiter_get_maximum();
                size_t mem_in_use, cur_size;
 
@@ -159,24 +168,29 @@ public:
                        mem_in_use = MEM_get_memory_in_use();
                }
 
-               for (iterator it = queue.begin(); 
-                    it != queue.end() && mem_in_use > max;)
-               {
-                       iterator jt = it;
-                       ++it;
+               if (mem_in_use <= max) {
+                       return;
+               }
+
+               priority_queue = get_priority_queue();
+
+               while (!priority_queue.empty() && mem_in_use > max) {
+                       MEM_CacheElementPtr elem = priority_queue.top();
 
                        if(getDataSize) {
-                               cur_size= getDataSize((*jt)->get()->get_data());
+                               cur_size = getDataSize(elem->get()->get_data());
                        } else {
-                               cur_size= mem_in_use;
+                               cur_size = mem_in_use;
                        }
 
-                       (*jt)->destroy_if_possible();
+                       elem->destroy_if_possible();
 
-                       if(getDataSize) {
-                               mem_in_use-= cur_size;
+                       priority_queue.pop();
+
+                       if (getDataSize) {
+                               mem_in_use -= cur_size;
                        } else {
-                               mem_in_use-= cur_size - MEM_get_memory_in_use();
+                               mem_in_use -= cur_size - MEM_get_memory_in_use();
                        }
                }
        }
@@ -187,7 +201,22 @@ public:
                --it;
                handle->me = it;
        }
+       void set_item_priority_func(MEM_CacheLimiter_ItemPriority_Func item_priority_func) {
+               getItemPriority = item_priority_func;
+       }
 private:
+       typedef MEM_CacheLimiterHandle<T> *MEM_CacheElementPtr;
+       typedef std::list<MEM_CacheElementPtr, MEM_Allocator<MEM_CacheElementPtr> > MEM_CacheQueue;
+       typedef typename MEM_CacheQueue::iterator iterator;
+
+       struct compare_element_priority : public std::binary_function<MEM_CacheElementPtr, MEM_CacheElementPtr, bool> {
+               bool operator()(const MEM_CacheElementPtr left_elem, const MEM_CacheElementPtr right_elem) const {
+                       return left_elem->get_priority() > right_elem->get_priority();
+               }
+       };
+
+       typedef std::priority_queue<MEM_CacheElementPtr, std::vector<MEM_CacheElementPtr>, compare_element_priority > MEM_CachePriorityQueue;
+
        size_t total_size() {
                size_t size = 0;
                for (iterator it = queue.begin(); it != queue.end(); it++) {
@@ -196,9 +225,32 @@ private:
                return size;
        }
 
-       std::list<MEM_CacheLimiterHandle<T>*,
-         MEM_Allocator<MEM_CacheLimiterHandle<T> *> > queue;
+       MEM_CachePriorityQueue get_priority_queue(void) {
+               MEM_CachePriorityQueue priority_queue;
+               iterator it;
+               int i;
+
+               for (it = queue.begin(), i = 0; it != queue.end(); it++, i++) {
+                       MEM_CacheElementPtr elem = *it;
+                       int priority;
+
+                       priority = i;
+
+                       if (getItemPriority) {
+                               priority = getItemPriority(elem->get()->get_data(), priority);
+                       }
+
+                       elem->set_priority(priority);
+
+                       priority_queue.push(elem);
+               }
+
+               return priority_queue;
+       }
+
+       MEM_CacheQueue queue;
        MEM_CacheLimiter_DataSize_Func getDataSize;
+       MEM_CacheLimiter_ItemPriority_Func getItemPriority;
 };
 
 #endif // __MEM_CACHELIMITER_H__

diff --git a/intern/memutil/MEM_CacheLimiterC-Api.h b/intern/memutil/MEM_CacheLimiterC-Api.h
index 4ed692fb55f503c3a428c164a2ac7996b06f60a6..263a67033615cc507b5bd4e2fc625d817969ff1d 100644 (file)
--- a/intern/memutil/MEM_CacheLimiterC-Api.h
+++ b/intern/memutil/MEM_CacheLimiterC-Api.h
@@ -44,6 +44,9 @@ typedef void(*MEM_CacheLimiter_Destruct_Func)(void*);
 /* function used to measure stored data element size */
 typedef size_t(*MEM_CacheLimiter_DataSize_Func) (void*);
 
+/* function used to measure priority of item when freeing memory */
+typedef int(*MEM_CacheLimiter_ItemPriority_Func) (void*, int);
+
 #ifndef __MEM_CACHELIMITER_H__
 extern void MEM_CacheLimiter_set_maximum(size_t m);
 extern int MEM_CacheLimiter_get_maximum(void);
@@ -140,6 +143,9 @@ extern int MEM_CacheLimiter_get_refcount(MEM_CacheLimiterHandleC * handle);
        
 extern void * MEM_CacheLimiter_get(MEM_CacheLimiterHandleC * handle);
 
+extern void MEM_CacheLimiter_ItemPriority_Func_set(MEM_CacheLimiterC *This,
+                                                   MEM_CacheLimiter_ItemPriority_Func item_priority_func);
+
 #ifdef __cplusplus
 }
 #endif

diff --git a/intern/memutil/intern/MEM_CacheLimiterC-Api.cpp b/intern/memutil/intern/MEM_CacheLimiterC-Api.cpp
index cfa6a207e1cf6613172fd8ac7caeaab4c635d4f9..fd0d0cf3161a6f421ce682eca614a28dbd856900 100644 (file)
--- a/intern/memutil/intern/MEM_CacheLimiterC-Api.cpp
+++ b/intern/memutil/intern/MEM_CacheLimiterC-Api.cpp
@@ -197,3 +197,9 @@ void * MEM_CacheLimiter_get(MEM_CacheLimiterHandleC * handle)
 {
        return cast(handle)->get()->get_data();
 }
+
+void MEM_CacheLimiter_ItemPriority_Func_set(MEM_CacheLimiterC *This,
+                                            MEM_CacheLimiter_ItemPriority_Func item_priority_func)
+{
+       cast(This)->get_cache()->set_item_priority_func(item_priority_func);
+}

diff --git a/source/blender/blenkernel/intern/movieclip.c b/source/blender/blenkernel/intern/movieclip.c
index 55b6d7408c104b2e5451b824f3b8647526bb1e53..5a4919da65d331c7a6dae3f74605e0cb1312d7bd 100644 (file)
--- a/source/blender/blenkernel/intern/movieclip.c
+++ b/source/blender/blenkernel/intern/movieclip.c
@@ -338,6 +338,10 @@ typedef struct MovieClipImBufCacheKey {
        short render_flag;
 } MovieClipImBufCacheKey;
 
+typedef struct MovieClipCachePriorityData {
+       int framenr;
+} MovieClipCachePriorityData;
+
 static void moviecache_keydata(void *userkey, int *framenr, int *proxy, int *render_flags)
 {
        MovieClipImBufCacheKey *key = (MovieClipImBufCacheKey *)userkey;
@@ -378,6 +382,32 @@ static int moviecache_hashcmp(const void *av, const void *bv)
        return 0;
 }
 
+void *moviecache_getprioritydata(void *key_v)
+{
+       MovieClipImBufCacheKey *key = (MovieClipImBufCacheKey *) key_v;
+       MovieClipCachePriorityData *priority_data;
+
+       priority_data = MEM_callocN(sizeof(priority_data), "movie cache clip priority data");
+       priority_data->framenr = key->framenr;
+
+       return priority_data;
+}
+
+int moviecache_getitempriority(void *last_userkey_v, void *priority_data_v)
+{
+       MovieClipImBufCacheKey *last_userkey = (MovieClipImBufCacheKey *) last_userkey_v;
+       MovieClipCachePriorityData *priority_data = (MovieClipCachePriorityData *) priority_data_v;
+
+       return -abs(last_userkey->framenr - priority_data->framenr);
+}
+
+void moviecache_prioritydeleter(void *priority_data_v)
+{
+       MovieClipCachePriorityData *priority_data = (MovieClipCachePriorityData *) priority_data_v;
+
+       MEM_freeN(priority_data);
+}
+
 static ImBuf *get_imbuf_cache(MovieClip *clip, MovieClipUser *user, int flag)
 {
        if (clip->cache) {
@@ -405,10 +435,17 @@ static void put_imbuf_cache(MovieClip *clip, MovieClipUser *user, ImBuf *ibuf, i
        MovieClipImBufCacheKey key;
 
        if (!clip->cache) {
+               struct MovieCache *moviecache;
+
                clip->cache = MEM_callocN(sizeof(MovieClipCache), "movieClipCache");
 
-               clip->cache->moviecache = IMB_moviecache_create(sizeof(MovieClipImBufCacheKey), NULL, moviecache_hashhash,
-                                                               moviecache_hashcmp, moviecache_keydata, NULL);
+               moviecache = IMB_moviecache_create(sizeof(MovieClipImBufCacheKey), moviecache_hashhash, moviecache_hashcmp);
+
+               IMB_moviecache_set_getdata_callback(moviecache, moviecache_keydata);
+               IMB_moviecache_set_priority_callback(moviecache, moviecache_getprioritydata, moviecache_getitempriority,
+                                                    moviecache_prioritydeleter);
+
+               clip->cache->moviecache = moviecache;
        }
 
        key.framenr = user->framenr;

diff --git a/source/blender/blenkernel/intern/seqcache.c b/source/blender/blenkernel/intern/seqcache.c
index 6dca3e69f2a827880969c9fd1307c66a6554e982..c169a4a822322ce64f8e412ce178dd22dc35af96 100644 (file)
--- a/source/blender/blenkernel/intern/seqcache.c
+++ b/source/blender/blenkernel/intern/seqcache.c
@@ -98,8 +98,7 @@ void seq_stripelem_cache_cleanup(void)
 {
        if (moviecache) {
                IMB_moviecache_free(moviecache);
-               moviecache = IMB_moviecache_create(sizeof(SeqCacheKey), NULL, seqcache_hashhash,
-                                                  seqcache_hashcmp, NULL, NULL);
+               moviecache = IMB_moviecache_create(sizeof(SeqCacheKey), seqcache_hashhash, seqcache_hashcmp);
        }
 }
 
@@ -133,8 +132,7 @@ void seq_stripelem_cache_put(
        }
 
        if (!moviecache) {
-               moviecache = IMB_moviecache_create(sizeof(SeqCacheKey), NULL, seqcache_hashhash,
-                                                  seqcache_hashcmp, NULL, NULL);
+               moviecache = IMB_moviecache_create(sizeof(SeqCacheKey), seqcache_hashhash, seqcache_hashcmp);
        }
 
        key.seq = seq;

diff --git a/source/blender/imbuf/IMB_moviecache.h b/source/blender/imbuf/IMB_moviecache.h
index 663d662785dcd0fe43c536b4cf5fe84a0795422b..8beb7e0f7e2b37433924bc5c1453155daf367a19 100644 (file)
--- a/source/blender/imbuf/IMB_moviecache.h
+++ b/source/blender/imbuf/IMB_moviecache.h
@@ -43,16 +43,24 @@ struct ImBuf;
 struct MovieCache;
 
 typedef void (*MovieCacheGetKeyDataFP) (void *userkey, int *framenr, int *proxy, int *render_flags);
-typedef void (*MoviKeyDeleterFP) (void *userkey);
+typedef void (*MovieCacheKeyDeleterFP) (void *userkey);
 typedef int (*MovieCacheCheckKeyUnusedFP) (void *userkey);
 
+typedef void  *(*MovieCacheGetPriorityDataFP) (void *userkey);
+typedef int    (*MovieCacheGetItemPriorityFP) (void *last_userkey, void *priority_data);
+typedef void   (*MovieCachePriorityDeleterFP) (void *priority_data);
+
 void IMB_moviecache_init(void);
 void IMB_moviecache_destruct(void);
 
-struct MovieCache *IMB_moviecache_create(int keysize, MoviKeyDeleterFP keydeleterfp,
-                                         GHashHashFP hashfp, GHashCmpFP cmpfp,
-                                         MovieCacheGetKeyDataFP getdatafp,
-                                         MovieCacheCheckKeyUnusedFP checkkeyunusedfp);
+struct MovieCache *IMB_moviecache_create(int keysize, GHashHashFP hashfp, GHashCmpFP cmpfp);
+void IMB_moviecache_set_key_deleter_callback(struct MovieCache *cache, MovieCacheKeyDeleterFP keydeleterfp);
+void IMB_moviecache_set_getdata_callback(struct MovieCache *cache, MovieCacheGetKeyDataFP getdatafp);
+void IMB_moviecache_set_check_unused_callback(struct MovieCache *cache, MovieCacheCheckKeyUnusedFP checkkeyunusedfp);
+void IMB_moviecache_set_priority_callback(struct MovieCache *cache, MovieCacheGetPriorityDataFP getprioritydatafp,
+                                          MovieCacheGetItemPriorityFP getitempriorityfp,
+                                          MovieCachePriorityDeleterFP prioritydeleterfp);
+
 void IMB_moviecache_put(struct MovieCache *cache, void *userkey, struct ImBuf *ibuf);
 struct ImBuf* IMB_moviecache_get(struct MovieCache *cache, void *userkey);
 void IMB_moviecache_free(struct MovieCache *cache);

diff --git a/source/blender/imbuf/intern/colormanagement.c b/source/blender/imbuf/intern/colormanagement.c
index 071bba8eea2f0ee05a8d3e2691e7fa73f3b60d2c..51f0e3b250e92ba0117e4e66fdd3dc938d60e80b 100644 (file)
--- a/source/blender/imbuf/intern/colormanagement.c
+++ b/source/blender/imbuf/intern/colormanagement.c
@@ -210,9 +210,10 @@ static void colormanage_keydeleter(void *key_v)
 
 static void colormanage_cache_init(void)
 {
-       colormanage_cache = IMB_moviecache_create(sizeof(ColormanageCacheKey), colormanage_keydeleter,
-                                                 colormanage_hashhash, colormanage_hashcmp,
-                                                 NULL, colormanage_checkkeyunused);
+       colormanage_cache = IMB_moviecache_create(sizeof(ColormanageCacheKey), colormanage_hashhash, colormanage_hashcmp);
+
+       IMB_moviecache_set_key_deleter_callback(colormanage_cache, colormanage_keydeleter);
+       IMB_moviecache_set_check_unused_callback(colormanage_cache, colormanage_checkkeyunused);
 }
 
 static void colormanage_cache_exit(void)

diff --git a/source/blender/imbuf/intern/moviecache.c b/source/blender/imbuf/intern/moviecache.c
index 281b5df2e88c24894374c9d8544c0b70c42e5a8d..04d563dd0ea5cb21a4c62b074ea761603537572e 100644 (file)
--- a/source/blender/imbuf/intern/moviecache.c
+++ b/source/blender/imbuf/intern/moviecache.c
@@ -48,18 +48,23 @@ static MEM_CacheLimiterC *limitor = NULL;
 
 typedef struct MovieCache {
        GHash *hash;
-       MoviKeyDeleterFP keydeleterfp;
+       MovieCacheKeyDeleterFP keydeleterfp;
        GHashHashFP hashfp;
        GHashCmpFP cmpfp;
        MovieCacheGetKeyDataFP getdatafp;
        MovieCacheCheckKeyUnusedFP checkkeyunusedfp;
 
+       MovieCacheGetPriorityDataFP getprioritydatafp;
+       MovieCacheGetItemPriorityFP getitempriorityfp;
+       MovieCachePriorityDeleterFP prioritydeleterfp;
+
        struct BLI_mempool *keys_pool;
        struct BLI_mempool *items_pool;
        struct BLI_mempool *userkeys_pool;
 
        int keysize;
-       unsigned long curtime;
+
+       void *last_userkey;
 
        int totseg, *points, proxy, render_flags;  /* for visual statistics optimization */
        int pad;
@@ -74,7 +79,7 @@ typedef struct MovieCacheItem {
        MovieCache *cache_owner;
        ImBuf *ibuf;
        MEM_CacheLimiterHandleC *c_handle;
-       unsigned long last_access;
+       void *priority_data;
 } MovieCacheItem;
 
 static unsigned int moviecache_hashhash(const void *keyv)
@@ -108,12 +113,17 @@ static void moviecache_keyfree(void *val)
 static void moviecache_valfree(void *val)
 {
        MovieCacheItem *item = (MovieCacheItem *)val;
+       MovieCache *cache = item->cache_owner;
 
        if (item->ibuf) {
                MEM_CacheLimiter_unmanage(item->c_handle);
                IMB_freeImBuf(item->ibuf);
        }
 
+       if (item->priority_data && cache->prioritydeleterfp) {
+               cache->prioritydeleterfp(item->priority_data);
+       }
+
        BLI_mempool_free(item->cache_owner->items_pool, item);
 }
 
@@ -201,9 +211,22 @@ static size_t get_item_size(void *p)
        return size;
 }
 
+static int get_item_priority(void *item_v, int default_priority)
+{
+       MovieCacheItem *item = (MovieCacheItem *) item_v;
+       MovieCache *cache = item->cache_owner;
+
+       if (!cache->getitempriorityfp)
+               return default_priority;
+
+       return cache->getitempriorityfp(cache->last_userkey, item->priority_data);
+}
+
 void IMB_moviecache_init(void)
 {
        limitor = new_MEM_CacheLimiter(IMB_moviecache_destructor, get_item_size);
+
+       MEM_CacheLimiter_ItemPriority_Func_set(limitor, get_item_priority);
 }
 
 void IMB_moviecache_destruct(void)
@@ -212,30 +235,49 @@ void IMB_moviecache_destruct(void)
                delete_MEM_CacheLimiter(limitor);
 }
 
-MovieCache *IMB_moviecache_create(int keysize, MoviKeyDeleterFP keydeleterfp,
-                                  GHashHashFP hashfp, GHashCmpFP cmpfp,
-                                  MovieCacheGetKeyDataFP getdatafp,
-                                  MovieCacheCheckKeyUnusedFP checkkeyunusedfp)
+MovieCache *IMB_moviecache_create(int keysize, GHashHashFP hashfp, GHashCmpFP cmpfp)
 {
        MovieCache *cache;
 
        cache = MEM_callocN(sizeof(MovieCache), "MovieCache");
+
        cache->keys_pool = BLI_mempool_create(sizeof(MovieCacheKey), 64, 64, 0);
        cache->items_pool = BLI_mempool_create(sizeof(MovieCacheItem), 64, 64, 0);
        cache->userkeys_pool = BLI_mempool_create(keysize, 64, 64, 0);
        cache->hash = BLI_ghash_new(moviecache_hashhash, moviecache_hashcmp, "MovieClip ImBuf cache hash");
 
-       cache->keydeleterfp = keydeleterfp;
        cache->keysize = keysize;
        cache->hashfp = hashfp;
        cache->cmpfp = cmpfp;
-       cache->getdatafp = getdatafp;
-       cache->checkkeyunusedfp = checkkeyunusedfp;
        cache->proxy = -1;
 
        return cache;
 }
 
+void IMB_moviecache_set_key_deleter_callback(MovieCache *cache, MovieCacheKeyDeleterFP keydeleterfp)
+{
+       cache->keydeleterfp = keydeleterfp;
+}
+
+void IMB_moviecache_set_getdata_callback(MovieCache *cache, MovieCacheGetKeyDataFP getdatafp)
+{
+       cache->getdatafp = getdatafp;
+}
+
+void IMB_moviecache_set_check_unused_callback(MovieCache *cache, MovieCacheCheckKeyUnusedFP checkkeyunusedfp)
+{
+       cache->checkkeyunusedfp = checkkeyunusedfp;
+}
+
+void IMB_moviecache_set_priority_callback(struct MovieCache *cache, MovieCacheGetPriorityDataFP getprioritydatafp,
+                                          MovieCacheGetItemPriorityFP getitempriorityfp,
+                                          MovieCachePriorityDeleterFP prioritydeleterfp)
+{
+       cache->getprioritydatafp = getprioritydatafp;
+       cache->getitempriorityfp = getitempriorityfp;
+       cache->prioritydeleterfp = prioritydeleterfp;
+}
+
 void IMB_moviecache_put(MovieCache *cache, void *userkey, ImBuf *ibuf)
 {
        MovieCacheKey *key;
@@ -254,18 +296,26 @@ void IMB_moviecache_put(MovieCache *cache, void *userkey, ImBuf *ibuf)
        item = BLI_mempool_alloc(cache->items_pool);
        item->ibuf = ibuf;
        item->cache_owner = cache;
-       item->last_access = cache->curtime++;
        item->c_handle = NULL;
+       item->priority_data = NULL;
+
+       if (cache->getprioritydatafp) {
+               item->priority_data = cache->getprioritydatafp(userkey);
+       }
 
        BLI_ghash_remove(cache->hash, key, moviecache_keyfree, moviecache_valfree);
        BLI_ghash_insert(cache->hash, key, item);
 
        item->c_handle = MEM_CacheLimiter_insert(limitor, item);
 
+       cache->last_userkey = userkey;
+
        MEM_CacheLimiter_ref(item->c_handle);
        MEM_CacheLimiter_enforce_limits(limitor);
        MEM_CacheLimiter_unref(item->c_handle);
 
+       cache->last_userkey = NULL;
+
        /* cache limiter can't remove unused keys which points to destoryed values */
        check_unused_keys(cache);
 
@@ -285,8 +335,6 @@ ImBuf *IMB_moviecache_get(MovieCache *cache, void *userkey)
        item = (MovieCacheItem *)BLI_ghash_lookup(cache->hash, &key);
 
        if (item) {
-               item->last_access = cache->curtime++;
-
                if (item->ibuf) {
                        MEM_CacheLimiter_touch(item->c_handle);
                        IMB_refImBuf(item->ibuf);