[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [57913] branches/soc-2013-depsgraph_mt/ source/blender: Replace stupid static balancing with task-based one
Sergey Sharybin
sergey.vfx at gmail.com
Mon Jul 1 23:23:26 CEST 2013
Revision: 57913
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=57913
Author: nazgul
Date: 2013-07-01 21:23:25 +0000 (Mon, 01 Jul 2013)
Log Message:
-----------
Replace stupid static balancing with task-based one
Initially i wanted to have some really simple and basic
threading scheduler and wrote one based on traversing
depsgraph in advance. But it ended up in some issues with
the single-pass traverse i did which didn't gather all
the dependencies actually.
That was for sure solvable, but it ended up in a bit of
time consuming thing and with huge help of Brecht's
patch it was faster just to write proper balancing.
But it's again really basic thing, which could be
easily changed depending on feedback and design decisions
from Joshua,
So for now it works in the following way:
- Currently DagNode is used for threaded evaluaiton,
meaning traversing actually happens for DagNodes.
This is easier than converting DAG to a graph where
only objects are stored, but required adding one int
field to DagNode for faster runtime checks.
We could change this later when it'll be clear how
and where we'll store evaluation data, but for now
it work pretty ok.
- The new field is called "valency" and it's basically
number of node parents which needs to be evaluated
before the node itself could be evaluated.
- Nodes' valency is getting initialized before threading,
and when node finished to update valency of it's childs
is getting decreased by one. And if it happens so
child's valency became zero, it's adding to task pool.
- There's thread lock around valency update, it'll be
replaced with spinlock in nearest future.
- Another update runtime data is node color. White nodes
represents objects, gray one non-objects.
Currently it's needed to distinguish whether we need to
call object_handle_update on node->ob or not. In the
future it could be replaced with node->type to support
granularity, meaning we then could update object data
separately from object itself.
- Needed to add some public depsgraph functions to make
it possible to traverse depsgraph without including
depsgraph private header to other files.
This change doesn't make code anyhow more stable, but
solves update order issues noticed while working on
fixing underlying bugs.
Threaded update is still ifdef-ed for until curves and
armatures are considered thread-safe, which is next
step to be done.
Modified Paths:
--------------
branches/soc-2013-depsgraph_mt/source/blender/blenkernel/BKE_depsgraph.h
branches/soc-2013-depsgraph_mt/source/blender/blenkernel/depsgraph_private.h
branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/depsgraph.c
branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/scene.c
branches/soc-2013-depsgraph_mt/source/blender/windowmanager/intern/wm_operators.c
Modified: branches/soc-2013-depsgraph_mt/source/blender/blenkernel/BKE_depsgraph.h
===================================================================
--- branches/soc-2013-depsgraph_mt/source/blender/blenkernel/BKE_depsgraph.h 2013-07-01 21:23:20 UTC (rev 57912)
+++ branches/soc-2013-depsgraph_mt/source/blender/blenkernel/BKE_depsgraph.h 2013-07-01 21:23:25 UTC (rev 57913)
@@ -116,58 +116,28 @@
void DAG_editors_update_cb(void (*id_func)(struct Main *bmain, struct ID *id),
void (*scene_func)(struct Main *bmain, struct Scene *scene, int updated));
-/* Threaded update: get groups of independent bases
- *
- * DAG_get_independent_groups goes over dependency graph and collects
- * groups of bases in a way that there's no dependencies between this
- * groups at all.
- *
- * Result is stored in a list called groups. This is a sliced list,
- * which means every element of list groups is a LinkData which data
- * represents list of bases in that group.
- *
- * List of bases uses LinkData as well, this is so because bases are
- * used from actual scene.
- *
- * Here's an example of groups storage. There're two groups, one of
- * them consists of two bases: base1 and base2, and base2 depends on
- * base1. Second group contains base3 which doesn't depend on base1
- * and base2.
- *
- * groups
- * |
- * +- LinkData
- * | |
- * | +- BasesList
- * | |
- * | +- LinkData
- * | | |
- * | | + - base1
- * | |
- * | +- LinkData
- * | |
- * | + - base2
- * |
- * +- LinkData
- * |
- * +- BasesList
- * |
- * +- LinkData
- * |
- * + - base3
- *
- * Bases in every group are sorted in a dependency order, meaning
- * first base in group doesn't depend on any other objects, and
- * further bases depends on bases above.
- */
-void DAG_get_independent_groups(struct Scene *scene, struct ListBase *groups);
+/* ** Threaded update ** */
+/* Initialize the DAG for threaded update. */
+void DAG_threaded_update_begin(struct Scene *scene);
+
+/* Run a callback for every node which is ready for update. */
+void DAG_threaded_update_foreach_ready_node(struct Scene *scene,
+ void (*func)(void *node, void *user_data),
+ void *user_data);
+
+struct Object *DAG_threaded_update_get_node_object(void *node_v);
+
+const char *DAG_threaded_update_get_node_name(void *node_v);
+
+void DAG_threaded_update_handle_node_updated(void *node_v,
+ void (*func)(void *node, void *user_data),
+ void *user_data);
+
/* Debugging: print dependency graph for scene or armature object to console */
void DAG_print_dependencies(struct Main *bmain, struct Scene *scene, struct Object *ob);
-void DAG_print_dependency_groups(struct Scene *scene);
-
#ifdef __cplusplus
}
#endif
Modified: branches/soc-2013-depsgraph_mt/source/blender/blenkernel/depsgraph_private.h
===================================================================
--- branches/soc-2013-depsgraph_mt/source/blender/blenkernel/depsgraph_private.h 2013-07-01 21:23:20 UTC (rev 57912)
+++ branches/soc-2013-depsgraph_mt/source/blender/blenkernel/depsgraph_private.h 2013-07-01 21:23:25 UTC (rev 57913)
@@ -92,6 +92,13 @@
struct DagAdjList *child;
struct DagAdjList *parent;
struct DagNode *next;
+
+ /* Threaded evaluation routines */
+ int valency; /* valency of the node is a number of parents which are not updated yet
+ * this node has got.
+ * Used by threaded update for faster detect whether node could be
+ * updated aready.
+ */
} DagNode;
typedef struct DagNodeQueueElem {
Modified: branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/depsgraph.c
===================================================================
--- branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/depsgraph.c 2013-07-01 21:23:20 UTC (rev 57912)
+++ branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/depsgraph.c 2013-07-01 21:23:25 UTC (rev 57913)
@@ -2652,170 +2652,121 @@
ugly_hack_sorry = 1;
}
-/* ******************* DAG FOR THREADED UPDATR ***************** */
+/* ************************ DAG FOR THREADED UPDATE ********************* */
-void DAG_get_independent_groups(Scene *scene, ListBase *groups)
+/* Initialize the DAG for threaded update.
+ *
+ * Sets up all the data needed for faster check whether DAG node is
+ * updatable already (whether all the dependencies are met).
+ */
+void DAG_threaded_update_begin(Scene *scene)
{
-#if defined __GNUC__ || defined __sun
-# define PRINT(format, args ...) { if (dag_print_dependencies) printf(format, ##args); } (void)0
-#else
-# define PRINT(format, ...) { if (dag_print_dependencies) printf(__VA_ARGS__); } (void)0
-#endif
+ DagNode *node;
- DagNode *node, *rootnode;
- DagNodeQueue *node_queue;
- DagAdjList *itA;
- bool skip = false;
- Base *base;
- ListBase *current_group = NULL;
- bool has_group = false;
- int root_count = 0;
-
- PRINT("Independend groups of objects:\n");
- PRINT("\nACHTUNG!!! Order of objects in groups is reversed in outout!\n");
- PRINT("Don't ask why, just be aware of this.\n\n");
-
- /* ** STEP 0: Some pre-initialization. ** */
-
- rootnode = scene->theDag->DagNode.first;
-
- node_queue = queue_create(DAGQUEUEALLOC);
-
- /* Mark all objects as unhandled.
- * This flag is checked later to detect cycle dependencies.
- */
- for (base = scene->base.first; base; base = base->next) {
- base->object->id.flag |= LIB_DOIT;
- }
-
- /* ** STEP 1: Find all nodes which doesn't depend on other nodes ** */
-
- /* Mark all nodes as not visited. */
+ /* We reset valency to zero first... */
for (node = scene->theDag->DagNode.first; node; node = node->next) {
- node->color = DAG_WHITE;
+ node->valency = 0;
}
- /* Detect all the nodes which doesn't have parent. */
+ /* ... and then iterate over all the nodes and
+ * increase valency for node childs.
+ */
for (node = scene->theDag->DagNode.first; node; node = node->next) {
DagAdjList *itA;
- if (node == rootnode) {
- continue;
- }
-
for (itA = node->child; itA; itA = itA->next) {
if (itA->node != node) {
- itA->node->color = DAG_BLACK;
+ itA->node->valency++;
}
}
}
- /* Always put root to a traverse queue. */
- rootnode->color = DAG_GRAY;
- push_stack(node_queue, rootnode);
-
- /* Put all nodes which that depend on other nodes to a traverse queue.
- * Also mark this nodes as gray (since they're visited but not finished)
- * and mark all other nodes as white (they're not viisted).
+ /* A bit tricky, tasks are operating with nodes, which is much
+ * easier from tracking dependnecies point of view, and also
+ * makes it possible to do partial object objects.
+ *
+ * However, currently the only way we're performing update is
+ * calling object_handle_update for objects which are ready,
+ * which also updates object data.
+ *
+ * And for this we need to know whether node represents object
+ * or not.
+ *
+ * And we mark all the nodes which represents objects as
+ * white color, All other nodes are staying gray.
*/
for (node = scene->theDag->DagNode.first; node; node = node->next) {
- if (node == rootnode) {
- continue;
+ Base *base = scene->base.first;
+ node->color = DAG_GRAY;
+ while (base && base->object != node->ob) {
+ base = base->next;
}
-
- if (node->color == DAG_WHITE) {
- PRINT("Root node: %s\n", dag_node_name(node));
-
- node->color = DAG_GRAY;
- push_stack(node_queue, node);
- }
- else {
+ if (base) {
node->color = DAG_WHITE;
}
}
+}
- root_count = node_queue->count;
+/* Call functor for every node in the graph which is ready for
+ * update (all it's dependencies are met). Quick check for this
+ * is valency == 0.
+ */
+void DAG_threaded_update_foreach_ready_node(Scene *scene,
+ void (*func)(void *node, void *user_data),
+ void *user_data)
+{
+ DagNode *node;
- /* ** STEP 2: Traverse the graph and collect all the groups. ** */
-
- while (node_queue->count) {
- skip = false;
- node = get_top_node_queue(node_queue);
-
- itA = node->child;
- while (itA != NULL) {
- if (itA->node->color == DAG_WHITE) {
- itA->node->color = DAG_GRAY;
- push_stack(node_queue, itA->node);
- skip = true;
- break;
- }
- itA = itA->next;
+ for (node = scene->theDag->DagNode.first; node; node = node->next) {
+ if (node->valency == 0) {
+ func(node, user_data);
}
+ }
+}
- if (!skip) {
- if (node) {
- node = pop_queue(node_queue);
- if (node->ob == scene) {
- /* Whatever Thom, we are done! */
- break;
- }
+/* Will return Object ID if node represents Object,
+ * and will return NULL otherwise.
+ */
+Object *DAG_threaded_update_get_node_object(void *node_v)
+{
+ DagNode *node = node_v;
- node->color = DAG_BLACK;
+ if (node->color == DAG_WHITE) {
+ return node->ob;
+ }
- base = scene->base.first;
- while (base && base->object != node->ob) {
- base = base->next;
- }
+ return NULL;
+}
- if (base) {
- base->object->id.flag &= ~LIB_DOIT;
+/* Returns node name, used for debug output only, atm. */
+const char *DAG_threaded_update_get_node_name(void *node_v)
+{
+ DagNode *node = node_v;
- if (has_group == false) {
- PRINT("- Next group\n");
+ return dag_node_name(node);
+}
- if (groups) {
- current_group = MEM_callocN(sizeof(ListBase), "DAG independent group");
- BLI_addhead(groups, BLI_genericNodeN(current_group));
- }
+/* This function is called when handling node is done.
+ *
+ * This function updates valency for all childs and
+ * schedules them if they're ready.
+ */
+void DAG_threaded_update_handle_node_updated(void *node_v,
+ void (*func)(void *node, void *user_data),
+ void *user_data)
+{
+ DagNode *node = node_v;
+ DagAdjList *itA;
- has_group = true;
- }
+ for (itA = node->child; itA; itA = itA->next) {
+ if (itA->node != node) {
+ itA->node->valency--;
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list