Introduction

Hello there, since this is the first post I’m making, I’ll also do a little introduction. I first started programming at the age of 11, and quickly decided that I wanted to work with making games. At some point down the line I realized that gameplay programming was not for me, but that working on game engines was what I was meant to do. I also got exposed to graphics/rendering programming at some point and went down that path, so that’s how I ended up where I am now. I’ve been working as a Graphics Programmer at Playdead for ~2.5 years now.

Now what is ‘Volt’? Volt is the game engine that me and some co-students made during our last year at The Game Assembly. The engine was specifically made to power the different projects we made during our last year (an example: Vipertrace). Unfortunatley the games ran pretty poorly due to lack of time. After school ended, me and a couple of friends decided to continue work on the engine as a side project in our spare time. Now to the actual Job System.

Background

Initially Volt wasn’t made for multithreading, but as we remade most systems, multithreading was one of the main goals. Initially a pretty simple job system was implemented using threads, it had job stealing and was built on similar principles, such as using counters as ‘signals’ for when jobs are finished. It later evolved a bit, adding priorities and using lockless queues for jobs.

I had seen the GDC talk Parallelizing the Naughty Dog Engine Using Fibers by Christian Gyrling from Naughty Dog, which is where the inspiration for the counters came from, and decided that I wanted to try to convert the job system in Volt to using fibers.

Fiber vs Thread

A thread uses preemptive scheduling, which means that the OS can, at any point, interrupt the thread execution and assign work to another thread. Fibers on the other hand use cooperative scheduling, meaning that they themselves yield to allow other fibers to be worked on. Important to note is that a fiber dosen’t run by itself, but it is executed on a thread. This means that a thread can run any number of fibers, since the fiber contains the execution context it self.

Since the fiber contains the execution context, a fiber can be yielded and the worker can pickup another fiber and do some work. The switch happens by reading out the current state of certain registers (mentioned later), and writing some other state to those same registers. This mechanism is used whenever a job needs to wait on a counter, which allows the worker to progess on another fiber.

You do have to be extra careful not to call blocking calls inside of a fibers execution, since that could lead to a deadlock. That problem is usually dealt with by having a set of background thread that do blocking work. In Volt we have the IOThreads, which fibers can use to send requests to do blocking calls such as IO.

Features

  • Priorities
  • Yielding
  • Waitlisting
  • Execution policy
  • Different stack sizes

Implementation

Fiber Context

Currently, the only platform Volt supports in Win64. Win64 has its own fibers, but they have some downsides, such as being expensive to create and you can not manage your own stack space. So instead I decided to roll my own, using this as a reference. Essentially, instead of keeping a OS primitive which contains the state, we have our own state, which we acquire and set through a couple of small ASM functions.

Our fiber context struct:

struct FiberContext
{
	void* rip, * rsp;
	void* rbx, * rbp, * r12, * r13, * r14, * r15, * rdi, * rsi;

	alignas(16) __m128i xmm6, xmm7, xmm8, xmm9, xmm10, 
        xmm11, xmm12, xmm13, xmm14, xmm15;

	// TEB
	void* stackBase;
	void* stackLimit;
	void* exceptionList;
	void* deallocationStack;

	// SSE & x87 FPU
	uint32_t mxcsr;
	uint32_t fpucw;

	void* userdata;
};

A couple of additions to the reference is the TEB (Thread Environment Block), SSE and FPU values. The TEB is mostly to keep the debugger happy, since it otherwise might think that we are accessing memory out of bounds, since we use different stack space than what has been allocated for the executing thread. The SSE and FPU stored values are just to ensure that we don’t accidentally switch SSE and FPU modes. Because a fiber context simply is a struct of registers, there is not limit to how many we can have. Instead the maximum number of fibers are determined by the number of fiber stacks we have. which end up being a more limited resource, since they can take up quite a chunk of memory. Even though we could have an ‘unlimited’ amount of fiber contexts, we still have a pool of them, mostly for organizational purposes, a fiber is assigned a stack, name and id, which needs to be kept track of.

Fiber Stacks

Currently we have five different fiber stack sizes starting at 16KB ending at 512KB. Since most stack heavy work (e.g shader compilation, mesh import) should not happen on fibers, it is often enough to use the 16KB-64KB range. The fiber stacks can be allocated normally using malloc, but it is advantageous to use the OS allocator directly, since that allows for setting up a guard page, which ensures that we crash on a stack overflow. Using this we can also set up an exception handler which tells the user that it was a stack overflow. The fiber stacks are kept in a lockless stack structure for quick acquiring and returning once a job has finished. The fiber stack management can be found here.

Job Counters

Job counters are essentially just an atomic integer, that helps keep track of if a job is finished or not. The job counters are reference counted to ensure reuse doesn’t happen while something references the counter. The job counter also ties into the waiting list feature, it holds the ‘head’ of the waiting list, which is a linked list. Each node is a job, which links to the next job in the waiting list. Having the waiting list linked to the counter like this helps to keep latency low when starting the jobs which were waiting.

The counter data looks something like this:

struct JobCounter
{
    std::atomic<Job*> waiterHead;
    std::atomic<int32_t> counter;
    std::atomic<int32_t> referenceCount;
    std::atomic<uint32_t> isCompleted;
};

