[Bf-blender-cvs] [eb2cfc3] master: Depsgrpah: Use deque for the flush queue

[Sergey Sharybin]

Commit: eb2cfc3a25513a7234e407978c7db984d7646351
Author: Sergey Sharybin
Date:   Thu Aug 25 15:12:21 2016 +0200
Branches: master
https://developer.blender.org/rBeb2cfc3a25513a7234e407978c7db984d7646351

Depsgrpah: Use deque for the flush queue

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.

===================================================================

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

===================================================================

diff --git a/source/blender/depsgraph/intern/eval/deg_eval_flush.cc b/source/blender/depsgraph/intern/eval/deg_eval_flush.cc
index f9e1504..98d8c60 100644
--- a/source/blender/depsgraph/intern/eval/deg_eval_flush.cc
+++ b/source/blender/depsgraph/intern/eval/deg_eval_flush.cc
@@ -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;
 					}
 				}