Depsgrpah: Use deque for the flush queue
authorSergey Sharybin <sergey.vfx@gmail.com>
Thu, 25 Aug 2016 13:12:21 +0000 (15:12 +0200)
committerSergey Sharybin <sergey.vfx@gmail.com>
Thu, 25 Aug 2016 13:13:36 +0000 (15:13 +0200)
The idea of the change is to avoid queue growing too long
and handle all the operations as quick as possible.

Gives about 3% speedup on one of the barber shots here.

source/blender/depsgraph/intern/eval/deg_eval_flush.cc

index f9e1504b3ce04db3757bf78b26dc3e54bb61e66e..98d8c60f012bcfa7baca4616cacb7e36957ac566 100644 (file)
@@ -33,7 +33,7 @@
 #include "intern/eval/deg_eval_flush.h"
 
 // TODO(sergey): Use some sort of wrapper.
-#include <queue>
+#include <deque>
 
 extern "C" {
 #include "DNA_object_types.h"
@@ -71,7 +71,7 @@ void lib_id_recalc_data_tag(Main *bmain, ID *id)
 
 }  /* namespace */
 
-typedef std::queue<OperationDepsNode *> FlushQueue;
+typedef std::deque<OperationDepsNode *> FlushQueue;
 
 static void flush_init_func(void *data_v, int i)
 {
@@ -122,14 +122,14 @@ void deg_graph_flush_updates(Main *bmain, Depsgraph *graph)
         */
        GSET_FOREACH_BEGIN(OperationDepsNode *, node, graph->entry_tags)
        {
-               queue.push(node);
+               queue.push_back(node);
                node->scheduled = true;
        }
        GSET_FOREACH_END();
 
        while (!queue.empty()) {
                OperationDepsNode *node = queue.front();
-               queue.pop();
+               queue.pop_front();
 
                for (;;) {
                        node->flag |= DEPSOP_FLAG_NEEDS_UPDATE;
@@ -154,7 +154,7 @@ void deg_graph_flush_updates(Main *bmain, Depsgraph *graph)
                                foreach (DepsRelation *rel, node->outlinks) {
                                        OperationDepsNode *to_node = (OperationDepsNode *)rel->to;
                                        if (to_node->scheduled == false) {
-                                               queue.push(to_node);
+                                               queue.push_front(to_node);
                                                to_node->scheduled = true;
                                        }
                                }