[Bf-blender-cvs] [ee98dc8d0fc] blender-v2.90-release: Fix T77277: building depsgraph inter-driver relations is slow
Sybren A. Stüvel
noreply at git.blender.org
Thu Jul 23 15:01:38 CEST 2020
Commit: ee98dc8d0fc8d25a2369e6da58d76652f324c8ea
Author: Sybren A. Stüvel
Date: Fri Jul 17 16:47:19 2020 +0200
Branches: blender-v2.90-release
https://developer.blender.org/rBee98dc8d0fc8d25a2369e6da58d76652f324c8ea
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
===================================================================
M source/blender/depsgraph/CMakeLists.txt
M source/blender/depsgraph/intern/builder/deg_builder_relations.cc
A source/blender/depsgraph/intern/builder/deg_builder_relations_drivers.cc
A source/blender/depsgraph/intern/builder/deg_builder_relations_drivers.h
===================================================================
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->fro
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list