Depsgraph: optimization of driver evaluation with many drivers.

7 files changed, 55 insertions, 27 deletions

diff --git a/source/blender/blenkernel/BKE_animsys.h b/source/blender/blenkernel/BKE_animsys.h
index 8b71d97c0e5..2aa939c8b63 100644
--- a/source/blender/blenkernel/BKE_animsys.h
+++ b/source/blender/blenkernel/BKE_animsys.h
@@ -33,6 +33,7 @@
 
 struct AnimData;
 struct AnimMapper;
+struct ChannelDriver;
 struct FCurve;
 struct ID;
 struct KS_Path;
@@ -202,7 +203,9 @@ void animsys_evaluate_action_group(struct PointerRNA *ptr, struct bAction *act,
 struct Depsgraph;
 
 void BKE_animsys_eval_animdata(struct Depsgraph *depsgraph, struct ID *id);
-void BKE_animsys_eval_driver(struct Depsgraph *depsgraph, struct ID *id, struct FCurve *fcurve);
+void BKE_animsys_eval_driver(struct Depsgraph *depsgraph, struct ID *id, int driver_index, struct ChannelDriver *driver_orig);
+
+void BKE_animsys_update_driver_array(struct ID *id);
 
 /* ************************************* */
 
diff --git a/source/blender/blenkernel/intern/anim_sys.c b/source/blender/blenkernel/intern/anim_sys.c
index a14231fd427..43b32a1ee3e 100644
--- a/source/blender/blenkernel/intern/anim_sys.c
+++ b/source/blender/blenkernel/intern/anim_sys.c
@@ -250,6 +250,9 @@ void BKE_animdata_free(ID *id, const bool do_id_user)
 			
 			/* free drivers - stored as a list of F-Curves */
 			free_fcurves(&adt->drivers);
+
+			/* free driver array cache */
+			MEM_SAFE_FREE(adt->driver_array);
 			
 			/* free overrides */
 			/* TODO... */
@@ -289,6 +292,7 @@ AnimData *BKE_animdata_copy(Main *bmain, AnimData *adt, const bool do_action, co
 	
 	/* duplicate drivers (F-Curves) */
 	copy_fcurves(&dadt->drivers, &adt->drivers);
+	dadt->driver_array = NULL;
 	
 	/* don't copy overrides */
 	BLI_listbase_clear(&dadt->overrides);
@@ -2973,34 +2977,45 @@ void BKE_animsys_eval_animdata(Depsgraph *depsgraph, ID *id)
 	BKE_animsys_evaluate_animdata(scene, id, adt, ctime, recalc);
 }
 
-/* TODO(sergey): This is slow lookup of driver from CoW datablock.
- * Keep this for until we've got something smarter for depsgraph
- * building.\
- */
-static FCurve *find_driver_from_evaluated_id(ID *id, FCurve *fcu)
+void BKE_animsys_update_driver_array(ID *id)
 {
-	/* We've got non-CoW datablock, can use f-curve as-is. */
-	if (id->orig_id == NULL) {
-		return fcu;
+	AnimData *adt = BKE_animdata_from_id(id);
+
+	/* Runtime driver map to avoid O(n^2) lookups in BKE_animsys_eval_driver.
+	 * Ideally the depsgraph could pass a pointer to the COW driver directly,
+	 * but this is difficult in the current design. */
+	if (adt && adt->drivers.first) {
+		BLI_assert(!adt->driver_array);
+
+		int num_drivers = BLI_listbase_count(&adt->drivers);
+		adt->driver_array = MEM_mallocN(sizeof(FCurve*) * num_drivers, "adt->driver_array");
+
+		int driver_index = 0;
+		for (FCurve *fcu = adt->drivers.first; fcu; fcu = fcu->next) {
+			adt->driver_array[driver_index++] = fcu;
+		}
 	}
-	/*const*/ ID *id_orig = id->orig_id;
-	const AnimData *adt_orig = BKE_animdata_from_id(id_orig);
-	const AnimData *adt_cow = BKE_animdata_from_id(id);
-	const int fcu_index = BLI_findindex(&adt_orig->drivers, fcu);
-	BLI_assert(fcu_index != -1);
-	return BLI_findlink(&adt_cow->drivers, fcu_index);
 }
 
 void BKE_animsys_eval_driver(Depsgraph *depsgraph,
                              ID *id,
-                             FCurve *fcu)
+                             int driver_index,
+                             ChannelDriver *driver_orig)
 {
 	/* TODO(sergey): De-duplicate with BKE animsys. */
-	ChannelDriver *driver = fcu->driver;
 	PointerRNA id_ptr;
 	bool ok = false;
 
-	fcu = find_driver_from_evaluated_id(id, fcu);
+	/* Lookup driver, accelerated with driver array map. */
+	const AnimData *adt = BKE_animdata_from_id(id);
+	FCurve* fcu;
+
+	if (adt->driver_array) {
+		fcu = adt->driver_array[driver_index];
+	}
+	else {
+		fcu = BLI_findlink(&adt->drivers, driver_index);
+	}
 
 	DEG_debug_print_eval_subdata_index(
 	        depsgraph, __func__, id->name, id, "fcu", fcu->rna_path, fcu, fcu->array_index);
@@ -3011,7 +3026,7 @@ void BKE_animsys_eval_driver(Depsgraph *depsgraph,
 	if ((fcu->flag & (FCURVE_MUTED | FCURVE_DISABLED)) == 0) {
 		/* check if driver itself is tagged for recalculation */
 		/* XXX driver recalc flag is not set yet by depsgraph! */
-		if ((driver) && !(driver->flag & DRIVER_FLAG_INVALID) /*&& (driver->flag & DRIVER_FLAG_RECALC)*/) {
+		if ((driver_orig) && !(driver_orig->flag & DRIVER_FLAG_INVALID) /*&& (driver_orig->flag & DRIVER_FLAG_RECALC)*/) {
 			/* evaluate this using values set already in other places
 			 * NOTE: for 'layering' option later on, we should check if we should remove old value before adding
 			 *       new to only be done when drivers only changed */
@@ -3027,12 +3042,12 @@ void BKE_animsys_eval_driver(Depsgraph *depsgraph,
 			//printf("\tnew val = %f\n", fcu->curval);
 
 			/* clear recalc flag */
-			driver->flag &= ~DRIVER_FLAG_RECALC;
+			driver_orig->flag &= ~DRIVER_FLAG_RECALC;
 
 			/* set error-flag if evaluation failed */
 			if (ok == 0) {
 				printf("invalid driver - %s[%d]\n", fcu->rna_path, fcu->array_index);
-				driver->flag |= DRIVER_FLAG_INVALID;
+				driver_orig->flag |= DRIVER_FLAG_INVALID;
 			}
 		}
 	}
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 00e22cbb911..1819928e20d 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -2819,6 +2819,7 @@ static void direct_link_animdata(FileData *fd, AnimData *adt)
 	/* link drivers */
 	link_list(fd, &adt->drivers);
 	direct_link_fcurves(fd, &adt->drivers);
+	adt->driver_array = NULL;
 	
 	/* link overrides */
 	// TODO...
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc
index 98881ba3e57..e4cdbdadee5 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc
+++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.cc
@@ -704,9 +704,10 @@ void DepsgraphNodeBuilder::build_animdata(ID *id)
 		}
 
 		/* drivers */
+		int driver_index = 0;
 		LISTBASE_FOREACH (FCurve *, fcu, &adt->drivers) {
 			/* create driver */
-			build_driver(id, fcu);
+			build_driver(id, fcu, driver_index++);
 		}
 	}
 }
@@ -715,16 +716,21 @@ void DepsgraphNodeBuilder::build_animdata(ID *id)
  * Build graph node(s) for Driver
  * \param id: ID-Block that driver is attached to
  * \param fcu: Driver-FCurve
+ * \param driver_index: Index in animation data drivers list
  */
-void DepsgraphNodeBuilder::build_driver(ID *id, FCurve *fcurve)
+void DepsgraphNodeBuilder::build_driver(ID *id, FCurve *fcurve, int driver_index)
 {
+	/* Create data node for this driver */
 	ID *id_cow = get_cow_id(id);
+	ChannelDriver *driver_orig = fcurve->driver;
 
-	/* Create data node for this driver */
-	/* TODO(sergey): Shall we use COW of fcu itself here? */
+	/* TODO(sergey): ideally we could pass the COW of fcu, but since it
+	 * has not yet been allocated at this point we can't. As a workaround
+	 * the animation systems allocates an array so we can do a fast lookup
+	 * with the driver index. */
 	ensure_operation_node(id,
 	                      DEG_NODE_TYPE_PARAMETERS,
-	                      function_bind(BKE_animsys_eval_driver, _1, id_cow, fcurve),
+	                      function_bind(BKE_animsys_eval_driver, _1, id_cow, driver_index, driver_orig),
 	                      DEG_OPCODE_DRIVER,
 	                      fcurve->rna_path ? fcurve->rna_path : "",
 	                      fcurve->array_index);
diff --git a/source/blender/depsgraph/intern/builder/deg_builder_nodes.h b/source/blender/depsgraph/intern/builder/deg_builder_nodes.h
index 488f4f273b9..8b9d2d1a010 100644
--- a/source/blender/depsgraph/intern/builder/deg_builder_nodes.h
+++ b/source/blender/depsgraph/intern/builder/deg_builder_nodes.h
@@ -178,7 +178,7 @@ struct DepsgraphNodeBuilder {
 	void build_particle_settings(ParticleSettings *part);
 	void build_cloth(Object *object);
 	void build_animdata(ID *id);
-	void build_driver(ID *id, FCurve *fcurve);
+	void build_driver(ID *id, FCurve *fcurve, int driver_index);
 	void build_driver_variables(ID *id, FCurve *fcurve);
 	void build_driver_id_property(ID *id, const char *rna_path);
 	void build_ik_pose(Object *object,
diff --git a/source/blender/depsgraph/intern/eval/deg_eval_copy_on_write.cc b/source/blender/depsgraph/intern/eval/deg_eval_copy_on_write.cc
index edae5fb002d..6bf7e2fe9e5 100644
--- a/source/blender/depsgraph/intern/eval/deg_eval_copy_on_write.cc
+++ b/source/blender/depsgraph/intern/eval/deg_eval_copy_on_write.cc
@@ -542,6 +542,7 @@ void update_special_pointers(const Depsgraph *depsgraph,
 			break;
 	}
 	update_edit_mode_pointers(depsgraph, id_orig, id_cow);
+	BKE_animsys_update_driver_array(id_cow);
 }
 
 /* This callback is used to validate that all nested ID datablocks are
diff --git a/source/blender/makesdna/DNA_anim_types.h b/source/blender/makesdna/DNA_anim_types.h
index c2248778c46..2839b393fcd 100644
--- a/source/blender/makesdna/DNA_anim_types.h
+++ b/source/blender/makesdna/DNA_anim_types.h
@@ -917,6 +917,8 @@ typedef struct AnimData {
 	ListBase    drivers;    /* standard user-created Drivers/Expressions (used as part of a rig) */
 	ListBase    overrides;  /* temp storage (AnimOverride) of values for settings that are animated (but the value hasn't been keyframed) */
 
+	FCurve **driver_array;  /* runtime data, for depsgraph evaluation */
+
 		/* settings for animation evaluation */
 	int flag;               /* user-defined settings */
 	int recalc;             /* depsgraph recalculation flags */