Thread Synchronization on the Xbox One Family

Andrew Farrier, Xbox Advanced Technology Group

Updated April 28th 2017

In this topic

Introduction

Tests

Xbox One X

Recommendations

Summary

Appendix A: Code samples

Introduction

Modern game architectures have some form of queue used to share data between threads. The most common usage for a shared queue is to contain a list of jobs for another thread to perform. These queues require some form of synchronization between at least a producer thread and a consumer thread.

This paper covers the most common patterns used to control access to a job queue and how the complexity of the jobs affects the overall performance. To be fully able to use the results of these tests, it is vital that you understand all forms of contention that may occur in your title. The most common contention is around a context switch that could be caused by the synchronization pattern and another thread taking the core.

The main takeaway from our tests is that it is preferable to break up your architecture into fewer jobs that are larger in complexity. This reduces the frequency of accessing the queue and thus lowers the cost of the synchronization pattern used. It is also vital that, if you choose to use a variant on a spin lock, you use the correct spin lock for your code.

The real costs from using various synchronization patterns is the extra contention it places on the system. In this white paper, we provide the details on the real-world costs associated with a variety of patterns.

Tests

Each test run consisted of 500 runs with the results summarized in Table 1. Graphs are also provided for the first 100 runs. Each test run per synchronization primitive consists of four different variations on number of jobs and number of operations per job resulting in the same number of total operations per run. An operation consists of a read from an array, multiplying that by a random number, and then using a new random value as the index into an array of output values. The input/output array is unique per thread; this removes any cache contention caused by shared operation data.

Table 1: Variations on number of jobs and number of operations per job.

Number of jobs Number of operations per job Total operations
52,000 100 5,200,000
5,200 1,000 5,200,000
520 10,000 5,200,000
52 100,000 5,200,000

Synchronization patterns

Special notes

You can view the code used for lock/unlock in Appendix A: Code Samples.

The threads for these tests were set up as follows:

Each of the queues use the same type of primitive to control access. In all cases, except for none, the six threads were started/stopped simultaneously. For none, they were run sequentially to protect against data race conditions.

Single thread

The baseline graph is from using a single job thread. The time to perform 52,000 jobs is the worst case and dominated by the cost of the synchronization primitive. This graph was pulled out on its own to highlight the core differences among the synchronization primitives.

The costs are as expected. The code is running sequentially single threaded. There is zero contention on the job queue. The cost is entirely dominated by the code generated for each form of synchronization. Spin counts have trivial code, CRITICAL_SECTION uses an interlocked compare and exchange mechanic when non-blocking, and std::mutex uses Slim Reader/Writer locks which have slightly more code before the interlocked compare and exchange on CRITICAL_SECTION.

Figure 1: Core differences among the synchronization primitives for 52,000 jobs and a single worker thread.

However, when we lower the job count to 520 jobs or 52 jobs, the overhead from the synchronization primitive disappears. The primitive is not being called enough to cause its overhead to be expensive relative to the cost of the job. Comparing the 52,000-job graph to the 520-job graph clearly shows the cost difference. You can see the median cost has gone from a best-case 95 milliseconds down to 90 milliseconds. The worst case (std::mutex) went from 107 milliseconds down to the same 90 milliseconds. The median for 5,200 jobs was 91 milliseconds, slightly higher than 520 jobs. The spikes are due to cache misses in that run related to other system threads running on the core.

Figure 2: Core differences among the synchronization primitives for 520 jobs and a single worker thread.

Multiple threads

By switching to four worker threads, we now require some type of thread-safe synchronization primitive to control access to the queue. The tests are still processing the same number of total jobs as the single-threaded version, but they are evenly spread across four worker threads as opposed to one worker thread.

Degenerate cases

Now that locking is required for queue access, we very quickly get one expensive and degenerate primitive at 52,000 jobs: std::mutex jumps to 1000 milliseconds versus 124 milliseconds on a single thread. The spin lock with a spin count of 1 has improved: it drops from 124 milliseconds to 41 milliseconds. The spin lock with a spin count of 100 drops by the same amount. The cost of calling the SwitchToThread function is very cheap; when there is no other thread ready to run, it will immediately return. There is no expensive context switch that can happen.