As you might have noticed there also is a atomic value called ‘isCompleted’, this is used by non worker threads (e.g the main thread) when they want to wait for a counter, by using the std::atomic::wait functionality.

Jobs

The job structure is the container for everything required to run a job, it holds its priority, execution policy, assigned fiber and more. A job have two different types of counters assigned to it: the ‘wait counter’ and one or more ‘associated counter’. The wait counter, quite obviosly, is the counter which the job needs to wait on, if the counter is not ready when the job is enqueued, it will end up on the waiting list of that counter. The associated counters are the counters which are decremented when a job has finished, these counters are the ones that other jobs wait on.

JobSystem

The JobSystem is the root of the system, it hosts the workers and jobs are queued through it.

Workers and Job Stealing

The process for a worker looks something like this:

  • Try to get a previously yielded job
  • If no job was yielded try to get a job from its queues
  • If no job was queued on the worker, try to steal a job from another worker
  • If a job was found, execute it, else wait.

We always try to run previously yielded jobs, which includes jobs from the waiting list, to reduce latency as much as possible. Otherwise we always try to run the jobs in the order of priority. If no work was available, we wait for some to be. Instead of using condition variables and a mutex, we use the new since C++20, std::counting_semaphore, which is extremely easy to use. To notify that a new ‘item’ is available you only need to call std::counting_semaphore::release, and to decrease the items available, you only need to call std::counting_semaphore::acquire, which will wait if the counter was zero.

Waiting list

As previously mentioned, the waiting list is located directly on the counter, instead of being a structure in the JobSystem. This means that it’s a quick process to queue all the jobs that were waiting on a counter. The worker that finishes a counter, can simply iterate the list and queue them.

The waiting list consists of three parts, the head on the counter, the next waiter on the job, and the enqueueing mechanism in the JobSystem. The counter:

class JobCounter
{
	...
	std::atomic<Job*> waiterHead;
	...
}

The job:

class Job
{
	...
	Job* m_nextWaiter;
	...
}

And the enqueueing mechanism:

bool JobSystem::TryEnqueueJobOnCounter(JobCounterRef counter, JobRef job)
{
	while (true)
	{
		JobRef listHead = counter->m_waiterHead.load(std::memory_order::acquire);
		if (listHead == JobCounter::WaitingListClosed)
		{
			// Counter was completed.
			return false;
		}

		job->m_nextWaiter = listHead;
		if (counter->m_waiterHead.compare_exchange_weak(
			listHead, job,
			std::memory_order::release,
			std::memory_order::acquire))
		{
			// Successfully enqueued.
			return true;
		}
	}

	return false;
}

Using an atomic as the ‘waiterHead’ means that

  1. Enqueueing is lockless.
  2. We can ensure that if this function fails, the counter has been completed, and the job can be run directly.
Interface

The minimal create job interface looks like the following:

template<typename Func> 
static Job* CreateJob(StringView jobName, ExecutionPriority priority, Func&& func, FiberStackSize stackSize);

CreateJob returns a JobRef (Job*), this job has not yet been queued, to queue it the user must call the ‘RunJob’ function:

static void RunJob(Job* job);

Example usage:

JobRef job = JobSystem::CreateJob("TestJob", ExecutionPriority::Immediate, []()
{
    VT_LOG(Trace, "Hello from TestJob!");
});

JobSystem::RunJob(job);

Most of the time though, we don’t use the JobSystem interface directly, instead we use our TaskGraph. The TaskGraph is a quick and simple way to build a graph of jobs that relate to eachother. It automates the process of setting up the correct counters to handle dependencies, since jobs that relate to eachother need to have the correct associated and wait counters.

Interface of the TaskGraph:

class TaskGraph
{
	...
	template<typename Func>
	TaskGraph::Task* AddTask(StringView name, Func&& func, FiberStackSize stackSize = FiberStackSize::KB16);
	template<typename Func> 
	
	TaskGraph::Task* AddTaskWithDependencies(StringView name, std::span<TaskGraph::Task*> dependencies, Func&& func, FiberStackSize stackSize = FiberStackSize::KB16);
	template<typename Func> 
	
	TaskGraph::Task* AddTaskWithDependencies(StringView name, std::initializer_list<TaskGraph::Task*> dependencies, Func&& func, FiberStackSize stackSize = FiberStackSize::KB16);

	void Execute();
	JobCounterRef ExecuteAndExtractCounter();
	void ExecuteAndWait();
	void Wait();
	...
}

Simple example usage of the TaskGraph:

TaskGraph taskGraph{ ExecutionPriority::Immediate };

for (const Filesystem::Path& assetFilepath : engineAssetFilepaths)
{
	taskGraph.AddTask("Deserialize Engine Asset Metadata", [this, &assetFilepath]() 
	{
		AssetMetadata assetMetadata{};
		assetMetadata.isEngineAsset = true;

		DeserializeAssetMetadata(assetFilepath, assetMetadata);
		if (assetMetadata.IsValid())
		{
			InsertAssetMetadata(std::move(assetMetadata));
		}
	}, FiberStackSize::KB32);
}

taskGraph.ExecuteAndWait();

References