Cross-Core Memory Costs on the Xbox One Family CPU
Andrew Farrier, Xbox Advanced Technology Group
Updated April 28th 2017
In this topic
Recommendations for some common usage patterns
Introduction
Building on the foundation established in the white paper Xbox One CPU: Introduction, this white paper addresses the performance issues and costs associated with different types of read/write operations between caches on the CPU cores. For a refresher on the architecture, features, and performance of the Xbox One Family CPU, we suggest that you take a look at that previously published white paper.
“Xbox One CPU: Introduction” describes the cost associated with an L1 cache miss. One of the most common patterns for an L1 cache miss is writing to an address shared between CPU cores—for instance, data shared between multiple threads. The purpose of this paper is to provide hard numbers for the penalty associated with sharing writable data between cores.
The main takeaway from our tests is that it’s preferable to confine data in read/write operations to each individual core, rather than sharing data between cores and threads. Sharing data across cores will actually slow down your code’s processing rather than speeding it up.
A look at shared data
Data sharing can happen in several ways. One of the more obvious is the direct sharing of variables, such as a reference count on a structure. This can easily result in the data being modified as each thread makes copies with a shared_ptr being passed around, for instance, as a parameter in a function call. That operation alone will result in resource contention.
Another kind of data sharing, known as false sharing, is harder to detect. False sharing occurs when two memory addresses resolve to the same cache line. On the Xbox One CPU, the L1 cache line is 64 bytes in size and is aligned to 64 bytes, so two integers in the same 64-byte block are considered to be shared. Consider, for example, the following two data structures:
The threadOne, threadTwo, threadThree, and threadFour data are unique per thread. Thread one will only operate on threadOne data, Thread two only on threadTwo data, and so forth. Between these two data structures, OuterClassSlow will operate up to four times slower than OuterClassFast when switching to multithreaded processing for a standard write operation alone. This is because the data in OuterClassSlow all share the same cache line as the result of false sharing. They are adjacent to each other in memory. This is an example of the difference between an array of structures (AoS) and a structure of arrays (SoA).
The costs of data sharing
The real costs for sharing data are significant. In this section we provide the details on the real-world costs associated with a variety of operations.
Test profile
At a high level, here’s an overview of the tests we performed:
- The instructions tested were a raw read, a raw write, an atomic load, an atomic store, and an atomic Compare and Store (CAS) operation. The code we used for each set of instructions is provided in the Appendix.
- All tests were performed first with a single uint64_t data structure shared by all threads (array of structures) or with each thread having its own uint64_t (structure of arrays).
- Forty-thousand operations were executed in a tight loop with some overhead to manage index lookup to keep relative times consistent throughout the entire test. On the multithread runs, the operations were equalized across four worker threads, 10,000 per thread. The optimizer was set to minimize size to disable loop unrolling. With full optimizations the compiler would remove the loop because it didn’t output any useful data.
- A total of 100 runs were performed; the results from each run are shown in the charts that follow.
- The times given are in ticks as reported by __rdtscp. On Xbox One X, the frequency for _rdtscp is locked to 1.7455 GHz; it is not at the processor speed of 2.3 GHz. Because of this, comparisons will also be given in wall clock time.
Testing on a single core
For our baseline, we started by testing each operation on a single core.
| Operation | Xbox One | Xbox One | Xbox One X | Xbox One X |
|---|---|---|---|---|
| Raw read | 120,065 ticks | 69 μs | 89,447 ticks | 51 μs |
| Atomic load | 120,116 ticks | 69 μs | 89,408 ticks | 51 μs |
| Raw write | 320,071 ticks | 183 μs | 238,383 ticks | 137 μs |
| Atomic store | 646,001 ticks | 370 μs | 476,665 ticks | 273 μs |
| Atomic CAS | 1,177,837 ticks | 675 μs | 864,301 ticks | 495 μs |
Comparing 40,000 straight reads with 40,000 atomic loads, there is zero difference in the times. This is due to the strong memory model of the CPU. The compiler is able to generate the same instructions for both operations. On the store side, there is a twofold increase in the cost between a raw write and an atomic store. This is because the atomic store is using the xchg instruction: because it’s to a memory location, the xchg operation always implicitly includes the lock prefix. This can stall the processor until the operation has been flushed to the cache. The processor cannot reorder operations across the lock. The raw write uses the mov operation. This will not stall the processor; it’s allowed to reorder operations around the mov operation.
This brings us to the CAS operation itself. The atomic CAS test is written with the standard pattern—do a load, modify the data, and then do the CAS—looping until the CAS operation succeeds. The penalty here comes from two different sources. The first is the cmpxchg instruction, which requires a read, compare, modify, and write. All of these need to happen with the lock prefix. This can stall the processor because it is not allowed to reorder instructions across the lock prefix. The CAS is more expensive than the previously mentioned xchg due to the compare. This causes the overall code to take more time than an atomic store. There is also the possibility that the CAS will fail, which requires another pass through the loop.
Testing on multiple cores
For the multiple-core tests we ran the same instructions as before (read, write, atomic load, atomic write, atomic CAS), with all four threads doing 10,000 operations each as opposed to a single thread doing 40,000 operations. The four threads were spread across the two CPU modules: Core 0 and Core 1 from the first module, and Core 4 and Core 5 from the second module.
We did two different runs for each test. In the first run, all four threads shared the same uint64_t address. In the second run, each thread had its own uint64_t data address. The reason we did this was to test the overhead cost of sharing L1 cache lines between cores versus not sharing. For each test, the threads were started at the same time, with the timing coming just from the loop iteration. The threads were also set to high priority to lower the chance of a context switch as much as possible. One-hundred runs were performed for each test; the results are shown in the graphs that follow.
Raw read
This is a straight read from a memory location. There is no contention between the threads, because nothing is changing the data: each core has its own copy of the data in its L1 cache. As a result, the times between reading shared data and reading unique data are the same.
The numbers show an almost perfect speed-up from running multithreaded, four times faster when running on four cores.
Atomic load
The Xbox One CPU provides a strong memory model. Because of this, there is no need for any type of barrier when performing an atomic load. The requesting CPU core can probe the cache on other CPU cores or the other module for the most up-to-date value. The code generated by the compiler is the same as raw read. This means there is no difference in the execution time with raw read.
Raw write
A simple write to shared memory between cores can operate up to 46 times slower than a write to a single core. The core will update the cache line and invalidate that line on all the other cores. When another core writes to the same cache line, it needs to request the updated cache line from the first core. The first core no longer has a valid copy of the entire cache line. This causes a very large amount of contention. The cost of the operation has gone from 3 cycles to over 140 cycles—the cost to access the local L1 cache versus accessing the L1 on another core or module.
When writing to a shared cache line, the performance penalty for these tests can be up to 4000% slower. This is entirely due to contention on the shared cache line. However, when the cache lines are not shared among cores, we again see the same almost-perfect speed-up as with the previous instructions: four cores are almost four times faster.
Atomic store
An atomic store between shared memory addresses can also be over 46 times slower than it is on unique data, just as with the previous write operation. The core will update the cache line and invalidate that line on all the other cores. When another core writes to the same cache line, it needs to request the updated cache line from the first core. The first core no longer has a valid copy of the entire cache line. This causes a very large amount of contention. The cost of the operation has gone from 3 cycles to over 140 cycles—the cost to access the local L1 cache versus accessing the L1 on another core or module.
Atomic store uses the xchg instruction, which is required to read and then write to the memory address in question. During this time the cache line is locked, preventing the other cores from accessing that cache line. This can stall the processor until the operation has been flushed to the cache. The processor cannot reorder operations across the lock. The instruction may also need to access the cache on another core during the read, because the other core might have modified the data since the last read on the current core. The other cores will stall during this entire sequence when operating on the shared cache line.
An interesting phenomenon occurs during this test, though. The timing includes all of the management of the loop around the operations. The cores will form a convoy as they each lock the shared cache line. This gets them out of sync with each other on requesting data from the shared cache line. Further iterations through the loop all operate in parallel. The stall is longer than for raw write; this is the cost of the full xchg operation. The prefetcher has a longer amount of time to help cover the stall. Because of this, the overall comparative timing in relation to raw write is actually faster.
As before, we see the same adjustments to the timing when the cores do not have to share data. We are very close to perfect speed-up, four times faster with four cores.
Atomic CAS
An atomic compare and store (CAS) between shared memory addresses can again be over 46 times slower than it is on unique data, just as with the two previous tests, raw write and atomic store. The core will update the cache line and invalidate that line on all the other cores. When another core writes to the same cache line, it needs to request the updated cache line from the first core. The first core no longer has a valid copy of the entire cache line. This causes a very large amount of contention. The cost of the operation has gone from 3 cycles to over 140 cycles—the cost to access the local L1 cache versus accessing the L1 on another core or module.
As with atomic write, the same phenomenon occurs during this test. The timing includes all of the management of the loop around the operations. The cores will form a convoy as they each lock the shared cache line. This gets them out of sync with each other on requesting data from the shared cache line. Further iterations through the loop are all operating in parallel. The stall is longer than for raw write and atomic store; this is the cost of the full cmpxchg operation. The loop code is also larger than atomic load due to the extra code to load the initial value. The prefetcher has even more time to cover the stall from the cross-core memory access. Because of this, the overall comparative timing in relation to raw write and atomic write is actually faster: down to 500% to 1000% slower than a unique cache line per core.
Finally, we once again have the same almost-perfect speed-up as in the previous tests when unique data per core is being used.
Recommendations for some common usage patterns
There are several key patterns you can follow to avoid sharing writable data between cores:
- Data structure: switch from using an array of structures (AoS) to a structure of arrays (SoA) when each thread is operating on a unique structure.
- Separate out read-only data from read/write data.
- Padding: you can pad a structure by a multiple of a cache line in size (64 bytes). This will remove false sharing if each thread operates on a structure.
- Reference counting (shared_ptr, weak_ptr, etc.): they all have a single reference count variable which is shared among all instances of the object.
- Be very clear on ownership of data. When data is passed off to another thread for processing, that thread now owns the data. Avoid doing anything on the data until that thread is done with it.
- Shared job queue: try to avoid using one job queue that is shared by multiple threads, especially if the jobs are small. Look instead at having a unique job queue for each thread. You can use the work stealing algorithm to help balance the load between the threads.
Summary
In testing read/write operations in various scenarios on the Xbox One Family CPU, we found that sharing data across cores resulted in significantly slower performance than keeping the memory locations for each core distinct. We found that it is preferable to break up the data per core so that each core works only on its own memory location. By keeping these findings and recommendations in mind, you can make the most of the architecture and performance characteristics of the Xbox One Family CPU.
The Xbox One X CPU behaves identically to the Xbox One CPU. The only difference is in the clock speed, from 1.75 GHz to 2.3 GHz. The relative costs for shared cache line access and unique cache access are the same between both consoles.
Appendix: Code
Raw read
uint32_t bufferIndex = params.baseIndex;
for (uint32_t j=0;j<params.iterations;j++,bufferIndex += params.offset)
{
fred += params.dataBuffer[bufferIndex & params.dataSize];
}
000001077810AAAC mov ecx,edx
000001077810AAAE add edx,dword ptr [rdi+10h]
000001077810AAB1 and rcx,qword ptr [rdi+20h]
000001077810AAB5 add r8,qword ptr [r10+rcx*8]
000001077810AAB9 dec r9
000001077810AABC jne ThreadPerf::WorkerThreadRead+50h (01077810AAACh)
Atomic load
uint32_t bufferIndex = params.baseIndex;
for (uint32_t j=0;j<params.iterations;j++,bufferIndex += params.offset)
{
fred = buffer[bufferIndex & params.dataSize].load ();
000001054CFE98E0 mov ecx,edx
000001054CFE98E2 and rcx,r9
000001054CFE98E5 mov rbp,qword ptr [r14+rcx*8]
000001054CFE98E9 add edx,dword ptr [rdi+10h]
000001054CFE98EC inc r8d
000001054CFE98EF cmp r8d,dword ptr [rdi+8]
000001054CFE98F3 jb ThreadPerf::WorkerThreadAtomicLoad+70h (01054CFE98E0h)
Raw write
uint32_t bufferIndex = params.baseIndex;
for (uint32_t j=0;j<params.iterations;j++,bufferIndex += params.offset)
{
params.dataBuffer[bufferIndex & params.dataSize] = j;
}
000001077810AB29 mov rax,qword ptr [rdi+18h]
000001077810AB2D mov ecx,r9d
000001077810AB30 mov edx,r8d
000001077810AB33 and rcx,qword ptr [rdi+20h]
000001077810AB37 inc r8d
000001077810AB3A mov qword ptr [rax+rcx*8],rdx
000001077810AB3E add r9d,dword ptr [rdi+10h]
000001077810AB42 cmp r8d,dword ptr [rdi+8]
000001077810AB46 jb ThreadPerf::WorkerThreadWrite+49h (01077810AB29h)
Atomic store
uint32_t bufferIndex = params.baseIndex;
for (uint32_t j=0;j<params.iterations;j++,bufferIndex += params.offset)
{
buffer[bufferIndex & params.dataSize].store (j);
}
000001077810ABC6 mov ecx,r9d
000001077810ABC9 mov edx,r8d
000001077810ABCC inc r8d
000001077810ABCF and rcx,qword ptr [rbx+20h]
000001077810ABD3 xchg rdx,qword ptr [rsi+rcx*8]
000001077810ABD7 add r9d,dword ptr [rbx+10h]
000001077810ABDB cmp r8d,dword ptr [rbx+8]
000001077810ABDF jb ThreadPerf::WorkerThreadAtomicStore+5Ah (01077810ABC6h)
Atomic CAS
uint32_t bufferIndex = params.baseIndex;
for (uint32_t j=0;j<params.iterations;j++)
{
uint64_t temp = buffer[bufferIndex & params.dataSize].load ();
buffer[bufferIndex & params.dataSize].compare_exchange_strong(temp,temp+1);
}
000001054CFE99F0 mov rcx,qword ptr [rdi+20h]
000001054CFE99F4 and rcx,r9
000001054CFE99F7 mov rax,qword ptr [r14+rcx*8]
000001054CFE99FB mov rcx,qword ptr [rdi+20h]
000001054CFE99FF and rcx,r9
000001054CFE9A02 lea rdx,[rax+1]
000001054CFE9A06 lock cmpxchg qword ptr [r14+rcx*8],rdx
000001054CFE9A0C inc r8d
000001054CFE9A0F cmp r8d,dword ptr [rdi+8]
000001054CFE9A13 jb ThreadPerf::WorkerThreadAtomicCAS+0D0h (01054CFE99F0h)