C++缓存性能奇怪的行为-6ren

C++缓存性能奇怪的行为

转载作者：塔克拉玛干更新时间：2023-11-03 00:15:05

我读了一篇文章(1.5岁的http://www.drdobbs.com/parallel/cache-friendly-code-solving-manycores-ne/240012736)，其中谈到了缓存性能和数据大小。他们显示了以下代码，他们说它们在i7(桑迪桥)上运行

static volatile int array[Size];
static void test_function(void)
{
    for (int i = 0; i < Iterations; i++)
        for (int x = 0; x < Size; x++)
          array[x]++;
}

他们声称，如果保持Size * Iterations不变，则增加Size，当数组内存的大小增加到超过L2高速缓存大小时，它们会观察到执行所需的巨大时间高峰(10x)。

作为我自己的练习，我想尝试一下以查看是否可以在我的机器上重现它们的结果。 (i7 3770k，win7，Visual c++ 2012编译器，Win32 Debug模式，未启用优化)。但是令我惊讶的是，我看不到执行时间的增加(甚至超过了L3缓存的大小)，这使我认为编译器正在某种程度上优化此代码。但是我也没有看到任何优化。我看到的唯一速度变化是，在我的机器字大小以下，它需要花费更长的时间。以下是我的时间安排，代码 list 和相关的反汇编。

有人知道原因吗:

1)为什么无论数组大小如何，花费的时间都根本不增加？或者我怎么能找到答案？

2)为什么要花很长时间才开始，然后减少直到达到高速缓存行大小，如果数据小于行大小，是否应该在不从高速缓存中读取的情况下处理更多的迭代？

时间:

Size=1,Iterations=1073741824, Time=3829
Size=2,Iterations=536870912, Time=2625
Size=4,Iterations=268435456, Time=2563
Size=16,Iterations=67108864, Time=2906
Size=32,Iterations=33554432, Time=3469
Size=64,Iterations=16777216, Time=3250
Size=256,Iterations=4194304, Time=3140
Size=1024,Iterations=1048576, Time=3110
Size=2048,Iterations=524288, Time=3187
Size=4096,Iterations=262144, Time=3078
Size=8192,Iterations=131072, Time=3125
Size=16384,Iterations=65536, Time=3109
Size=32768,Iterations=32768, Time=3078
Size=65536,Iterations=16384, Time=3078
Size=262144,Iterations=4096, Time=3172
Size=524288,Iterations=2048, Time=3109
Size=1048576,Iterations=1024, Time=3094
Size=2097152,Iterations=512, Time=3313
Size=4194304,Iterations=256, Time=3391
Size=8388608,Iterations=128, Time=3312
Size=33554432,Iterations=32, Time=3109
Size=134217728,Iterations=8, Time=3515
Size=536870912,Iterations=2, Time=3532

代码:

#include <string>
#include <cassert>
#include <windows.h>

template <unsigned int SIZE, unsigned int ITERATIONS>
static void test_body(volatile char* array)
{
     for (unsigned int i = 0; i < ITERATIONS; i++)
    {
        for (unsigned int  x = 0; x < SIZE; x++)
        {
            array[x]++;
        }
    }
}

template <unsigned int SIZE, unsigned int ITERATIONS>
static void test_function()
{
    assert(SIZE*ITERATIONS == 1024*1024*1024);
    static volatile char array[SIZE];

    test_body<SIZE, 1>(array); //warmup

    DWORD beginTime = GetTickCount();
    test_body<SIZE, ITERATIONS>(array); 
    DWORD endTime= GetTickCount();
    printf("Size=%u,Iterations=%u, Time=%d\n", SIZE,ITERATIONS, endTime-beginTime);
}

int main()
{
    enum { eIterations= 1024*1024*1024};
    test_function<1, eIterations>();
    test_function<2, eIterations/2>();
    test_function<4, eIterations/4>();
    test_function<16, eIterations/16>();
    test_function<32, eIterations/ 32>();
    test_function<64, eIterations/ 64>();
    test_function<256, eIterations/ 256>();
    test_function<1024, eIterations/ 1024>();
    test_function<2048, eIterations/ 2048>();
    test_function<4096, eIterations/ 4096>();
    test_function<8192, eIterations/ 8192>();
    test_function<16384, eIterations/ 16384>();
    test_function<32768, eIterations/ 32768>();
    test_function<65536, eIterations/ 65536>();
    test_function<262144, eIterations/ 262144>();
    test_function<524288, eIterations/ 524288>();
    test_function<1048576, eIterations/ 1048576>();
    test_function<2097152, eIterations/ 2097152>();
    test_function<4194304, eIterations/ 4194304>();
    test_function<8388608, eIterations/ 8388608>();
    test_function<33554432, eIterations/ 33554432>();
    test_function<134217728, eIterations/ 134217728>();
    test_function<536870912, eIterations/ 536870912>();
}

