I have a few questions regarding Cache memories used in Multicore CPUs or Multiprocessor systems. (Although not directly related to programming, it has many repercussions while one writes software for multicore processors/multiprocessors systems, hence asking here!)

  1. In a multiprocessor system or a multicore processor (Intel Quad Core, Core two Duo etc..) does each cpu core/processor have its own cache memory (data and program cache)?

  2. Can one processor/core access each other&#39;s cache memory, because if they are allowed to access each other&#39;s cache, then I believe there might be lesser cache misses, in the scenario that if that particular processors cache does not have some data but some other second processors&#39; cache might have it thus avoiding a read from memory into cache of first processor? Is this assumption valid and true?

  3. Will there be any problems in allowing any processor to access other processor&#39;s cache memory?


How are cache memories shared in multicore Intel CPUs?

I&#39;m currently trying to get a better understanding of memory/cache related performance issues. I read somewhere that memory locality is more important for reading than for writing, because in the former case the CPU has to actually wait for the data whereas in the latter case it can just ship them out and forget about them.

With that in mind, I did the following quick-and-dirty test: I wrote a script that creates an array of N random floats and a permutation, i.e. an array containing the numbers 0 to N-1 in random order. Then it repeatedly either (1) reads the data array linearly and writes it back to a new array in the random access pattern given by the permutation or (2) reads the data array in the permuted order and linearly writes it to a new array.

To my surprise (2) seemed consistently faster than (1). There were, however, problems with my script

   - The script is written in python/numpy. This being quite a high-level language it is not clear how pecisely the read/write are implemented.
   - I probably did not balance the two cases properly.

Also, some of the answers/comments below suggest that my original expectation isn&#39;t correct and that depending on details of the cpu cache either case might be faster.

My question is:

   - Which (if any) of the two should be faster?
   - What are the relvant cache concepts here; how do they influence the result

A beginner-friendly explanation would be appreciated. Any supporting code should be in C / cython / numpy / numba or python.

Optionally:

   - Explain why the absolute durations are nonlinear in problem size (cf. timings below).
   - Explain the behavior of my clearly inadequate python experiments.

For reference, my platform is `Linux-4.12.14-lp150.11-default-x86_64-with-glibc2.3.4`. Python version is 3.6.5.

Here is the code I wrote:

    import numpy as np
    from timeit import timeit
    
    def setup():
        global a, b, c
        a = np.random.permutation(N)
        b = np.random.random(N)
        c = np.empty_like(b)
    
    def fwd():
        c = b[a]
    
    def inv():
        c[a] = b
    
    N = 10_000
    setup()
    
    timeit(fwd, number=100_000)
    # 1.4942631321027875
    timeit(inv, number=100_000)
    # 2.531870319042355
    
    N = 100_000
    setup()
    
    timeit(fwd, number=10_000)
    # 2.4054739447310567
    timeit(inv, number=10_000)
    # 3.2365565397776663
    
    N = 1_000_000
    setup()
    
    timeit(fwd, number=1_000)
    # 11.131387163884938
    timeit(inv, number=1_000)
    # 14.19817715883255

As pointed out by @Trilarion and @Yann Vernier my snippets aren&#39;t properly balanced, so I replaced them with

    def fwd():
        c[d] = b[a]
        b[d] = c[a]
    
    def inv():
        c[a] = b[d]
        b[a] = c[d]

where `d = np.arange(N)` (I shuffle everything both ways to hopefully reduce across trial caching effects). I also replaced `timeit` with `repeat` and reduced the numbers of repeats by a factor of 10.

Then I get

    [0.6757169323973358, 0.6705542299896479, 0.6702114241197705]    #fwd
    [0.8183442652225494, 0.8382121799513698, 0.8173762648366392]    #inv
    [1.0969422250054777, 1.0725746559910476, 1.0892365919426084]    #fwd
    [1.0284497970715165, 1.025063106790185, 1.0247828317806125]     #inv
    [3.073981977067888, 3.077839042060077, 3.072118630632758]       #fwd
    [3.2967213969677687, 3.2996009718626738, 3.2817375687882304]    #inv

So there still seems to be a difference, but it is much more subtle and can now go either way depending on the problem size.


Why is linear read-shuffled write not faster than shuffled read-linear write?

