diff options
author | Sybren A. Stüvel <sybren@blender.org> | 2020-07-17 17:47:19 +0300 |
---|---|---|
committer | Sybren A. Stüvel <sybren@blender.org> | 2020-07-23 15:52:46 +0300 |
commit | ee98dc8d0fc8d25a2369e6da58d76652f324c8ea (patch) | |
tree | eca1c596b50ea77ea75dbdd3e40b33c15d294cc9 /source | |
parent | 37ad90c35f640d9e5cb649ed3342e9c43cc37745 (diff) |
Fix T77277: building depsgraph inter-driver relations is slow
The extra depsgraph relations that were added to prevent threading
issues during evaluation (rB4c30dc343165) caused a considerable slowdown
on complex scenes with many drivers (T77277, T78615). This commit
improves this as follows.
Only the following drivers are considered for execution serialisation:
- Drivers on Array elements, and
- Drivers on Boolean or Enum properties.
Relations between drivers of the same arrays are added blindly, i.e.
without checking for transitive or cyclic relations. This is possible as
other relations will just target the `PROPERTIES_ENTRY` or
`PROPERTIES_EXIT` nodes.
Checking whether a driver is on an array is first done by checking
`array_index > 0`, and then falling back to resolving the RNA path to an
RNA property and inspecting that.
The code also avoids circular dependencies when there are multiple
drivers on the same property. This not something that is expected to
happen (both the UI and the Python API prevent duplicate drivers), it
did happen in a file (F8669945, example file of T78615) and it is easy
to deal with here.
Reviewers: sergey
Subscribers: mont29
Comment update
Diffstat (limited to 'source')
4 files changed, 337 insertions, 115 deletions
diff --git a/source/blender/depsgraph/CMakeLists.txt b/source/blender/depsgraph/CMakeLists.txt index 355d2536e1a..839a3712129 100644 --- a/source/blender/depsgraph/CMakeLists.txt +++ b/source/blender/depsgraph/CMakeLists.txt @@ -46,6 +46,7 @@ set(SRC intern/builder/deg_builder_nodes_view_layer.cc intern/builder/deg_builder_pchanmap.cc intern/builder/deg_builder_relations.cc + intern/builder/deg_builder_relations_drivers.cc intern/builder/deg_builder_relations_keys.cc intern/builder/deg_builder_relations_rig.cc intern/builder/deg_builder_relations_scene.cc @@ -100,6 +101,7 @@ set(SRC intern/builder/deg_builder.h intern/builder/deg_builder_cache.h intern/builder/deg_builder_cycle.h + intern/builder/deg_builder_relations_drivers.h intern/builder/deg_builder_map.h intern/builder/deg_builder_nodes.h intern/builder/deg_builder_pchanmap.h diff --git a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc index 8eeea4c18eb..c5c509ee853 100644 --- a/source/blender/depsgraph/intern/builder/deg_builder_relations.cc +++ b/source/blender/depsgraph/intern/builder/deg_builder_relations.cc @@ -104,6 +104,7 @@ #include "intern/builder/deg_builder.h" #include "intern/builder/deg_builder_pchanmap.h" +#include "intern/builder/deg_builder_relations_drivers.h" #include "intern/debug/deg_debug.h" #include "intern/depsgraph_physics.h" #include "intern/depsgraph_tag.h" @@ -2843,121 +2844,6 @@ void DepsgraphRelationBuilder::build_copy_on_write_relations(IDNode *id_node) #endif } -static bool is_reachable(const Node *const from, const Node *const to) -{ - if (from == to) { - return true; - } - - // Perform a graph walk from 'to' towards its incoming connections. - // Walking from 'from' towards its outgoing connections is 10x slower on the Spring rig. - deque<const Node *> queue; - Set<const Node *> seen; - queue.push_back(to); - while (!queue.empty()) { - // Visit the next node to inspect. - const Node *visit = queue.back(); - queue.pop_back(); - - if (visit == from) { - return true; - } - - // Queue all incoming relations that we haven't seen before. - for (Relation *relation : visit->inlinks) { - const Node *prev_node = relation->from; - if (seen.add(prev_node)) { - queue.push_back(prev_node); - } - } - } - return false; -} - -void DepsgraphRelationBuilder::build_driver_relations() -{ - for (IDNode *id_node : graph_->id_nodes) { - build_driver_relations(id_node); - } -} - -void DepsgraphRelationBuilder::build_driver_relations(IDNode *id_node) -{ - /* Add relations between drivers that write to the same datablock. - * - * This prevents threading issues when two separate RNA properties write to - * the same memory address. For example: - * - Drivers on individual array elements, as the animation system will write - * the whole array back to RNA even when changing individual array value. - * - Drivers on RNA properties that map to a single bit flag. Changing the RNA - * value will write the entire int containing the bit, in a non-thread-safe - * way. - */ - ID *id_orig = id_node->id_orig; - AnimData *adt = BKE_animdata_from_id(id_orig); - if (adt == nullptr) { - return; - } - - // Mapping from RNA prefix -> set of driver evaluation nodes: - Map<string, Vector<Node *>> driver_groups; - - LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) { - if (fcu->rna_path == nullptr) { - continue; - } - // Get the RNA path except the part after the last dot. - char *last_dot = strrchr(fcu->rna_path, '.'); - StringRef rna_prefix; - if (last_dot != nullptr) { - rna_prefix = StringRef(fcu->rna_path, last_dot); - } - - // Insert this driver node into the group belonging to the RNA prefix. - OperationKey driver_key( - id_orig, NodeType::PARAMETERS, OperationCode::DRIVER, fcu->rna_path, fcu->array_index); - Node *node_driver = get_node(driver_key); - driver_groups.lookup_or_add_default_as(rna_prefix).append(node_driver); - } - - for (Span<Node *> prefix_group : driver_groups.values()) { - // For each node in the driver group, try to connect it to another node - // in the same group without creating any cycles. - int num_drivers = prefix_group.size(); - if (num_drivers < 2) { - // A relation requires two drivers. - continue; - } - for (int from_index = 0; from_index < num_drivers; ++from_index) { - Node *op_from = prefix_group[from_index]; - - // Start by trying the next node in the group. - for (int to_offset = 1; to_offset < num_drivers; ++to_offset) { - int to_index = (from_index + to_offset) % num_drivers; - Node *op_to = prefix_group[to_index]; - - // Investigate whether this relation would create a dependency cycle. - // Example graph: - // A -> B -> C - // and investigating a potential connection C->A. Because A->C is an - // existing transitive connection, adding C->A would create a cycle. - if (is_reachable(op_to, op_from)) { - continue; - } - - // No need to directly connect this node if there is already a transitive connection. - if (is_reachable(op_from, op_to)) { - break; - } - - add_operation_relation( - op_from->get_exit_operation(), op_to->get_entry_operation(), "Driver Serialization"); - break; - } - } - } -} - /* **** ID traversal callbacks functions **** */ void DepsgraphRelationBuilder::modifier_walk(void *user_data, diff --git a/source/blender/depsgraph/intern/builder/deg_builder_relations_drivers.cc b/source/blender/depsgraph/intern/builder/deg_builder_relations_drivers.cc new file mode 100644 index 00000000000..717c8300f9b --- /dev/null +++ b/source/blender/depsgraph/intern/builder/deg_builder_relations_drivers.cc @@ -0,0 +1,258 @@ +/* + * 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. + * + * The Original Code is Copyright (C) 2013 Blender Foundation. + * All rights reserved. + */ + +/** \file + * \ingroup depsgraph + * + * Methods for constructing depsgraph relations for drivers. + */ + +#include "intern/builder/deg_builder_relations_drivers.h" + +#include <cstring> + +#include "DNA_anim_types.h" + +#include "BKE_anim_data.h" + +#include "intern/builder/deg_builder_relations.h" +#include "intern/depsgraph_relation.h" +#include "intern/node/deg_node.h" + +namespace blender { +namespace deg { + +DriverDescriptor::DriverDescriptor(PointerRNA *id_ptr, FCurve *fcu) + : rna_prefix(), + rna_suffix(), + id_ptr_(id_ptr), + fcu_(fcu), + driver_relations_needed_(false), + pointer_rna_(), + property_rna_(nullptr), + is_array_(false) +{ + driver_relations_needed_ = determine_relations_needed(); + split_rna_path(); +} + +bool DriverDescriptor::determine_relations_needed() +{ + if (fcu_->array_index > 0) { + /* Drivers on array elements always need relations. */ + is_array_ = true; + return true; + } + + if (!resolve_rna()) { + /* Properties that don't exist can't cause threading issues either. */ + return false; + } + + if (RNA_property_array_check(property_rna_)) { + /* Drivers on array elements always need relations. */ + is_array_ = true; + return true; + } + + /* Drivers on Booleans and Enums (when used as bitflags) can write to the same memory location, + * so they need relations between each other. */ + return ELEM(RNA_property_type(property_rna_), PROP_BOOLEAN, PROP_ENUM); +} + +bool DriverDescriptor::driver_relations_needed() const +{ + return driver_relations_needed_; +} + +bool DriverDescriptor::is_array() const +{ + return is_array_; +} + +/* Assumes that 'other' comes from the same RNA group, that is, has the same RNA path prefix. */ +bool DriverDescriptor::is_same_array_as(const DriverDescriptor &other) const +{ + if (!is_array_ || !other.is_array_) { + return false; + } + return rna_suffix == other.rna_suffix; +} + +OperationKey DriverDescriptor::depsgraph_key() const +{ + return OperationKey(id_ptr_->owner_id, + NodeType::PARAMETERS, + OperationCode::DRIVER, + fcu_->rna_path, + fcu_->array_index); +} + +void DriverDescriptor::split_rna_path() +{ + const char *last_dot = strrchr(fcu_->rna_path, '.'); + if (last_dot == nullptr || last_dot[1] == '\0') { + rna_prefix = StringRef(); + rna_suffix = StringRef(fcu_->rna_path); + return; + } + + rna_prefix = StringRef(fcu_->rna_path, last_dot); + rna_suffix = StringRef(last_dot + 1); +} + +bool DriverDescriptor::resolve_rna() +{ + return RNA_path_resolve_property(id_ptr_, fcu_->rna_path, &pointer_rna_, &property_rna_); +} + +static bool is_reachable(const Node *const from, const Node *const to) +{ + if (from == to) { + return true; + } + + // Perform a graph walk from 'to' towards its incoming connections. + // Walking from 'from' towards its outgoing connections is 10x slower on the Spring rig. + deque<const Node *> queue; + Set<const Node *> seen; + queue.push_back(to); + while (!queue.empty()) { + // Visit the next node to inspect. + const Node *visit = queue.back(); + queue.pop_back(); + + if (visit == from) { + return true; + } + + // Queue all incoming relations that we haven't seen before. + for (Relation *relation : visit->inlinks) { + const Node *prev_node = relation->from; + if (seen.add(prev_node)) { + queue.push_back(prev_node); + } + } + } + return false; +} + +/* **** DepsgraphRelationBuilder functions **** */ + +void DepsgraphRelationBuilder::build_driver_relations() +{ + for (IDNode *id_node : graph_->id_nodes) { + build_driver_relations(id_node); + } +} + +void DepsgraphRelationBuilder::build_driver_relations(IDNode *id_node) +{ + /* Add relations between drivers that write to the same datablock. + * + * This prevents threading issues when two separate RNA properties write to + * the same memory address. For example: + * - Drivers on individual array elements, as the animation system will write + * the whole array back to RNA even when changing individual array value. + * - Drivers on RNA properties that map to a single bit flag. Changing the RNA + * value will write the entire int containing the bit, in a non-thread-safe + * way. + */ + ID *id_orig = id_node->id_orig; + AnimData *adt = BKE_animdata_from_id(id_orig); + if (adt == nullptr) { + return; + } + + // Mapping from RNA prefix -> set of driver descriptors: + Map<string, Vector<DriverDescriptor>> driver_groups; + + PointerRNA id_ptr; + RNA_id_pointer_create(id_orig, &id_ptr); + + LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) { + if (fcu->rna_path == nullptr) { + continue; + } + + DriverDescriptor driver_desc(&id_ptr, fcu); + if (!driver_desc.driver_relations_needed()) { + continue; + } + + driver_groups.lookup_or_add_default_as(driver_desc.rna_prefix).append(driver_desc); + } + + for (Span<DriverDescriptor> prefix_group : driver_groups.values()) { + // For each node in the driver group, try to connect it to another node + // in the same group without creating any cycles. + int num_drivers = prefix_group.size(); + if (num_drivers < 2) { + // A relation requires two drivers. + continue; + } + for (int from_index = 0; from_index < num_drivers; ++from_index) { + const DriverDescriptor &driver_from = prefix_group[from_index]; + Node *op_from = get_node(driver_from.depsgraph_key()); + + // Start by trying the next node in the group. + for (int to_offset = 1; to_offset < num_drivers; ++to_offset) { + const int to_index = (from_index + to_offset) % num_drivers; + const DriverDescriptor &driver_to = prefix_group[to_index]; + Node *op_to = get_node(driver_to.depsgraph_key()); + + // Duplicate drivers can exist (see T78615), but cannot be distinguished by OperationKey + // and thus have the same depsgraph node. Relations between those drivers should not be + // created. This not something that is expected to happen (both the UI and the Python API + // prevent duplicate drivers), it did happen in a file and it is easy to deal with here. + if (op_from == op_to) { + continue; + } + + if (from_index < to_index && driver_from.is_same_array_as(driver_to)) { + // This is for adding a relation like `color[0]` -> `color[1]`. + // When the search for another driver wraps around, we cannot blindly add relations any + // more. + } + else { + // Investigate whether this relation would create a dependency cycle. + // Example graph: + // A -> B -> C + // and investigating a potential connection C->A. Because A->C is an + // existing transitive connection, adding C->A would create a cycle. + if (is_reachable(op_to, op_from)) { + continue; + } + + // No need to directly connect this node if there is already a transitive connection. + if (is_reachable(op_from, op_to)) { + break; + } + } + + add_operation_relation( + op_from->get_exit_operation(), op_to->get_entry_operation(), "Driver Serialization"); + break; + } + } + } +} + +} // namespace deg +} // namespace blender diff --git a/source/blender/depsgraph/intern/builder/deg_builder_relations_drivers.h b/source/blender/depsgraph/intern/builder/deg_builder_relations_drivers.h new file mode 100644 index 00000000000..c80c69be9e2 --- /dev/null +++ b/source/blender/depsgraph/intern/builder/deg_builder_relations_drivers.h @@ -0,0 +1,76 @@ +/* + * 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. + * + * The Original Code is Copyright (C) 2013 Blender Foundation. + * All rights reserved. + */ + +/** \file + * \ingroup depsgraph + */ + +#pragma once + +#include "BLI_string_ref.hh" + +#include "RNA_types.h" + +#include "intern/builder/deg_builder_relations.h" + +struct FCurve; + +namespace blender { +namespace deg { + +/* Helper class for determining which relations are needed between driver evaluation nodes. */ +class DriverDescriptor { + public: + /* Drivers are grouped by their RNA prefix. The prefix is the part of the RNA + * path up to the last dot, the suffix is the remainder of the RNA path: + * + * fcu->rna_path rna_prefix rna_suffix + * ------------------------------- ---------------------- ---------- + * 'color' '' 'color' + * 'rigidbody_world.time_scale' 'rigidbody_world' 'time_scale' + * 'pose.bones["master"].location' 'pose.bones["master"]' 'location' + */ + StringRef rna_prefix; + StringRef rna_suffix; + + public: + DriverDescriptor(PointerRNA *id_ptr, FCurve *fcu); + + bool driver_relations_needed() const; + bool is_array() const; + /* Assumes that 'other' comes from the same RNA group, that is, has the same RNA path prefix. */ + bool is_same_array_as(const DriverDescriptor &other) const; + OperationKey depsgraph_key() const; + + private: + PointerRNA *id_ptr_; + FCurve *fcu_; + bool driver_relations_needed_; + + PointerRNA pointer_rna_; + PropertyRNA *property_rna_; + bool is_array_; + + bool determine_relations_needed(); + void split_rna_path(); + bool resolve_rna(); +}; + +} // namespace deg +} // namespace blender |