使用C/Assembly程序进行缓存延迟基准测试，为什么我的缓存似乎是8倍？

Question

我编写了一个小程序来测试CPU缓存延迟。其思路是用随机值填充缓冲区，并让CPU根据加载的值自行调整步幅从中读取。

根据缓冲区的大小，我期望看到延迟在一些明确定义的集群中。我必须说，我看到了一个清晰的模式，这是一种成功。来自经典文章中图3.10、3.11的顺序读取程序对我来说并不像以前那样好用，可能是因为自2007年以来预取已经大大改进。

奇怪的是，我得到的模式与我的缓存8倍大的缓存一致。所以我的问题是：

我的系统（2014年中期的2核MacBook Pro）具有L1d缓存32k、L2缓存256k、L3缓存3M（共享），体系结构是Intel Haswell。

我看到的模式如下：

Size 1024 Loops 10240000 Cycles 7.60162
Size 2048 Loops 10240000 Cycles 7.14387
Size 4096 Loops 10240000 Cycles 7.74612
Size 8192 Loops 10240000 Cycles 6.93018
Size 16384 Loops 10240000 Cycles 7.32189
Size 32768 Loops 10240000 Cycles 7.84709
Size 65536 Loops 10240000 Cycles 8.32192 # <- L1 cache is 32k so I expect a step here
Size 131072 Loops 10240000 Cycles 7.51579
Size 262144 Loops 10240000 Cycles 9.07455
Size 524288 Loops 10240000 Cycles 16.1824 # <- L1 step is here instead / here I would expect a step associated with L2
Size 1048576 Loops 10240000 Cycles 19.0783
Size 2097152 Loops 10240000 Cycles 11.633
Size 4194304 Loops 10240000 Cycles 23.773 # <- L2 step is here instead 
Size 8388608 Loops 10240000 Cycles 24.2754
Size 16777216 Loops 10240000 Cycles 61.0624 # <- L3 step is here, apparently (makes sense, since L3 is shared, that it comes a bit earlier than expected)
Size 33554432 Loops 10240000 Cycles 57.5953
Size 67108864 Loops 10240000 Cycles 44.3678

我承认可能是我无法测量L1缓存，将L2步骤作为L1步骤，但如果我看一下以前的答案，来自32位时代，我看到一个显眼的语句（强调乘以* 4）：

test_cache(attempts, cache_sizes[i] * 4, latencies, sizeof(latencies) / sizeof(*latencies));

出于某种原因，回答者在一个4倍于缓存区标称大小的缓冲区中测试了延迟。

我感到困惑-这样做的原因是什么？

下面是我的代码（在macOS和clang上运行，但可以轻松适应其他系统）

mwe.c

#include <stdio.h>
#include "x86intrin.h"
#include <fcntl.h>
#include <unistd.h>

#define N (134217728)
#define START_N (1024)

extern uint64_t access_random_place_to_place_memory_dep(uint64_t *, size_t, size_t);

int main (int argc, char** argv) {
    unsigned long long n = N, ta, tb;
    unsigned long long int loops = 10240000;

    // create buffer of random memory
    uint64_t *p = malloc(n);
    uint64_t res;
    int randomData = open("/dev/urandom", O_RDONLY);
    read(randomData, p, n);

    // result arrays
    double results[64];
    size_t memories[64];
    int i;
    for (int working_memory=START_N; working_memory < n; working_memory <<= 1) {
        ta = _rdtsc();
        access_random_place_to_place_memory_dep(p, working_memory, loops);
        tb = _rdtsc();
        memories[i] = working_memory;
        results[i] = (double)(tb-ta)/loops;
        i++;
    }
    free(p);

    for (int j=0; j<i; j++) {
        printf("Size %zu Loops %llu Cycles %g\n", memories[j], loops, results[j]);
    }
    return res;
}

mwe.s

.intel_syntax

.global _access_random_place_to_place_memory_dep

.section __DATA,__data


.section __TEXT,__text

/*
Access memory randomly, by pointer chasing,
each stride depends on the last read
*/
// (rdi, rsi, rdx) -> 
// (rax) pointer to buffer
// (rsi) size of buffer (power of 2)
// (rdx) iterations
// no need to pad stack since no function call
_access_random_place_to_place_memory_dep:
    mov rbx, [rdi]
    xor rcx, rcx
// will use as AND mask
    dec rsi 
beginz:
    cmp rdx, rcx
    jbe endz
    inc rcx
    and rbx, rsi
    lea rbx, [rdi + rbx]
    mov r8, [rbx]
    add rbx, r8
    jmp beginz
endz:
    mov rax, rbx
    ret

要编译 clang mwe.c mwe.s -o mwe 并使用 ./mwe 运行

---

编辑（2022/3/23）

感谢纠正！我呈现当前版本及其输出。希望它能帮助别人，因为我自己没有轻易找到这样的代码。

mwe.c