The cost is similar to the single threaded case. The overhead from the synchronization pattern controls the overall time. However, this single job queue is shared between all the worker threads. Due to the large number of calls into the queue, there’s a greater chance of contention and a thread stalling. Another thread is accessing the queue at the same time. This reduces the gain on performance drastically. Previously the best case was the spin lock at 95ms; going to 4 threads only reduced the overall time to 45ms. That’s slightly more than a twofold improvement, even though it’s across 4 threads.

Figure 3: Core differences among the synchronization primitives for 52,000 jobs and multiple worker threads.

When we lower the job count to 520, the time on the different primitives converge. The median cost for all synchronization primitives is 23 milliseconds. The total cost of 520 jobs single-threaded with no synchronization primitive was around 87 milliseconds in the best case. A perfect speedup would be four times faster across four threads. In this case, we’ve achieved a speedup of 3.78, which is very respectable. The reason for not hitting four times faster is the usage contention on the single locking primitive used. There is still a chance that a thread needs to wait for access, and there are some cache collisions on the single shared synchronization primitive. The volatility on the spin locks versus the CRITICAL_SECTION and std::mutex is entirely due to cache collision. The spin loops are tighter, which means multiple threads are accessing the same cache line for the lock flag, which causes a pipeline stall on the processor core. The timings for 52 jobs are identical to the timings for 520 jobs.

Figure 4: Core differences among the synchronization primitives for 520 jobs and multiple worker threads.

CPU contention

The interesting test was the addition of CPU contention to the worker thread. A second thread was created on the same core as each worker thread. This second thread:

This can be a common case with libraries from several different vendors. The architecture has more threads than cores, so it must double up threads on a core.

The overhead from the lock causes a twofold to tenfold increase in the cost compared to the non-contention case. The high variability in the times for the spin lock with a spin count of 1 is caused by the higher chance of a context switch. If the lock on a queue is held by another thread, the current thread always gets a context switch from the call to SwitchToThread. With a spin count of 100, the spin count is greater than the time needed to hold the lock on the queue. This means there is not a forced context switch in most cases. The pattern using SwitchToThread causes the other thread to be given the remaining quantum time of the blocking thread. This can be significant—several milliseconds.

Figure 5: Core differences with addition of CPU contention for 52,000 jobs and multiple worker threads.

By reducing the job count down to 520, the numbers start to converge. The chance of waiting on a lock has decreased. However, we still have a high variability in the cost to use a spin lock with a spin count of 1. If the lock is held, the requesting thread will always switch due to the call to SwitchToThread. This means the requesting thread will give up the rest of its quantum. You can clearly see that it’s the most expensive of the operations. CRITICAL_SECTION and std::mutex are actually the cheapest. This is due to the longer time of the spin; their inner loop code is more expensive than our implementation of a spin count. The scheduler also forces a context switch when the CRITICAL_SECTION or std::mutex become available to be acquired.

Figure 6: Core differences with addition of CPU contention for 520 jobs and multiple worker threads.

std::atomic vs volatile vs CRITICAL_SECTION

A common theme in titles for a time-critical lock has been a spin loop on a volatile object. On Xbox One there are three problems with this:

  1. The Microsoft default implementation is not the ISO standard, which makes your code break in subtle ways on other platforms. For details, see volatile (C++) and the Standard C++11 specification.

  2. If you’re not very careful, you can end up with code that is equivalent to disabling the optimizer for time-critical functions. The default Microsoft implementation is required to perform acquire/release semantics around any read-write to the volatile object. This means it must either reload or flush all non-temporary variables around access to the volatile object.

  3. The final problem is that you still need an interlock compare and exchange to get it all correct. Multiple threads could change the volatile object during a read-modify-write operation. You must perform a compare and exchange loop instead of the final write.

These tests were done by using the C++11 ISO standard for volatile. With the required compare-and-swap (CAS) operation, the generated code is almost identical to using std::atomic, making the timings similar. Using std::atomic has the added benefit of working across all compilers.

A very interesting piece of data is that with high usage contention on the lock, a CRITICAL_SECTION can be more performant. This seems counter intuitive at first; however, with how the underlying scheduler works, it starts to make sense. The CRITICAL_SECTION was created with a spin count so we’re getting similar functionality to the other two spin lock methods for the normal case. The difference happens at the scheduler level when the locking thread needs to switch out.

