C++性能：std::array与std::vector的比较

Question

我知道 C 风格的数组或 std::array 并不比向量更快。我一直在使用向量（而且我使用它们很好）。然而，有些情况下，使用 std::array 比 std::vector 更好，并且我不知道为什么（使用 clang 7.0 和 gcc 8.2 进行测试）。

让我分享一个简单的代码：

#include <vector>
#include <array>

// some size constant
const size_t N = 100;

// some vectors and arrays
using vec = std::vector<double>;
using arr = std::array<double,3>;
// arrays are constructed faster here due to known size, but it is irrelevant
const vec v1 {1.0,-1.0,1.0};
const vec v2 {1.0,2.0,1.0};
const arr a1 {1.0,-1.0,1.0};
const arr a2 {1.0,2.0,1.0};

// vector to store combinations of vectors or arrays
std::vector<double> glob(N,0.0);

上述初始化变量的代码未包含在基准测试中。现在，让我们编写一个函数来组合v1和v2或a1和a2的元素（double）。

// some combination
auto comb(const double m, const double f)
{
  return m + f;
}

还有基准函数：

void assemble_vec()
{
    for (size_t i=0; i<N-2; ++i)
    {
        glob[i] += comb(v1[0],v2[0]);
        glob[i+1] += comb(v1[1],v2[1]);
        glob[i+2] += comb(v1[2],v2[2]);
    }  
}

void assemble_arr()
{
    for (size_t i=0; i<N-2; ++i)
    {
        glob[i] += comb(a1[0],a2[0]);
        glob[i+1] += comb(a1[1],a2[1]);
        glob[i+2] += comb(a1[2],a2[2]);
    }  
}

我已经尝试过使用clang 7.0和gcc 8.2。在两种情况下，数组版本的速度几乎是向量版本的两倍。

有人知道为什么吗？

- mfnx

---

你是否开启了优化？此外，100个测试用例数量非常少。通常在基准测试时，您至少需要数万次迭代。您可以使用 quick bench 进行在线基准测试。 - NathanOliver

数组和向量解决不同的问题。我并不真正看到用这种方式比较它们的性能有什么意义。 - François Andrieux

作为程序员，我不会从一个假设开始认为C风格数组或者std::array比向量(vector)更快。因为通常情况下我们认为在堆栈(stack)上分配内存比动态内存分配更快速。 - Xirema

@Xirema 我听说动态分配内存比“分配”栈内存慢。但我没有听说栈内存比动态分配的内存更快。这是缓存命中的问题吗？ - François Andrieux

区别的原因是a1和a2是常量。编译器在编译时计算它们的总和。不幸的是，gcc和clang并不聪明到足以将comb(v1[0], v2[0])移出循环（即使将它们的data()放入__restrict指针中 - 这是一个被忽略的优化）。 - geza

Answer 1

GCC（可能也包括Clang）会优化掉数组，但不会优化向量

您的基本假设——数组比向量慢——是不正确的。因为向量需要使用动态内存（默认分配器）中的分配空间来存储它们的数据，所以需要使用的值必须存储在堆内存中，并在程序执行期间重复访问。相反，数组使用的值可以被完全优化掉，直接在程序的汇编中引用。

下面是启用优化后GCC针对assemble_vec和assemble_arr函数输出的汇编代码：

[-snip-]
//==============
//Vector Version
//==============
assemble_vec():
        mov     rax, QWORD PTR glob[rip]
        mov     rcx, QWORD PTR v2[rip]
        mov     rdx, QWORD PTR v1[rip]
        movsd   xmm1, QWORD PTR [rax+8]
        movsd   xmm0, QWORD PTR [rax]
        lea     rsi, [rax+784]
.L23:
        movsd   xmm2, QWORD PTR [rcx]
        addsd   xmm2, QWORD PTR [rdx]
        add     rax, 8
        addsd   xmm0, xmm2
        movsd   QWORD PTR [rax-8], xmm0
        movsd   xmm0, QWORD PTR [rcx+8]
        addsd   xmm0, QWORD PTR [rdx+8]
        addsd   xmm0, xmm1
        movsd   QWORD PTR [rax], xmm0
        movsd   xmm1, QWORD PTR [rcx+16]
        addsd   xmm1, QWORD PTR [rdx+16]
        addsd   xmm1, QWORD PTR [rax+8]
        movsd   QWORD PTR [rax+8], xmm1
        cmp     rax, rsi
        jne     .L23
        ret

