如何提高缓存未命中率的实例？

Question

我正在尝试编写一个示例程序，它的高缓存未命中率。我想我可以尝试按列访问矩阵，如下所示：

#include <stdlib.h>

int main(void)
{
    int i, j, k;

    int w = 1000;
    int h = 1000;

    int **block = malloc(w * sizeof(int*));
    for (i = 0; i < w; i++) {
        block[i] = malloc(h * sizeof(int));
    }

    for (k = 0; k < 10; k++) {
        for (i = 0; i < w; i++) {
            for (j = 0; j < h; j++) {
                block[j][i] = 0;
            }
        }
    }

    return 0;
}

当我使用-O0标志编译并使用perf stat -r 5 -B -e cache-references,cache-misses ./a.out运行时，它会给我：

 Performance counter stats for './a.out' (5 runs):

    715,463 cache-references                                      ( +-  0.42% )
    527,634 cache-misses          #   73.747 % of all cache refs  ( +-  2.53% )

0.112001160 seconds time elapsed                                  ( +-  1.58% )

这对于我的需求已经足够好了。但是，如果我将矩阵大小更改为2000x2000，它会显示：

 Performance counter stats for './a.out' (5 runs):

  6,364,995 cache-references                                      ( +-  2.32% )
  2,534,989 cache-misses          #   39.827 % of all cache refs  ( +-  0.02% )

0.461104903 seconds time elapsed                                  ( +-  0.92% )

如果我将其进一步增加到3000x3000，我会得到：

 Performance counter stats for './a.out' (5 runs):

 59,204,028 cache-references                                      ( +-  1.36% )
  5,662,629 cache-misses          #    9.565 % of all cache refs  ( +-  0.11% )

1.116573625 seconds time elapsed                                  ( +-  0.32% )

这很奇怪，因为我期望随着大小的增加，缓存未命中率会更高。我需要尽可能与平台无关的解决方案。计算机体系结构课程已经很久以前了，所以任何见解都会受到欢迎。

注

我说过我需要相对独立于平台的解决方案，但这些是我的规格：

• Intel® Core™ i5-2467M
• 4 GiB RAM
• 64位ubuntu 12.04

- none

---

@AlexChamberlain 我不明白我应该做什么。 - none

请尝试使用“-O3”参数运行您的示例。 - Alex Chamberlain

@AlexChamberlain -O2 和 -O3 都让我获得了约 28% 的提升。 - none

从Bjarne Stroustrup本人（意思是）：“一个愚蠢的缓存未命中代码的典型例子是线性遍历链表。” 你可以尝试一下。如果节点被创建得有些非线性，并且在已经被大量分段/使用的堆上（当然，列表很大），那么预期的缓存未命中率几乎达到100％。 - Mikael Persson

有趣的是，缓存未命中次数和时间的增加大致与您使用的总内存成比例增加，而缓存引用次数则超出了预期的n^2增长。那是怎么回事呢？如果我正确地认为这很奇怪，那么这就是将您的缓存未命中率稀释到意外低百分比的原因。 - Steve Jessop

Answer 1

要注意现代CPU中的自动预取功能-它通常可以检测到步长访问。可以尝试随机访问模式，例如：

int main(void)
{
    int i;

    int n = 1000 * 1000;

    int *block = malloc(n * sizeof(int));

    for (i = 0; i < n / 10; i++) {
         int ri = rand() % n;
         block[ri] = 0;
    }

    return 0;
}

- Paul R

---

我不反对。只是“记录”一下 ;) - Nik Bougalis

对于一个小矩阵，你需要摆脱外部的 k 循环，否则 L2/L3 缓存会挫败你的目标。（现在已经编辑回答，删除了外部的 k 循环。） - Paul R

我认为既然我们不需要访问所有元素，我可以将嵌套的for循环中的数字减少到一些固定值，如10、100和100，但对于3000矩阵，这给了我37%。 - none

@gokcehan：问题在于1000x1000个整数基本上适合L1缓存，这意味着（如果没有操作系统或任何东西），_任何_访问模式都不会有_任何_缺失。你主要因为其他程序和操作系统也在运行而出现缺失。 - Mooing Duck

@Mooing Duck，那可真是一个强大的处理器。 - user1252446

Answer 2

我并不确信你能够比较这些程序或者保证任何事情，因为这取决于操作系统如何分配个别内存块。

你至少应该将所有的内存都分配为一个块，然后通过索引进入该块以获得所有数组（int*和int）。这样你就有了一个一致的起点。你可能需要将数组大小作为参数传递，而不是每次重新编译。

你也可以进行微调，使其分配远超你所需的内存，并将每行（或列，按照你的写法）放置到其中，以确保矩阵中只加载了一行（列）的缓存。例如：找出你的高速缓存的大小，并将每个块之间至少分隔那么多字节。

请注意，在退出前你应该真正地释放你的内存。free内存。

正如其他人已经指出的那样，随机化访问模式是一个好主意。

- paddy

---

我曾经尝试过连续的内存块，在某些情况下，它给了我大约相同的数字。在这一点上，传递数组大小和释放内存似乎并不重要，除非我漏掉了什么。 - none

好的，也许我有点守旧。那是在你可以在进程外泄漏内存的日子里。 - paddy