diff options
author | Manuel Castilla <manzanillawork@gmail.com> | 2021-09-04 17:59:02 +0300 |
---|---|---|
committer | Manuel Castilla <manzanillawork@gmail.com> | 2021-09-04 18:09:59 +0300 |
commit | b225a7c4705104245c2267101adec2f2ee2fe20a (patch) | |
tree | a147d04b821a23e143dd63abc42b1eb514592aed | |
parent | d84c79a218e63d0d752d918e2c1cbcc2f90fd35e (diff) |
Compositor: Merge equal operations
Some operations can take a lot of time to execute and
any duplication should be avoided.
This patch implements a compile step that detects
operations with the same type, inputs and parameters that
produce the same result and merge them. Now operations
can generate a hash that represents their output result. They only
need to implement `hash_output_params` and hash any parameter
that affects the output result.
Reviewed By: jbakker
Differential Revision: https://developer.blender.org/D12341
9 files changed, 373 insertions, 11 deletions
diff --git a/source/blender/compositor/CMakeLists.txt b/source/blender/compositor/CMakeLists.txt index 8ddcf11602a..4f78d82f486 100644 --- a/source/blender/compositor/CMakeLists.txt +++ b/source/blender/compositor/CMakeLists.txt @@ -647,6 +647,7 @@ if(WITH_GTESTS) tests/COM_BufferArea_test.cc tests/COM_BufferRange_test.cc tests/COM_BuffersIterator_test.cc + tests/COM_NodeOperation_test.cc ) set(TEST_INC ) diff --git a/source/blender/compositor/intern/COM_Debug.cc b/source/blender/compositor/intern/COM_Debug.cc index a0333cf96cf..007085ee528 100644 --- a/source/blender/compositor/intern/COM_Debug.cc +++ b/source/blender/compositor/intern/COM_Debug.cc @@ -425,7 +425,8 @@ bool DebugInfo::graphviz_system(const ExecutionSystem *system, char *str, int ma } const bool has_execution_groups = system->getContext().get_execution_model() == - eExecutionModel::Tiled; + eExecutionModel::Tiled && + system->m_groups.size() > 0; len += graphviz_legend(str + len, maxlen > len ? maxlen - len : 0, has_execution_groups); len += snprintf(str + len, maxlen > len ? maxlen - len : 0, "}\r\n"); diff --git a/source/blender/compositor/intern/COM_NodeOperation.cc b/source/blender/compositor/intern/COM_NodeOperation.cc index 1b87cdf72fb..a87485fd51c 100644 --- a/source/blender/compositor/intern/COM_NodeOperation.cc +++ b/source/blender/compositor/intern/COM_NodeOperation.cc @@ -41,6 +41,49 @@ NodeOperation::NodeOperation() this->m_btree = nullptr; } +/** + * Generate a hash that identifies the operation result in the current execution. + * Requires `hash_output_params` to be implemented, otherwise `std::nullopt` is returned. + * If the operation parameters or its linked inputs change, the hash must be re-generated. + */ +std::optional<NodeOperationHash> NodeOperation::generate_hash() +{ + params_hash_ = get_default_hash_2(m_width, m_height); + + /* Hash subclasses params. */ + is_hash_output_params_implemented_ = true; + hash_output_params(); + if (!is_hash_output_params_implemented_) { + return std::nullopt; + } + + hash_param(getOutputSocket()->getDataType()); + NodeOperationHash hash; + hash.params_hash_ = params_hash_; + + hash.parents_hash_ = 0; + for (NodeOperationInput &socket : m_inputs) { + NodeOperation &input = socket.getLink()->getOperation(); + const bool is_constant = input.get_flags().is_constant_operation; + combine_hashes(hash.parents_hash_, get_default_hash(is_constant)); + if (is_constant) { + const float *elem = ((ConstantOperation *)&input)->get_constant_elem(); + const int num_channels = COM_data_type_num_channels(socket.getDataType()); + for (const int i : IndexRange(num_channels)) { + combine_hashes(hash.parents_hash_, get_default_hash(elem[i])); + } + } + else { + combine_hashes(hash.parents_hash_, get_default_hash(input.get_id())); + } + } + + hash.type_hash_ = typeid(*this).hash_code(); + hash.operation_ = this; + + return hash; +} + NodeOperationOutput *NodeOperation::getOutputSocket(unsigned int index) { return &m_outputs[index]; diff --git a/source/blender/compositor/intern/COM_NodeOperation.h b/source/blender/compositor/intern/COM_NodeOperation.h index b402dc7f174..ef7cf319222 100644 --- a/source/blender/compositor/intern/COM_NodeOperation.h +++ b/source/blender/compositor/intern/COM_NodeOperation.h @@ -22,6 +22,8 @@ #include <sstream> #include <string> +#include "BLI_ghash.h" +#include "BLI_hash.hh" #include "BLI_math_color.h" #include "BLI_math_vector.h" #include "BLI_threads.h" @@ -269,6 +271,42 @@ struct NodeOperationFlags { } }; +/** Hash that identifies an operation output result in the current execution. */ +struct NodeOperationHash { + private: + NodeOperation *operation_; + size_t type_hash_; + size_t parents_hash_; + size_t params_hash_; + + friend class NodeOperation; + + public: + NodeOperation *get_operation() const + { + return operation_; + } + + bool operator==(const NodeOperationHash &other) const + { + return type_hash_ == other.type_hash_ && parents_hash_ == other.parents_hash_ && + params_hash_ == other.params_hash_; + } + + bool operator!=(const NodeOperationHash &other) const + { + return !(*this == other); + } + + bool operator<(const NodeOperationHash &other) const + { + return type_hash_ < other.type_hash_ || + (type_hash_ == other.type_hash_ && parents_hash_ < other.parents_hash_) || + (type_hash_ == other.type_hash_ && parents_hash_ == other.parents_hash_ && + params_hash_ < other.params_hash_); + } +}; + /** * \brief NodeOperation contains calculation logic * @@ -282,6 +320,9 @@ class NodeOperation { Vector<NodeOperationInput> m_inputs; Vector<NodeOperationOutput> m_outputs; + size_t params_hash_; + bool is_hash_output_params_implemented_; + /** * \brief the index of the input socket that will be used to determine the resolution */ @@ -363,6 +404,8 @@ class NodeOperation { return flags; } + std::optional<NodeOperationHash> generate_hash(); + unsigned int getNumberOfInputSockets() const { return m_inputs.size(); @@ -624,6 +667,33 @@ class NodeOperation { protected: NodeOperation(); + /* Overridden by subclasses to allow merging equal operations on compiling. Implementations must + * hash any subclass parameter that affects the output result using `hash_params` methods. */ + virtual void hash_output_params() + { + is_hash_output_params_implemented_ = false; + } + + static void combine_hashes(size_t &combined, size_t other) + { + combined = BLI_ghashutil_combine_hash(combined, other); + } + + template<typename T> void hash_param(T param) + { + combine_hashes(params_hash_, get_default_hash(param)); + } + + template<typename T1, typename T2> void hash_params(T1 param1, T2 param2) + { + combine_hashes(params_hash_, get_default_hash_2(param1, param2)); + } + + template<typename T1, typename T2, typename T3> void hash_params(T1 param1, T2 param2, T3 param3) + { + combine_hashes(params_hash_, get_default_hash_3(param1, param2, param3)); + } + void addInputSocket(DataType datatype, ResizeMode resize_mode = ResizeMode::Center); void addOutputSocket(DataType datatype); diff --git a/source/blender/compositor/intern/COM_NodeOperationBuilder.cc b/source/blender/compositor/intern/COM_NodeOperationBuilder.cc index 10a91bbcd3e..5e18b5396b1 100644 --- a/source/blender/compositor/intern/COM_NodeOperationBuilder.cc +++ b/source/blender/compositor/intern/COM_NodeOperationBuilder.cc @@ -101,16 +101,16 @@ void NodeOperationBuilder::convertToOperations(ExecutionSystem *system) add_datatype_conversions(); if (m_context->get_execution_model() == eExecutionModel::FullFrame) { - /* Copy operations to system. Needed for graphviz. */ - system->set_operations(m_operations, {}); - - DebugInfo::graphviz(system, "compositor_prior_folding"); + save_graphviz("compositor_prior_folding"); ConstantFolder folder(*this); folder.fold_operations(); } determineResolutions(); + save_graphviz("compositor_prior_merging"); + merge_equal_operations(); + if (m_context->get_execution_model() == eExecutionModel::Tiled) { /* surround complex ops with read/write buffer */ add_complex_operation_buffers(); @@ -149,22 +149,28 @@ void NodeOperationBuilder::replace_operation_with_constant(NodeOperation *operat ConstantOperation *constant_operation) { BLI_assert(constant_operation->getNumberOfInputSockets() == 0); + unlink_inputs_and_relink_outputs(operation, constant_operation); + addOperation(constant_operation); +} + +void NodeOperationBuilder::unlink_inputs_and_relink_outputs(NodeOperation *unlinked_op, + NodeOperation *linked_op) +{ int i = 0; while (i < m_links.size()) { Link &link = m_links[i]; - if (&link.to()->getOperation() == operation) { + if (&link.to()->getOperation() == unlinked_op) { link.to()->setLink(nullptr); m_links.remove(i); continue; } - if (&link.from()->getOperation() == operation) { - link.to()->setLink(constant_operation->getOutputSocket()); - m_links[i] = Link(constant_operation->getOutputSocket(), link.to()); + if (&link.from()->getOperation() == unlinked_op) { + link.to()->setLink(linked_op->getOutputSocket()); + m_links[i] = Link(linked_op->getOutputSocket(), link.to()); } i++; } - addOperation(constant_operation); } void NodeOperationBuilder::mapInputSocket(NodeInput *node_socket, @@ -456,6 +462,48 @@ void NodeOperationBuilder::determineResolutions() } } +static Vector<NodeOperationHash> generate_hashes(Span<NodeOperation *> operations) +{ + Vector<NodeOperationHash> hashes; + for (NodeOperation *op : operations) { + std::optional<NodeOperationHash> hash = op->generate_hash(); + if (hash) { + hashes.append(std::move(*hash)); + } + } + return hashes; +} + +/** Merge operations with same type, inputs and parameters that produce the same result. */ +void NodeOperationBuilder::merge_equal_operations() +{ + bool any_merged = true; + while (any_merged) { + /* Re-generate hashes with any change. */ + Vector<NodeOperationHash> hashes = generate_hashes(m_operations); + + /* Make hashes be consecutive when they are equal. */ + std::sort(hashes.begin(), hashes.end()); + + any_merged = false; + const NodeOperationHash *prev_hash = nullptr; + for (const NodeOperationHash &hash : hashes) { + if (prev_hash && *prev_hash == hash) { + merge_equal_operations(prev_hash->get_operation(), hash.get_operation()); + any_merged = true; + } + prev_hash = &hash; + } + } +} + +void NodeOperationBuilder::merge_equal_operations(NodeOperation *from, NodeOperation *into) +{ + unlink_inputs_and_relink_outputs(from, into); + m_operations.remove_first_occurrence_and_reorder(from); + delete from; +} + Vector<NodeOperationInput *> NodeOperationBuilder::cache_output_links( NodeOperationOutput *output) const { @@ -728,6 +776,14 @@ void NodeOperationBuilder::group_operations() } } +void NodeOperationBuilder::save_graphviz(StringRefNull name) +{ + if (COM_EXPORT_GRAPHVIZ) { + exec_system_->set_operations(m_operations, m_groups); + DebugInfo::graphviz(exec_system_, name); + } +} + /** Create a graphviz representation of the NodeOperationBuilder. */ std::ostream &operator<<(std::ostream &os, const NodeOperationBuilder &builder) { diff --git a/source/blender/compositor/intern/COM_NodeOperationBuilder.h b/source/blender/compositor/intern/COM_NodeOperationBuilder.h index 1f76765c846..aca4d043d41 100644 --- a/source/blender/compositor/intern/COM_NodeOperationBuilder.h +++ b/source/blender/compositor/intern/COM_NodeOperationBuilder.h @@ -169,7 +169,10 @@ class NodeOperationBuilder { private: PreviewOperation *make_preview_operation() const; - + void unlink_inputs_and_relink_outputs(NodeOperation *unlinked_op, NodeOperation *linked_op); + void merge_equal_operations(); + void merge_equal_operations(NodeOperation *from, NodeOperation *into); + void save_graphviz(StringRefNull name = ""); #ifdef WITH_CXX_GUARDEDALLOC MEM_CXX_CLASS_ALLOC_FUNCS("COM:NodeCompilerImpl") #endif diff --git a/source/blender/compositor/operations/COM_ConvertOperation.cc b/source/blender/compositor/operations/COM_ConvertOperation.cc index d377903efea..9a3733dda5b 100644 --- a/source/blender/compositor/operations/COM_ConvertOperation.cc +++ b/source/blender/compositor/operations/COM_ConvertOperation.cc @@ -40,6 +40,10 @@ void ConvertBaseOperation::deinitExecution() this->m_inputOperation = nullptr; } +void ConvertBaseOperation::hash_output_params() +{ +} + void ConvertBaseOperation::update_memory_buffer_partial(MemoryBuffer *output, const rcti &area, Span<MemoryBuffer *> inputs) @@ -269,6 +273,12 @@ void ConvertRGBToYCCOperation::executePixelSampled(float output[4], output[3] = inputColor[3]; } +void ConvertRGBToYCCOperation::hash_output_params() +{ + ConvertBaseOperation::hash_output_params(); + hash_param(m_mode); +} + void ConvertRGBToYCCOperation::update_memory_buffer_partial(BuffersIterator<float> &it) { for (; !it.is_end(); ++it) { @@ -327,6 +337,12 @@ void ConvertYCCToRGBOperation::executePixelSampled(float output[4], output[3] = inputColor[3]; } +void ConvertYCCToRGBOperation::hash_output_params() +{ + ConvertBaseOperation::hash_output_params(); + hash_param(m_mode); +} + void ConvertYCCToRGBOperation::update_memory_buffer_partial(BuffersIterator<float> &it) { for (; !it.is_end(); ++it) { diff --git a/source/blender/compositor/operations/COM_ConvertOperation.h b/source/blender/compositor/operations/COM_ConvertOperation.h index 0334959ae7e..72864b3c5e2 100644 --- a/source/blender/compositor/operations/COM_ConvertOperation.h +++ b/source/blender/compositor/operations/COM_ConvertOperation.h @@ -37,6 +37,7 @@ class ConvertBaseOperation : public MultiThreadedOperation { Span<MemoryBuffer *> inputs) final; protected: + virtual void hash_output_params() override; virtual void update_memory_buffer_partial(BuffersIterator<float> &it) = 0; }; @@ -124,6 +125,7 @@ class ConvertRGBToYCCOperation : public ConvertBaseOperation { void setMode(int mode); protected: + void hash_output_params() override; void update_memory_buffer_partial(BuffersIterator<float> &it) override; }; @@ -141,6 +143,7 @@ class ConvertYCCToRGBOperation : public ConvertBaseOperation { void setMode(int mode); protected: + void hash_output_params() override; void update_memory_buffer_partial(BuffersIterator<float> &it) override; }; diff --git a/source/blender/compositor/tests/COM_NodeOperation_test.cc b/source/blender/compositor/tests/COM_NodeOperation_test.cc new file mode 100644 index 00000000000..94e9fdeedb1 --- /dev/null +++ b/source/blender/compositor/tests/COM_NodeOperation_test.cc @@ -0,0 +1,169 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Copyright 2021, Blender Foundation. + */ + +#include "testing/testing.h" + +#include "COM_ConstantOperation.h" + +namespace blender::compositor::tests { + +class NonHashedOperation : public NodeOperation { + public: + NonHashedOperation(int id) + { + set_id(id); + addOutputSocket(DataType::Value); + setWidth(2); + setHeight(3); + } +}; + +class NonHashedConstantOperation : public ConstantOperation { + float constant_; + + public: + NonHashedConstantOperation(int id) + { + set_id(id); + addOutputSocket(DataType::Value); + setWidth(2); + setHeight(3); + constant_ = 1.0f; + } + + const float *get_constant_elem() override + { + return &constant_; + } + + void set_constant(float value) + { + constant_ = value; + } +}; + +class HashedOperation : public NodeOperation { + private: + int param1; + float param2; + + public: + HashedOperation(NodeOperation &input, int width, int height) + { + addInputSocket(DataType::Value); + addOutputSocket(DataType::Color); + setWidth(width); + setHeight(height); + param1 = 2; + param2 = 7.0f; + + getInputSocket(0)->setLink(input.getOutputSocket()); + } + + void set_param1(int value) + { + param1 = value; + } + + void hash_output_params() override + { + hash_params(param1, param2); + } +}; + +static void test_non_equal_hashes_compare(NodeOperationHash &h1, + NodeOperationHash &h2, + NodeOperationHash &h3) +{ + if (h1 < h2) { + if (h3 < h1) { + EXPECT_TRUE(h3 < h2); + } + else if (h3 < h2) { + EXPECT_TRUE(h1 < h3); + } + else { + EXPECT_TRUE(h1 < h3); + EXPECT_TRUE(h2 < h3); + } + } + else { + EXPECT_TRUE(h2 < h1); + } +} + +TEST(NodeOperation, generate_hash) +{ + /* Constant input. */ + { + NonHashedConstantOperation input_op1(1); + input_op1.set_constant(1.0f); + EXPECT_EQ(input_op1.generate_hash(), std::nullopt); + + HashedOperation op1(input_op1, 6, 4); + std::optional<NodeOperationHash> hash1_opt = op1.generate_hash(); + EXPECT_NE(hash1_opt, std::nullopt); + NodeOperationHash hash1 = *hash1_opt; + + NonHashedConstantOperation input_op2(1); + input_op2.set_constant(1.0f); + HashedOperation op2(input_op2, 6, 4); + NodeOperationHash hash2 = *op2.generate_hash(); + EXPECT_EQ(hash1, hash2); + + input_op2.set_constant(3.0f); + hash2 = *op2.generate_hash(); + EXPECT_NE(hash1, hash2); + } + + /* Non constant input. */ + { + NonHashedOperation input_op(1); + EXPECT_EQ(input_op.generate_hash(), std::nullopt); + + HashedOperation op1(input_op, 6, 4); + HashedOperation op2(input_op, 6, 4); + NodeOperationHash hash1 = *op1.generate_hash(); + NodeOperationHash hash2 = *op2.generate_hash(); + EXPECT_EQ(hash1, hash2); + op1.set_param1(-1); + hash1 = *op1.generate_hash(); + EXPECT_NE(hash1, hash2); + + HashedOperation op3(input_op, 11, 14); + NodeOperationHash hash3 = *op3.generate_hash(); + EXPECT_NE(hash2, hash3); + EXPECT_NE(hash1, hash3); + + test_non_equal_hashes_compare(hash1, hash2, hash3); + test_non_equal_hashes_compare(hash3, hash2, hash1); + test_non_equal_hashes_compare(hash2, hash3, hash1); + test_non_equal_hashes_compare(hash3, hash1, hash2); + + NonHashedOperation input_op2(2); + HashedOperation op4(input_op2, 11, 14); + NodeOperationHash hash4 = *op4.generate_hash(); + EXPECT_NE(hash3, hash4); + + input_op2.set_id(1); + hash4 = *op4.generate_hash(); + EXPECT_EQ(hash3, hash4); + } +} + +} // namespace blender::compositor::tests |