为什么我的 8M L3 缓存对大于 1M 的阵列没有任何好处?

Why does my 8M L3 cache not provide any benefit for arrays larger than 1M?

我受到这个问题的启发,写了一个简单的程序来测试我机器在每个缓存级别的内存带宽:

Why vectorizing the loop does not have performance improvement

我的代码使用 memset 一遍又一遍地写入一个缓冲区(或多个缓冲区)并测量速度。它还保存每个缓冲区的地址以在最后打印。这是清单:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define SIZE_KB {8, 16, 24, 28, 32, 36, 40, 48, 64, 128, 256, 384, 512, 768, 1024, 1025, 2048, 4096, 8192, 16384, 200000}
#define TESTMEM 10000000000 // Approximate, in bytes
#define BUFFERS 1

double timer(void)
{
    struct timeval ts;
    double ans;

    gettimeofday(&ts, NULL);
    ans = ts.tv_sec + ts.tv_usec*1.0e-6;

    return ans;
}

int main(int argc, char **argv)
{
    double *x[BUFFERS];
    double t1, t2;
    int kbsizes[] = SIZE_KB;
    double bandwidth[sizeof(kbsizes)/sizeof(int)];
    int iterations[sizeof(kbsizes)/sizeof(int)];
    double *address[sizeof(kbsizes)/sizeof(int)][BUFFERS];
    int i, j, k;

    for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
        iterations[k] = TESTMEM/(kbsizes[k]*1024);

    for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
    {
        // Allocate
        for (j = 0; j < BUFFERS; j++)
        {
            x[j] = (double *) malloc(kbsizes[k]*1024);
            address[k][j] = x[j];
            memset(x[j], 0, kbsizes[k]*1024);
        }

        // Measure
        t1 = timer();
        for (i = 0; i < iterations[k]; i++)
        {
            for (j = 0; j < BUFFERS; j++)
                memset(x[j], 0xff, kbsizes[k]*1024);
        }
        t2 = timer();
        bandwidth[k] = (BUFFERS*kbsizes[k]*iterations[k])/1024.0/1024.0/(t2-t1);

        // Free
        for (j = 0; j < BUFFERS; j++)
            free(x[j]);
    }

    printf("TESTMEM = %ld\n", TESTMEM);
    printf("BUFFERS = %d\n", BUFFERS);
    printf("Size (kB)\tBandwidth (GB/s)\tIterations\tAddresses\n");
    for (k = 0; k < sizeof(kbsizes)/sizeof(int); k++)
    {
        printf("%7d\t\t%.2f\t\t\t%d\t\t%x", kbsizes[k], bandwidth[k], iterations[k], address[k][0]);
        for (j = 1; j < BUFFERS; j++)
            printf(", %x", address[k][j]);
        printf("\n");
    }

    return 0;
}

结果(BUFFERS = 1):

TESTMEM = 10000000000
BUFFERS = 1
Size (kB)   Bandwidth (GB/s)    Iterations  Addresses
      8     52.79               1220703     90b010
     16     56.48               610351      90b010
     24     57.01               406901      90b010
     28     57.13               348772      90b010
     32     45.40               305175      90b010
     36     38.11               271267      90b010
     40     38.02               244140      90b010
     48     38.12               203450      90b010
     64     37.51               152587      90b010
    128     36.89               76293       90b010
    256     35.58               38146       d760f010
    384     31.01               25431       d75ef010
    512     26.79               19073       d75cf010
    768     26.20               12715       d758f010
   1024     26.20               9536        d754f010
   1025     18.30               9527        90b010
   2048     18.29               4768        d744f010
   4096     18.29               2384        d724f010
   8192     18.31               1192        d6e4f010
  16384     18.31               596         d664f010
 200000     18.32               48          cb2ff010

我很容易看出32K一级缓存和256K二级缓存的效果。我不明白的是为什么memset缓冲区大小超过1M后性能会突然下降。我的三级缓存应该是8M。它也发生得很突然,根本不像超过 L1 和 L2 缓存大小时那样逐渐变细。

我的处理器是 Intel i7 3700。/sys/devices/system/cpu/cpu0/cache 的 L3 缓存的详细信息是:

level = 3
coherency_line_size = 64
number_of_sets = 8192
physical_line_partition = 1
shared_cpu_list = 0-7
shared_cpu_map = ff
size = 8192K
type = Unified
ways_of_associativity = 16

我想我会尝试使用多个缓冲区 - 在每个 1M 的 2 个缓冲区上调用 memset,看看性能是否会下降。 BUFFERS = 2,我得到:

