Thread by @SebAaltonen

First draft of a job system API.

LaunchJob() schedules a job. Job is eligible for execution when the array of existing jobs have been finished. Job scheduler only schedules jobs if they don't have resource conflicts. 1x ReadWrite or multiple ReadOnly for each resource...

Resources are 64 bit void pointers. Job body is declared as a lambda function. It can capture data from the scope. It's common to capture the resources and some other data by value. Can also capture pointer to temp allocated storage (linear frame allocator).

If you want to run an ECS system on top of this, each component table in the ECS system would be a resource (64 bit pointer to an object). ReadWrite access ensures that only one job can run at once modifying the same component table. Multiple ReadOnly accesses run concurrently.

There's no mutexes/semaphores in this system. You use resource accesses to control what can run concurrently. User land code has no naked sync primitives and never stalls waiting for a mutex. And never deadlocks.

Jobs can spawn other jobs. If you want to elevate your resource access, you need to spawn a continuation job with different set of ReadOnly/ReadWrite resources. Scheduler runs that job once the resources are free to use.

This design doesn't need a main thread or render thread at all. It's actually preferable to avoid the main thread completely, as that solves all main thread bottlenecks elegantly. You could have a job that spawns the main jobs needed for a frame, and then it spawns itself again.

For convenience there would be a function to combine job dependencies. Like this:

Job frameFinished = combineJobDependencies(gameJob, renderJob);

The job that starts next frame and kicks all next frame jobs would depend on frameFinished.

The low level scheduler has one worker thread per core. Threads execute jobs from their queue. Job stealing is lockfree. Threads steal half of the jobs from other thread when their own job queue runs out of work (lazy binary splitting algorithm).

Resources and dependencies are solved in high level scheduler which runs when a thread fails to steal work (nothing is left). The thread finishing first runs the dependency solver and fills the work stealing queues of all threads. So they can run ASAP. This way we avoid a bubble.

That's it basically. I don't think we need anything more complex than that. Implementation should be <1000 lines of standard C/C++ code.

Some technical tidbits:

The examples use initializer_lists to provide the dependencies and resources. This is enabled by using slice/span abstraction in the interface. No memory allocs are required to provide these variable length datas.

https://twitter.com/SebAaltonen/status/1502640283502227465?s=20&t=VaJ8_waYcRW7sHTONAGwFw

C/C++ guarantees that temporary objects used in function parameter list live until the function body returns. This means that initializer_list is safe to pass to a slice/span function parameter.

We don't use std::function to store the lambda, since std::function allocates memory (small size optimization only covers 64 bits IIRC). Instead we use a custom function implementation that doesn't allocate.

The dependency/resource arrays and the lambda captured variables are stored in a big ring buffer inside the scheduler. This is just a bump allocator (offset += size). Scheduling and executing jobs doesn't allocate any memory (no malloc/new).

Link to the Lazy Binary Splitting paper:
terpconnect.umd.edu/~barua/ppopp16…

It's a very simple and efficient algorithm. Split the remaining work to half. That's it basically :)

Clarification: The scheduled jobs are stored immediately to the ring buffer and the function returns to caller. The execution of the jobs starts once the higher level scheduler has resolved the depedencies (work queues are empty) and jobs are pushed to per-thread queues.