拆卸

    for (unsigned int i = 0; i < ITERATIONS; i++)
00281A59  mov         dword ptr [ebp-4],0  
00281A60  jmp         test_body<536870912,2>+1Bh (0281A6Bh)  
00281A62  mov         eax,dword ptr [ebp-4]  
00281A65  add         eax,1  
00281A68  mov         dword ptr [ebp-4],eax  
00281A6B  cmp         dword ptr [ebp-4],2  
00281A6F  jae         test_body<536870912,2>+53h (0281AA3h)  
    {
        for (unsigned int  x = 0; x < SIZE; x++)
00281A71  mov         dword ptr [ebp-8],0  
00281A78  jmp         test_body<536870912,2>+33h (0281A83h)  
00281A7A  mov         eax,dword ptr [ebp-8]  
    {
        for (unsigned int  x = 0; x < SIZE; x++)
00281A7D  add         eax,1  
00281A80  mov         dword ptr [ebp-8],eax  
00281A83  cmp         dword ptr [ebp-8],20000000h  
00281A8A  jae         test_body<536870912,2>+51h (0281AA1h)  
        {
            array[x]++;
00281A8C  mov         eax,dword ptr [array]  
00281A8F  add         eax,dword ptr [ebp-8]  
00281A92  mov         cl,byte ptr [eax]  
00281A94  add         cl,1  
00281A97  mov         edx,dword ptr [array]  
00281A9A  add         edx,dword ptr [ebp-8]  
00281A9D  mov         byte ptr [edx],cl  
        }
00281A9F  jmp         test_body<536870912,2>+2Ah (0281A7Ah)  
    }
00281AA1  jmp         test_body<536870912,2>+12h (0281A62h)

最佳答案

TL; DR:您的测试为，对于缓存延迟或速度而言，测试不正确。相反，它测量了一些通过OoO CPU管道砍断复杂代码的问题。

使用正确的测试来测量高速缓存和内存延迟:lat_mem_rd from lmbench;进行速度(带宽)测量的正确测试:STREAM benchmark进行内存速度测试； tests from memtest86表示使用 rep movsl main operation的缓存速度)

此外，在现代(2010年及更新版本)台式机/服务器CPU中，在L1和L2高速缓存附近内置了硬件预取逻辑，它将检测线性访问模式并将数据从外部高速缓存预加载到内部，然后再请求此数据:Intel Optimization Manual - 7.2 Hardware prefetching of data ，第365页； intel.com blog, 2009。很难禁用所有硬件预取(SO Q/A 1，SO Q/A 2)

很长的故事:

我将尝试使用Linux中的perf性能监视工具(也称为perf_events)进行几次类似测试的测量。该代码基于Joky(32位int数组，而不是chars)中的程序，并分成几个二进制文件，如下所示:a5的大小为2 ^ 5 = 32； a10 => 2 ^ 10 = 1024(4 KB); a15 => 2 ^ 15 = 32768，a20(100万个整数= 4 MB)和a25(3200万个整数= 128MB)。 CPU是i7-2600四核Sandy Bridge 3.4 GHz。

让我们从具有默认事件集的基本perf stat开始(跳过一些行)。我选择了2 ^ 10(4 KB)和2 ^ 20(4 MB)

$ perf stat ./a10
Size=1024 ITERATIONS=1048576, TIME=2372.09 ms

 Performance counter stats for './a10':

               276 page-faults               #    0,000 M/sec
     8 238 473 169 cycles                    #    3,499 GHz
     4 936 244 310 stalled-cycles-frontend   #   59,92% frontend cycles idle
       415 849 629 stalled-cycles-backend    #    5,05% backend  cycles idle
    11 832 421 238 instructions              #    1,44  insns per cycle
                                             #    0,42  stalled cycles per insn
     1 078 974 782 branches                  #  458,274 M/sec
         1 080 091 branch-misses             #    0,10% of all branches

