From 9ef272bae31931fe9afc0c037259fd936540ae0b Mon Sep 17 00:00:00 2001 From: Jeroen Bakker Date: Mon, 25 May 2020 12:24:56 +0200 Subject: Task: Graph Flow Task Scheduling Add TBB::flow graph scheduling to BLI_task. Using flow graphs, a graph of nodes (tasks) and links can be defined. Work can flow though the graph. During this process the execution of the nodes will be scheduled among the available threads. We are planning to use this to improve the threading in the draw manager. The implemented API is still limited it only supports sequential flows. Joins and buffers are not supported. We could eventually support them as part of an CPP API. These features from uses compile time templates and are hard to make a clean C-API for this. Reviewed By: Sergey Sharybin, Brecht van Lommel Differential Revision: https://developer.blender.org/D7578 --- tests/gtests/blenlib/BLI_task_graph_test.cc | 188 ++++++++++++++++++++++++++++ tests/gtests/blenlib/CMakeLists.txt | 1 + 2 files changed, 189 insertions(+) create mode 100644 tests/gtests/blenlib/BLI_task_graph_test.cc (limited to 'tests/gtests') 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") -- cgit v1.2.3