Atomic increment is flushing other cache lines (code and results provided)?

Question

Set-up: Intel Ivy Bridge Core i7, compiling in 64-bit mode, MSVC(2012) and Win 7 64-bit.

I am trying to understand whether atomic increments causes cache misses.

I set up a test where an atomic variable and another variable were in the same cache line and not in the same cache line and then compared cache misses. Code and results below.

Results

Different cache lines:

• Atomic increment no L1 cache misses
• Both the increments of d.a suffered 40-50% L1 cache misses.

Same cache lines

• Incrementing d.a had no cache misses
• Incrementing atomic encountered 100% L1 cache misses.

Could someone please explain this?! I was expecting when the atomic was in the same cache line as d.a then d.a would suffer 100% cache misses and when they were in different cache lines d.a would not be affected.

#include <atomic>
#include <iostream>
#include <iomanip>
#include <vector>

//Structure to ensure not in same cache line
__declspec(align(64)) struct S{
  volatile double a,b,d,c,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t;
  volatile std::atomic<short> atom;
};

//Structure to ensure same cache line
/*__declspec(align(64)) struct S{
   volatile std::atomic<short> atom;
   volatile short a;
};*/


int main(){

    volatile S d;

    for(long long i=0; i<1000000000; i++){
        d.a++;
        d.atom++;
        d.a++;
    }
}

UPDATE here is some of the asm:

    /* _Atomic_fetch_add_2, _Atomic_fetch_sub_2 */
inline _Uint2_t _Fetch_add_seq_cst_2(volatile _Uint2_t *_Tgt, _Uint2_t _Value)
    {   /* add _Value to *_Tgt atomically with
 mov         word ptr [_Tgt],dx  
 mov         qword ptr [rsp+8],rcx  
 push        rdi  
            sequentially consistent memory order */

    return (_INTRIN_SEQ_CST(_InterlockedExchangeAdd16)((volatile short *)_Tgt, _Value));
 movzx       eax,word ptr [_Value]  
 mov         rcx,qword ptr [_Tgt]  
 lock xadd   word ptr [rcx],ax  
    }
 pop         rdi  

Answer 1

Looking at this sequence:

for(long long i=0; i<1000000000; i++){
    d.a++;
    d.atom++;
    d.a++;
}

we could rewrite it as (roughly):

for(long long i=0; i<1000000000 / 4; i+=4){
    d.a++;
    d.atom++;
    d.a++;
    d.a++;
    d.atom++;
    d.a++;
    d.a++;
    d.atom++;
    d.a++;
    d.a++;
    d.atom++;
    d.a++;
}

I could go on and expand the loop further, but it becomes obvious that you have two d.a++ in a row after the d.atom++.

In other words, you should expect around 50% cache miss on d.a++, based on the d.a++ at the end of the loop fetching the data for the d.a++ for the next iteration of the loop. Any discrepancy from this would be a measurement error (and cache misses I believe are measured on statistics, not exact steps on exact lines).

In the case where d.a and d.atom are on different cache lines, obviously d.atom++ gets all of the cache-misses accounted on that particular address, explaining the 100% figure in that case.

I'm not 100% sure that the definition of locked operations ("locked operation" = atomic in x86 land) REQUIRE a cache-flush, but it certainly requires an "exclusive access", which means that all other CPU (cores) will need to be told that "you must now flush any copy of this data from your cache". It would appear from your testing that, at least on this model of processor, this equates to "flush all caches for this line", including the one currently holding the data.

Answer 2

See the SO discussion What is a memory fence?. This is how modern Intel CPUs implement lock instructions. A memory barrier enforces data being written fully to memory and then reread on next access. In the case of [ref to A] [barrier] [ref to A] the CPU cannot do any clever prefetch of the second reference. All barrier instructions operate in same way though some allow you to explicitly limit to a left or right fence mode.

Doing a barrier instruction incurs a performance hit. Trying to understand the character of this hit will vary CPU architecture by architecture, and the internals of the algorthms to do this in H/W is not something that Intel will publish in detail.