为什么遍历`std::vector`比遍历`std::array`更快？

Question

我最近提出了这个问题： 为什么迭代std::array比迭代std::vector快得多？ 正如人们很快指出的那样，我的基准测试有很多缺陷。因此在尝试修复基准测试时，我注意到std::vector并不比std::array慢，在实际中情况恰好相反。

#include <vector>
#include <array>
#include <stdio.h>
#include <chrono>

using namespace std;

constexpr int n = 100'000'000;
vector<int> v(n);
//array<int, n> v;

int main()
{
    int res = 0;
    auto start = chrono::steady_clock::now();
    for(int x : v)
        res += x;
    auto end = chrono::steady_clock::now();
    auto diff = end - start;
    double elapsed =
        std::chrono::duration_cast<
            std::chrono::duration<double, std::milli>
        >(end - start).count();
    printf("result: %d\ntime: %f\n", res, elapsed);
}

我尝试改进前面的基准测试的内容：

• 确保正在使用结果，以便整个循环不会被优化掉
• 使用 -O3 标志以提高速度
• 使用 std::chrono 而不是 time 命令。这样我们就可以隔离要测量的部分（仅为循环）。变量的静态初始化和诸如此类的事情将不会被测量。

测量时间：

array：

$ g++ arrVsVec.cpp -O3
$ ./a.out
result: 0
time: 99.554109

向量：

$ g++ arrVsVec.cpp -O3
$ ./a.out
result: 0
time: 30.734491

我只是想知道这次我做错了什么。

在godbolt中查看反汇编

- tuket

---

很可能动态分配导致了构成向量存储的内存页面的“预热”。数组“存储”在未初始化的内存中，该内存会被按需分页，因此对数组进行迭代会生成需要操作系统分配和清除底层内存页面的页面故障。创建第二个循环，在第一个循环之后运行，并计时第二个循环而不是第一个循环。更好的方法是：将第一个循环移入不同的翻译单元中的单独函数中，并在第二个循环之前调用它。 - Sam Varshavchik

现在将第一个循环移入一个外部函数，该函数会被单独编译。编译器可能仍然会使用一些优化技巧。 - Sam Varshavchik

你可以尝试使用堆分配的 std::array 进行比较，例如 auto pv = std::make_unique<std::array<int, n>>(); auto& v = *pv;。 - Ben

@Ben，它们的性能是相同的 :) - tuket

我不是心灵读者，但我认为OP的问题并不特定于此处array和vector具有静态存储（对于vector来说并不完全正确）的情况。@PeterCordes的评论清楚地解释了在我们计时的代码部分之前会发生许多事情。这突显了我们应该在实际计时之前进行干跑，或者至少计时多次以摊销这些外围成本的事实。 - prog-fh

Answer 1

这种差异是由于array的内存页面未驻留在进程地址空间中（全局作用域数组存储在可执行文件的.bss部分中，尚未进行分页，它被初始化为零）。而vector已经被分配并填充了零，因此它的内存页面已经存在。

如果你添加

std::fill_n(v.data(), n, 1); // included in <algorithm>

将页面（预缺页）带入主函数的第一行，使得数组时间与向量相同。

---

在Linux上，您可以使用mlock(v.data(), v.size() * sizeof(v[0]));来将页面带入地址空间，而不是使用Windows的方法。有关详细信息，请参见man mlock。

- Maxim Egorushkin

---

你可以通过使用预热循环来读取数组而不是写入它，从而使数组比向量更快，这样页面就可以保持CoW映射到相同的物理零页。然后，当遍历巨大的数组时，您可以获得L1d或L2命中，只有一些可能的TLB缺失，这取决于微架构。 - Peter Cordes

@PeterCordes 这是 .bss 部分，它不由可执行映像中的页面支持，因此其页面始终是 CoW，对吧？哦，你可能是指它使用相同的只读零页用于整个 .bss 部分。现在我明白了，说盲人。 - Maxim Egorushkin

是的，完全正确。我的理解/心智模型是，Linux使用单一物理4k和/或2M零页面，用于所有进程/任务中已知的“零后备匿名页面”。任何对它的映射当然都是只读的。对匿名页面的读取故障只是设置此只读CoW映射，而不是准备进行写操作。 - Peter Cordes

