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

2 files changed, 189 insertions, 0 deletions

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")