//=============
//Array Version
//=============
assemble_arr():
        mov     rax, QWORD PTR glob[rip]
        movsd   xmm2, QWORD PTR .LC1[rip]
        movsd   xmm3, QWORD PTR .LC2[rip]
        movsd   xmm1, QWORD PTR [rax+8]
        movsd   xmm0, QWORD PTR [rax]
        lea     rdx, [rax+784]
.L26:
        addsd   xmm1, xmm3
        addsd   xmm0, xmm2
        add     rax, 8
        movsd   QWORD PTR [rax-8], xmm0
        movapd  xmm0, xmm1
        movsd   QWORD PTR [rax], xmm1
        movsd   xmm1, QWORD PTR [rax+8]
        addsd   xmm1, xmm2
        movsd   QWORD PTR [rax+8], xmm1
        cmp     rax, rdx
        jne     .L26
        ret
[-snip-]

这些代码段之间存在几个区别，但关键的区别在于分别在 .L23 和 .L26 标签之后，在向量版本中，数字通过效率较低的操作码进行相加，而数组版本则使用（更多）SSE指令。与数组版本相比，向量版本还涉及更多的内存查找。这些因素结合在一起将导致代码在 std::array 版本中的执行速度比在 std::vector 版本中快。

- Xirema

---

不错的回答！Clang版本的数组大约快了67％，gcc则快了100％。 - mfnx

使用-stdlib=libc++的Clang（而不是通常的libstdc++）可以优化掉std::vector的分配/释放，如果你已经安装了libc++（https://libcxx.llvm.org/）。我认为这包括当最终结果未被使用且数组/向量上的循环也可以被优化掉的情况。 - Peter Cordes

但无论如何，您在此展示的汇编代码似乎并未证明glob和源数组不重叠，因此它实际上正在重复加载v1 [0]并重复执行加法，以防存储到glob [i]更改了它。 - Peter Cordes

正如@geza在问题中评论的那样，编译器正在优化掉a1[]和a2[]，并从.LC1[rip]加载总和。这是关键点。array版本并没有使用“更有效的操作码”，它们都是纯标量。(movapd是如何复制xmm寄存器的，无论您是否对整个寄存器感兴趣，还是只对底部的标量double或float感兴趣。movsd xmm，xmm进行合并，并依赖于输出寄存器，因此编译器永远不会使用它，除非作为洗牌) - Peter Cordes

@PeterCordes 这非常有趣！我通过将comb函数更改为m + c*f来确认您所说的，其中c是每次迭代都会更改的变量。现在两个版本的性能相等了。 - mfnx

Answer 2

C++的别名规则不允许编译器证明glob[i] += stuff不会修改const vec v1 {1.0,-1.0,1.0};或v2中的一个元素。在std::vector上使用const意味着可以假定"控制块"指针在构造后不会被修改，但内存仍然是动态分配的，编译器只知道它实际上具有静态存储中的const double *。在std::vector实现中没有任何东西让编译器排除一些指向该存储区域的其他non-const指针。例如，在glob的控制块中的double *data。

C++无法为库实现者提供一种方式，让编译器知道不同的std::vector存储区域不重叠。它们不能使用__restrict（即使在支持该扩展的编译器上也是如此），因为这可能会破坏获取向量元素地址的程序。请参见C99文档中关于restrict的说明。

---

但是对于const arr a1 {1.0,-1.0,1.0};和a2，这些双精度数本身可以进入只读静态存储器，编译器知道这一点。因此它可以在编译时评估comb(a1[0],a2[0])等等。在@Xirema的答案中，您可以看到asm输出加载常量.LC1和.LC2。(仅有两个常量，因为a1[0]+a2[0]和a1[2]+a2[2]都是1.0+1.0。循环体两次使用xmm2作为addsd的源操作数，并且另一个常量使用一次。)

---

但编译器在运行时不能在循环外部仍然计算总和吗？

不行，这还是因为可能存在别名的原因。它不知道对glob [i + 0..3]的存储是否会修改v1 [0..2]的内容，因此在每次循环后存储glob之后，它会重新加载v1和v2。

（但是，它不必重新加载vector<>控制块指针，因为基于类型的严格别名规则使其假定存储double不会修改double*。）

编译器可以检查glob.data() + 0..N-3与v1/v1.data() + 0..2都没有重叠，并为该情况创建不同版本的循环，将三个comb()结果提升出循环。

这是一种有用的优化，如果编译器无法证明缺乏别名，则某些编译器在自动向量化时会执行此操作。在您的情况下，gcc没有检查重叠，这显然是一个未能优化的问题，因为它会使函数运行得更快。但问题是编译器是否可以合理地猜测值得发出运行时检查重叠的汇编代码，并具有相同循环的2个不同版本。通过基于配置文件的优化，它将知道循环很热（运行多次迭代），并且值得额外花费时间。但是，如果没有这个，编译器可能不想冒太多膨胀代码的风险。