With the atomic/volatile spin lock, when usage contention occurs, the blockee thread calls SwitchToThread. SwitchToThread will always switch to another ready thread, even if it is lower priority than the blockee thread. The blocker thread will eventually release its lock; however, it still has the rest of its quanta to run. That single attempt to grab the lock for the blockee ends up with a cost of most of a quantum when it should have been very small. There is also the possibility that another thread may grab the lock before the original blockee gets a chance to run, causing the loss of yet another quantum.

With the CRITICAL_SECTION object, you get the help of the scheduler. If you’re waiting on the CRITICAL_SECTION, the blockee will get a bump in priority as soon as the CRITICAL_SECTION is released. This means it can immediately start running as opposed to losing an entire quantum. The cost for blocking has gone from several milliseconds to several microseconds. The reason for the bump in priority is to keep one thread from hogging the CRITICAL_SECTION so that no other threads get time to run.

The difference can be subtle, but it is clearly visible with a high number of jobs and a higher chance for contention on the lock. The other key takeaway from this data is that it is vital to choose the correct spin count. You can see a spin count of 1 has a much higher cost and variability. There will always be a context switch if the thread needs to block waiting for the access to the job queue.

Figure 7: Performance gain with CRITICAL_SECTION and CPU contention for 52,000 jobs.

These numbers show CRITICAL_SECTION being slower than a straight spin lock with a spin count of 100. This is due to a proper choice of a spin. For this code, it takes longer to spin than the time the lock is held. This means the code will almost never have a context switch if the spin runs out. It’s vital to choose a proper spin count for any type of spinning. If the spinning cost is less than the cost of the protected code, you’ll see similar performance to that just shown for a spin count of 1.

Work-stealing queues

One of the primary design features of a work-stealing algorithm is that each worker thread gets its own job queue. If one thread finishes all its tasks early, it will attempt to steal work from another thread. This has the benefit of helping balance work between worker threads when various jobs have different execution times. You can find more data about work stealing on Wikipedia or in various research papers.

The highest level of usage contention comes from the simulation thread adding jobs to a worker queue, and from the worker thread adding results to the render queue. However, there is only usage contention between worker threads if one thread needs to steal work from another thread. The chance of a steal operation occurring is directly related to how balanced the initial workload is on each thread.

Work stealing is an excellent way to handle worker threads on the second module. Each core on the second module can spend time processing OS threads as opposed to title tasks; this is especially an issue on the seventh core. When a worker thread on one of these cores loses time to the OS, it will not be able to process all its tasks in time. The other worker threads will automatically pick up the delayed tasks as they finish and balance out the load.

The same tests as the previous tests were run by using one shared job queue. For details about the synchronization patterns used, see the Tests section.

We see a difference with 52,000 jobs when compared to single-threaded and multithreaded with a single job queue. The median for single-threaded was 95 milliseconds, while the best case median for the multithreaded single job queue version was 45 milliseconds. The median for the work-stealing implementation was better at 40 milliseconds. The source of the improvement between a single job queue and multiple job queues comes from two sources:

  1. Cache contention on a single job queue is no longer shared by all the workers.
  2. Worker threads do not block each other’s access to a shared single job queue.

There is still some contention between the source thread and a worker thread on the input queue, and between the sink thread and a worker thread on the output queue. With 52,000 jobs, there is still the overhead of the job queue access dominating the execution time.

Figure 8: Core differences among the synchronization primitives for 52,000 jobs when using work stealing.

By dropping down to 5,200 or fewer jobs, the numbers become stable with a median of 22.5 milliseconds. The median for the original single job queue did not drop this low until less than or equal to 520 jobs. The spin count makes no difference now because there is no usage contention on the queues between the worker threads. The only usage contention on the queue comes from either insertion by the source thread or removal by the sink thread. The lock is held for less time than it takes to perform one job, so the chance of contention is very close to zero.

The graph below is for 520 jobs. The graphs for 5,200 and 52 jobs are identical to these timings.

A similar CPU contention test case was created as the single job queue. A second thread is created on the core for each worker thread that just sits in an infinite loop doing math. In general, the times were slightly higher versus no contention. This is due to losing the core after a quantum end event; the OS gives equal time to the second thread.

