[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [57864] branches/soc-2013-depsgraph_mt/ source/blender: Towards threaded object update
Sergey Sharybin
sergey.vfx at gmail.com
Fri Jun 28 23:58:56 CEST 2013
Revision: 57864
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=57864
Author: nazgul
Date: 2013-06-28 21:58:56 +0000 (Fri, 28 Jun 2013)
Log Message:
-----------
Towards threaded object update
This commit contains changes related on running function
BKE_object_handle_update_ex from multiple threads in order
to increase scene update time when having multiple
independent groups of objects.
Currently this required changes to two areas:
- scene.c, where scene_update_tagged_recursive is now using
threads for updating the object
There're some tricks to prevent threads from being spawned
when it's not needed:
* Threading will only happen if there're more than one CPU
core.
* Threading will happen only if there're more than single
object which needed to be updated.
There's currently one crappy part of the change: which is
freeing object caches (derivedFinal, derivedDeform and so)
from main thread. This is so because in case VBO are used
freeing DM is not thread safe. This is because DrawObject
used global array. Would look into possibility of making
that code safe later.
There're also currently some ifdef-ed debug-only code, which
helps a lot troubleshooting whether everything is working
fine. This code looks a bit ugly now, will either drop it
later or make it more cleat.
And one more thing: threaded update is CURRENTLY DISABLED.
This is because of some thread-unsafe issues discovered
while was working on this patch. Namely:
* I have once a crash in Curve module. Wasn't been able
to reproduce the crash, but could thing about some
unsafe code there.
* Virtual modifier list is not thread-safe (it uses static
variables).
* Armature modifier is also doesn't seem to be thread safe
because of storing some temporary runtime data in actual
armature.
All this issues are to be solved next.
- depsgraph.c, where i've added a function which gives list
of groups, each group contains objects and dependency is
only allowed between objects inside one group.
This is needed to make scheduling of objects easier, which
means update threads will operate on groups, and will handle
objects one-by-one inside group. Different threads will
operate on different groups.
Currently such groups will be generated on every update.
Actually, on every run of scene_update_objects_threaded which
only happens if there're objects marked for update. In the
future we could consider storing such groups in graph itself,
which will help saving CPU power on building such groups.
But this is something to be discussed with Joshua first.
P.S. If you really want to test threaded update, you'll
need to replace:
#undef USE_THREADED_UPDATE
with:
#define USE_THREADED_UPDATE
Modified Paths:
--------------
branches/soc-2013-depsgraph_mt/source/blender/blenkernel/BKE_depsgraph.h
branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/DerivedMesh.c
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-06-28 21:58:52 UTC (rev 57863)
+++ branches/soc-2013-depsgraph_mt/source/blender/blenkernel/BKE_depsgraph.h 2013-06-28 21:58:56 UTC (rev 57864)
@@ -48,6 +48,7 @@
struct Main;
struct Object;
struct Scene;
+struct ListBase;
/* Build and Update
*
@@ -115,10 +116,58 @@
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);
+
/* 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/intern/DerivedMesh.c
===================================================================
--- branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/DerivedMesh.c 2013-06-28 21:58:52 UTC (rev 57863)
+++ branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/DerivedMesh.c 2013-06-28 21:58:56 UTC (rev 57864)
@@ -49,6 +49,7 @@
#include "BLI_array.h"
#include "BLI_utildefines.h"
#include "BLI_linklist.h"
+#include "BLI_threads.h"
#include "BKE_pbvh.h"
#include "BKE_cdderivedmesh.h"
Modified: branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/depsgraph.c
===================================================================
--- branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/depsgraph.c 2013-06-28 21:58:52 UTC (rev 57863)
+++ branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/depsgraph.c 2013-06-28 21:58:56 UTC (rev 57864)
@@ -2655,6 +2655,172 @@
ugly_hack_sorry = 1;
}
+/* ******************* DAG FOR THREADED UPDATR ***************** */
+
+void DAG_get_independent_groups(Scene *scene, ListBase *groups)
+{
+#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, *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. */
+ for (node = scene->theDag->DagNode.first; node; node = node->next) {
+ node->color = DAG_WHITE;
+ }
+
+ /* Detect all the nodes which doesn't have parent. */
+ 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;
+ }
+ }
+ }
+
+ /* 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).
+ */
+ for (node = scene->theDag->DagNode.first; node; node = node->next) {
+ if (node == rootnode) {
+ continue;
+ }
+
+ if (node->color == DAG_WHITE) {
+ PRINT("Root node: %s\n", dag_node_name(node));
+
+ node->color = DAG_GRAY;
+ push_stack(node_queue, node);
+ }
+ else {
+ node->color = DAG_WHITE;
+ }
+ }
+
+ root_count = node_queue->count;
+
+ /* ** 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;
+ }
+
+ if (!skip) {
+ if (node) {
+ node = pop_queue(node_queue);
+ if (node->ob == scene) {
+ /* Whatever Thom, we are done! */
+ break;
+ }
+
+ node->color = DAG_BLACK;
+
+ base = scene->base.first;
+ while (base && base->object != node->ob) {
+ base = base->next;
+ }
+
+ if (base) {
+ base->object->id.flag &= ~LIB_DOIT;
+
+ if (has_group == false) {
+ PRINT("- Next group\n");
+
+ if (groups) {
+ current_group = MEM_callocN(sizeof(ListBase), "DAG independent group");
+ BLI_addhead(groups, BLI_genericNodeN(current_group));
+ }
+
+ has_group = true;
+ }
+
+ PRINT(" %s\n", dag_node_name(node));
+
+ if (groups) {
+ BLI_addhead(current_group, BLI_genericNodeN(base));
+ }
+ }
+
+ if (node_queue->count < root_count) {
+ root_count--;
+ has_group = false;
+ }
+ }
+ }
+ }
+
+ /* Here we put all cyclic objects to separate groups */
+ for (base = scene->base.first; base; base = base->next) {
+ if (base->object->id.flag & LIB_DOIT) {
+ base->object->id.flag &= ~LIB_DOIT;
+
+ PRINT("- Next cyclic group\n");
+ PRINT(" %s\n", base->object->id.name + 2);
+
+ if (groups) {
+ current_group = MEM_callocN(sizeof(ListBase), "DAG independent group");
+ BLI_addtail(groups, BLI_genericNodeN(current_group));
+ BLI_addtail(current_group, BLI_genericNodeN(base));
+ }
+ }
+ }
+
+ queue_delete(node_queue);
+
+#undef PRINT
+}
+
/* ************************ DAG DEBUGGING ********************* */
void DAG_print_dependencies(Main *bmain, Scene *scene, Object *ob)
@@ -2674,3 +2840,11 @@
dag_print_dependencies = 0;
}
+void DAG_print_dependency_groups(Scene *scene)
+{
+ dag_print_dependencies = 1;
+
+ DAG_get_independent_groups(scene, NULL);
+
+ dag_print_dependencies = 0;
+}
Modified: branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/scene.c
===================================================================
--- branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/scene.c 2013-06-28 21:58:52 UTC (rev 57863)
+++ branches/soc-2013-depsgraph_mt/source/blender/blenkernel/intern/scene.c 2013-06-28 21:58:56 UTC (rev 57864)
@@ -1163,32 +1163,298 @@
BKE_rigidbody_do_simulation(scene, ctime);
}
+#undef USE_THREADED_UPDATE
+
+/* Debugging only!
+ *
+ * Will enable some additional checks about whether threaded
+ * update went all fine or there's some mistake in code somewhere
+ * (like, missing object update or object being updated from two threads).
+ */
+#undef UPDATE_SANITY_CHECK
+
+typedef struct SceneUpdateThreadHandle {
+#ifdef UPDATE_SANITY_CHECK
+ int thread;
+#endif
+
+ /* Current scene and it's parent */
+ Scene *scene;
+ Scene *scene_parent;
+
+ /* Every thread handles several independent groups.
+ * This is a current group.
+ */
+ LinkData *current_group_link;
+
+ /* This is a first group which shouldn't be handled
+ * (aka it's handled by another thread as as soon
+ * as current thread reaches it thread shall stop).
+ */
+ LinkData *barrier_group_link;
+
+ /* Current link to a base which wasn't updated yet. */
+ LinkData *current_base_link;
+} SceneUpdateThreadHandle;
+
+static Base *scene_update_thread_next_base(SceneUpdateThreadHandle *handle)
+{
+ Base *base = NULL;
+
+ /* If current base link became NULL, it means traversing current group
+ * is finished and we need to go to a next group.
+ */
+ if (handle->current_base_link == NULL) {
+ ListBase *current_bases;
+
+ handle->current_group_link = handle->current_group_link->next;
+
+ /* If we've reached barrier group, we need to stop current thread. */
+ if (handle->current_group_link == handle->barrier_group_link) {
+ return NULL;
+ }
+
+ current_bases = handle->current_group_link->data;
+ handle->current_base_link = current_bases->first;
+ }
+
+ if (handle->current_base_link) {
+ base = handle->current_base_link->data;
+ handle->current_base_link = handle->current_base_link->next;
+ }
+
+ return base;
+}
+
+static void scene_update_single_base(Scene *scene_parent, Scene *scene, Base *base)
+{
+ Object *object = base->object;
+
+ BKE_object_handle_update_ex(scene_parent, object, scene->rigidbody_world);
+
+ if (object->dup_group && (object->transflag & OB_DUPLIGROUP))
+ BKE_group_handle_recalc_and_update(scene_parent, object, object->dup_group);
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list