Towards threaded object update
authorSergey Sharybin <sergey.vfx@gmail.com>
Fri, 28 Jun 2013 21:58:56 +0000 (21:58 +0000)
committerSergey Sharybin <sergey.vfx@gmail.com>
Fri, 28 Jun 2013 21:58:56 +0000 (21:58 +0000)
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

source/blender/blenkernel/BKE_depsgraph.h
source/blender/blenkernel/intern/DerivedMesh.c
source/blender/blenkernel/intern/depsgraph.c
source/blender/blenkernel/intern/scene.c
source/blender/windowmanager/intern/wm_operators.c

index 6baf20aeb2c89e4423cbbe35cbd57c9d8c23cef4..09170c2898c1ae5665f609159d48a37d036fb2b2 100644 (file)
@@ -48,6 +48,7 @@ struct ID;
 struct Main;
 struct Object;
 struct Scene;
+struct ListBase;
 
 /* Build and Update
  *
@@ -115,10 +116,58 @@ void DAG_pose_sort(struct Object *ob);
 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
index aeb664b3c2f5f60b955836b9f68305b29d87e74f..d1bf42183c10edb62a83df02cf77d7fa4ce969d0 100644 (file)
@@ -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"
index 03891f0fed34d59acf8290266ef45549164bd437..c2912a39b6585f26c2a2ce401d1b3e62cb336e3a 100644 (file)
@@ -2655,6 +2655,172 @@ void DAG_pose_sort(Object *ob)
        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 @@ void DAG_print_dependencies(Main *bmain, Scene *scene, Object *ob)
        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;
+}
index 26563afa65b4441019014076409f94fa6d99266c..5636b5a8b87c79fcb0f0afd142efa5197b5cd150 100644 (file)
@@ -1163,32 +1163,298 @@ static void scene_do_rb_simulation_recursive(Scene *scene, float ctime)
                BKE_rigidbody_do_simulation(scene, ctime);
 }
 
-static void scene_update_tagged_recursive(Main *bmain, Scene *scene, Scene *scene_parent)
+#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);
+
+       /* always update layer, so that animating layers works (joshua july 2010) */
+       /* XXX commented out, this has depsgraph issues anyway - and this breaks setting scenes
+        * (on scene-set, the base-lay is copied to ob-lay (ton nov 2012) */
+       // base->lay = ob->lay;
+
+#ifdef UPDATE_SANITY_CHECK
+       base->object->id.flag &= ~LIB_DOIT;
+#endif
+}
+
+static void scene_update_all_bases(Scene *scene_parent, Scene *scene)
 {
        Base *base;
-       
+
+       for (base = scene->base.first; base; base = base->next) {
+               scene_update_single_base(scene_parent, scene, base);
+       }
+}
+
+static void *scene_update_tagged_thread(void *handle_v)
+{
+       SceneUpdateThreadHandle *handle = handle_v;
+       Base *base;
+
+       while ((base = scene_update_thread_next_base(handle))) {
+#ifdef UPDATE_SANITY_CHECK
+               BLI_lock_thread(LOCK_CUSTOM1);
+               printf("Thread %d: updating %s\n", handle->thread, base->object->id.name + 2);
+
+               BLI_assert(base->object->id.flag & LIB_DOIT);
+#endif
+
+               scene_update_single_base(handle->scene_parent, handle->scene, base);
+
+#ifdef UPDATE_SANITY_CHECK
+               BLI_unlock_thread(LOCK_CUSTOM1);
+#endif
+       }
+
+       return NULL;
+}
+
+static void scene_update_objects_threaded(Scene *scene, Scene *scene_parent)
+{
+       ListBase threads;
+       SceneUpdateThreadHandle *handles;
+       ListBase groups = {NULL, NULL};
+       LinkData *current_group_link;
+       int i, tot_thread = BLI_system_thread_count();
+       int tot_group, groups_per_thread, additional_group_threads;
+
+       /* XXX: Releasing DrawObject is not thread safe, but adding lock
+        *      around it is gonna to harm even more. So for now let's
+        *      free all caches from main thread.
+        *
+        * TODO(sergey): Making DrawObject thread-safe is a nice task on
+        *               it's own and it'll also make it possible to remove
+        *               this hack.
+        */
+       {
+               Base *base;
+               for (base = scene->base.first; base; base = base->next) {
+                       Object *ob = base->object;
+
+                       if (ob->recalc & OB_RECALC_ALL) {
+                               BKE_object_free_derived_caches(ob);
+                       }
+               }
+       }
+
+       /* Get independent groups of bases. */
+       DAG_get_independent_groups(scene, &groups);
+
+       /* TODO(sergey): It could make sense to make DAG_get_independent_groups
+        *               to return number of groups. */
+       tot_group = BLI_countlist(&groups);
+
+       /* We don't use more threads than we've got groups. */
+       tot_thread = min_ii(tot_group, tot_thread);
+       if (tot_thread > 1) {
+               BLI_init_threads(&threads, scene_update_tagged_thread, tot_thread);
+       }
+
+       handles = MEM_callocN(sizeof(SceneUpdateThreadHandle) * tot_thread,
+                             "scene update object handles");
+
+#ifdef UPDATE_SANITY_CHECK
+       {
+               Base *base;
+               for (base = scene->base.first; base; base = base->next) {
+                       base->object->id.flag |= LIB_DOIT;
+               }
+       }
+#endif
+
+       /* Every thread handles groups_per_thread groups of bases. */
+       current_group_link = groups.first;
+       groups_per_thread = tot_group / tot_thread;
+
+       /* Some threads will handle more groups,
+        * This happens if devision of groups didn't give integer value
+        * and in this case 'additional_group_threads' of threads will
+        * handle one more extra group.
+        */
+       additional_group_threads = tot_group - groups_per_thread * tot_thread;
+
+       /* Fill in thread handles. */
+       for (i = 0; i < tot_thread; i++) {
+               SceneUpdateThreadHandle *handle = &handles[i];
+               ListBase *current_bases = current_group_link->data;
+               int j, current_groups_per_thread = groups_per_thread;
+
+               if (i < additional_group_threads) {
+                       current_groups_per_thread++;
+               }
+
+#ifdef  UPDATE_SANITY_CHECK
+               handle->thread = i;
+#endif
+
+               handle->scene = scene;
+               handle->scene_parent = scene_parent;
+               handle->current_group_link = current_group_link;
+               handle->current_base_link = current_bases->first;
+
+               /* Find the barried link, which will also be a start group link
+                * for the next thread.
+                *
+                * If this is the last thread, we could skip iteration cycle here.
+                */
+               if (i != tot_thread - 1) {
+                       for (j = 0; j < current_groups_per_thread && current_group_link; j++) {
+                               current_group_link = current_group_link->next;
+                       }
+               }
+               else {
+                       current_group_link = NULL;
+               }
+
+               handle->barrier_group_link = current_group_link;
+
+               if (tot_thread > 1) {
+                       BLI_insert_thread(&threads, handle);
+               }
+       }
+
+       if (tot_thread > 1) {
+               BLI_end_threads(&threads);
+       }
+       else {
+               scene_update_tagged_thread(handles);
+       }
+
+       /* Free memory used by thread handles. */
+       MEM_freeN(handles);
+
+       /* Traverse groups and fee all the memory used by them. */
+       for (current_group_link = groups.first;
+            current_group_link;
+            current_group_link = current_group_link->next)
+       {
+               ListBase *current_bases = current_group_link->data;
+
+               BLI_freelistN(current_bases);
+               MEM_freeN(current_bases);
+       }
+       BLI_freelistN(&groups);
+
+#ifdef UPDATE_SANITY_CHECK
+       {
+               Base *base;
+               for (base = scene->base.first; base; base = base->next) {
+                       BLI_assert((base->object->id.flag & LIB_DOIT) == 0);
+               }
+       }
+#endif
+}
+
+static void scene_update_objects(Scene *scene, Scene *scene_parent)
+{
+       Base *base;
+       int update_count = 0;
+
+       /* Optimization thing: don't do threads if no modifier
+        * stack need to be evaluated.
+        */
+       for (base = scene->base.first; base; base = base->next) {
+               Object *ob = base->object;
+
+               if (ob->recalc & OB_RECALC_ALL) {
+                       update_count++;
+               }
+       }
+
+#ifndef USE_THREADED_UPDATE
+       if (true) {
+               scene_update_all_bases(scene_parent, scene);
+       }
+       else
+#endif
+       if (update_count > 1) {
+               scene_update_objects_threaded(scene, scene_parent);
+       }
+       else {
+               scene_update_all_bases(scene_parent, scene);
+       }
+}
+
+static void scene_update_tagged_recursive(Main *bmain, Scene *scene, Scene *scene_parent)
+{
        scene->customdata_mask = scene_parent->customdata_mask;
 
        /* sets first, we allow per definition current scene to have
         * dependencies on sets, but not the other way around. */
        if (scene->set)
                scene_update_tagged_recursive(bmain, scene->set, scene_parent);
-       
+
        /* scene objects */
-       for (base = scene->base.first; base; base = base->next) {
-               Object *ob = base->object;
-               
-               BKE_object_handle_update_ex(scene_parent, ob, scene->rigidbody_world);
-               
-               if (ob->dup_group && (ob->transflag & OB_DUPLIGROUP))
-                       BKE_group_handle_recalc_and_update(scene_parent, ob, ob->dup_group);
-                       
-               /* always update layer, so that animating layers works (joshua july 2010) */
-               /* XXX commented out, this has depsgraph issues anyway - and this breaks setting scenes
-                * (on scene-set, the base-lay is copied to ob-lay (ton nov 2012) */
-               // base->lay = ob->lay;
-       }
-       
+       scene_update_objects(scene, scene_parent);
+
        /* scene drivers... */
        scene_update_drivers(bmain, scene);
 
index d782725bdcbcb6ee764671a58891278793481c68..0771e6b8f5ae0d249a0ad60c523e23a10e6276e8 100644 (file)
@@ -4075,6 +4075,24 @@ static void WM_OT_dependency_relations(wmOperatorType *ot)
        ot->exec = dependency_relations_exec;
 }
 
+static int dependency_groups_exec(bContext *C, wmOperator *UNUSED(op))
+{
+       Scene *scene = CTX_data_scene(C);
+
+       DAG_print_dependency_groups(scene);
+
+       return OPERATOR_FINISHED;
+}
+
+static void WM_OT_dependency_groups(wmOperatorType *ot)
+{
+       ot->name = "Dependency Groups";
+       ot->idname = "WM_OT_dependency_groups";
+       ot->description = "Print dependency graph groups to the console";
+
+       ot->exec = dependency_groups_exec;
+}
+
 /* ******************************************************* */
 
 static int wm_ndof_sensitivity_exec(bContext *UNUSED(C), wmOperator *op)
@@ -4167,6 +4185,7 @@ void wm_operatortype_init(void)
        WM_operatortype_append(WM_OT_redraw_timer);
        WM_operatortype_append(WM_OT_memory_statistics);
        WM_operatortype_append(WM_OT_dependency_relations);
+       WM_operatortype_append(WM_OT_dependency_groups);
        WM_operatortype_append(WM_OT_debug_menu);
        WM_operatortype_append(WM_OT_operator_defaults);
        WM_operatortype_append(WM_OT_splash);