Taskflow Part 2

TaskFlow was initially conceived as a way to write Task structs fluently and to chain them together. But the initial implementation was far from what I really needed as it relied heavily on C#’s async/await. Internally, all this meant is:

* Execute a Task A on a separate thread
* Pause the main thread until Task A finishes
* Resumes the caller and executes Task B

You can do this without TaskFlow and execute everything using closures/lambdas and plain old C# tasks.

await Task.Factory.StartNew(() => {
    // Do some work here
});

await Task.Factory.StartNew(() => {
    // Do some extra work here
});

It honestly works and I can leave it like that, but I do want a way to write an entire graph of Tasks that executes in order. That’s where V2 of TaskFlow comes in. It implements a dependency graph that allows you to chain tasks together first and then executes the context later. An example from from the test is:

private class RefInt {
    public int Value;
}

private struct S : ITaskFor {
    public RefInt RefInt;
    public readonly void Execute(int index) {
        RefInt.Value = Interlocked.Increment(ref RefInt.Value);
    }
}

TaskHandle handleA = new S { }.Schedule();
TaskHandle handleB = new S { }.Schedule(handleA);
TaskHandle handleC = new S { }.Schedule(handleA);
TaskHandle handleD = new S { }.Schedule(handleC);
TaskHandle handleE = new S { }.Schedule();
TaskHandle handleF = new S { }.Schedule(handleB);

// This produces a graph executing tasks in groups of
// A E - Group 1
// B C - Group 2
// F D - Group 3

ITaskFor  

Previously, I implemented ITask and ITaskParallelFor which are meant for single unit tasks and multi unit jobs respectively. That path has gone the way of the dodo and converged to a struct implementing: ITaskFor. When you implement ITaskFor, you can call the Schedule(...) API to make it a single or multi unit task.

TaskHandle  

I ditched the concept of a returnable Task and returned a TaskHandle instead. TaskHandles are struct that contain mostly blittable data. Internally, it contains the following members

• LocalHandle
• GlobalHandle
• FixedUInt16Array32
• ITaskDefPoolable

LocalHandle  

Because all tasks are structs, they also need to be stored somewhere to later execution. This causes an ITaskFor struct to be boxed and allocated on the heap. To avoid the garbage collector from running, all ITaskFor structs are stored in a static container of its own type and reused. When scheduling a new ITaskFor, we copy the user constructed ITaskFor into the static container. The LocalHandle provides a way internally for me to access the correct ITaskFor in the static container.

A LocalHandle is an alias for a UInt16 or ushort data type.

GlobalHandle  

The GlobalHandle represents the TaskHandle’s unique ID. You cannot have a duplicate TaskHandle returned when scheduling ITaskFors.

A GlobalHandle is an alias for a UInt16 or ushort data type.

FixedUInt16Array32  

ITaskFor structs can depend on other ITaskFor structs. At most, a TaskHandle can store up to 32 unique dependencies. In the code example above, handleA is considered the root as it is scheduled without any dependencies.

handleB relies on handleA, so when executing the Tasks, handleA must run first before handleB runs. The FixedUInt16Array32 stores the GlobalHandle from dependent TaskHandles.

ITaskDefPoolable  

All ITaskFor structs are stored in static containers. To access the ITaskFor structs our LocalHandle serves as an index into the internal array defined by implementations of ITaskDefPoolable.

Sorting the Order  

When scheduling a new ITaskFor, they are all

1. Stored into a TaskGraph

2. Topologically sorted

   • a. Visit each ITaskFor (the key for an ITaskFor is the TaskHandle’s GlobalHandle) and keep track of which one is visited.
   • b. If we have a valid ITaskFor stored in the TaskGraph, then we keep track of the dependencies in a linear adjacency matrix and increment the total number of edges that comes from the TaskHandle.
   • c. Once all the TaskHandles are tracked, enqueue all of the TaskHandles into a queue.
   • d. Dequeue all of the Taskhandles and check the current number of edges the TaskHandle has. If the total number of edges is 0, we queue the ITaskFor in an ordered array. We keep track of each queued ITaskFor because we need to know which ITaskFor can be grouped together to run in parallel.

   For example, if we write the following:

   TaskHandle handleA = new SomeTask { }.Schedule();
   TaskHandle handleB = new SomeTask { }.Schedule();
   
   TaskHandle handleC = new SomeTask { }.Schedule(handleB);
   TaskHandle handleD = new SomeTask { }.Schedule();

   We need 2 groups of ITaskFors. The first group will run, A, B, and D, because they run without any additional dependencies. The last group will consist of C, because it relies on ITaskFor B to finish first.

3. Lastly, we run the TaskGraph. We run through each group and request a worker to run. Any multi-unit ITaskFor will request multiple workers and wait on them until all workers from every ITaskFor in the group finish.