Of note is that the high variability caused by having a spin count of 1 in the single queue version is severely reduced when each thread has its own job queue. The standard deviation is drastically lower with the median cost in the 100-millisecond range. This again is due to almost no contention on the job queue. The chance for a context switch between the worker threads and/or the simulation/render threads is almost zero.

Figure 10: Core differences among the synchronization primitives for 520 jobs when using work stealing and contention.

Lock-free queues

The final test is using a queue that follows the standard lock-free single-producer/single-consumer pattern. It is similar to the work-stealing pattern mentioned earlier; however, no blocking synchronization primitive is used. It can only be used with a single thread adding jobs to the queue and a single thread pulling jobs off the queue. This pattern works well with a single job queue per thread.

The times for all runs from 52,000 jobs to 52 jobs are all similar with a median between 23 and 21 milliseconds. The original single-threaded version had a median cost of 87 milliseconds in the best case. This represents almost a perfect speedup of 3.8 times faster. Even if you have a large number of small jobs (52,000), the speedup is the same at 3.8 times faster. Previously, the overhead of the locking job queue kept the speedup down to a twofold performance gain.

Figure 11: Core differences among various job counts when using a lock-free queue.

The best valid comparison is against the work-stealing pattern that uses a spin lock. With a spin count of 100, the chance for the lock being taken is close to 0. In the non-CPU contention cases, the median for the spin lock is 23 milliseconds compared to 21 milliseconds for the lock-free version. In the contention cases, the median for the spin lock is 60 milliseconds compared to 50 milliseconds for the lock-free version.

Figure 12: Core differences between lock-free and work stealing for 520 jobs.

The main reason for the lower cost of the lock-free queue is from cache contention between the two threads. The lock-free queue uses two pointers that do not share a cache line. Updating one pointer will not invalidate the second pointer in the cache. The work-stealing pattern has one locking primitive shared between two cores. Each time the lock is taken, the cache line on the other core is invalidated. For more details, see the Xbox One CPU Introduction and the Cross Core Memory Costs on the Xbox One CPU white papers on the GDN portal.

Shared statics

The final numbers are a quick comparison on possible cache contention that can come from rapid access to a shared object. This is a very common case with job queues: the locking primitive used is shared between threads. The random number function used for these tests uses a thread-local variable to hold the previous number generated. This number serves as the basis for the next number. A quick change to convert from thread-local to a static changes the time from a median of 25 milliseconds to a median of 75 milliseconds for 520 jobs. The following numbers are the timings that use the work-stealing pattern with no locking primitive.

Figure 13: Core differences between static and threadlocal.

The cache contention comes from the static variable in the random function. Each time a thread updates that value, it will cause the cache line for that variable to be invalidated on all the other cores. For more details, see the Xbox One CPU Introduction and the Cross Core Memory Costs on the Xbox One CPU white papers on the GDN portal.

Because of the cost of this cache contention, it is vital that each locking primitive used for your job queues sits on their own cache line. You can easily do this by padding them out to at least 64 bytes each.

Xbox One X

The Xbox One CPU speed has been increased in Xbox One X, from 1.75GHz to 2.3GHz. This results in a 30% boost in performance. In all the none contention cases this can be seen as a straight performance boost.

For example, a single job queue being accessed by multiple threads and 520 jobs. The slight variations in through different runs are entirely attributed to cache contention on the shared synchronization object.

Figure 14: Xbox One X performance improvement vs. Xbox One.

The more interesting case is when there is contention between multiple threads on the same core. In this case, the cost of a context switch can be magnified. CRITICAL_SECTION can recover more quickly since it will resume a paused thread based on an interrupt which happen at the clock speed of the processor. Spin locks will resume their thread based on wall clock time, they must wait for the running thread to finish its quantum.

This is the same set of tests as the previous graph, however an extra thread has been added to create contention on the CPU for each worker thread.

Figure 15: Xbox One X performance improvement vs. Xbox One with contention.