在我的Skylake上，当反复循环未写入的数组时，我看到了大量的L2命中。https://godbolt.org/z/SxI2_j（我检查了汇编代码，以确保我的技巧阻止了重复循环的优化）。我使用了`taskset -c 3 perf stat -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles,instructions,uops_issued.any,uops_executed.thread,mem_load_retired.l2_hit:u,mem_load_retired.l2_miss:u,mem_load_retired.l1_hit:u -r4 ./touchpage-array-readinit-O3-native`。我只看到了808个页面错误，所以只读也鼓励了更多的故障周围，或者是hugepages？ - Peter Cordes

@PeterCordes - 这是一种实现上的权衡。制作快速、低延迟、低功率的VIPT L1缓存并不容易，因此AMD使用了一种称为“微标记”的东西。这使您可以仅使用V地址进行L1查找，将TLB移出关键路径。缺点是虚拟别名未被解决，因此您只能同时在缓存中有一个给定P地址的V别名。 - BeeOnRope

Answer 2

内存映射/分配是懒惰的（Lazy）：对一个页面的第一次访问将导致出现页故障异常，例如x86上的#PF。这包括BSS，以及像可执行文件的文本段这样的文件支持映射。这些页故障是“有效”的，所以它们不会导致发送SIGSEGV；相反，如果必要，内核将分配物理页面并连接硬件页表，以便加载或存储可以重新运行而不会导致第二次故障。

这是很昂贵的，特别是如果内核不“规避故障”并在一个页故障期间准备多个页面。（特别是当Spectre + Meltdown防护使得当前x86-64硬件上的用户<->内核往返更加昂贵时。）

你在动态分配后让std::vector的构造函数将零写入数组中。std::vector在你的计时循环之外完成所有的页故障操作。这发生在主函数之前，当实现正在运行静态对象的构造函数时。

但是数组被零初始化，因此它被放置在BSS中。第一次访问它的是你的循环。你的array<>循环为计时区域内所有的页故障付出了代价。

如果你使用new int[n]来动态分配但不初始化内存块，你会看到与静态array<>相同的行为。（如果Linux更愿意为动态分配而不是BSS映射使用透明大页，则可能会稍微好些。）

---

---

脚注1：在libstdc++和libc++中的std::vector太愚蠢了，不能利用从操作系统获取已经清零的页面，就像如果它使用calloc或等效函数一样。如果库提供了一个新/删除兼容的分配器以获取清零内存，那么这是可能的。

C++的new/delete与malloc/free/calloc/realloc相比要弱化。我不知道为什么ISO C++省略了calloc和realloc：两者对于大型分配特别有用，特别是对于可平凡复制对象的std::vector进行大小调整的realloc，因为它可能有增长其映射而不复制的空间。但由于new/delete不能保证与malloc/free兼容，而new是可替换的，因此即使在内部，库也很难使用calloc和realloc。

---

另一个因素：只读叶页映射到相同的物理零页面

当读取（而非写入）时触发惰性分配，它将读取为零。 （BSS页面读取为零，来自 mmap（MAP_ANONYMOUS） 的新页面全部读取为零。）

软缺页处理程序将硬件页表连接起来的时候，不需要实际分配物理页面（也就是页面帧）来支持虚拟页面。相反，Linux 将干净（未写入）的匿名页面映射到单个物理清零页面。（这适用于所有任务。）

如果我们对数组进行多次遍历，那么我们会遇到一个有趣的情况：由于我们有多个虚拟页面指向同一物理位置，这会导致TLB缺失但是L1d或L3命中（这取决于是否使用 hugepage ）。

（某些CPU，例如 AMD Ryzen，在L1d高速缓存中使用微标记来节省成本，从而使高速缓存仅能针对单个虚拟地址命中，即使相同的内存映射到多个虚拟地址。Intel CPU使用真正的 VIPT L1d 高速缓存，并且确实可以获得此效果）。

我为Linux编写了一个测试程序，该程序将使用madvise(MADV_HUGEPAGE)（以鼓励内核为 hugepages 整理内存）或madvise(MADV_NOHUGEPAGE)（即使对于只读情况也禁用 hugepages）。

由于某种原因，Linux BSS页面在写入时不使用 hugepages。 只有读取它们才会使用 2M 的 hugepages（这对于 L1d 或 L2 来说太大了，但符合 L3。但我们确实获得所有TLB命中）。 在 /proc/PID/smaps 中很难看到这一点，因为未编写的内存根本不显示为“驻留”。 （记住，它是由系统范围的零共享区域物理支持的）。

我对您的基准代码进行了一些更改，以便在初始化进行读取或写入的情况下多次重新运行 sum 循环之后进行重复循环，根据命令行参数进行更改。重复循环使其运行时间更长，从而可以获得更精确的定时，并摊销初始化，以便我们从 perf 中获得有用的结果。

