Simple multithreading tricks

Today I’d like to share a simple multithreading trick you can use to minimize “bubbles” in your pipeline. “Simple” because it applies mostly to “oldschool” threading systems, ie. the ones with main thread concept that kicks jobs and eventually flushes them. Cool kids using proper task graphs where everything just flows beautifully should not need it. Imagine we have a simple scenario, our thread produces some work, continues with whatever it’s doing, eventually waits for the job to finish (ideally this overlaps the work from previous point, so not much to do here) and processes results. The most straightforward approach might look like:

KickJobs();

DoSomething();

FlushJobs(); // ***
ProcessResults();

Now, a line marked with stars is the problematic one. In a perfect world, our job is finished by the time we reach it, so we just early out somewhere and process the results. If that’s your case and we can guarantee it, we’re done. If, however, we’re not so lucky, we’ll now either wait before we can process or hopefully help with some of the ‘leftovers’. It’s possible we could be already processing the results, while workers finish the remaining ones, but we can’t do it in this approach as it’s “all or nothing”. It’s quite simple to tweak, luckily. All we have to do is to add a flag per item, signaling whether it’s done or not. Worker thread processes an item, publishes result and sets the flag. Main thread does not flush immediately, instead it actually tries to process items that are ready (remember about your barriers!). If not ready, we simply ignore it for now, we can either keep it on the list or move to another one, to be processed later. Rough code:

// Job
// ..do your thing
// publish results
MEMORY_WRITE_BARRIER();
jobData.isInFlight = false;

// Main thread
KickJobs();

DoSomething();

// No flush yet!
for(auto& result : jobResults)
{
    if(result.isInFlight)
    {
        remainingResults.push_back(result);
        continue;
    }
    MEMORY_READ_BARRIER();
    // Process 'result'
}
FlushJobs();
ProcessRemainingResults();

Of course, this only makes sense if workers are ‘mostly done’. If you end up with most of your items still not ready, you’re not really saving much, it should not be used blindly. Another question is what do we do with items that are not ready yet.. Technically we could repeat what we’ve just done, ie. instead of flushing, just keep iterating until we’re done with them all, but it defeats the point a little bit and probably indicates your workers are simply taking too long (see previous point).