title: Measuring Cache Latencies
body: <p>So I am trying to measure the latencies of L1, L2, L3 cache using C. I know the size of them and I feel I understand conceptually how to do it but I am running into problems with my implementation. I am wondering if some of the other hardware intricacies like pre-fetching are causing issues.</p>
  
  <pre><code>#include &lt;time.h&gt;
  #include &lt;stdio.h&gt;
  #include &lt;string.h&gt;
  
  int main(){
      srand(time(NULL));  // Seed ONCE
      const int L1_CACHE_SIZE =  32768/sizeof(int);
      const int L2_CACHE_SIZE =  262144/sizeof(int);
      const int L3_CACHE_SIZE =  6587392/sizeof(int);
      const int NUM_ACCESSES = 1000000;
      const int SECONDS_PER_NS = 1000000000;
      int arrayAccess[L1_CACHE_SIZE];
      int arrayInvalidateL1[L1_CACHE_SIZE];
      int arrayInvalidateL2[L2_CACHE_SIZE];
      int arrayInvalidateL3[L3_CACHE_SIZE];
      int count=0;
      int index=0;
      int i=0;
      struct timespec startAccess, endAccess;
      double mainMemAccess, L1Access, L2Access, L3Access;
      int readValue=0;
  
      memset(arrayAccess, 0, L1_CACHE_SIZE*sizeof(int));
      memset(arrayInvalidateL1, 0, L1_CACHE_SIZE*sizeof(int));
      memset(arrayInvalidateL2, 0, L2_CACHE_SIZE*sizeof(int));
      memset(arrayInvalidateL3, 0, L3_CACHE_SIZE*sizeof(int));
  
      index = 0;
      clock_gettime(CLOCK_REALTIME, &amp;startAccess); //start clock
      while (index &lt; L1_CACHE_SIZE) {
          int tmp = arrayAccess[index];               //Access Value from L2
          index = (index + tmp + ((index &amp; 4) ? 28 : 36));   // on average this should give 32 element skips, with changing strides
          count++;                                           //divide overall time by this 
      }
      clock_gettime(CLOCK_REALTIME, &amp;endAccess); //end clock
      mainMemAccess = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
      mainMemAccess /= count;
  
      printf("Main Memory Access %lf\n", mainMemAccess);
  
      index = 0;
      count=0;
      clock_gettime(CLOCK_REALTIME, &amp;startAccess); //start clock
      while (index &lt; L1_CACHE_SIZE) {
          int tmp = arrayAccess[index];               //Access Value from L2
          index = (index + tmp + ((index &amp; 4) ? 28 : 36));   // on average this should give 32 element skips, with changing strides
          count++;                                           //divide overall time by this 
      }
      clock_gettime(CLOCK_REALTIME, &amp;endAccess); //end clock              
      L1Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
      L1Access /= count;
  
      printf("L1 Cache Access %lf\n", L1Access);
  
      //invalidate L1 by accessing all elements of array which is larger than cache
      for(count=0; count &lt; L1_CACHE_SIZE; count++){
          int read = arrayInvalidateL1[count]; 
          read++;
          readValue+=read;               
      }
  
      index = 0;
      count = 0;
      clock_gettime(CLOCK_REALTIME, &amp;startAccess); //start clock
      while (index &lt; L1_CACHE_SIZE) {
          int tmp = arrayAccess[index];               //Access Value from L2
          index = (index + tmp + ((index &amp; 4) ? 28 : 36));   // on average this should give 32 element skips, with changing strides
          count++;                                           //divide overall time by this 
      }
      clock_gettime(CLOCK_REALTIME, &amp;endAccess); //end clock
      L2Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
      L2Access /= count;
  
      printf("L2 Cache Acces %lf\n", L2Access);
  
      //invalidate L2 by accessing all elements of array which is larger than cache
      for(count=0; count &lt; L2_CACHE_SIZE; count++){
          int read = arrayInvalidateL2[count];  
          read++;
          readValue+=read;                        
      }
  
      index = 0;
      count=0;
      clock_gettime(CLOCK_REALTIME, &amp;startAccess); //sreadValue+=read;tart clock
      while (index &lt; L1_CACHE_SIZE) {
          int tmp = arrayAccess[index];               //Access Value from L2
          index = (index + tmp + ((index &amp; 4) ? 28 : 36));   // on average this should give 32 element skips, with changing strides
          count++;                                           //divide overall time by this 
      }
      clock_gettime(CLOCK_REALTIME, &amp;endAccess); //end clock
      L3Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
      L3Access /= count;
  
      printf("L3 Cache Access %lf\n", L3Access);
  
      printf("Read Value: %d", readValue);
  
  }
  </code></pre>
  
  <p>I start out by accessing a value in the array I want data from. This should obviously come from main memory because it the first access. The array is small (less than page size) so it should be copied into L1, L2, L3. I access value from the same array which should now be L1. I then access all the values from an array of the same size as L1 cache to invalidate data I want to access (so now it should just be in L2/3). Then I repeat this process for L2 and L3. The access times are clearly off though, which means I am doing something wrong...</p>
  
  <p>I think there might be issues with the time it takes to clock (start and stop are going to take some time in ns and it will change when they are cached/unchached)</p>
  
  <p>Can someone give me some pointers on what I might be doing wrong?</p>
  
  <p>UPDATE1: So i amortized the cost of the timer by making lots of accesses, I fixed the size of my caches and I also took the advice to make a more complex indexing scheme to avoid fixed strides. Unfortunately the times are still off. They all seem to be coming for L1. I am thinking the issue might be with invalidating instead of accessing. Would a random vs LRU scheme affect the data being invalidated?</p>
  
  <p>UPDATE2: Fixed the memset (Added L3 memset to invalidate data in L3 as well so first access starts at main memory) and indexing scheme, still no luck.</p>
  
  <p>UPDATE3: I couldn't ever get this method to work but there were some good suggested answers and I posted a couple solutions of my own.</p>
  
  <p>I also ran Cachegrind to view hit/miss</p>
  
  <pre><code> ==6710== I   refs:      1,735,104
  ==6710== I1  misses:        1,092
  ==6710== LLi misses:        1,084
  ==6710== I1  miss rate:      0.06%
  ==6710== LLi miss rate:      0.06%
  ==6710== 
  ==6710== D   refs:      1,250,696  (721,162 rd   + 529,534 wr)
  ==6710== D1  misses:      116,492  (  7,627 rd   + 108,865 wr)
  ==6710== LLd misses:      115,102  (  6,414 rd   + 108,688 wr)
  ==6710== D1  miss rate:       9.3% (    1.0%     +    20.5%  )
  ==6710== LLd miss rate:       9.2% (    0.8%     +    20.5%  )
  ==6710== 
  ==6710== LL refs:         117,584  (  8,719 rd   + 108,865 wr)
  ==6710== LL misses:       116,186  (  7,498 rd   + 108,688 wr)
  ==6710== LL miss rate:        3.8% (    0.3%     +    20.5%  )
  
  
          Ir I1mr ILmr      Dr  D1mr  DLmr     Dw D1mw DLmw 
  
        .    .    .       .     .     .      .    .    .  #include &lt;time.h&gt;
        .    .    .       .     .     .      .    .    .  #include &lt;stdio.h&gt;
        .    .    .       .     .     .      .    .    .  #include &lt;string.h&gt;
        .    .    .       .     .     .      .    .    .  
        6    0    0       0     0     0      2    0    0  int main(){
        5    1    1       0     0     0      2    0    0      srand(time(NULL));  // Seed ONCE
        1    0    0       0     0     0      1    0    0      const int L1_CACHE_SIZE =  32768/sizeof(int);
        1    0    0       0     0     0      1    0    0      const int L2_CACHE_SIZE =  262144/sizeof(int);
        1    0    0       0     0     0      1    0    0      const int L3_CACHE_SIZE =  6587392/sizeof(int);
        1    0    0       0     0     0      1    0    0      const int NUM_ACCESSES = 1000000;
        1    0    0       0     0     0      1    0    0      const int SECONDS_PER_NS = 1000000000;
       21    2    2       3     0     0      3    0    0      int arrayAccess[L1_CACHE_SIZE];
       21    1    1       3     0     0      3    0    0      int arrayInvalidateL1[L1_CACHE_SIZE];
       21    2    2       3     0     0      3    0    0      int arrayInvalidateL2[L2_CACHE_SIZE];
       21    1    1       3     0     0      3    0    0      int arrayInvalidateL3[L3_CACHE_SIZE];
        1    0    0       0     0     0      1    0    0      int count=0;
        1    1    1       0     0     0      1    0    0      int index=0;
        1    0    0       0     0     0      1    0    0      int i=0;
        .    .    .       .     .     .      .    .    .      struct timespec startAccess, endAccess;
        .    .    .       .     .     .      .    .    .      double mainMemAccess, L1Access, L2Access, L3Access;
        1    0    0       0     0     0      1    0    0      int readValue=0;
        .    .    .       .     .     .      .    .    .  
        7    0    0       2     0     0      1    1    1      memset(arrayAccess, 0, L1_CACHE_SIZE*sizeof(int));
        7    1    1       2     2     0      1    0    0      memset(arrayInvalidateL1, 0, L1_CACHE_SIZE*sizeof(int));
        7    0    0       2     2     0      1    0    0      memset(arrayInvalidateL2, 0, L2_CACHE_SIZE*sizeof(int));
        7    1    1       2     2     0      1    0    0      memset(arrayInvalidateL3, 0, L3_CACHE_SIZE*sizeof(int));
        .    .    .       .     .     .      .    .    .  
        1    0    0       0     0     0      1    1    1      index = 0;
        4    0    0       0     0     0      1    0    0      clock_gettime(CLOCK_REALTIME, &amp;startAccess); //start clock
      772    1    1     514     0     0      0    0    0      while (index &lt; L1_CACHE_SIZE) {
    1,280    1    1     768   257   257    256    0    0          int tmp = arrayAccess[index];               //Access Value from L2
    2,688    0    0     768     0     0    256    0    0          index = (index + tmp + ((index &amp; 4) ? 28 : 36));   // on average this should give 32 element skips, with changing strides
      256    0    0     256     0     0      0    0    0          count++;                                           //divide overall time by this 
        .    .    .       .     .     .      .    .    .      }
        4    0    0       0     0     0      1    0    0      clock_gettime(CLOCK_REALTIME, &amp;endAccess); //end clock
       14    1    1       5     1     1      1    1    1      mainMemAccess = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
        6    0    0       2     0     0      1    0    0      mainMemAccess /= count;
        .    .    .       .     .     .      .    .    .  
        6    1    1       2     0     0      2    0    0      printf("Main Memory Access %lf\n", mainMemAccess);
        .    .    .       .     .     .      .    .    .  
        1    0    0       0     0     0      1    0    0      index = 0;
        1    0    0       0     0     0      1    0    0      count=0;
        4    1    1       0     0     0      1    0    0      clock_gettime(CLOCK_REALTIME, &amp;startAccess); //start clock
      772    1    1     514     0     0      0    0    0      while (index &lt; L1_CACHE_SIZE) {
    1,280    0    0     768   240     0    256    0    0          int tmp = arrayAccess[index];               //Access Value from L2
    2,688    0    0     768     0     0    256    0    0          index = (index + tmp + ((index &amp; 4) ? 28 : 36));   // on average this should give 32 element skips, with changing strides
      256    0    0     256     0     0      0    0    0          count++;                                           //divide overall time by this 
        .    .    .       .     .     .      .    .    .      }
        4    0    0       0     0     0      1    0    0      clock_gettime(CLOCK_REALTIME, &amp;endAccess); //end clock              
       14    1    1       5     0     0      1    1    0      L1Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
        6    1    1       2     0     0      1    0    0      L1Access /= count;
        .    .    .       .     .     .      .    .    .  
        6    0    0       2     0     0      2    0    0      printf("L1 Cache Access %lf\n", L1Access);
        .    .    .       .     .     .      .    .    .  
        .    .    .       .     .     .      .    .    .      //invalidate L1 by accessing all elements of array which is larger than cache
   32,773    1    1  24,578     0     0      1    0    0      for(count=0; count &lt; L1_CACHE_SIZE; count++){
   40,960    0    0  24,576   513   513  8,192    0    0          int read = arrayInvalidateL1[count]; 
    8,192    0    0   8,192     0     0      0    0    0          read++;
   16,384    0    0  16,384     0     0      0    0    0          readValue+=read;               
        .    .    .       .     .     .      .    .    .      }
        .    .    .       .     .     .      .    .    .  
        1    0    0       0     0     0      1    0    0      index = 0;
        1    1    1       0     0     0      1    0    0      count = 0;
        4    0    0       0     0     0      1    1    0      clock_gettime(CLOCK_REALTIME, &amp;startAccess); //start clock
      772    1    1     514     0     0      0    0    0      while (index &lt; L1_CACHE_SIZE) {
    1,280    0    0     768   256     0    256    0    0          int tmp = arrayAccess[index];               //Access Value from L2
    2,688    0    0     768     0     0    256    0    0          index = (index + tmp + ((index &amp; 4) ? 28 : 36));   // on average this should give 32 element skips, with changing strides
      256    0    0     256     0     0      0    0    0          count++;                                           //divide overall time by this 
        .    .    .       .     .     .      .    .    .      }
        4    1    1       0     0     0      1    0    0      clock_gettime(CLOCK_REALTIME, &amp;endAccess); //end clock
       14    0    0       5     1     0      1    1    0      L2Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
        6    1    1       2     0     0      1    0    0      L2Access /= count;
        .    .    .       .     .     .      .    .    .  
        6    0    0       2     0     0      2    0    0      printf("L2 Cache Acces %lf\n", L2Access);
        .    .    .       .     .     .      .    .    .  
        .    .    .       .     .     .      .    .    .      //invalidate L2 by accessing all elements of array which is larger than cache
  262,149    2    2 196,610     0     0      1    0    0      for(count=0; count &lt; L2_CACHE_SIZE; count++){
  327,680    0    0 196,608 4,097 4,095 65,536    0    0          int read = arrayInvalidateL2[count];  
   65,536    0    0  65,536     0     0      0    0    0          read++;
  131,072    0    0 131,072     0     0      0    0    0          readValue+=read;                        
        .    .    .       .     .     .      .    .    .      }
        .    .    .       .     .     .      .    .    .  
        1    0    0       0     0     0      1    0    0      index = 0;
        1    0    0       0     0     0      1    0    0      count=0;
        4    0    0       0     0     0      1    1    0      clock_gettime(CLOCK_REALTIME, &amp;startAccess); //sreadValue+=read;tart clock
      772    1    1     514     0     0      0    0    0      while (index &lt; L1_CACHE_SIZE) {
    1,280    0    0     768   256     0    256    0    0          int tmp = arrayAccess[index];               //Access Value from L2
    2,688    0    0     768     0     0    256    0    0          index = (index + tmp + ((index &amp; 4) ? 28 : 36));   // on average this should give 32 element skips, with changing strides
      256    0    0     256     0     0      0    0    0          count++;                                           //divide overall time by this 
        .    .    .       .     .     .      .    .    .      }
        4    0    0       0     0     0      1    0    0      clock_gettime(CLOCK_REALTIME, &amp;endAccess); //end clock
       14    1    1       5     1     0      1    1    0      L3Access = ((endAccess.tv_sec - startAccess.tv_sec) * SECONDS_PER_NS) + (endAccess.tv_nsec - startAccess.tv_nsec);
        6    0    0       2     0     0      1    0    0      L3Access /= count;
        .    .    .       .     .     .      .    .    .  
        6    1    1       2     0     0      2    0    0      printf("L3 Cache Access %lf\n", L3Access);
        .    .    .       .     .     .      .    .    .  
        6    0    0       1     0     0      1    0    0      printf("Read Value: %d", readValue);
        .    .    .       .     .     .      .    .    .  
        3    0    0       3     0     0      0    0    0  }
  </code></pre>