#include <vector>
#include <array>
#include <stdio.h>
#include <chrono>
#include <sys/mman.h>

using namespace std;

constexpr int n = 100'000'000;
//vector<int> v(n);
alignas(4096) array<int, n> v;

//template<class T>
__attribute__((noinline))
int toucharray(volatile int *vv, int write_init) {
        int res=vv[0];
        for(int i=32 ; i<n ; i+=128)
                if(write_init)
                    vv[i] = 0;
                else
                    res += vv[i];
//      volatile int sum = res;  // noinline is fine, we don't need to stop multiple calls from CSEing
        return res;
}

template <class T>
__attribute__((noinline,noclone))
int sum_container(T &vv) {
    unsigned int res=0;
    for(int x : vv)
        res += x;
    __attribute__((used)) static volatile int sink;
    sink = res;  // a side-effect stops IPA from deciding that this is a pure function
    return res;
}

int main(int argc, char**argv)
{
    int write_init = 0;
    int hugepage = 0;
    if (argc>1) {
            hugepage = argv[1][0] & 1;
            write_init = argv[1][0] & 2;
    }
    int repcount = 1000;
    if (argc>2)
            repcount = atoi(argv[2]);

// TODO: option for no madvise.
    madvise(v.data(), n*sizeof(v[0]), MADV_SEQUENTIAL);
    madvise(v.data(), n*sizeof(v[0]), hugepage ? MADV_HUGEPAGE : MADV_NOHUGEPAGE);  
    madvise(v.data(), n*sizeof(v[0]), MADV_WILLNEED); 
 // SEQ and WILLNEED probably only matter for file-backed mappings to reduce hard page faults.
 //  Probably not encouraging faultahead / around for lazy-allocation soft page fault

    toucharray(v.data(), write_init);

    int res = 0;
    auto start = chrono::steady_clock::now();
    for(int i=0; i<repcount ; i++)
        res = sum_container(v);
    auto end = chrono::steady_clock::now();
    double elapsed =
        std::chrono::duration_cast<
            std::chrono::duration<double, std::milli>
        >(end - start).count();
    printf("result: %d\ntime: %f\n", res, elapsed);
}

最佳情况：clang++ -O3 -march=native（Skylake）实际上可以使用多个累加器展开，而gcc -funroll-loops则做得很傻。

在我的Skylake i7-6700k上，DDR4-2666 DRAM配置为最大睿频4.2GHz和governor=performance -

# using std::array<int,n>
# 0&1 = 0 -> MADV_NOHUGEPAGE.  0&2 = 0 -> read-only init
taskset -c 3 perf stat -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles,instructions,mem_load_retired.l2_hit:u,mem_load_retired.l1_hit:u,mem_inst_retired.stlb_miss_loads:u ./touchpage-array-argc.clang 0 1000
result: 0
time: 1961.952394

 Performance counter stats for './touchpage-array-madv-nohuge-argc.clang 0 1000':

          2,017.34 msec task-clock:u              #    1.000 CPUs utilized          
                50      context-switches          #    0.025 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
            97,774      page-faults               #    0.048 M/sec                  
     8,287,680,837      cycles                    #    4.108 GHz                    
    14,500,762,859      instructions              #    1.75  insn per cycle         
            13,688      mem_load_retired.l2_hit:u #    0.007 M/sec                  
    12,501,329,912      mem_load_retired.l1_hit:u # 6196.927 M/sec                  
           144,559      mem_inst_retired.stlb_miss_loads:u #    0.072 M/sec                  

       2.017765632 seconds time elapsed

       1.979410000 seconds user
       0.036659000 seconds sys

注意到了相当多的TLB未命中(mem_inst_retired.stlb_miss_loads:u表示用户空间中的二级TLB未命中次数)。并且有97k页错误。这几乎正好覆盖了100M * 4 = 400MB数组所需的4k页面数，因此我们每个页面都出现了1个错误，没有预先错误/围绕错误。

幸运的是，Skylake有两个页行走单元，因此可以同时执行两个推测页行走操作。此外，所有数据访问都会命中L1d，因此页表将至少保持在L2中，加速页行走。

