故意制造高L1缓存未命中率的程序

Question

我目前正在尝试编写一个程序，使其L1缺失率尽可能高。

为了测量L1缺失率，我正在使用Intel Core i7处理器上的MEM_LOAD_RETIRED.L1_MISS和MEM_LOAD_RETIRED.L1_HIT性能计数器事件（我不关心填充缓冲区命中情况）。我修改了Linux内核以在每个上下文切换时给出精确的测量结果，以便我可以确定每个程序获得的命中和缺失次数。

硬件预取器已禁用。

这是我目前的代码：

#define LINE_SIZE 64
#define CACHE_SIZE 4096 * 8
#define MEM_SIZE CACHE_SIZE * 64


void main(int argc, char* argv[])
{

    volatile register char* addr asm ("r12") = mmap(0, MEM_SIZE, PROT_READ|PROT_WRITE, MAP_ANONYMOUS|MAP_PRIVATE, -1, 0);

    volatile register unsigned long idx asm ("r13") = 0;
    volatile register unsigned long store_val asm ("r14") = 0;

    volatile register unsigned long x64 asm ("r15") = 88172645463325252ull;

    while(1)
    {
        x64 ^= x64 << 13;
        x64 ^= x64 >> 7;
        x64 ^= x64 << 17;

        store_val = addr[x64 % MEM_SIZE];
    }
}

这段代码每个循环迭代都只产生一次内存访问，那么我的问题是：为什么我在这里得到的缺失率接近0%？即使没有异或移位操作，只是线性访问数组（编辑：每次访问增加64个索引），我应该获得接近100%的缺失率，对吗？我错了什么？

提前感谢！ :)

更新：使用callgrind进行线性访问时，我得到了预期的99.9% miss率。我不理解。

使用perf-tool和以下命令： “perf stat -r 10 -B -e mem_load_retired.l1_miss,mem_load_retired.l1_hit ./thrasher” 给出的结果与我使用修改过的内核输出得到的结果类似。

- arn

---

它是否生成了预期的汇编代码？ - user253751

@BenVoigt，线性访问是指每次访问将索引增加64，因此每次访问都需要一个新的缓存行，对于措辞不够精确表示抱歉。 - arn

@user253751 当我反复访问将映射到相同高速缓存集的内存（每次增加4096个索引并绕回），那么不命中率不应该接近于100％吗？ - arn

@user253751 是的，但不幸的是那也行不通。 - arn

@PeterCordes 我已禁用硬件预取器，所以那不应该是问题（也无法解释随机访问的高命中率）。我通过callgrind运行了一个线性4KB步幅，得到了预期的缺失率。我还尝试计算在L2中命中的硬件预取次数，但命中次数微不足道。我已经花了几个小时试图找到答案，但没有任何进展 :/ 真是令人困惑。 - arn

Answer 1

x64 % MEM_SIZE 是 x64 % CACHE_SIZE * 64，即 x64 % 4096 * 16 * 64，它等价于 ((x64 % 4096) * 16) * 64，最多会涉及到 4096 个不同的位置。

在括号中放置你的宏替换文本。

（我不确定这是否是完整的解释，因为以1024字节间隔的4096个位置应该会重复映射到相同的高速缓存集上，但或许配合移位和异或操作可以产生在移动之前多次击中的模式。快速测试显示，前4096次迭代仅触及2558个位置。）

- Eric Postpischil

---

谢谢你的提示！我肯定没有发现那个问题。不幸的是，那并没有解决问题:/ - arn

Answer 2

更新:

我终于找到了问题！这是一个非常愚蠢的错误：我假设Linux有一些零页去重操作，因此因为我没有初始化数组，所有访问都被映射到同一个物理页面，显然导致高命中率。

我像下面这样更新了我的代码:

#define PAGE 4096
#define LINE_SIZE 64
#define CACHE_SIZE 4096 * 8
#define MEM_SIZE (CACHE_SIZE * 512)

char array[MEM_SIZE] = {[0 ... MEM_SIZE-1] = 5};


void main(int argc, char* argv[])
{
    volatile register char* addr asm ("r12") = array;

    volatile register unsigned long idx asm ("r13") = 0;
    volatile register unsigned long store_val asm ("r14") = 0;

    volatile register unsigned long cnt asm ("r15") = 0;

    while(cnt++ < 100000000)
    {
        idx += PAGE;
        idx %= MEM_SIZE;

        store_val += addr[idx];
    }
}

我现在已经达到了想要的100%错误率。

感谢大家的参与和帮助，非常感激！

- arn

---

不是完全去重，只是将匿名页面（包括BSS）在第一次读取时进行写时复制映射到相同的物理零页面。将数组放在“.data”中，使其成为文件支持的私有映射会破坏这一点；即使是第一个元素的非零初始化程序也可以做到这一点。（因为工具链不够智能，无法跨越.data/.bss边界的数组。） - Peter Cordes

请参阅为什么迭代std :: vector比迭代std :: array更快？了解详细信息。我在评估性能的惯用方式？的答案中添加了提及。 - Peter Cordes

@PeterCordes 是的！这正是我所说的，我们在我的大学称之为零页重复消除:D 感谢您提供的链接，非常有趣！ - arn

还有一个很好的提示，只需要初始化第一个元素。我甚至没有尝试过 ^^ - arn

通常，“去重”意味着哈希/扫描以查找持有相同数据的不同页面（或全部为零）。避免首先使它们分开可以称为反重复机制，以避免在第一次出现时进行重复，或者只是共享。你可以称之为去重，但我个人会避免这样做，因为该术语已经在存储/内存上下文中具有更具体的含义/常规实现（https://en.wikipedia.org/wiki/Data_deduplication和[Linux KSM]（https://en.wikipedia.org/wiki/Kernel_same-page_merging））。 - Peter Cordes

将所有元素都变为非零并不会更糟，这只是因为C具有良好的初始化器语法而使源代码稍微复杂了一些。可执行文件的大小完全相同。如果您想要写入它，实际上在Skylake中有一种[硬件优化]（https://travisdowns.github.io/blog/2020/05/13/intel-zero-opt.html）专门用于将零存储到已清零内存，可能是因为很多软件使用效率低下的东西，如C++ std :: vector，无法请求已清零内存，因此总是必须自己写零进行调整大小。与您的RO案例无关。 - Peter Cordes