c - 缓存大小对代码的影响

Question

我想研究缓存大小对代码的影响。对于在大型数组上运行的程序，如果数组适合缓存，则可以显着提高速度。

我如何衡量这一点？

我尝试运行这个 C 程序:

#define L1_CACHE_SIZE       32      //  Kbytes  8192 integers
#define L2_CACHE_SIZE       256     //  Kbytes  65536 integers
#define L3_CACHE_SIZE       4096    //  Kbytes

#define ARRAYSIZE 32000
#define ITERATIONS 250

int arr[ARRAYSIZE];

/*************** TIME MEASSUREMENTS ***************/

double microsecs() {
    struct timeval t;
    if (gettimeofday(&t, NULL) < 0 )
    return 0.0;
    return (t.tv_usec + t.tv_sec * 1000000.0);    
}

void init_array() {
    int i;
    for (i = 0; i < ARRAYSIZE; i++) {
        arr[i] = (rand() % 100);
    }
}

int operation() {
    int i, j;
    int sum = 0;
    for (j = 0; j < ITERATIONS; j++) {
        for (i = 0; i < ARRAYSIZE; i++) {
            sum =+ arr[i];
        }
    }

    return sum;
}

void main() {

    init_array();

    double t1 = microsecs();
    int result = operation();
    double t2 = microsecs();

    double t = t2 - t1;

    printf("CPU time %f milliseconds\n", t/1000);
    printf("Result: %d\n", result);    
}

采用 ARRAYSIZE 和 ITERATION 的值(保持乘积，从而保持指令数量恒定)，以检查如果数组适合缓存，程序是否运行得更快，但我总是获得相同的 CPU 时间。

谁能告诉我我做错了什么吗？

Answer 1

你真正想做的是 build 一座“内存山”。内存山可以帮助您直观地了解内存访问如何影响程序性能。具体来说，它测量读取吞吐量与空间局部性和时间局部性。良好的空间局部性意味着连续的内存访问彼此靠近，良好的时间局部性意味着某个内存位置在短时间内被多次访问。这是a link其中简要提到了缓存性能和内存山。该链接中提到的教科书的第三版是一个非常好的引用资料，特别是第 6 章，用于了解内存和缓存性能。 (事实上​​，我目前正在使用该部分作为回答这个问题的引用。)

另一个link显示了一个可用于测量缓存性能的测试函数，我已将其复制到此处:

void test(int elems, int stride)
{
    int i, result = 0;
    volatile int sink;
    for (i = 0; i < elems; i+=stride)
        result += data[i];
    sink = result;
}

跨度是时间局部性 - 内存访问的间隔有多远。这个想法是这个函数将估计运行所需的周期数。为了获得吞吐量，您需要采用(大小/步长)/(周期数/MHz)，其中大小是数组的大小(以字节为单位)，周期数是此函数的结果，MHz 是处理器的时钟速度。在进行任何测量以“预热”缓存之前，您需要调用此函数一次。然后，运行循环并进行测量。

我找到了GitHub repository您可以使用它在自己的机器上构建 3D 内存山。我鼓励您在具有不同处理器的多台机器上尝试并比较差异。