I am trying to profile and optimize algorithms and I would like to understand the specific impact of the caches on various processors.  For recent Intel x86 processors (e.g. Q9300), it is very hard to find detailed information about cache structure.  In particular, most web sites (including [Intel.com][1]) that post processor specs do not include any reference to L1 cache.  Is this because the L1 cache does not exist or is this information for some reason considered unimportant?  Are there any articles or discussions about the elimination of the L1 cache?

[edit]
After running various tests and diagnostic programs (mostly those discussed in the answers below), I have concluded that my Q9300 seems to have a 32K L1 data cache.  I still haven&#39;t found a clear explanation as to why this information is so difficult to come by.  My current working theory is that the details of L1 caching are now being treated as trade secrets by Intel.

  [1]: http://www.intel.com/products/processor/core2quad/specifications.htm

Where is the L1 memory cache of Intel x86 processors documented?

I am interested in forcing a CPU cache flush in Windows (for benchmarking reasons, I want to emulate starting with no data in CPU cache), preferably a basic C implementation or Win32 call.

Is there a known way to do this with a system call or even something as sneaky as doing say a large `memcpy`?

Intel i686 platform (P4 and up is okay as well). 

How can I do a CPU cache flush in x86 Windows?

Are CPU registers and CPU cache different?

I am aware of multiple questions on this topic, however, I haven&#39;t seen any clear answers nor any benchmark measurements. I thus created a simple program that works with two arrays of integers. The first array `a` is very large (64 MB) and the second array `b` is small to fit into L1 cache. The program iterates over `a` and adds its elements to corresponding elements of `b` in a modular sense (when the end of `b` is reached, the program starts from its beginning again). The measured numbers of L1 cache misses for different sizes of `b` is as follows:

[![enter image description here][1]][1]

The measurements were made on a Xeon E5 2680v3 Haswell type CPU with 32 kiB L1 data cache. Therefore, in all the cases, `b` fitted into L1 cache. However, the number of misses grew considerably by around 16 kiB of `b` memory footprint. This might be expected since the loads of both `a` and `b` causes invalidation of cache lines from the beginning of `b` at this point.

There is absolutely no reason to keep elements of `a` in cache, they are used only once. I therefore run a program variant with non-temporal loads of `a` data, but the number of misses did not change. I also run a variant with non-temporal prefetching of `a` data, but still with the very same results. 

My benchmark code is as follows (variant w/o non-temporal prefetching shown):

    int main(int argc, char* argv[])
    {
       uint64_t* a;
       const uint64_t a_bytes = 64 * 1024 * 1024;
       const uint64_t a_count = a_bytes / sizeof(uint64_t);
       posix_memalign((void**)(&amp;a), 64, a_bytes);

       uint64_t* b;
       const uint64_t b_bytes = atol(argv[1]) * 1024;
       const uint64_t b_count = b_bytes / sizeof(uint64_t);
       posix_memalign((void**)(&amp;b), 64, b_bytes);

       __m256i ones = _mm256_set1_epi64x(1UL);
       for (long i = 0; i &lt; a_count; i += 4)
           _mm256_stream_si256((__m256i*)(a + i), ones);

       // load b into L1 cache
       for (long i = 0; i &lt; b_count; i++)
           b[i] = 0;

       int papi_events[1] = { PAPI_L1_DCM };
       long long papi_values[1];
       PAPI_start_counters(papi_events, 1);

       uint64_t* a_ptr = a;
       const uint64_t* a_ptr_end = a + a_count;
       uint64_t* b_ptr = b;
       const uint64_t* b_ptr_end = b + b_count;

       while (a_ptr &lt; a_ptr_end) {
    #ifndef NTLOAD
          __m256i aa = _mm256_load_si256((__m256i*)a_ptr);
    #else
          __m256i aa = _mm256_stream_load_si256((__m256i*)a_ptr);
    #endif
          __m256i bb = _mm256_load_si256((__m256i*)b_ptr);
          bb = _mm256_add_epi64(aa, bb);
          _mm256_store_si256((__m256i*)b_ptr, bb);

          a_ptr += 4;
          b_ptr += 4;
          if (b_ptr &gt;= b_ptr_end)
             b_ptr = b;
       }

       PAPI_stop_counters(papi_values, 1);
       std::cout &lt;&lt; &quot;L1 cache misses: &quot; &lt;&lt; papi_values[0] &lt;&lt; std::endl;
  
       free(a);
       free(b);
    }