TESTMEM = 10000000000
BUFFERS = 2
Size (kB)   Bandwidth (GB/s)    Iterations  Addresses
      8     54.15               1220703     e59010, e5b020
     16     51.52               610351      e59010, e5d020
     24     38.94               406901      e59010, e5f020
     28     38.53               348772      e59010, e60020
     32     38.31               305175      e59010, e61020
     36     38.29               271267      e59010, e62020
     40     38.29               244140      e59010, e63020
     48     37.46               203450      e59010, e65020
     64     36.93               152587      e59010, e69020
    128     35.67               76293       e59010, 63769010
    256     27.21               38146       63724010, 636e3010
    384     26.26               25431       63704010, 636a3010
    512     26.19               19073       636e4010, 63663010
    768     26.20               12715       636a4010, 635e3010
   1024     26.16               9536        63664010, 63563010
   1025     18.29               9527        e59010, f59420
   2048     18.23               4768        63564010, 63363010
   4096     18.27               2384        63364010, 62f63010
   8192     18.29               1192        62f64010, 62763010
  16384     18.31               596         62764010, 61763010
 200000     18.31               48          57414010, 4b0c3010

看起来两个 1M 缓冲区都保留在 L3 缓存中。但是尝试稍微增加任一缓冲区的大小,性能就会下降。

我一直在用-O3 编译。它没有太大区别(除了可能在缓冲区上展开循环)。我试过 -O0,除了 L1 速度外,它是一样的。 gcc 版本是 4.9.1.

总而言之,我有一个由两部分组成的问题:

  1. 为什么我的 8 MB L3 缓存对大于 1M 的内存块没有任何好处?
  2. 为什么性能下降如此突然?

编辑:

根据 Gabriel Southern 的建议,我 运行 我的代码 perf 使用 BUFFERS=1,一次只有一个缓冲区大小。这是完整的命令:

perf stat -e dTLB-loads,dTLB-load-misses,dTLB-stores,dTLB-store-misses -r 100 ./a.out 2> perfout.txt

-r表示perf会运行a.out100次和return平均统计。

perf的输出,#define SIZE_KB {1024}:

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

         1,508,798 dTLB-loads                                                    ( +-  0.02% )
                 0 dTLB-load-misses          #    0.00% of all dTLB cache hits 
       625,967,550 dTLB-stores                                                   ( +-  0.00% )
             1,503 dTLB-store-misses                                             ( +-  0.79% )

       0.360471583 seconds time elapsed                                          ( +-  0.79% )

#define SIZE_KB {1025}:

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

         1,670,402 dTLB-loads                                                    ( +-  0.09% )
                 0 dTLB-load-misses          #    0.00% of all dTLB cache hits 
       626,099,850 dTLB-stores                                                   ( +-  0.00% )
             2,115 dTLB-store-misses                                             ( +-  2.19% )

       0.503913416 seconds time elapsed                                          ( +-  0.06% )

所以 1025K 缓冲区似乎确实有更多的 TLB 未命中。但是,使用这个大小的缓冲区,程序执行了大约 9500 次 memset 调用,因此每次 memset 调用仍然少于 1 次未命中。

您的基准测试只写入内存,从不读取,使用的 memset 可能设计得很巧妙,不会从缓存中读取任何内容到内存中。很可能在这段代码中,您只使用了缓存内存的一半容量,与原始内存相比,性能没有任何提升。写入原始内存非常接近 L2 速度这一事实可能是一个暗示。如果 L2 以 26 GB/sec 运行,主内存以 18 GB/sec 运行,您对 L3 缓存的真正期望是什么?

您测量的是吞吐量,而不是延迟。我会尝试一个基准测试,您实际使用 L3 缓存的强度,以比主内存更低的延迟提供数据。

简答:

您的 memset 版本在初始化大于 1 MB 的内存区域时开始使用 non-temporal 存储。因此 CPU 不会将这些行存储在其缓存中,即使您的 L3 缓存大于 1 MB。因此,对于大于 1 MB 的缓冲区值,性能受到系统中可用内存带宽的限制。

详情:

背景:

我在几个不同的系统上测试了您提供的代码,最初专注于调查 TLB,因为我认为二级 TLB 中可能存在抖动。然而,none 我收集的数据证实了这个假设。

我测试的一些系统使用 Arch Linux,它有最新版本的 glibc,而其他系统使用 Ubuntu 10.04,它使用旧版本的 eglibc。在使用多个不同的 CPU 架构进行测试时,使用静态链接的二进制文件时,我能够重现问题中描述的行为。我关注的行为是 SIZE_KB10241025 时运行时的显着差异。性能差异的原因是为慢速和快速版本执行的代码发生了变化。

汇编代码

我用perf recordperf annotate收集了执行汇编代码的踪迹,以查看热代码路径是什么。代码使用以下格式显示在下方:

percentage time executing instruction | address | instruction

我从省略了大部分地址的较短版本复制了热循环,并且有一条线连接循环后缘和循环 header。

对于在 Arch Linux 上编译的版本,热循环是(对于 1024 和 1025 大小):

  2.35 │a0:┌─+movdqa %xmm8,(%rcx)
 54.90 │   │  movdqa %xmm8,0x10(%rcx)
 32.85 │   │  movdqa %xmm8,0x20(%rcx)
  1.73 │   │  movdqa %xmm8,0x30(%rcx)
  8.11 │   │  add    [=10=]x40,%rcx      
  0.03 │   │  cmp    %rcx,%rdx       
       │   └──jne    a0

