" 缓存不友好代码 "和" 缓存友好 "代码之间有什么区别？

如何确保编写高效缓存代码？

可能重复:
这两个for循环中的哪一个在时间和缓存性能方面更有效

下面是两个几乎相同的程序,除了我切换i和j变量.它们都运行在不同的时间.有人能解释为什么会这样吗？

版本1

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (i = 0; i < 4000; i++) {
    for (j = 0; j < 4000; j++) {
      x[j][i] = i + j; }
  }
}

版本2

#include <stdio.h>
#include <stdlib.h>

main () {
  int i,j;
  static int x[4000][4000];
  for (j = 0; j < 4000; j++) {
     for (i = 0; i < 4000; i++) {
       x[j][i] = i …

任何人都可以给我大概的时间(以纳秒为单位)来访问L1,L2和L3缓存,以及Intel i7处理器上的主内存吗？

虽然这不是一个特别的编程问题,但是对于某些低延迟编程挑战而言,了解这些速度细节是必要的.

这听起来像是一个主观问题,但我正在寻找的是特定的实例,你可能遇到过与此相关的问题.

1. 如何制作代码,缓存有效/缓存友好(更多缓存命中,尽可能少的缓存未命中)？从两个角度来看,数据缓存和程序缓存(指令缓存),即一个代码中与数据结构和代码结构相关的内容,应该由一个人来处理,使其缓存有效.

2. 是否有必须使用/避免的特定数据结构,或者是否有特定方式来访问该结构的成员等...以使代码缓存有效.

3. 是否存在任何程序结构(if,for,switch,break,goto,...),代码流(对于if内部,如果在for之内等等),应该遵循/避免这个问题？

我期待听到有关制作缓存高效代码的个人经验.它可以是任何编程语言(C,C++,汇编,...),任何硬件目标(ARM,Intel,PowerPC,...),任何操作系统(Windows,Linux,S ymbian,...)等. .

这种变化将有助于更好地理解它.

我的理解是两种方法的主要区别在于,在"直写"方法中,数据立即通过高速缓存写入主存,而在"回写"数据则是在"后期"写入.

我们还需要在"后期"等待内存,那么"直写"的好处是什么？

在时间(缓存性能)方面,嵌套循环在迭代2D阵列中的哪一个排序更有效？为什么？

int a[100][100];

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
       a[i][j] = 10;    
   }
}

要么

for(i=0; i<100; i++)
{
   for(j=0; j<100; j++)
   {
      a[j][i] = 10;    
   }
}

从第11章(性能和可扩展性)和部分命名上下文切换的的JCIP书:

当切换新线程时,它所需的数据不太可能在本地处理器高速缓存中,因此上下文切换会导致一连串的高速缓存未命中,因此线程在首次调度时运行速度会慢一些.

1. 有人可以用一种易于理解的方式解释缓存未命中的概念及其可能的相反(缓存命中)吗？
2. 为什么上下文切换会导致大量缓存未命中？

我测试了memcpy()在i*4KB时注意速度急剧下降的速度.结果如下:Y轴是速度(MB /秒),X轴是缓冲区的大小memcpy(),从1KB增加到2MB.子图2和子图3详述了1KB-150KB和1KB-32KB的部分.

环境:

CPU:Intel(R)Xeon(R)CPU E5620 @ 2.40GHz

操作系统:2.6.35-22-通用#33-Ubuntu

GCC编译器标志:-O3 -msse4 -DINTEL_SSE4 -Wall -std = c99

我想它必须与缓存相关,但我无法从以下缓存不友好的情况中找到原因:

• 为什么我的程序在完全循环8192个元素时会变慢？

• 为什么转换512x512的矩阵要比转换513x513的矩阵慢得多？

由于这两种情况的性能下降是由不友好的循环引起的,这些循环将分散的字节读入高速缓存,浪费了高速缓存行的其余空间.

这是我的代码:

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(&start, NULL);
    for(int i = 0; i < iters; ++i){
        memcpy(pbuff_2, pbuff_1, buf_size);
    }   
    gettimeofday(&end, NULL);
    printf("%5.3f\n", ((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

考虑到来自@ usr,@ ChrisW和@Leeor的建议,我更准确地重新测试了测试,下面的图表显示了结果.缓冲区大小从26KB到38KB,我每隔64B测试一次(26KB,26KB + …

有没有办法在C++中确定CPU的缓存大小？我有一个处理大量数据的算法,我想将这些数据分解成块,以便它们适合缓存.这可能吗？你能否给我一些有关缓存大小的编程的其他提示(特别是在多线程/多核数据处理方面)？

谢谢!

我目前正在努力更好地了解与内存相关的性能问题.我读到某处内存局部性对于读取比写入更重要,因为在前一种情况下,CPU必须实际等待数据,而在后一种情况下,它可以将它们运出并忘记它们.

考虑到这一点,我做了以下快速和肮脏的测试:

更新3(非python/numpy用户解释):

我在python/numpy中编写了一个脚本,它创建了一个N个随机浮点数和一个置换数组,即一个包含随机顺序的数字0到N-1的数组.然后重复(1)线性地读取数据阵列并将其写回由置换给出的随机访问模式中的新阵列,或者(2)以置换顺序读取数据阵列并线性地将其写入新阵列.

令我惊讶的是(2)似乎始终比(1)快.但是,我的脚本存在问题

• python/numpy是相当高级别的,不清楚读/写是如何实现的.
• 我可能没有正确平衡这两个案例.

此外,下面的一些答案/评论表明我原来的期望并不总是正确的,根据cpu缓存的细节,这两种情况可能会更快.

我现在放置的赏金适用于以下内容:

更新2:

鉴于迄今为止的评论和答案,我希望得到澄清

• 是@ BM的numba实验结论？
• 或者它可以采取任何方式取决于缓存细节？

请以初学者友好的方式解释可能与此相关的各种缓存概念(参见@Trilarion的评论,@ Yann Vernier的回答).支持代码可能在C/cython/numpy/numba或python中.

或者,解释我明显不足的python实验的行为.

原文:

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() …