$ perf stat ./a20
Size=1048576 ITERATIONS=1024, TIME=2432.4 ms

 Performance counter stats for './a20':

             2 321 page-faults               #    0,001 M/sec
     8 487 656 735 cycles                    #    3,499 GHz
     5 184 295 720 stalled-cycles-frontend   #   61,08% frontend cycles idle
       663 245 253 stalled-cycles-backend    #    7,81% backend  cycles idle
    11 836 712 988 instructions              #    1,39  insns per cycle
                                             #    0,44  stalled cycles per insn
     1 077 257 745 branches                  #  444,104 M/sec
            30 601 branch-misses             #    0,00% of all branches

我们在这里可以看到什么？指令计数非常接近(因为Size * Iterations是常数)，周期计数和时间也很接近。这两个示例均具有10亿个分支，具有99％的良好预测。但是前端有60％的失速计数，后端有5-8％的失速计数。前端停顿是指令获取和解码中的停顿，很难说清原因，但是对于您的代码而言，前端每滴答声无法解码4条指令( Intel optimisation manual 的第B-41页，第B.3节-“性能调优“Sandy Bridge技术”，B.3.2小节自上而下的分层性能表征...)

$ perf record -e stalled-cycles-frontend ./a20
Size=1048576 ITERATIONS=1024, TIME=2477.65 ms
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.097 MB perf.data (~4245 samples) ]
$ perf annotate -d a20|cat
 Percent |      Source code & Disassembly of a20
------------------------------------------------
         :      08048e6f <void test_body<1048576u, 1024u>(int volatile*)>:

   10.43 :       8048e87:       mov    -0x8(%ebp),%eax
    1.10 :       8048e8a:       lea    0x0(,%eax,4),%edx
    0.16 :       8048e91:       mov    0x8(%ebp),%eax
    0.78 :       8048e94:       add    %edx,%eax
    6.87 :       8048e96:       mov    (%eax),%edx
   52.53 :       8048e98:       add    $0x1,%edx
    9.89 :       8048e9b:       mov    %edx,(%eax)
   14.15 :       8048e9d:       addl   $0x1,-0x8(%ebp)
    2.66 :       8048ea1:       mov    -0x8(%ebp),%eax
    1.39 :       8048ea4:       cmp    $0xfffff,%eax

或者在这里使用原始操作码( objdump -d)，其中一些具有相当复杂的索引编制，因此可能无法由3个简单的解码器处理它们并等待唯一的复杂解码器(图像在那里: http://www.realworldtech.com/sandy-bridge/4/)

 8048e87:       8b 45 f8                mov    -0x8(%ebp),%eax
 8048e8a:       8d 14 85 00 00 00 00    lea    0x0(,%eax,4),%edx
 8048e91:       8b 45 08                mov    0x8(%ebp),%eax
 8048e94:       01 d0                   add    %edx,%eax
 8048e96:       8b 10                   mov    (%eax),%edx
 8048e98:       83 c2 01                add    $0x1,%edx
 8048e9b:       89 10                   mov    %edx,(%eax)
 8048e9d:       83 45 f8 01             addl   $0x1,-0x8(%ebp)
 8048ea1:       8b 45 f8                mov    -0x8(%ebp),%eax
 8048ea4:       3d ff ff 0f 00          cmp    $0xfffff,%eax

后端停顿是通过等待内存或高速缓存(测量高速缓存时您感兴趣的事情)和内部执行核心停顿而创建的停顿:

$ perf record -e stalled-cycles-backend ./a20
Size=1048576 ITERATIONS=1024, TIME=2480.09 ms
[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.095 MB perf.data (~4149 samples) ]
$ perf annotate -d a20|cat
    4.25 :       8048e96:       mov    (%eax),%edx
   58.68 :       8048e98:       add    $0x1,%edx
    8.86 :       8048e9b:       mov    %edx,(%eax)
    3.94 :       8048e9d:       addl   $0x1,-0x8(%ebp)
    7.66 :       8048ea1:       mov    -0x8(%ebp),%eax
    7.40 :       8048ea4:       cmp    $0xfffff,%eax

报告了大多数后端停顿的 add 0x1,%edx，因为它是数据的使用者，是从上一条命令中的数组加载的。通过存储到阵列，它们占后端停顿的70％，或者如果我们乘以程序中后端停顿的总份额(7％)，则为 的所有停顿的5％。或换句话说， cache is faster比您的程序。现在我们可以回答您的第一个问题:

Why the time taken does not increase at all regardless of the size of my array?

您的测试是如此糟糕(未优化)，以至于您试图测量缓存，但是它们的总运行时间仅降低了5％。您的测试是如此不稳定(嘈杂)，您将看不到5％的效果。

使用自定义的 perf stat运行，我们还可以测量缓存请求/未命中率。对于4 KB程序，L1数据高速缓存服务于所有负载的99,99％和所有存储的99,999％。我们可以注意到，不正确的测试所产生的缓存请求比在数组上遍历并增加每个元素(10亿个加载+ 10亿个存储)所需的请求多出两倍。其他访问用于使用局部变量(例如 x)，它们始终由缓存提供服务，因为它们的地址是恒定的)