ICC19（英特尔编译器）实际上在这里确实做了类似的事情，但很奇怪：如果您查看 assemble_vec 的开头（on the Godbolt compiler explorer），它从 glob 加载数据指针，然后加 8 并再次减去指针，产生一个常量 8。然后它在运行时根据 8 > 784（不采取）和 -8 < 784（采取）分支。看起来这应该是一个重叠检查，但它可能使用了同一个指针而不是 v1 和 v2？（784 = 8*100 - 16 = sizeof(double)*N - 16）

无论如何，它最终运行了`..B2.19`循环，该循环提升了所有3个`comb()`计算，并且有趣的是，使用4个标量加载和存储到`glob[i+0..4]`，并且进行了2次迭代，以及6个`addsd`（标量双精度）加法指令。

在函数体的其他地方，有一个矢量化版本，使用3个`addpd`（打包双精度），只存储/重新加载部分重叠的128位向量。这将导致存储转发停顿，但乱序执行可能能够隐藏它。只是真的很奇怪，在运行时分支计算会产生每次都会产生相同结果，却从未使用该循环。看起来像是一个错误。

---

如果glob[]是静态数组，你仍然会遇到问题。因为编译器无法知道v1/v2.data()是否指向该静态数组。

我认为，如果通过double *__restrict g = &glob[0];访问，就不会有任何问题。这将向编译器保证g[i] += ...不会影响通过其他指针访问的任何值，如v1[0]。

实际上，对于gcc、clang或ICC -O3来说，这并不能使comb()提升。但是对于MSVC来说，可以。 （我读过MSVC不执行基于类型的严格别名优化，但它没有在循环内重新加载glob.data()，所以它已经找出存储double不会修改指针的方式。但是，与其他C++实现不同，MSVC定义了用于类型转换的*(int*)my_float的行为。）

为了测试，我把这个放在Godbolt上

//__attribute__((noinline))
void assemble_vec()
{
     double *__restrict g = &glob[0];   // Helps MSVC, but not gcc/clang/ICC
    // std::vector<double> &g = glob;   // actually hurts ICC it seems?
    // #define g  glob                  // so use this as the alternative to __restrict
    for (size_t i=0; i<N-2; ++i)
    {
        g[i] += comb(v1[0],v2[0]);
        g[i+1] += comb(v1[1],v2[1]);
        g[i+2] += comb(v1[2],v2[2]);
    }  
}

我们从循环外部获取这个 MSVC。

    movsd   xmm2, QWORD PTR [rcx]       # v2[0]
    movsd   xmm3, QWORD PTR [rcx+8]
    movsd   xmm4, QWORD PTR [rcx+16]
    addsd   xmm2, QWORD PTR [rax]       # += v1[0]
    addsd   xmm3, QWORD PTR [rax+8]
    addsd   xmm4, QWORD PTR [rax+16]
    mov     eax, 98                             ; 00000062H

然后我们得到了一个看起来很有效的循环。

所以这是gcc/clang/ICC的一个未优化之处。

- Peter Cordes

---

相同的优化可以完成，因为您已经向编译器承诺 g[i] += ... 不会影响通过其他指针访问的任何值。奇怪的是，无论是否使用 __restrict，gcc 或 clang 都不会利用它。他们生成相同的代码（我已经使用 gcc 8.2.0 和 clang 8.0.0 进行了检查）。 - geza

我按照您的说明在assemble_vec()中访问了全局变量glob，但似乎没有任何改变（clang 7.0和gcc 8.2）。 - mfnx

@geza：奇怪，你说得对。MSVC是唯一一个真正利用__restrict以完全按照我所描述的方式启用优化的编译器。（我几乎没有尝试过MSVC，这真是个惊喜。） - Peter Cordes

@MFnx：是的，geza已经评论过了。结果只有MSVC能够发现__restrict允许的优化！请看我的更新答案。 - Peter Cordes

Answer 3

我认为重点在于您使用的存储大小太小（六个双精度数），这使得编译器在使用 std::array 时能够通过将值放入寄存器中来完全消除RAM存储。如果更优，则编译器可以将栈变量存储到寄存器中。这样可以将内存访问减少一半（只保留写入 glob）。对于 std::vector，由于使用动态内存，编译器无法执行此类优化。尝试使用更大的大小来定义 a1、a2、v1、v2。

- Dmytro Dadyka