# using array
# MADV_HUGEPAGE,  read-only init
taskset -c 3 perf stat -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles,instructions,mem_load_retired.l2_hit:u,mem_load_retired.l1_hit:u,mem_inst_retired.stlb_miss_loads:u ./touchpage-array-argc.clang 1 1000
result: 0
time: 5947.741408

 Performance counter stats for './touchpage-array-argc.clang 1 1000':

          5,951.40 msec task-clock:u              #    1.000 CPUs utilized          
                 9      context-switches          #    0.002 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
               687      page-faults               #    0.115 K/sec                  
    24,377,094,416      cycles                    #    4.096 GHz                    
    14,397,054,228      instructions              #    0.59  insn per cycle         
     2,183,878,846      mem_load_retired.l2_hit:u #  366.952 M/sec                  
       313,684,419      mem_load_retired.l1_hit:u #   52.708 M/sec                  
            13,218      mem_inst_retired.stlb_miss_loads:u #    0.002 M/sec                  

       5.951530513 seconds time elapsed

       5.944087000 seconds user
       0.003284000 seconds sys

通知：TLB缺失率仅为1/10，但在相同的约12G内存加载中，只有2G能够在L2中命中，这可能要归功于成功的硬件预取。 （其余的确实命中了L3。）并且我们仅有687个页面错误；故障绕过和大页面的组合使这更加高效。

请注意，由于L3带宽瓶颈，所需时间增加了3倍。

---

数组的写入初始化让我们拥有最糟糕的两种情况：

# using array
# MADV_HUGEPAGE (no apparent effect on BSS)  and write-init

taskset -c 3 perf stat -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles,instructions,mem_load_retired.l2_hit:u,mem_load_retired.l1_hit:u,mem_inst_retired.stlb_miss_loads:u ./touchpage-array-argc.clang 3 1000
result: 0
time: 16510.222762

 Performance counter stats for './touchpage-array-argc.clang 3 1000':

         17,143.35 msec task-clock:u              #    1.000 CPUs utilized          
               341      context-switches          #    0.020 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
            95,218      page-faults               #    0.006 M/sec                  
    70,475,978,274      cycles                    #    4.111 GHz                    
    17,989,948,598      instructions              #    0.26  insn per cycle         
       634,015,284      mem_load_retired.l2_hit:u #   36.983 M/sec                  
       107,041,744      mem_load_retired.l1_hit:u #    6.244 M/sec                  
        37,715,860      mem_inst_retired.stlb_miss_loads:u #    2.200 M/sec                  

      17.147615898 seconds time elapsed

      16.494211000 seconds user
       0.625193000 seconds sys

大量页面错误。也有更多的TLB未命中。

std::vector版本基本上与数组相同：

strace显示madvise没有起作用是因为我没有对齐指针。glibc / libstdc ++new倾向于返回一个页面对齐+ 16的指针，并在前16个字节中保留分配器记录。对于数组，我使用alignas(4096)来确保我可以将其传递给madvise。

madvise(0x7f760d133010, 400000000, MADV_HUGEPAGE) = -1 EINVAL (Invalid argument)

总之，由于我的内核调优设置，它只尝试在madvise上对巨大页面的内存进行碎片整理，而目前内存相当分散。所以它最终没有使用任何巨大页面。

taskset -c 3 perf stat -etask-clock:u,context-switches,cpu-migrations,page-faults,cycles,instructions,mem_load_retired.l2_hit:u,mem_load_retired.l1_hit:u,mem_inst_retired.stlb_miss_loads:u ./touchpage-vector-argv.clang 3 1000
result: 0
time: 16020.821517

 Performance counter stats for './touchpage-vector-argv.clang 3 1000':

         16,159.19 msec task-clock:u              #    1.000 CPUs utilized          
                17      context-switches          #    0.001 K/sec                  
                 0      cpu-migrations            #    0.000 K/sec                  
            97,771      page-faults               #    0.006 M/sec                  
    66,146,780,261      cycles                    #    4.093 GHz                    
    15,294,999,994      instructions              #    0.23  insn per cycle         
       217,426,277      mem_load_retired.l2_hit:u #   13.455 M/sec                  
       842,878,166      mem_load_retired.l1_hit:u #   52.161 M/sec                  
         1,788,935      mem_inst_retired.stlb_miss_loads:u #    0.111 M/sec                  

      16.160982779 seconds time elapsed

      16.017206000 seconds user
       0.119618000 seconds sys

我不确定为什么TLB缺失率比THP只读测试高这么多。也许是由于内存访问争用和/或通过触及更多内存来驱逐缓存页表而导致页面行走变慢，因此TLB预取无法跟上。

在大约12G的加载中，硬件预取能够使其中约1G的数据在L1d或L2缓存中命中。

- Peter Cordes