对于 Ubuntu 10.04 二进制文件,当 运行 大小为 1024 时,热循环是:

       │a00:┌─+lea    -0x80(%r8),%r8
  0.01 │    │  cmp    [=11=]x80,%r8     
  5.33 │    │  movdqa %xmm0,(%rdi)  
  4.67 │    │  movdqa %xmm0,0x10(%rdi)
  6.69 │    │  movdqa %xmm0,0x20(%rdi)
 31.23 │    │  movdqa %xmm0,0x30(%rdi)
 18.35 │    │  movdqa %xmm0,0x40(%rdi)
  0.27 │    │  movdqa %xmm0,0x50(%rdi)
  3.24 │    │  movdqa %xmm0,0x60(%rdi)
 16.36 │    │  movdqa %xmm0,0x70(%rdi)
 13.76 │    │  lea    0x80(%rdi),%rdi 
       │    └──jge    a00    

对于 Ubuntu 10.04 版本 运行 缓冲区大小为 1025 的热循环是:

       │a60:┌─+lea    -0x80(%r8),%r8  
  0.15 │    │  cmp    [=12=]x80,%r8       
  1.36 │    │  movntd %xmm0,(%rdi)    
  0.24 │    │  movntd %xmm0,0x10(%rdi)
  1.49 │    │  movntd %xmm0,0x20(%rdi)
 44.89 │    │  movntd %xmm0,0x30(%rdi)
  5.46 │    │  movntd %xmm0,0x40(%rdi)
  0.02 │    │  movntd %xmm0,0x50(%rdi)
  0.74 │    │  movntd %xmm0,0x60(%rdi)
 40.14 │    │  movntd %xmm0,0x70(%rdi)
  5.50 │    │  lea    0x80(%rdi),%rdi 
       │    └──jge    a60

这里的主要区别是较慢的版本使用 movntd 指令,而较快的版本使用 movdqa 指令。英特尔软件开发人员手册对 non-temporal 存储有以下说明:

For WC memory type in particular, the processor never appears to read the data into the cache hierarchy. Instead, the non-temporal hint may be implemented by loading a temporary internal buffer with the equivalent of an aligned cache line without filling this data to the cache.

所以这似乎解释了使用 memset 且值大于 1 MB 不适合缓存的行为。接下来的问题是为什么Ubuntu10.04系统和ArchLinux系统有区别,为什么选择1MB作为分界点。为了调查这个问题,我查看了 glibc 源代码:

memset

的源代码

查看 sysdeps/x86_64/memset.S 处的 glibc git 回购协议,我发现第一个提交很有趣 b2b671b677d92429a3d41bf451668f476aa267ed

提交描述为:

Faster memset on x64

This implementation speed up memset in several ways. First is avoiding expensive computed jump. Second is using fact that arguments of memset are most of time aligned to 8 bytes.

Benchmark results on: kam.mff.cuni.cz/~ondra/benchmark_string/memset_profile_result27_04_13.tar.bz2

并且 website referenced 有一些有趣的分析数据。

diff of the commit 表明 memset 的代码被简化了很多, non-temporal 商店被删除了。这与 Arch Linux 中的分析代码显示的相符。

查看 older code 我看到选择是否使用 non-temporal 商店似乎使用了描述为 The largest cache size

的值
L(byte32sse2_pre):

    mov    __x86_shared_cache_size(%rip),%r9d  # The largest cache size
    cmp    %r9,%r8
    ja     L(sse2_nt_move_pre)

计算这个的代码在:sysdeps/x86_64/cacheinfo.c

虽然看起来有计算实际共享缓存大小的代码,但默认值也是1 MB:

long int __x86_64_shared_cache_size attribute_hidden = 1024 * 1024;

所以我怀疑是否使用了默认值,但可能还有其他一些原因导致代码选择 1MB 作为截止点。

在任何一种情况下,您问题的总体答案似乎是当设置大于 1 MB 的内存区域时,您系统上的 memset 版本正在使用 non-temporal 存储。

鉴于 Gabriel 对生成的汇编代码的反汇编,我认为这确实是问题所在[编辑:他的回答已被编辑,现在看来是根本原因,所以我们达成一致]:

请注意,movnt 是一个流媒体商店,它可能具有(取决于确切的微架构实现)几个影响:

  1. 排序语义较弱(使其速度更快)。
  2. 如果它覆盖整行(无需获取以前的数据并合并),则延迟会有所改善。
  3. 有一个非时间提示,使其不可缓存。

#1 和#2 如果它们受内存限制,可能会改善这些操作的延迟和带宽,但#3 基本上强制它们受内存限制,即使它们可以适合某些缓存级别。这可能超过了好处,因为内存 latency/BW 开始时要差得多。

因此,您的 memset 库实现可能使用了错误的阈值来切换到流式存储版本(我猜它不会费心检查您的 LLC 大小,但假设 1M 是内存驻留是很奇怪的)。我建议尝试替代库,或禁用编译器生成它们的能力(如果支持)。