$ perf stat -e 'L1-dcache-loads,L1-dcache-load-misses,L1-dcache-stores,L1-dcache-store-misses' ./a10
Size=1024 ITERATIONS=1048576, TIME=2412.25 ms

 Performance counter stats for './a10':

     5 375 195 765 L1-dcache-loads
           364 140 L1-dcache-load-misses     #    0,01% of all L1-dcache hits
     2 151 408 053 L1-dcache-stores
            13 350 L1-dcache-store-misses

对于4 MB的程序，命中率要差很多倍。错过次数增加100倍!现在，所有内存请求的1.2％不是由L1服务，而是由L2服务。

$ perf stat -e 'L1-dcache-loads,L1-dcache-load-misses,L1-dcache-stores,L1-dcache-store-misses' ./a20
Size=1048576 ITERATIONS=1024, TIME=2443.92 ms

 Performance counter stats for './a20':

     5 378 035 007 L1-dcache-loads
        67 725 008 L1-dcache-load-misses     #    1,26% of all L1-dcache hits
     2 152 183 588 L1-dcache-stores
        67 266 426 L1-dcache-store-misses

当我们要注意缓存延迟如何变为 from 4 cpu ticks up to 12(长3倍)，此更改仅影响1.2％的缓存请求以及我们的程序对缓存延迟敏感的仅7％的减速时，不是这种情况吗？？

如果我们将使用更大的数据集怎么办？好的，这是a25(4字节整数的2 ^ 25 = 128 MB，是缓存大小的几倍):

$ perf stat   ./a25
Size=134217728 ITERATIONS=8, TIME=2437.25 ms

 Performance counter stats for './a25':

           262 417 page-faults               #    0,090 M/sec
    10 214 588 827 cycles                    #    3,499 GHz
     6 272 114 853 stalled-cycles-frontend   #   61,40% frontend cycles idle
     1 098 632 880 stalled-cycles-backend    #   10,76% backend  cycles idle
    13 683 671 982 instructions              #    1,34  insns per cycle
                                             #    0,46  stalled cycles per insn
     1 274 410 549 branches                  #  436,519 M/sec
           315 656 branch-misses             #    0,02% of all branches

$ perf stat -e 'L1-dcache-loads,L1-dcache-load-misses,L1-dcache-stores,L1-dcache-store-misses' ./a25
Size=134217728 ITERATIONS=8, TIME=2444.13 ms

 Performance counter stats for './a25':

     6 138 410 226 L1-dcache-loads
        77 025 747 L1-dcache-load-misses     #    1,25% of all L1-dcache hits
     2 515 141 824 L1-dcache-stores
        76 320 695 L1-dcache-store-misses

L1丢失率几乎相同，并且更多后端停滞。我能够获取“cache-references，cache-misses”事件的统计信息，我建议它们与L3缓存有关(对L2的请求要多几倍):

$ perf stat -e 'cache-references,cache-misses' ./a25
Size=134217728 ITERATIONS=8, TIME=2440.71 ms

 Performance counter stats for './a25':

        17 053 482 cache-references
        11 829 118 cache-misses              #   69,365 % of all cache refs

因此，未命中率很高，但是该测试可处理10亿个(有用)负载，其中只有0.8亿个未命中L1。内存处理了1亿个请求。内存延迟约为 230 cpu clocks，而不是4时钟L1延迟。测试可以看到吗？可能是，如果噪音很低。

关于C++缓存性能奇怪的行为，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23282744/

文章推荐： linux - 如果内核是交叉编译的，我必须交叉编译模块吗？

文章推荐： c - 了解代码 Linux 设备驱动程序 m25p80.c

