为什么第二个循环比第一个循环更快？

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);
}

我已经运行了一两次,第二次打印总是显示一个较小的值...但是,如果我在其中一个循环中将更改c更改为c2,则两个打印之间的时间差异可以忽略不计......这是什么原因为了这个区别？

编辑:

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

Answer 1

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

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

在Linux操作系统(UNIX)的世界,这意味着,除了这两个c和c2将特殊的ELF文件部分分配的.bss:

...数据段包含最初仅由零值位表示的静态分配变量

该.bss段创建为全零不存储在二进制,它只是说,像"这个程序要具有清零的内存200MB的".

当您加载程序时,ELF加载程序(在经典静态二进制文件的情况下为内核,或者ld.so也称为动态加载程序interp)将为内存分配内存.bss,通常类似于mmap使用MAP_ANONYMOUSflag和READ + WRITE权限/保护请求.

但是OS内核中的内存管理器不会给你所有200 MB的零内存.相反,它会将进程的虚拟内存部分标记为零初始化,并且此内存的每个页面都将指向物理内存中的特殊零页面.这个页面有4096字节的零字节,所以如果你正在读取c或者c2,你将获得零字节; 而这种机制允许内核减少内存需求.

零页的映射是特殊的; 它们被标记为(在页表中)为只读.当您第一次写入任何此类虚拟页面时,通用保护错误或页面错误异常将由硬件生成(我会说,由MMU和TLB).此错误将由内核处理,在您的情况下,由次要页面错误处理程序处理.它将分配一个物理页面,用零字节填充它,并重置刚加入的虚拟页面到该物理页面的映射.然后它将重新运行故障指令.

我转换了你的代码(两个循环都移动到单独的函数):

$ 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以获取pagefault计数:

$ 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,5千个小页面错误.如果x86/x86_64上的标准页面大小为4096,则接近100兆字节.

使用perf record/ perf reportlinux 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不生成任何页面故障.每个页面故障都对应于一些工作,由OS内核完成,而这项工作每页只执行一次bss(因为bss没有取消映射并重新映射回来).

Answer 2

在出现动画问题后，这是由于缓存引起的-我不敢相信您可以享受〜100M阵列带来的缓存好处，因此您很可能在返回任何有用数据之前就将其完全废弃了。

但是，根据平台（主要是OS）的不同，还有其他一些工作原理-分配数组时，您永远不会对其进行初始化，因此第一个循环可能会导致每4k页第一次访问的代价。这通常会导致系统调用的某些辅助操作，而该调用具有很高的开销。
在这种情况下，您还修改了页面，因此大多数系统将被迫执行写时复制流程（只要您仅从页面中读取就可以使用的优化功能），这甚至更重。

在每页上添加少量访问权限（在实际缓存方面应忽略不计，并且仅从每4k页中获取一条64B行），设法使结果在我的系统上更均匀（尽管这种测量形式不是很准确的开始）

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

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

int main()
{
   int i;
   for(i = 0; i < SIZE; i+=4096)      ////  access and modify each page once
       c[i] = 0;                      ////

   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);
}