Cycles: Optimize nodes deduplication routines

The idea is to have separate sets per node name in order to speed up the
comparison process. This will use a bit more memory and slow down simple
shaders, but this extra memory is not so much huge and time penalty is
not really measurable (at least from initial tests).

This saves orders of magnitude seconds when de-duplicating 17K nodes and
overall process now takes 0.01sec on my laptop,

1 files changed, 5 insertions, 4 deletions

diff --git a/intern/cycles/render/graph.cpp b/intern/cycles/render/graph.cpp
index 563317a0b10..852aaca5ad5 100644
--- a/intern/cycles/render/graph.cpp
+++ b/intern/cycles/render/graph.cpp
@@ -676,7 +676,8 @@ void ShaderGraph::deduplicate_nodes()
 	 *   already deduplicated.
 	 */
 
-	ShaderNodeSet done, scheduled;
+	ShaderNodeSet scheduled;
+	map<ustring, ShaderNodeSet> done;
 	queue<ShaderNode*> traverse_queue;
 
 	/* Schedule nodes which doesn't have any dependencies. */
@@ -690,7 +691,7 @@ void ShaderGraph::deduplicate_nodes()
 	while(!traverse_queue.empty()) {
 		ShaderNode *node = traverse_queue.front();
 		traverse_queue.pop();
-		done.insert(node);
+		done[node->name].insert(node);
 		/* Schedule the nodes which were depending on the current node. */
 		foreach(ShaderOutput *output, node->outputs) {
 			foreach(ShaderInput *input, output->links) {
@@ -701,14 +702,14 @@ void ShaderGraph::deduplicate_nodes()
 					continue;
 				}
 				/* Schedule node if its inputs are fully done. */
-				if(check_node_inputs_traversed(input->parent, done)) {
+				if(check_node_inputs_traversed(input->parent, done[input->parent->name])) {
 					traverse_queue.push(input->parent);
 					scheduled.insert(input->parent);
 				}
 			}
 		}
 		/* Try to merge this node with another one. */
-		foreach(ShaderNode *other_node, done) {
+		foreach(ShaderNode *other_node, done[node->name]) {
 			if(node == other_node) {
 				/* Don't merge with self. */
 				continue;