#include <stdlib.h>
#include <stdio.h>
#include "x86intrin.h"
#include <fcntl.h>
#include <unistd.h>

#define N (134217728)
#define START_N (128)

extern uint64_t access_random_place_to_place_memory_dep(uint64_t *, size_t, size_t);

void place_random_shuffle(uint64_t *p, uint64_t max_offset) {
    uint64_t max_offset_q = max_offset/8;

    // start by writing for each qword its own offset
    for (uint64_t i=0; i<max_offset_q; i++) {
        p[i] = 8*i;
    }

    // then shuffle (Fisher Yates shuffling)
    for (uint64_t i=0; i<max_offset_q-1; i++) {
        uint64_t t;
        uint64_t j = (rand() % (max_offset_q-i)) + i;
        t = p[i];
        p[i] = p[j];
        p[j] = t;
    }

}


int main (int argc, char** argv) {
    unsigned long long n = N, ta, tb;
    unsigned long long int loops = 10240000;

    // create buffer of random memory
    uint64_t *p = malloc(n);
    uint64_t res;

    // result arrays
    double results[64];
    size_t memories[64];
    int i;
    for (int working_memory=START_N; working_memory < n; working_memory <<= 1) {
        place_random_shuffle(p, working_memory);
        ta = _rdtsc();
        res = access_random_place_to_place_memory_dep(p, working_memory, loops);
        tb = _rdtsc();
        memories[i] = working_memory;
        results[i] = (double)(tb-ta)/loops;
        i++;
    }
    free(p);

    for (int j=0; j<i; j++) {
        printf("Size %zu Loops %llu Cycles %g\n", memories[j], loops, results[j]);
    }
    return res;
}

mwe.s

.intel_syntax

.global _access_random_place_to_place_memory_dep

.section __DATA,__data

.section __TEXT,__text

/*
Access memory randomly, by pointer chasing,
each stride depends on the last read
*/
// (rdi, rsi, rdx) -> 
// (rdi) pointer to buffer
// (rsi) size of buffer
// (rdx) iterations (must be >1)
// no need to pad stack since no function call
_access_random_place_to_place_memory_dep:
    xor rax, rax
    xor r8, r8
beginz:
    mov rax, [rdi+rax]
    add r8, rax
    dec rdx
    jnz beginz
endz:
    mov rax, r8
    ret

现在的输出效果要好得多了！

Size 128 Loops 10240000 Cycles 4.51077
Size 256 Loops 10240000 Cycles 4.67502
Size 512 Loops 10240000 Cycles 4.46404
Size 1024 Loops 10240000 Cycles 4.47518
Size 2048 Loops 10240000 Cycles 4.67881
Size 4096 Loops 10240000 Cycles 4.5293
Size 8192 Loops 10240000 Cycles 4.36537
Size 16384 Loops 10240000 Cycles 4.56763
Size 32768 Loops 10240000 Cycles 4.59288
Size 65536 Loops 10240000 Cycles 8.66269 # <- L1 step
Size 131072 Loops 10240000 Cycles 9.48717
Size 262144 Loops 10240000 Cycles 15.2417
Size 524288 Loops 10240000 Cycles 27.2223 # <- L2 (?) step
Size 1048576 Loops 10240000 Cycles 47.3154
Size 2097152 Loops 10240000 Cycles 104.716 # <- we start to be out of L3
Size 4194304 Loops 10240000 Cycles 177.333
Size 8388608 Loops 10240000 Cycles 218.087
Size 16777216 Loops 10240000 Cycles 234.883
Size 33554432 Loops 10240000 Cycles 242.916
Size 67108864 Loops 10240000 Cycles 260.416

"循环"实际上是"伪循环"，因为有着Turbo Boost技术的存在，但我不知道如何将其考虑在内。

- Ralph

---

将参考周期（您称之为伪周期）缩放到核心时钟周期最简单的方法是假设CPU始终以最大睿频运行，并硬编码比率。对于大小为1的循环，每次迭代应该恰好运行5个周期。（或使用每个imul 3个周期的imul eax，eax链）。如果您测量墙钟时间和TSC滴答声，则可以找到该频率和已知的核心时钟周期。（或者在您的确切CPU型号上搜索TSC频率。例如，Linux进行校准，如我i7-6700k上的“tsc：经过改进的TSC时钟源校准：4008.057 MHz”内核日志） - Peter Cordes

如果你有类似于Linux perf或Intel VTune的工具，你也可以让它计算核心周期和参考周期的硬件PMU事件 (cpu_clk_unhalted.ref_tsc和cpu_clk_unhalted.thread)。这将直接为你提供给定运行的核心与TSC比率。 - Peter Cordes

Answer 1

