c - 为什么 BSS 中静态数组的第二个循环比第一个更快？

Question

我有以下代码，它写入一个带有零的全局数组两次，一次向前，一次向后。

#include <string.h>
#include <time.h>
#include <stdio.h>
#define SIZE 100000000

char c[SIZE];
char c2[SIZE];

int main()
{
   int i;
   clock_t t = clock();
   for(i = 0; i < SIZE; i++)
       c[i] = 0;

   t = clock() - t;
   printf("%d\n\n", t);

   t = clock(); 
   for(i = SIZE - 1; i >= 0; i--)
      c[i] = 0;

   t = clock() - t;
   printf("%d\n\n", t);
}

我已经运行了几次，第二次打印总是显示较小的值......

但是，如果我在其中一个循环中将 Change c 更改为 c2，则两次打印之间的时间差可以忽略不计......造成这种差异的原因是什么？

编辑:

我尝试使用 -O3 进行编译并查看了程序集:有 2 次调用 memset，但第二次仍然打印较小的值。

Answer 1

当你在C中定义一些全局数据时，它是零初始化的:

char c[SIZE];
char c2[SIZE];

在 linux (unix) 世界中，这意味着 c 和 c2 都将分配在特殊的 ELF 文件部分，即 .bss 中。 :

... data segment containing statically-allocated variables represented solely by zero-valued bits initially

创建 .bss 段是为了不在二进制文件中存储全零，它只是说“这个程序想要有 200MB 的归零内存”。

加载程序时，ELF 加载器(经典静态二进制文件的内核，或 ld.so 动态加载器也称为 interp)将为.bss，通常类似于 mmap带有 MAP_ANONYMOUS 标志和 READ+WRITE 权限/保护请求。

但是操作系统内核中的内存管理器不会为您提供所有 200 MB 的零内存。相反，它会将进程的部分虚拟内存标记为零初始化，并且该内存的每个页面都将指向物理内存中的特殊零页面。该页有 4096 个字节的零字节，因此如果您从 c 或 c2 读取，您将获得零字节；这种机制允许内核减少内存需求。

到零页的映射是特殊的；它们被标记(在 page table 中)为只读。当您第一次写入任何此类虚拟页面时，General protection fault或pagefault异常将由硬件生成(我会说，由 MMU 和 TLB)。此错误将由内核处理，在您的情况下，由 minor pagefault 处理。处理程序。它将分配一个物理页，用零字节填充它，并重置刚刚访问的虚拟页到该物理页的映射。然后它将重新运行错误的指令。

我对您的代码进行了一些转换(两个循环都移至单独的函数):

$ cat b.c
#include <string.h>
#include <time.h>
#include <stdio.h>
#define SIZE 100000000

char c[SIZE];
char c2[SIZE];

void FIRST()
{
   int i;
   for(i = 0; i < SIZE; i++)
       c[i] = 0;
}

void SECOND()
{
   int i;
   for(i = 0; i < SIZE; i++)
       c[i] = 0;
}


int main()
{
   int i;
   clock_t t = clock();
   FIRST();
   t = clock() - t;
   printf("%d\n\n", t);

   t = clock(); 
   SECOND();

   t = clock() - t;
   printf("%d\n\n", t);
}

使用gcc b.c -fno-inline -O2 -o b编译，然后在linux的perf stat或更通用的/usr/bin/time下运行code> 获取页面错误计数:

$ perf stat ./b
139599

93283


 Performance counter stats for './b':
 ....
            24 550 page-faults               #    0,100 M/sec           


$ /usr/bin/time ./b
234246

92754

Command exited with non-zero status 7
0.18user 0.15system 0:00.34elapsed 99%CPU (0avgtext+0avgdata 98136maxresident)k
0inputs+8outputs (0major+24576minor)pagefaults 0swaps

因此，我们有 24,500 个小页面错误。 x86/x86_64 上的标准页面大小为 4096，这接近 100 MB。

使用 perf record/perf report linux profiler，我们可以找到页面错误发生的位置(生成):

$ perf record -e page-faults ./b
...skip some spam from non-root run of perf...
213322

97841

[ perf record: Woken up 1 times to write data ]
[ perf record: Captured and wrote 0.018 MB perf.data (~801 samples) ]

$ perf report -n |cat
...
# Samples: 467  of event 'page-faults'
# Event count (approx.): 24583
#
# Overhead       Samples  Command      Shared Object                   Symbol
# ........  ............  .......  .................  .......................
#
    98.73%           459        b  b                  [.] FIRST              
     0.81%             1        b  libc-2.19.so       [.] __new_exitfn       
     0.35%             1        b  ld-2.19.so         [.] _dl_map_object_deps
     0.07%             1        b  ld-2.19.so         [.] brk                
     ....

所以，现在我们可以看到，只有 FIRST 函数会生成页面错误(在第一次写入 bss 页面时)，而 SECOND 不会生成任何页面错误。每个页面错误都对应着一些工作，由操作系统内核完成，而这项工作只在 bss 的每页上完成一次(因为 bss 不会取消映射并重新映射回来)。