One last graph that clearly shows the issues when contention is added with a spin lock pattern using SwitchToThread. In this case, we’re comparing to a lock free system. When there is no contention all systems (lock free and work stealing) have the same performance boost of 30% when running on Xbox One X. The reason for the increased volatility in the timings is entirely due to the same reason as mentioned previously. Resuming from a context switch is based on CPU cycle time and SwitchToThread is based on wall clock time.

Figure 16: Xbox One X performance improvement vs. Xbox One. Lock Free vs. Work Stealing.

Recommendations

There are several key takeaways from all the data presented:

Summary

In testing various scenarios and patterns for job queues on Xbox One and Xbox One X, we found that the number of jobs is the major contributing factor to performance. A close second is the synchronization pattern used for the job queue. By keeping these findings and recommendations in mind, you can make the best decision for your implementation of job size and job queue.

Almost all the job queue patterns scale nicely on the faster hardware of Xbox One X. The major pattern that does not scale are spin locks using SwitchToThread. These have a higher degree of volatility in the performance boost and, in some cases, can run significantly slower.

Appendix A: Code samples

QueueLockType is the enumeration for the locks this code supports.

enum class QueueLockType
{
    USE_NONE,
    USE_CRIT_SECTION,
    USE_MUTEX,
    USE_ATOMIC,
    USE_VOLATILE,
};

LockWrapper is the structure that maintains the ownership of the locking primitive. This removes the need for the queue to know what type of lock it is using.

template<QueueLockType lockType,uint32_t spinCount>
struct LockWrapper
{
    CRITICAL_SECTION m_dataCrit;
    std::mutex m_dataMutex;
    std::atomic<uint32_t> m_dataAtomic;
    volatile uint32_t m_dataVolatile;
    LockWrapper ()
    {
        if (lockType == QueueLockType::USE_CRIT_SECTION)
        {
            if (spinCount)
                InitializeCriticalSectionAndSpinCount(&m_dataCrit,spinCount);
            else
                InitializeCriticalSection(&m_dataCrit);
        }
        m_dataAtomic.store (0);
        m_dataVolatile = 0;
    }
    ~LockWrapper()
    {
        if (lockType == QueueLockType::USE_CRIT_SECTION)
            DeleteCriticalSection(&m_dataCrit);
    }
};

LockScope provides automatic lock/unlock on the primitive based on scope lifetime.

template<QueueLockType lockType,uint32_t spinCount>
class LockScope
{
private:
    LockWrapper<lockType,spinCount>& m_heldLock;
    void operator=(const LockScope& p1);
    LockScope (const LockScope& p1);
public:
    LockScope (LockWrapper<lockType,spinCount>& lock) : m_heldLock (lock)
    {
        switch (lockType)
        {
        case QueueLockType::USE_CRIT_SECTION:
            EnterCriticalSection (&m_heldLock.m_dataCrit);
            break;
        case QueueLockType::USE_MUTEX:
            m_heldLock.m_dataMutex.lock ();
            break;
        case QueueLockType::USE_ATOMIC:
            {                          
                uint32_t currentSpin=0;
                uint32_t expected = 0;
                while (!m_heldLock.m_dataAtomic.compare_exchange_strong(expected,1))
                { 
                    currentSpin++;
                    if (currentSpin == spinCount)
                    {
                        SwitchToThread ();
                        currentSpin = 0;
                    }
                    expected = 0;
                }
            }
            break;
        case QueueLockType::USE_VOLATILE:
            {
                uint32_t currentSpin=0;
                while (InterlockedCompareExchange(&m_heldLock.m_dataVolatile,1,0)!=0)
                { 
                    currentSpin++;
                    if (currentSpin == spinCount)
                    {
                        SwitchToThread ();
                        currentSpin = 0;
                    }
                }
            }
        }
    }
    ~LockScope ()
    {
        switch (lockType)
        {
        case QueueLockType::USE_CRIT_SECTION:
            LeaveCriticalSection (&m_heldLock.m_dataCrit);
            break;
        case QueueLockType::USE_MUTEX:
            m_heldLock.m_dataMutex.unlock ();
            break;
        case QueueLockType::USE_ATOMIC:
            m_heldLock.m_dataAtomic.store(0,std::memory_order_relaxed);
            break;
        case QueueLockType::USE_VOLATILE:
            m_heldLock.m_dataVolatile = 0;
            break;
        }
    }
};