Cross Core Memory Costs

​

Abstract

​

Introduction

• Modified
  • This processor has the only valid copy of the cache line and has made changes.
  • The cache line does not match memory.
• Owned
  • This processor has the only valid copy and has made changes.
  • Other processors may have a read-only copy.
• Exclusive
  • The processor has the only copy of the cache line.
  • The contents of the cache line match memory.
• Shared
  • This processor has one of several copies of the cache line.
  • Another processor may have it in the Owned state if changes have been made
• Invalid
  • This cache line is not valid and must be fetched before access.

​

Shared Data

class OuterClassSlow
{
    struct InnerStruct
    {
        uint64_t threadOne;
        uint64_t threadTwo;
        uint64_t threadThree;
        uint64_t threadFour;
    };

    InnerStruct dataArray[1024];
};

class OuterClassFast
{
    uint64_t dataArrayThreadOne[1024];
    uint64_t dataArrayThreadTwo[1024];
    uint64_t dataArrayThreadThree[1024];
    uint64_t dataArrayThreadFour[1024];
};

​

The costs of data sharing

​

Test profile

• 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 used for each set of instructions is provided in the Appendix: Code.
• Tests were performed with an 8-byte memory location shared by all threads (shared cache line) or with each thread having a unique 8-byte memory location (unique cache line).
• Forty-thousand operations were executed in a tight loop.
• The optimizer was set to minimize size to disable loop unrolling.
• A total of 100 runs were performed; the median from all the runs is shown in the tables that follow.

​

Testing on a single core

​

Testing on multiple cores

• Two threads on separate physical cores, but in the same cluster.
• Two threads on separate physical cores and in separate clusters.
• Where SMT was enabled, two threads running on the two logical cores on a single physical processor.

​

Raw read/Atomic Load

​

Raw write

​

Atomic store

​

Atomic Compare and Store (CAS)

​

Recommendations

• Data structure: switch from using an array of structures (AoS) to a structure of arrays (SoA) where 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, and so on): they both 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.

​

Appendix: Code

​

Raw read

for (uint64_t j = 0; j < params.iterations; j++)
{
    fred += *buffer + j;
}

mov         rcx,qword ptr [r8]  
add         rcx,rdx  
inc         rdx  
add         rdi,rcx  
cmp         rdx,r9  
jb          PerfRun::WorkerThreadRead+0D4h (07FF756A2E094h)  

​

Atomic load

for (uint64_t j = 0; j < params.iterations; j++)
{
    fred += buffer->load() + j;
}

mov         rax,qword ptr [rsi]  
add         rax,rcx  
inc         rcx  
add         rdi,rax  
cmp         rcx,rdx  
jb          PerfRun::WorkerThreadAtomicRead+0CFh (07FF756A2E4EFh)  

​

Raw write

for (uint64_t j = 0; j < params.iterations; j++)
{
    *buffer = *buffer + 1;
}

mov         rcx,qword ptr [r8]  
inc         rcx  
mov         qword ptr [r8],rcx  
sub         rdx,1  
jne         PerfRun::WorkerThreadWrite+0D2h (07FF756A2E212h)  

​

Atomic store

for (uint64_t j = 0; j < params.iterations; j++)
{
    buffer->store(buffer->load() + 1);
}

mov         rcx,qword ptr [rdi]  
inc         rcx  
xchg        rcx,qword ptr [rdi]  
sub         rdx,1  
jne         PerfRun::WorkerThreadAtomicWrite+0CAh (07FF756A2E38Ah)  

​

Atomic CAS

for (uint64_t j = 0; j < params.iterations; j++)
{
    uint64_t temp = buffer->load();
    buffer->compare_exchange_strong(temp, temp + 1);
}

mov         rax,qword ptr [rdi]  
lea         rcx,[rax+1]  
lock cmpxchg qword ptr [rdi],rcx  
sub         rdx,1  
jne         PerfRun::WorkerThreadAtomicCAS+0CDh (07FF756A2E68Dh)