[Bf-blender-cvs] [5697fd53f23] functions: implement initial Remove Duplicates optimization

Jacques Lucke noreply at git.blender.org
Sat Jan 18 20:18:09 CET 2020


Commit: 5697fd53f236c1dce8474c5bcbfa03287dcbaf95
Author: Jacques Lucke
Date:   Sat Jan 18 20:03:10 2020 +0100
Branches: functions
https://developer.blender.org/rB5697fd53f236c1dce8474c5bcbfa03287dcbaf95

implement initial Remove Duplicates optimization

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

M	source/blender/functions/FN_multi_function_network_optimization.h
M	source/blender/functions/intern/multi_function_network_optimization.cc
M	source/blender/functions/intern/node_tree_multi_function_network/generate.cc

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

diff --git a/source/blender/functions/FN_multi_function_network_optimization.h b/source/blender/functions/FN_multi_function_network_optimization.h
index 0e6d5eb2fc4..6c6ef713771 100644
--- a/source/blender/functions/FN_multi_function_network_optimization.h
+++ b/source/blender/functions/FN_multi_function_network_optimization.h
@@ -11,6 +11,7 @@ using BLI::ResourceCollector;
 
 void optimize_network__constant_folding(MFNetworkBuilder &network, ResourceCollector &resources);
 void optimize_network__remove_unused_nodes(MFNetworkBuilder &network_builder);
+void optimize_network__remove_duplicates(MFNetworkBuilder &network_builder);
 
 }  // namespace FN
 
diff --git a/source/blender/functions/intern/multi_function_network_optimization.cc b/source/blender/functions/intern/multi_function_network_optimization.cc
index c7a97f8eea8..66400ad6b85 100644
--- a/source/blender/functions/intern/multi_function_network_optimization.cc
+++ b/source/blender/functions/intern/multi_function_network_optimization.cc
@@ -3,11 +3,104 @@
 #include "FN_multi_functions.h"
 
 #include "BLI_stack_cxx.h"
+#include "BLI_multi_map.h"
+#include "BLI_rand.h"
 
 namespace FN {
 
+using BLI::MultiMap;
 using BLI::Stack;
 
+void optimize_network__remove_duplicates(MFNetworkBuilder &network_builder)
+{
+  Array<Optional<uint32_t>> hash_by_output_socket(network_builder.socket_id_amount());
+  Array<bool> node_outputs_are_hashed(network_builder.node_id_amount(), false);
+
+  RNG *rng = BLI_rng_new(0);
+
+  for (MFBuilderDummyNode *node : network_builder.dummy_nodes()) {
+    for (MFBuilderOutputSocket *output_socket : node->outputs()) {
+      uint32_t output_hash = BLI_rng_get_uint(rng);
+      hash_by_output_socket[output_socket->id()].set_new(output_hash);
+    }
+    node_outputs_are_hashed[node->id()] = true;
+  }
+
+  Stack<MFBuilderFunctionNode *> nodes_to_check = network_builder.function_nodes();
+  while (!nodes_to_check.is_empty()) {
+    MFBuilderFunctionNode &node = *nodes_to_check.peek();
+    if (node_outputs_are_hashed[node.id()]) {
+      nodes_to_check.pop();
+      continue;
+    }
+
+    bool all_dependencies_ready = true;
+    node.foreach_origin_node([&](MFBuilderNode &origin_node) {
+      if (!node_outputs_are_hashed[origin_node.id()]) {
+        all_dependencies_ready = false;
+        nodes_to_check.push(&origin_node.as_function());
+      }
+    });
+
+    if (!all_dependencies_ready) {
+      continue;
+    }
+
+    uint32_t combined_inputs_hash = 827823743;
+    for (MFBuilderInputSocket *input_socket : node.inputs()) {
+      MFBuilderOutputSocket *origin = input_socket->origin();
+      uint32_t input_hash;
+      if (origin == nullptr) {
+        input_hash = BLI_rng_get_uint(rng);
+      }
+      else {
+        input_hash = *hash_by_output_socket[origin->id()];
+      }
+
+      combined_inputs_hash = combined_inputs_hash * 456123 + input_hash;
+    }
+
+    Optional<uint32_t> maybe_operation_hash = node.function().operation_hash();
+    uint32_t operation_hash = (maybe_operation_hash.has_value()) ? *maybe_operation_hash :
+                                                                   BLI_rng_get_uint(rng);
+    uint32_t node_hash = combined_inputs_hash * 462347 + operation_hash;
+
+    for (MFBuilderOutputSocket *output_socket : node.outputs()) {
+      uint32_t output_hash = node_hash * (45234 + 567243 * output_socket->index());
+      hash_by_output_socket[output_socket->id()].set_new(output_hash);
+    }
+
+    nodes_to_check.pop();
+    node_outputs_are_hashed[node.id()] = true;
+  }
+
+  MultiMap<uint32_t, MFBuilderOutputSocket *> outputs_by_hash;
+  for (uint id : hash_by_output_socket.index_range()) {
+    Optional<uint32_t> maybe_hash = hash_by_output_socket[id];
+    if (maybe_hash.has_value()) {
+      uint32_t hash = *maybe_hash;
+      MFBuilderOutputSocket &socket = network_builder.socket_by_id(id).as_output();
+      outputs_by_hash.add(hash, &socket);
+    }
+  }
+
+  outputs_by_hash.foreach_item(
+      [&](uint32_t UNUSED(hash), ArrayRef<MFBuilderOutputSocket *> outputs_with_hash) {
+        if (outputs_with_hash.size() <= 1) {
+          return;
+        }
+
+        MFBuilderOutputSocket &deduplicated_output = *outputs_with_hash[0];
+        for (MFBuilderOutputSocket *socket : outputs_with_hash.drop_front(1)) {
+          for (MFBuilderInputSocket *target : socket->targets()) {
+            network_builder.relink_origin(deduplicated_output, *target);
+          }
+        }
+      });
+
+  BLI_rng_free(rng);
+}
+
 void optimize_network__remove_unused_nodes(MFNetworkBuilder &network_builder)
 {
   ArrayRef<MFBuilderNode *> dummy_nodes = network_builder.dummy_nodes();
@@ -132,8 +225,7 @@ void optimize_network__constant_folding(MFNetworkBuilder &network_builder,
         *dummy_nodes_to_compute[param_index]->input(0).origin();
 
     for (MFBuilderInputSocket *target : original_socket.targets()) {
-      network_builder.remove_link(original_socket, *target);
-      network_builder.add_link(folded_node.output(0), *target);
+      network_builder.relink_origin(folded_node.output(0), *target);
     }
   }
 
diff --git a/source/blender/functions/intern/node_tree_multi_function_network/generate.cc b/source/blender/functions/intern/node_tree_multi_function_network/generate.cc
index 6baae08a65b..f60bc77ee85 100644
--- a/source/blender/functions/intern/node_tree_multi_function_network/generate.cc
+++ b/source/blender/functions/intern/node_tree_multi_function_network/generate.cc
@@ -271,6 +271,7 @@ std::unique_ptr<FunctionTreeMFNetwork> generate_node_tree_multi_function_network
   }
 
   optimize_network__constant_folding(network_builder, resources);
+  optimize_network__remove_duplicates(network_builder);
   optimize_network__remove_unused_nodes(network_builder);
   network_builder.to_dot__clipboard();
   auto function_tree_network = build(function_tree, network_builder, dummy_socket_mapping);



More information about the Bf-blender-cvs mailing list