使用真正随机的数据从/dev/urandom原始获取，你不知道你是否全部触及到了它。你可能很容易陷入一个只触及缓冲区一小部分的循环中。大约在触及缓冲区中某些缓存行的一部分后，你会随机访问一个以前已经访问过的字节偏移量，从而创建一个长度为一定值的循环。这个长度取决于你回到序列中的多远。我很容易相信1/4或1/8的总缓存行数是典型随机运行的合理值。

还有，这个周期内可能存在一些局部性，比如在接触到其他缓存行之前多次接触到某些缓存行的子集。

我认为你需要的是qword偏移量0..n-1的随机排列。（或者0, 8, 16, ... 8*(n-1)，因为你将它们用作字节偏移量，未缩放。）或者对于更小的大小，由于你屏蔽了高位字节，你可以把它看作32位甚至24位值的缓冲区；尽管你会丢弃高位字节，但进行8字节加载似乎很可能会引入偶尔的缓存行分裂。

需要确保你在回到同一个qword之前触及每个qword一次。 （或者更好的是，在缓存线的基础上，也许只使用每个缓存线的一个qword。）

使用可能部分重叠的任意字节偏移量似乎更难避免创建周期较短的循环，这些循环不会触及每个缓存行。

---

你的汇编函数在不保存/恢复RBX的情况下破坏了它；在正常的x86调用约定中，包括x86-64 SysV，它是被调用者保留的。如果调用方依赖它，这是一个不太可能的症状，但你应该修复它。你直到最后才使用RAX，所以你可以使用RAX而不是RBX来简化循环。

此外，你可以通过将dec rdx/jnz beginz放在底部来简化循环，就像一个do{}while(--rdx)，假设迭代计数参数非零。（或者如果你不想假设，test rdx,rdx/jz .end跳过循环，仍然允许一个具有单个底部分支的高效循环。）为什么循环总是编译成“do...while”样式（尾调用）？

我不认为LEA有什么意义; 只需使用带索引的寻址模式与mov或甚至是add rbx，[rdi + rbx]（这可以微融合成一个load+add uop，并且在Haswell中即使在ROB中也保持微融合尽管使用了带索引的寻址模式）。

Haswell的L1d加载使用延迟为5个周期，除非真正进行指针追踪（使用像[reg + 0..2047]这样的寻址模式，其中reg值直接来自负载，没有涉及and）。并且+disp位移不会将其带入下一页。请参见当基础+offset在不同页面时是否存在惩罚？

还要注意，RDTSC参考频率通常不是CPU频率，除非禁用turbo。然后，在Haswell上，它通常非常接近，因为特别是旧CPU的TSC频率非常接近其额定的持续非turbo频率。通过turbo，CPU频率要高得多，特别是对于运行低吞吐量工作负载（如指针追踪）的低功率笔记本电脑CPU。

如果您了解TSC与实际核心时钟的区别，则可以接受这一点，但不要假设这些数字是您循环传递的依赖链（包括and/lea/add以及负载）的实际长度。因此，如果所有L1d命中，则应为8个核心时钟周期。如果删除无用的LEA并允许该添加在load port AGU中发生，则为7个周期。

- Peter Cordes

---

非常感谢！我根据您写的内容纠正了代码。您似乎比我更专业，我只是一个好奇的程序员。您能看一下修改后的版本吗？我会非常感激任何见解！ - Ralph

还有一个问题，如果可以的话。在Linux Ivy Bridge E机器上，对于非常小的大小（CPU在大约相同的14-15个地址或相同的两个缓存行之间来回移动），我看到比稍大一点的大小具有非常一致的更高延迟：（大小112周期14.1617; 大小120周期14.1738; 大小128周期14.1199; 大小136周期8.23; 大小144周期5.00002）你知道为什么吗？ - Ralph

@Ralph：这是你的新代码，不会进行未对齐的访问，对吧？这就是为什么非2的幂大小可以进行测试，因为你没有使用AND进行取模。我不知道，这似乎很奇怪。由于所有内容都是相关的，所以不应该有任何银行冲突，并且涉及的行是连续的，因此我们不应该出现冲突缺失。 - Peter Cordes

@Ralph：你更新后的汇编代码看起来更合理，C语言也做了洗牌。如果你交换使用那些寄存器的方式，比如mov r8, [rdi+r8] / add rax, r8，就可以在结尾处省略mov rax,r8指令。我不知道为什么要对你看到的偏移量求和，但这很幸运地不在关键路径上，只有MOV喂给MOV。main函数目前没有将返回值用作校验和或其他任何东西。（如果你使用mov rdi, [rdi]从一个以p[i] = &p[i]开始的洗牌数组中加载实际指针，你将看到4个周期的快速路径，所有操作都会缩短1个周期。） - Peter Cordes

@Ralph：如果你仍然无法解释那个结果，你可以发布一个带有[mcve]的新问题，以便人们可以在自己的机器上运行并进行分析。变化似乎太大了，不可能是由于Turbo频率的变化所致，并且你运行的时间足够长，预热效应也不会很显著。 - Peter Cordes