What I wonder is whether CPU vendors support or are going to support non-temporal loads / prefetching or any other way how to label some data as not-being-hold in cache (e.g., to tag them as LRU). There are situations, e.g., in HPC, where similar scenarios are common in practice. For example, in sparse iterative linear solvers / eigensolvers, matrix data are usually very large (larger than cache capacities), but vectors are sometimes small enough to fit into L3 or even L2 cache. Then, we would like to keep them there at all costs. Unfortunately, loading of matrix data can cause invalidation of especially x-vector cache lines, even though in each solver iteration, matrix elements are used only once and there is no reason to keep them in cache after they have been processed.

**UPDATE**

I just did a similar experiment on an Intel Xeon Phi KNC, while measuring  runtime instead of L1 misses (I haven&#39;t find a way how to measure them reliably; PAPI and VTune gave weird metrics.) The results are here:

[![enter image description here][2]][2]

The orange curve represents ordinary loads and it has the expected shape. The blue curve represents loads with so-call eviction hint (EH) set in the instruction prefix and the gray curve represents a case where each cache line of `a` was manually evicted; both these tricks enabled by KNC obviously worked as we wanted to for `b` over 16 kiB. The code of the measured loop is as follows:

    while (a_ptr &lt; a_ptr_end) {
    #ifdef NTLOAD
       __m512i aa = _mm512_extload_epi64((__m512i*)a_ptr,
          _MM_UPCONV_EPI64_NONE, _MM_BROADCAST64_NONE, _MM_HINT_NT);
    #else
       __m512i aa = _mm512_load_epi64((__m512i*)a_ptr);
    #endif
       __m512i bb = _mm512_load_epi64((__m512i*)b_ptr);
       bb = _mm512_or_epi64(aa, bb);
       _mm512_store_epi64((__m512i*)b_ptr, bb);

    #ifdef EVICT
       _mm_clevict(a_ptr, _MM_HINT_T0);
    #endif

       a_ptr += 8;
       b_ptr += 8;
       if (b_ptr &gt;= b_ptr_end)
           b_ptr = b;
    }

**UPDATE 2**

On Xeon Phi, `icpc` generated for normal-load variant (orange curve) prefetching for `a_ptr`:

    400e93:       62 d1 78 08 18 4c 24    vprefetch0 [r12+0x80]

When I manually (by hex-editing the executable) modified this to:

    400e93:       62 d1 78 08 18 44 24    vprefetchnta [r12+0x80]

I got the desired resutls, even better than the blue/gray curves. However, I was not able to force the compiler to generate non-temporal prefetchnig for me, even by using `#pragma prefetch a_ptr:_MM_HINT_NTA` before the loop :(
  [1]: https://i.stack.imgur.com/LgpsB.png
  [2]: https://i.stack.imgur.com/CU2dY.png

Do current x86 architectures support non-temporal loads (from &quot;normal&quot; memory)?

I am wondering how much of Ulrich Drepper&#39;s [What Every Programmer Should Know About Memory][1] from 2007 is still valid. Also I could not find a newer version than 1.0 or an errata.

(Also in PDF form on Ulrich Drepper&#39;s own site: https://www.akkadia.org/drepper/cpumemory.pdf)


  [1]: http://lwn.net/Articles/250967/

What Every Programmer Should Know About Memory?

Can anyone give me the approximate time (in nanoseconds) to access L1, L2 and L3 caches, as well as main memory on Intel i7 processors?

While this isn&#39;t specifically a programming question, knowing these kinds of speed details is neccessary for some low-latency programming challenges.  




Approximate cost to access various caches and main memory?

What is the difference between &quot;**cache unfriendly code**&quot; and the &quot;**cache friendly**&quot; code?

How can I make sure I write cache-efficient code? 

What is a &quot;cache-friendly&quot; code?

This could sound like a subjective question, but what I am looking for are specific instances, which you could have encountered related to this.


  1. How to make code, cache effective/cache friendly (more cache hits, as few cache misses as possible)? From both perspectives, data cache &amp; program cache (instruction cache),
i.e. what things in one&#39;s code, related to data structures and code constructs, should one take care of to make it cache effective.
 
  2. Are there any particular data structures one must use/avoid, or is there a particular way of accessing the members of that structure etc... to make code cache effective.

  3. Are there any program constructs (if, for, switch, break, goto,...), code-flow (for inside an if, if inside a for, etc ...) one should follow/avoid in this matter?

I am looking forward to hearing individual experiences related to making cache efficient code in general. It can be any programming language (C, C++, Assembly, ...), any hardware target (ARM, Intel, PowerPC, ...), any OS  (Windows, Linux,S ymbian, ...), etc.. 

The variety will help to better to understand it deeply.

How does one write code that best utilizes the CPU cache to improve performance?

My understanding is that the main difference between the two methods is that in &quot;write-through&quot; method data is written to the main memory through the cache immediately, while in &quot;write-back&quot; data is written in a &quot;later time&quot;.

We still need to wait for the memory in &quot;later time&quot; so What is the benefit of &quot;write-through&quot;?

Write-back vs Write-Through caching?

From a previous [question][1] on this forum, I learned that in most of the memory systems, L1 cache is a subset of the L2 cache means any entry removed from L2 is also removed from L1. 

So now my question is how do I determine a corresponding entry in L1 cache for an entry in the L2 cache. The only information stored in the L2 entry is the tag information. Based on this tag information, if I re-create the addr it may span multiple lines in the L1 cache if the line-sizes of L1 and L2 cache are not same. 

Does the architecture really bother about flushing both the lines or it just maintains L1 and L2 cache with the same line-size. 

I understand that this is a policy decision but I want to know the commonly used technique.


  [1]: https://stackoverflow.com/questions/14705840/cache-eviction-from-l1-cache-on-l2-eviction

Line size of L1 and L2 caches

C++17 added [`std::hardware_destructive_interference_size` and `std::hardware_constructive_interference_size`][1]. First, I thought it is just a portable way to get the size of a L1 cache line but that is an oversimplification.

Questions:

* How are these constants related to the L1 cache line size?
* Is there a good example that demonstrates their use cases?
* Both are defined `static constexpr`. Is that not a problem if you build a binary and execute it on other machines with different cache line sizes? How can it protect against false sharing in that scenario when you are not certain on which machine your code will be running?

  [1]: http://en.cppreference.com/w/cpp/thread/hardware_destructive_interference_size

Understanding std::hardware_destructive_interference_size and std::hardware_constructive_interference_size

From the 11th Chapter(*Performance and Scalability*) and the section named *Context Switching* of the [JCIP book][1]:

&gt; When a new thread is switched in, the data it needs is unlikely to be
&gt; in the local processor cache, so a context-switch causes a flurry of
&gt; cache misses, and thus threads run a little more slowly when they are
&gt; first scheduled.

 1. Can someone explain in an easy to understand way the concept of *cache miss* and its probable opposite (*cache hit*)?
 2. Why context-switching would cause a lot of cache miss?

[1]:http://jcip.net.s3-website-us-east-1.amazonaws.com/

What is a cache hit and a cache miss? Why would context-switching cause cache miss?

Below are two programs that are almost identical except that I switched the `i` and `j` variables around. They both run in different amounts of time. Could someone explain why this happens?

Version 1

    #include &lt;stdio.h&gt;
    #include &lt;stdlib.h&gt;
    
    main () {
      int i,j;
      static int x[4000][4000];
      for (i = 0; i &lt; 4000; i++) {
        for (j = 0; j &lt; 4000; j++) {
          x[j][i] = i + j; }
      }
    }

 
Version 2

    #include &lt;stdio.h&gt;
    #include &lt;stdlib.h&gt;
        
    main () {
      int i,j;
      static int x[4000][4000];
      for (j = 0; j &lt; 4000; j++) {
         for (i = 0; i &lt; 4000; i++) {
           x[j][i] = i + j; }
       }
    }

Why does the order of the loops affect performance when iterating over a 2D array?

Which of the following orderings of nested loops to iterate over a 2D array is more efficient in terms of time (cache performance)? Why?

    int a[100][100];
    
    for(i=0; i&lt;100; i++)
    {
       for(j=0; j&lt;100; j++)
       {
           a[i][j] = 10;    
       }
    }
or

    for(i=0; i&lt;100; i++)
    {
       for(j=0; j&lt;100; j++)
       {
          a[j][i] = 10;    
       }
    }



Which ordering of nested loops for iterating over a 2D array is more efficient

I tested the speed of `memcpy()` noticing the speed drops dramatically at i*4KB. The result is as follow: the Y-axis is the speed(MB/second) and the X-axis is the size of buffer for `memcpy()`, increasing from 1KB to 2MB. Subfigure 2 and Subfigure 3 detail the part of 1KB-150KB and 1KB-32KB.

Environment：

CPU : Intel(R) Xeon(R) CPU E5620  @ 2.40GHz 

OS :  2.6.35-22-generic #33-Ubuntu

GCC compiler flags : -O3 -msse4 -DINTEL_SSE4 -Wall -std=c99
 
![Graphs of memcpy speed showing troughs every 4k][1]

I guess it must be related to caches, but I can&#39;t find a reason from the following cache-unfriendly cases:

 * https://stackoverflow.com/questions/12264970/why-is-my-program-slow-when-looping-over-exactly-8192-elements

 * https://stackoverflow.com/questions/11413855/why-is-transposing-a-matrix-of-512x512-much-slower-than-transposing-a-matrix-of

Since the performance degradation of these two cases are caused by unfriendly loops which read scattered bytes into the cache, wasting the rest of the space of a cache line.

Here is my code:

    void memcpy_speed(unsigned long buf_size, unsigned long iters){
        struct timeval start,  end;
        unsigned char * pbuff_1;
        unsigned char * pbuff_2;

        pbuff_1 = malloc(buf_size);
        pbuff_2 = malloc(buf_size);

        gettimeofday(&amp;start, NULL);
        for(int i = 0; i &lt; iters; ++i){
            memcpy(pbuff_2, pbuff_1, buf_size);
        }   
        gettimeofday(&amp;end, NULL);
        printf(&quot;%5.3f\n&quot;, ((buf_size*iters)/(1.024*1.024))/((end.tv_sec - \
        start.tv_sec)*1000*1000+(end.tv_usec - start.tv_usec)));
        free(pbuff_1);
        free(pbuff_2);
    }

UPDATE
=====
Considering suggestions from @usr, @ChrisW and @Leeor, I redid the test more precisely and the graph below shows the results. The buffer size is from 26KB to 38KB, and I tested it every other 64B(26KB, 26KB+64B, 26KB+128B, ......, 38KB). Each test loops 100,000 times in about 0.15 second. The interesting thing is the drop not only occurs exactly in 4KB boundary, but also comes out in 4*i+2 KB, with a much less falling amplitude.


![More graphs showing performance drops][2]


PS
==
@Leeor offered a way to fill the drop, adding a 2KB dummy buffer between `pbuff_1` and `pbuff_2`. It works, but I am not sure about Leeor&#39;s explanation.


![enter image description here][3] 


  [1]: http://i.stack.imgur.com/TJ4Xx.png
  [2]: http://i.stack.imgur.com/qto0R.png
  [3]: http://i.stack.imgur.com/NL3uy.png

Why does the speed of memcpy() drop dramatically every 4KB?

is there a way in C++ to determine the CPU&#39;s cache size? i have an algorithm that processes a lot of data and i&#39;d like to break this data down into chunks such that they fit into the cache. Is this possible?
Can you give me any other hints on programming with cache-size in mind (especially in regard to multithreaded/multicore data processing)?

Thanks!

C++ cache aware programming

I&#39;m writing a small program in C, and I want to measure it&#39;s performance.

I want to see how much time do it run in the processor and how many cache hit+misses has it made. Information about context switches and memory usage would be nice to have too. 

The program takes less than a second to execute.

I like the information of /proc/[pid]/stat, but I don&#39;t know how to see it after the program has died/been killed.

Any ideas?

**EDIT:** I think Valgrind adds a lot of overhead. That&#39;s why I wanted a simple tool, like /proc/[pid]/stat, that is always there.

All Cpu Cache Solutions on Gang of Coders

Total of 19 Cpu Cache Solutions