diff options
| -rw-r--r-- | source/blender/blenlib/BLI_task.h | 76 | ||||
| -rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 1 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/task_graph.cc | 161 | ||||
| -rw-r--r-- | tests/gtests/blenlib/BLI_task_graph_test.cc | 188 | ||||
| -rw-r--r-- | tests/gtests/blenlib/CMakeLists.txt | 1 |
5 files changed, 427 insertions, 0 deletions
diff --git a/source/blender/blenlib/BLI_task.h b/source/blender/blenlib/BLI_task.h index 64dfdc2ad25..a4a855c354b 100644 --- a/source/blender/blenlib/BLI_task.h +++ b/source/blender/blenlib/BLI_task.h @@ -237,6 +237,82 @@ BLI_INLINE void BLI_parallel_range_settings_defaults(TaskParallelSettings *setti * Only here for code to be removed. */ int BLI_task_parallel_thread_id(const TaskParallelTLS *tls); +/* Task Graph Scheduling */ +/* Task Graphs can be used to create a forest of directional trees and schedule work to any tree. + * The nodes in the graph can be run in separate threads. + * + * +---- [root] ----+ + * | | + * v v + * [node_1] +---- [node_2] ----+ + * | | + * v v + * [node_3] [node_4] + * + * TaskGraph *task_graph = BLI_task_graph_create(); + * TaskNode *root = BLI_task_graph_node_create(task_graph, root_exec, NULL, NULL); + * TaskNode *node_1 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL); + * TaskNode *node_2 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL); + * TaskNode *node_3 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL); + * TaskNode *node_4 = BLI_task_graph_node_create(task_graph, node_exec, NULL, NULL); + * + * BLI_task_graph_edge_create(root, node_1); + * BLI_task_graph_edge_create(root, node_2); + * BLI_task_graph_edge_create(node_2, node_3); + * BLI_task_graph_edge_create(node_2, node_4); + * + * Any node can be triggered to start a chain of tasks. Normally you would trigger a root node but + * it is supported to start the chain of tasks anywhere in the forest or tree. When a node + * completes, the execution flow is forwarded via the created edges. + * When a child node has multiple parents the child node will be triggered once for each parent. + * + * BLI_task_graph_node_push_work(root); + * + * In this example After `root` is finished, `node_1` and `node_2` will be started. + * Only after `node_2` is finished `node_3` and `node_4` will be started. + * + * After scheduling work we need to wait until all the tasks have been finished. + * + * BLI_task_graph_work_and_wait(); + * + * When finished you can clean up all the resources by freeing the task_graph. Nodes are owned by + * the graph and are freed task_data will only be freed if a free_func was given. + * + * BLI_task_graph_free(task_graph); + * + * Work can enter a tree on any node. Normally this would be the root_node. + * A `task_graph` can be reused, but the caller needs to make sure the task_data is reset. + * + * ** Task-Data ** + * + * Typically you want give a task data to work on. + * Task data can be shared with other nodes, but be carefull not to free the data multiple times. + * Task data is freed when calling `BLI_task_graph_free`. + * + * MyData *task_data = MEM_callocN(sizeof(MyData), __func__); + * TaskNode *root = BLI_task_graph_node_create(task_graph, root_exec, task_data, MEM_freeN); + * TaskNode *node_1 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL); + * TaskNode *node_2 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL); + * TaskNode *node_3 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL); + * TaskNode *node_4 = BLI_task_graph_node_create(task_graph, node_exec, task_data, NULL); + * + */ +struct TaskGraph; +struct TaskNode; + +typedef void (*TaskGraphNodeRunFunction)(void *__restrict task_data); +typedef void (*TaskGraphNodeFreeFunction)(void *task_data); + +struct TaskGraph *BLI_task_graph_create(void); +void BLI_task_graph_work_and_wait(struct TaskGraph *task_graph); +void BLI_task_graph_free(struct TaskGraph *task_graph); +struct TaskNode *BLI_task_graph_node_create(struct TaskGraph *task_graph, + TaskGraphNodeRunFunction run, + void *task_data, + TaskGraphNodeFreeFunction free_func); +bool BLI_task_graph_node_push_work(struct TaskNode *task_node); +void BLI_task_graph_edge_create(struct TaskNode *from_node, struct TaskNode *to_node); + #ifdef __cplusplus } #endif diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index 18d58cdcaf3..8f1511ca118 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -119,6 +119,7 @@ set(SRC intern/string_utf8.c intern/string_utils.c intern/system.c + intern/task_graph.cc intern/task_iterator.c intern/task_pool.cc intern/task_range.cc diff --git a/source/blender/blenlib/intern/task_graph.cc b/source/blender/blenlib/intern/task_graph.cc new file mode 100644 index 00000000000..9a7f18c8348 --- /dev/null +++ b/source/blender/blenlib/intern/task_graph.cc @@ -0,0 +1,161 @@ +/* + * 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. + */ + +/** \file + * \ingroup bli + * + * Task graph. + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_task.h" + +#include <memory> +#include <vector> + +#ifdef WITH_TBB +/* Quiet top level deprecation message, unrelated to API usage here. */ +# define TBB_SUPPRESS_DEPRECATED_MESSAGES 1 +# include <tbb/flow_graph.h> +# include <tbb/tbb.h> +#endif + +/* Task Graph */ +struct TaskGraph { +#ifdef WITH_TBB + tbb::flow::graph tbb_graph; +#endif + std::vector<std::unique_ptr<TaskNode>> nodes; + +#ifdef WITH_CXX_GUARDEDALLOC + MEM_CXX_CLASS_ALLOC_FUNCS("task_graph:TaskGraph") +#endif +}; + +/* TaskNode - a node in the task graph. */ +struct TaskNode { + /* TBB Node. */ +#ifdef WITH_TBB + tbb::flow::continue_node<tbb::flow::continue_msg> tbb_node; +#endif + /* Successors to execute after this task, for serial execution fallback. */ + std::vector<TaskNode *> successors; + + /* User function to be executed with given task data. */ + TaskGraphNodeRunFunction run_func; + void *task_data; + /* Optional callback to free task data along with the graph. If task data + * is shared between nodes, only a single task node should free the data. */ + TaskGraphNodeFreeFunction free_func; + + TaskNode(TaskGraph *task_graph, + TaskGraphNodeRunFunction run_func, + void *task_data, + TaskGraphNodeFreeFunction free_func) + : +#ifdef WITH_TBB + tbb_node(task_graph->tbb_graph, + tbb::flow::unlimited, + std::bind(&TaskNode::run, this, std::placeholders::_1)), +#endif + run_func(run_func), + task_data(task_data), + free_func(free_func) + { + } + + TaskNode(const TaskNode &other) = delete; + TaskNode &operator=(const TaskNode &other) = delete; + + ~TaskNode() + { + if (task_data && free_func) { + free_func(task_data); + } + } + +#ifdef WITH_TBB + tbb::flow::continue_msg run(const tbb::flow::continue_msg UNUSED(input)) + { + tbb::this_task_arena::isolate([this] { run_func(task_data); }); + return tbb::flow::continue_msg(); + } +#endif + + void run_serial() + { + run_func(task_data); + for (TaskNode *successor : successors) { + successor->run_serial(); + } + } + +#ifdef WITH_CXX_GUARDEDALLOC + MEM_CXX_CLASS_ALLOC_FUNCS("task_graph:TaskNode") +#endif +}; + +TaskGraph *BLI_task_graph_create(void) +{ + return new TaskGraph(); +} + +void BLI_task_graph_free(TaskGraph *task_graph) +{ + delete task_graph; +} + +void BLI_task_graph_work_and_wait(TaskGraph *task_graph) +{ +#ifdef WITH_TBB + task_graph->tbb_graph.wait_for_all(); +#endif +} + +struct TaskNode *BLI_task_graph_node_create(struct TaskGraph *task_graph, + TaskGraphNodeRunFunction run, + void *user_data, + TaskGraphNodeFreeFunction free_func) +{ + TaskNode *task_node = new TaskNode(task_graph, run, user_data, free_func); + task_graph->nodes.push_back(std::unique_ptr<TaskNode>(task_node)); + return task_node; +} + +bool BLI_task_graph_node_push_work(struct TaskNode *task_node) +{ +#ifdef WITH_TBB + if (BLI_task_scheduler_num_threads() > 1) { + return task_node->tbb_node.try_put(tbb::flow::continue_msg()); + } +#endif + + task_node->run_serial(); + return true; +} + +void BLI_task_graph_edge_create(struct TaskNode *from_node, struct TaskNode *to_node) +{ +#ifdef WITH_TBB + if (BLI_task_scheduler_num_threads() > 1) { + tbb::flow::make_edge(from_node->tbb_node, to_node->tbb_node); + return; + } +#endif + + from_node->successors.push_back(to_node); +} diff --git a/tests/gtests/blenlib/BLI_task_graph_test.cc b/tests/gtests/blenlib/BLI_task_graph_test.cc new file mode 100644 index 00000000000..efcbf923625 --- /dev/null +++ b/tests/gtests/blenlib/BLI_task_graph_test.cc @@ -0,0 +1,188 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" + +#include "MEM_guardedalloc.h" + +#include "BLI_task.h" + +struct TaskData { + int value; + int store; +}; + +static void TaskData_increase_value(void *taskdata) +{ + TaskData *data = (TaskData *)taskdata; + data->value += 1; +} +static void TaskData_decrease_value(void *taskdata) +{ + TaskData *data = (TaskData *)taskdata; + data->value -= 1; +} +static void TaskData_multiply_by_two_value(void *taskdata) +{ + TaskData *data = (TaskData *)taskdata; + data->value *= 2; +} + +static void TaskData_multiply_by_two_store(void *taskdata) +{ + TaskData *data = (TaskData *)taskdata; + data->store *= 2; +} + +static void TaskData_store_value(void *taskdata) +{ + TaskData *data = (TaskData *)taskdata; + data->store = data->value; +} + +static void TaskData_square_value(void *taskdata) +{ + TaskData *data = (TaskData *)taskdata; + data->value *= data->value; +} + +/* Sequential Test for using `BLI_task_graph` */ +TEST(task, GraphSequential) +{ + TaskData data = {0}; + TaskGraph *graph = BLI_task_graph_create(); + + /* 0 => 1 */ + TaskNode *node_a = BLI_task_graph_node_create(graph, TaskData_increase_value, &data, NULL); + /* 1 => 2 */ + TaskNode *node_b = BLI_task_graph_node_create( + graph, TaskData_multiply_by_two_value, &data, NULL); + /* 2 => 1 */ + TaskNode *node_c = BLI_task_graph_node_create(graph, TaskData_decrease_value, &data, NULL); + /* 2 => 1 */ + TaskNode *node_d = BLI_task_graph_node_create(graph, TaskData_square_value, &data, NULL); + /* 1 => 1 */ + TaskNode *node_e = BLI_task_graph_node_create(graph, TaskData_increase_value, &data, NULL); + /* 1 => 2 */ + const int expected_value = 2; + + BLI_task_graph_edge_create(node_a, node_b); + BLI_task_graph_edge_create(node_b, node_c); + BLI_task_graph_edge_create(node_c, node_d); + BLI_task_graph_edge_create(node_d, node_e); + + EXPECT_TRUE(BLI_task_graph_node_push_work(node_a)); + BLI_task_graph_work_and_wait(graph); + + EXPECT_EQ(expected_value, data.value); + BLI_task_graph_free(graph); +} + +TEST(task, GraphStartAtAnyNode) +{ + TaskData data = {4}; + TaskGraph *graph = BLI_task_graph_create(); + + TaskNode *node_a = BLI_task_graph_node_create(graph, TaskData_increase_value, &data, NULL); + TaskNode *node_b = BLI_task_graph_node_create( + graph, TaskData_multiply_by_two_value, &data, NULL); + TaskNode *node_c = BLI_task_graph_node_create(graph, TaskData_decrease_value, &data, NULL); + TaskNode *node_d = BLI_task_graph_node_create(graph, TaskData_square_value, &data, NULL); + TaskNode *node_e = BLI_task_graph_node_create(graph, TaskData_increase_value, &data, NULL); + + // ((4 - 1) * (4 - 1)) + 1 + const int expected_value = 10; + + BLI_task_graph_edge_create(node_a, node_b); + BLI_task_graph_edge_create(node_b, node_c); + BLI_task_graph_edge_create(node_c, node_d); + BLI_task_graph_edge_create(node_d, node_e); + + EXPECT_TRUE(BLI_task_graph_node_push_work(node_c)); + BLI_task_graph_work_and_wait(graph); + + EXPECT_EQ(expected_value, data.value); + BLI_task_graph_free(graph); +} + +TEST(task, GraphSplit) +{ + TaskData data = {1}; + + TaskGraph *graph = BLI_task_graph_create(); + TaskNode *node_a = BLI_task_graph_node_create(graph, TaskData_increase_value, &data, NULL); + TaskNode *node_b = BLI_task_graph_node_create(graph, TaskData_store_value, &data, NULL); + TaskNode *node_c = BLI_task_graph_node_create(graph, TaskData_increase_value, &data, NULL); + TaskNode *node_d = BLI_task_graph_node_create( + graph, TaskData_multiply_by_two_store, &data, NULL); + BLI_task_graph_edge_create(node_a, node_b); + BLI_task_graph_edge_create(node_b, node_c); + BLI_task_graph_edge_create(node_b, node_d); + EXPECT_TRUE(BLI_task_graph_node_push_work(node_a)); + BLI_task_graph_work_and_wait(graph); + + EXPECT_EQ(3, data.value); + EXPECT_EQ(4, data.store); + BLI_task_graph_free(graph); +} + +TEST(task, GraphForest) +{ + TaskData data1 = {1}; + TaskData data2 = {3}; + + TaskGraph *graph = BLI_task_graph_create(); + + { + TaskNode *tree1_node_a = BLI_task_graph_node_create( + graph, TaskData_increase_value, &data1, NULL); + TaskNode *tree1_node_b = BLI_task_graph_node_create(graph, TaskData_store_value, &data1, NULL); + TaskNode *tree1_node_c = BLI_task_graph_node_create( + graph, TaskData_increase_value, &data1, NULL); + TaskNode *tree1_node_d = BLI_task_graph_node_create( + graph, TaskData_multiply_by_two_store, &data1, NULL); + BLI_task_graph_edge_create(tree1_node_a, tree1_node_b); + BLI_task_graph_edge_create(tree1_node_b, tree1_node_c); + BLI_task_graph_edge_create(tree1_node_b, tree1_node_d); + EXPECT_TRUE(BLI_task_graph_node_push_work(tree1_node_a)); + } + + { + TaskNode *tree2_node_a = BLI_task_graph_node_create( + graph, TaskData_increase_value, &data2, NULL); + TaskNode *tree2_node_b = BLI_task_graph_node_create(graph, TaskData_store_value, &data2, NULL); + TaskNode *tree2_node_c = BLI_task_graph_node_create( + graph, TaskData_increase_value, &data2, NULL); + TaskNode *tree2_node_d = BLI_task_graph_node_create( + graph, TaskData_multiply_by_two_store, &data2, NULL); + BLI_task_graph_edge_create(tree2_node_a, tree2_node_b); + BLI_task_graph_edge_create(tree2_node_b, tree2_node_c); + BLI_task_graph_edge_create(tree2_node_b, tree2_node_d); + EXPECT_TRUE(BLI_task_graph_node_push_work(tree2_node_a)); + } + + BLI_task_graph_work_and_wait(graph); + + EXPECT_EQ(3, data1.value); + EXPECT_EQ(4, data1.store); + EXPECT_EQ(5, data2.value); + EXPECT_EQ(8, data2.store); + BLI_task_graph_free(graph); +} + +TEST(task, GraphTaskData) +{ + TaskData data = {0}; + TaskGraph *graph = BLI_task_graph_create(); + TaskNode *node_a = BLI_task_graph_node_create( + graph, TaskData_store_value, &data, TaskData_increase_value); + TaskNode *node_b = BLI_task_graph_node_create(graph, TaskData_store_value, &data, NULL); + BLI_task_graph_edge_create(node_a, node_b); + EXPECT_TRUE(BLI_task_graph_node_push_work(node_a)); + BLI_task_graph_work_and_wait(graph); + EXPECT_EQ(0, data.value); + EXPECT_EQ(0, data.store); + BLI_task_graph_free(graph); + /* data should be freed once */ + EXPECT_EQ(1, data.value); + EXPECT_EQ(0, data.store); +} diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt index a0621448630..6fbb304581d 100644 --- a/tests/gtests/blenlib/CMakeLists.txt +++ b/tests/gtests/blenlib/CMakeLists.txt @@ -72,6 +72,7 @@ BLENDER_TEST(BLI_string_map "bf_blenlib") BLENDER_TEST(BLI_string_ref "bf_blenlib") BLENDER_TEST(BLI_string_utf8 "bf_blenlib") BLENDER_TEST(BLI_task "bf_blenlib;bf_intern_numaapi") +BLENDER_TEST(BLI_task_graph "bf_blenlib;bf_intern_numaapi") BLENDER_TEST(BLI_vector "bf_blenlib") BLENDER_TEST(BLI_vector_set "bf_blenlib") |