javascript - 如何使 textarea 内容可以设置样式或设置 div 行为(如 textarea 行为)？
我想创建一个基于 jQuery 的非常简单的 html 编辑器(不是所见即所得)。我的问题是如何制作 textarea或 div可能在上面写一些文字然后样式即标签(例如 some stuff 将
Ant isset 行为
根据文档 isset 条款“测试此项目中是否已设置给定属性”。我不明白设置属性时 isset 返回 true 还是 false 在下面的代码片段中，当 env.JAVA_HOME 未设置时，java.
关于默认命令超时的 Vim 行为
我正在尝试取消映射 o这是执行 :only 的默认命令( :help :only )，所以我尝试的第一件事是: nmap o 这种作品，除非我按，等待超过timeoutlen ms 然后按 o
Django auto_now 行为
我有以下型号: class MetaData(models.Model): created_at = models.DateTimeField(auto_now_add=True, auto_
R strftime() 行为
下面列出了两行代码。两者对日期和时间的期望相同，但只有一个有效。我正在使用 R 3.1。以下不起作用: DateTime2=strftime("08/13/2010 05:26:24.350", f
C 行为(非初始化值)
我有一个关于 C 代码的问题。 #include void foo(void){ int a; printf("%d\n",a); } void bar(void){
Java BufferedInputStream 行为
如果文件大小 > 8k，为什么读取的最后一个字节 = 0？ private static final int GAP_SIZE = 8 * 1024; public static void main(
powershell - ValueFromPipeline 行为？
我有一个命令 Get-Testdata从不同来源检索测试数据并将这些数据存储到 PSObject以不同的值作为属性。然后将对象总数存储为数组，以便于操作、排序、计算等。我的问题是我希望能够将这些数据
写入文件描述符时的 epoll 行为
我正在使用 epoll 将大消息写入使用 HTTP 协议(protocol)的服务器。 fds 都设置为非阻塞，我正在使用边缘触发事件。我知道对于 EPOLLIN，我需要循环读取 fd，直到返回 EA
PHP intval() 行为？
这对我来说听起来很奇怪: $test_1 = 'string'; $test_2 = '0'; var_dump(intval($test_1)); // Output: int 0 var_dump
java - 在java中等于和==行为
这个问题在这里已经有了答案: Java: Integer equals vs. == (7 个回答) 7年前关闭。请您解释以下行为。 public class EqAndRef { publ
jquery - Drupal 行为
Drupal 的行为到底是什么？它为模块开发人员提供什么类型的服务层？它映射到 jQuery.ready 的关系类型是什么？最佳答案长版:Drupal.behaviors 不仅仅是 jQuer
iphone - dispatch_get_global_queue 行为
以下代码: dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_HIGH, 0), ^{ for (int i=0
javascript - 移动设备上的奇怪的toggle()行为
人们可以将项目添加到数据库中。我让他们选择在此时添加它，或手动选择日期。因此我得到了这个 HTML 结构。 (请注意，我将日期和时间选择器妥协为只有一行文本) Selec
r - is.nan() 行为
创建了一个数据框: simpleDF is.na(simpleDF$vals) [1] TRUE TRUE FALSE > is.nan(simpleDF$vals) [1] FALSE TRU
Docker Squash 行为
我有一个大的 docker 镜像 A，我创建了一个新的 Dockerfile FROM A RUN rm /big-folder 我尝试使用以下方法构建图像: docker build --squas
操作系统内存不足时的 JVM 行为
我想知道以下情况下 JVM 的行为是什么: JVM 最小堆大小 = 500MB JVM 最大堆大小 = 2GB 操作系统有 1GB 内存 JVM启动后，程序运行一段时间后，使用内存超过1GB。我想知道
Apigee - SpikeArrest 行为
我们正在使用 spikeearrest 策略，但我们不了解其工作原理。峰值逮捕配置如下: 5pm 阅读文档，我们了解到，如果我们在一分钟内调用此流超过 5 次，则该策略将在第 5 次之后
javascript - BodyParser 行为
我正在使用 cURL 发送 POST 请求: curl http://tarvos.local:8080/partial_Users/2 -d '{currentPage : 1, firstID :
java - RowNum 行为
我的表中有 6442670 条记录，我正在使用以下命令获取它们jdbctemplate 使用行号一次 1000000 个。以下是查询 select * from (select rowNum rn

塔克拉玛干

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

C++缓存性能奇怪的行为