Costs for Synchronization Primitives
Andrew Farrier, Xbox Advanced Technology Group
Updated April 28th 2017
In this topic
Introduction
When using various synchronization primitives on Xbox One, it’s useful to know the median overall cost for each call. These numbers can be difficult to quantify because there is such a wide variety of cases and usage patterns. This paper covers the most extreme case, when two threads need to communicate between different processor cores, either physical, logical, or virtual. In this case, because each processor core maintains its own list of threads, some form of communication is required.
Due to the way the underlying thread lists are maintained, an increased cost is not based on the number of total threads in the system, but on the number of threads interacting with the synchronization primitive. However, the higher the number of threads in the system, the higher the chance of interference in the test runs. Because of this chance of interference, all tests were executed with only the minimum required threads.
All the tests were done on an Xbox One and Xbox One X console with the June Preview 1 2017 recovery image and the test suite built against the June Preview 1 2017 XDK. The scheduler used by a title is contained as part of the XDK. This means that the costs should stay consistent throughout the lifetime of your title; they will not change as new recovery images are released to retail customers.
Overview
All the synchronization primitives can be broken down into two categories:
- Kernel level – These primitives always transition to the kernel (Ring 0) on any call that uses them. For example, just checking their status causes a transition that has a cost of several thousand cycles. The primary reason for this cost is the ability to use these primitives between different processes.
- User level – These primitives attempt to stay at the user mode (Ring 3). The only time a user level primitive will transition to the kernel is if the calling thread must suspend for any reason. You lose the ability to share these primitives across different processes, but they are drastically faster than kernel level primitives if the thread does not have to suspend.
Two major operations that you can perform on a synchronization primitive are:
- Release the primitive – A primitive can be in one of two states: ready to acquire and not ready to acquire. Releasing the primitive switches it to ready to acquire; if the primitive is already ready to acquire, nothing happens.
- Acquire the primitive – This performs one of two actions depending on the state of the primitive:
- No contention – The primitive can be acquired immediately. The requesting thread returns immediately from the request with the primitive acquired.
- Contention – The primitive cannot be acquired. If the thread needs to acquire the primitive and not just check for contention, it needs to suspend until the primitive can be acquired. The times given are for how long it takes the thread to start running as soon as it can acquire the primitive.
In general, the Xbox One X times will be lower than those for Xbox One. This is entirely due to the increased clock speed of Xbox One X, from 1.75 GHz on Xbox One to 2.3 GHz on Xbox One X.
Kernel level
Following are the three major kernel level primitives we’ll cover in this paper:
- Semaphore – Generally used when multiple threads can acquire the primitive at the same time. When the semaphore value is greater than 0, it can be acquired. Each time the semaphore is acquired, the state is decremented by 1. When a thread releases a semaphore, the state is incremented by 1, thus letting another thread acquire it.
- Event – Generally used to signal that something has changed in the system. For example, data requested from a file is available now. The event can be acquired when it is signaled. When the event is acquired, the event state can either stay signaled and be acquirable by other threads, or the state can flip to not acquirable. This is the bManualReset parameter used in CreateEvent.
- Mutex – Generally used to provide mutual exclusion to a resource. One and only one thread can acquire the primitive at a time. A mutex also supports recursive locks, something that is not common in synchronization primitives.
All kernel level primitives will transition to the kernel when performing any of these three operations: setting the state, querying the state, and acquiring. The minimum cost for this transition is in the 2,000 to 3,000 cycle range. The costs for these primitives are almost identical across all the tests. Internally they work the same way; it is just the external interfaces that change.
How they work
These primitives tend to work through a linked list attached to the primitive itself on all waiting threads. This means that when the primitive is released, only the waiting threads need to be touched to determine which should acquire primitives. An increased cost is not based on the number of actual threads in the system, only on the number of waiting threads. If there are multiple threads waiting on a primitive that can be resumed at the same time, they are all grouped together into one notification. For example, an event using manual reset will notify all the threads waiting on it. Due to the grouping of the notification, the cost does not increase that much with multiple threads waiting.
Data
Release with no contention
The cost to release a kernel primitive when there is no contention can be fairly expensive because it is a kernel level object. The code is required to transition to the kernel. This cost accounts for a majority of the overhead.
Figure 1. Times for release with no contention across all cores.
As can be seen in this table, the cost is consistent on each core. The median cost is in the 0.5 μs range on Xbox One and 0.32 μs on Xbox One X. There is some slight deviation between runs, but that’s entirely from slight differences in cache misses between calls in the test runs.
This is the minimum amount of work that needs to be done on the primitive; it just sets the state from one value to another value. No notification needs to be done in the system because no other threads are currently waiting on the primitive.
Release with contention
When another thread is currently waiting to acquire the primitive, a lot more work needs to be done. This is the case where we say there is contention on the object. The costs are higher because notification now needs to be handled. If the thread in question is on another core, an interrupt needs to be sent to the second core so that the second core can determine if it needs to perform a context switch to the new thread. This is done through an IPI (Inter Processor Interrupt).
Figure 2. Times for release with contention between cores on the first module.
As you can see, the median cost has risen from 0.5 μs to 4 μs on Xbox One—almost a tenfold increase in cost. The source of this increased cost is the management of the internal linked list of waiting threads that need to be notified along with the cost for the notification. Xbox One X is of course faster due to the faster processor clock speed.
However, if the two cores in question are on separate modules, the cost for the IPI is higher because it needs to cross the module boundary.
Figure 3. Times for release with contention across all cores.
As you can see with these numbers, the extra cost for the cross module IPI is almost 2 μs higher across the board.
Acquire with no contention
The cost to acquire a primitive when there is no contention is almost identical to the cost to release the primitive, with just a slight increase. In both cases, the major cost is to transition into the kernel. The cost to flip the state on the primitive is very minor.
Figure 4. Times to acquire with no contention across all cores.
The release cost with no contention was in the 0.5 μs range. The overall cost is approximately 0.03 μs higher for acquire. This is due to underlying race condition protection if multiple threads attempt to acquire the primitive at the same time.
Acquire with contention
The most expensive cost is to acquire a primitive when there is contention. In this case, the thread needs to suspend until the acquisition can happen. The numbers given here are how long it takes the thread to resume after the primitive has been released.
As with the release with contention case, an interrupt is sent between processor cores. If the thread can be resumed, the releasing core is required to notify the acquiring core to check its thread priority queue. The notification is only sent if the releasing core can determine whether a context switch needs to happen.
Figure 5. Times to acquire with contention between cores on the first module.
This table shows the cost for a thread to transition to running when it had to block waiting to acquire the primitive. The cases are for a thread on core 0 releasing the primitive and threads on cores 1, 2, and 3 waiting to acquire the primitive. In this case, the cost going from core 0 to core 1 has a median cost of 10.5 μs on Xbox One. Xbox One X has the same 30% boost in performance due to increased clock speed.
As with the release with contention case, there is an increased cost in the notification when the cores in question are on different modules.
Figure 6. Times to acquire with contention across all cores.
As you can see, the cost rose by about 3.5 μs when the notification crossed between two modules. This increase is consistent between Xbox One and Xbox One X.
Final notes
All the costs tend to be reciprocal between cores. Therefore, the cost from core 0 to core 4 is the same as going from core 4 to core 0. The only controlling factor is whether the notification needs to cross the module boundary.
User level
The key feature with user level primitives is the drastic reduction in costs. The implementation is not required to transition to the kernel when there is no contention on the primitive. This results in a ten-fold improvement in the performance.
Four user level objects are covered in this section:
- CRITICAL_SECTION – Provides the same level of mutual exclusion as a mutex. The main difference with a mutex is the inability to share the CRITICAL_SECTION between separate processes. Because of this restriction, the CRITICAL_SECTION can stay at the user level for most of the operations and will perform drastically faster than a mutex.
- SRW – Short hand used by Microsoft for its Slim Reader/Writer locks. The primitive can be acquired in either read mode or write mode. In read mode, any number of other threads can acquire it in read mode as well. In write mode, one and only one thread can acquire it. If a thread has acquired the primitive in write mode, no other threads can acquire it in either read or write mode until it is released.
- WaitOnAddress – Similar to an event; however, no direct primitive is involved. The process can choose any address within its address space. The thread can “acquire” when the value at the memory location is different from a second value.
- Condition variables – Can be used with either a CRITICAL_SECTION or an SRW. They allow a thread to wait until notification happens, and they can acquire the attached CRITICAL_SECTION or SRW.
The numbers are similar between the primitives, with the outliers for certain operations shown as well.
How they work
Only a CRITICAL_SECTION is required to be destroyed; none of the other primitives allocate any extra memory or have any form of cleanup. Because of this, they tend to work as a linked list attached to the thread currently holding the primitive. When a thread releases a primitive, it can check its list of waiting threads and alert the ones that can acquire the primitive. As with the kernel level primitives, this means that the cost is not related to the total number of threads in the system, but only to the number of threads waiting on the primitive.
When a primitive is released and there are waiting threads, there can be an increased cost based on the number of waiting threads. All the primitives except for CRITICAL_SECTION can attempt to wake up all their waiting threads. When this happens, each thread in turn must be awoken before the next thread in the list can be checked. Therefore, if three threads are all awoken from one notification, the cost is 3 times the numbers listed here.
Data
Release with no contention
Releasing a user level primitive when there are no other threads waiting requires only an interlocked exchange on a single memory location.
Figure 7. Times for release with no contention across all cores.
The cost is the same across cores. The only variability that could come into play with the second module is due to other system work that happens on the second module that might interrupt the release action. As with all the other tests, Xbox One X will perform significantly faster than Xbox One.
Release with contention
Releasing when there is another thread waiting on the CRITICAL_SECTION requires the same amount of work as releasing any kernel primitive. This is due to the transition to the kernel to notify the waiting thread.
Figure 8. Times for release with contention across all cores.
If you compare these numbers to the previous set, you can see that the user mode primitives are cheaper. The primary reason is the difference in how the linked list of waiting threads is managed (mentioned in the user level How they work section and the kernel level How they work section).
Figure 9. Comparison on release times with contention between user level and kernel level primitives.
Acquire with no contention
The code required to acquire a user primitive when there is no contention is approximately 100 cycles when there are no cache misses. This results in a drastic performance benefit over the previous kernel level primitives.
Figure 10. Times to acquire with no contention across all cores.
As you can see, the median duration is around 0.05 μs on Xbox One, and only 0.039 μs on Xbox One X. The cost to acquire a kernel primitive when there was no contention was about 0.5 μs. This performance does come at a cost though. A user primitive cannot be shared between different processes. This means that they can’t be used to protect data shared in multiple processes.
Acquire with contention
When there is contention, the cost goes back to the average cost for a kernel level primitive. The system is required to transition to the kernel, notify the waiting thread, and perform the context switch.
Figure 11. Times to acquire with contention between cores on the first module.
If you compare these numbers to the previous kernel costs, you will see that they are almost identical. Again, this is due to the overhead of the kernel transition and the associated context switch.
Figure 12. Comparison on acquire times with contention between user level and kernel level primitives.
WaitOnAddress
The WaitOnAddress primitive works slightly differently than the previous primitives. No direct primitive is involved; rather, the process can choose any address within its address space. The thread can “acquire” when the value at the memory location is different from a second value.
Acquire with no contention
One significant outlier when using WaitOnAddress as compared to the other user level primitives is attempting to acquire the primitive when there is no contention. This is due to its internal mechanics to avoid a race condition. The code first must tell the kernel that it is waiting on the address to change; only then can it check if the value is already different. Without this ordering, the thread could check the value, see it isn’t different, and then tell the kernel it’s waiting. Between the last two steps, the value could have changed, but the kernel will not know that the thread is waiting and will not notify it.
Figure 13. Increased cost for WaitOnAddress versus other user primitives when acquiring with no contention.
As you can see, the cost is higher due to notifying the kernel about the request. SRW and CRITICAL_SECTION were 0.05 μs versus 0.12 μs for the WaitOnAddress primitive on Xbox One. However, a transition to the kernel isn’t needed, which keeps the cost lower than semaphore, event, or mutex.
Recommendations
Three main pieces of information come out of these tests as recommendations:
- Reduce contention on primitive use. If the requesting thread needs to suspend, there is a drastic cost increase.
- Use the user level primitives whenever possible. The no contention cost is approximately 10 times faster than the kernel level primitives.
- Avoid having threads communicate between modules on Xbox One hardware, which results in approximately a 25% cost increase.
Summary
This paper covered the performance costs for all the major Windows synchronization primitives in a variety of use cases. Using these numbers, you can adjust your threading strategy to achieve maximum performance.
Xbox One X has a 30% boost in clock speed, which translates directly to the cost of all the synchronization primitives.