CommitQueue - A turn based Queue for Reduced Contention

date: 2026-09-07
author: Peterino

Look at this profile trace, one might be tempted to look at it and think "Our game is slow because we're single threaded, I think we can make animations go wide."

So lets go wide!

A simple algorithm for this is simply take the work and spin up some number of workers, and push work to them (say 4 in this case)

# old, single threaded, simple
Actor.OnTick():
    outputPose = animator.animate();

# new 

# 1. spin up workers
for i in range(0, N):
    spawnWorker(animationWorker)

# 2. gather work 
workDispatched = 0
workComplete = 0

Actor.OnTick():
    queueWork(animator.getWork())
    workDispatched += 1
    
# spin until work is complete or you can join in and pick up work yourself 
while(workComplete.atomic_load() != workDispatched) 
    
# 3. workers pick up work and notify the amount of work done
def workerFunc(work):
    work = queue.takeWork()
    while work != null:  
        doAnimationWork(work)
        workComplete.atomic_add(1);
    # you'll want to retire these workers when it's done. 

Any Locked or lock-free queue can implement this, but here's a real example seen with the legendary MPMC queue from rigtorp (which i believe originally came from EA's frostbite)

https://github.com/rigtorp/MPMCQueue

But something is wrong here... if we sum up all of those individual blocks.

4.0 + 2.9 + 3.0 + 2.8 + 0.4 = 13.1ms We ended up using more cpu time overall not less, in this case 31% more. You might think "well that's fine, we ended up with better fps"

Well... like most things in game engine tooling "It's not a problem until it is". Let me ask you this- what happens when every subsystem in your game wants the same treatment?

Suddenly the cost of concurrency rears it's ugly head, and we don't have enough cores for this.

So what is wrong with our algorithm?

Well there are two things that are potentially issues. Think about what is happening on the queue. Each time we need to send data into a data structure or format in a way that will cross cores, we need to pay a concurrency cost. So we're paying a cost for each unit of work we push into the queue- and also a cost for each time we take work out of the queue.

Imagine each of those red lines just being wasted cpu time, the core aint doing anything but syncing.

A well crafted parallel for can potentially help here but only if we have the luxury of being able to separate out the work cleanly by itself. Which given the Actor.OnTick binding, probably isn't so easy (and oftentimes is the case.)

Enter the Commit Queue

No idea if there is a real name for this thing yet but I'm calling it that. This is a pretty easy format to arrive at if you're working from first principles and just asking yourself "how can I reduce the number of concurrency events?"

Lets define what we want here. I want a queue that is

1. Single Producer Multi Consumer - SPMC
2. must operate on data chunks numbering in the 10s of thousands
3. cost must be negligible or zero relative to pure cpu sided work that is around 10ms

So first lets start by recording work.

For this, all we need to do is create a buffer and start recording work. on the producer's side this is literally just a threadlocal buffer recording, zero concurrency cost at all

Secondly lets define what the consumer looks like

When the reader conducts a read, remaining_items and active_readers are atomically updated. You can encode the two of them together like this to do atomic CAS instructions to update both states in one shot.

struct PackedState = packed struct(u32){
    active_readers: u8,
    remaining_items: u24,
};

remaining_items gets decremented and active_readers goes up, via a cas loop. when a worker claims a slot, when a worker is done copying out the slot or is done work, it can use an atomic fetch-subtract

and the API just looks like this:

Consumer side:

work = queue.takeWork();
if(work != null) doWork(work);

Producer side:

try queue.push(work);
// once a batch has been produced, commit the work swapping both buffers

queue.commit();

pub fn canCommit(self: *@This()) void {
    const s = self.state.load(.acquire);
    return s.remaining_entries == 0 && s.active_readers == 0;
}

pub fn commit(self: *CommitQueue) void{
    while (!self.canCommit()) { spinHint(); }
    std.mem.swap(@TypeOf(work), self.committed, self.submitting);
}

Those commit operations are safe because the workers can only ever decrement remaining_entries, and cas loop increment active_readers while operating and decrement when they're done. The way I implement this commit will stall if there are still any active readers or remaining queue items not yet disbursed.

Now here's the awesome part. Because the workers are completely divorced from the reader's queue submission. it is possible for the queue to enact a chunking or 'skip' policy, which gives you a lot of control over how much work each worker decides to take for each concurrency operation.

Now a data structure discussion aint complete without some benchmarking so let's see some benchmarks.

In a synthetic test where we need to submit 10k items batched once every single frame (these are 16 byte synthetic entries with no work in them)

the commit based queue pushes 64% more items than the arbitrary MPMC queue with 2 workers

But the performance begins to degrade as more workers get introduced

But the fact that it gets worse with more consumers, I think has to do with that fact that our contention story on the consumer side is probably worse than rigtorp's MPMC, we implement our current consume with two CAS loops.

Because we do a publish then take strategy- we actually have the interesting capability of setting a specific chunk size, that is when a worker takes- instead of paying the cost of taking from the queue for every single object, we could... just take some number events at once for the worker?

This can be set as a policy on the consumer side of the algorithm. So... by chunking the takes with a 256 events per take

results are pretty dramatic, when chunking is enabled at a modest 256- the cost of the concurrency overhead is almost 14x lower for just one consumer, and 41x lower when there's more cores being used.

Hope this gives you ideas, and helps you reduce your contention!

A reference implementation of the full chunked SPMC is here spmc.zig