[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