C++性能std :: array vs 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);

到现在为止还挺好.初始化变量的上述代码不包含在基准测试中.现在,让我们写一个函数元素(结合double)的v1和v2,或a1和a2:

// 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试过这个.在这两种情况下,阵列版本的速度几乎是矢量版本的两倍.

有谁知道为什么？谢谢!

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.

Answer 2

C++ 别名规则不允许编译器证明glob[i] += stuff不修改const vec v1 {1.0,-1.0,1.0};或的元素之一v2。

const在std::vector某种意义上，可以假定“控制块”指针在构造后不会被修改，但是内存仍然是动态分配的，并且编译器只知道它实际上有一个const double *静态存储。

实现中的任何内容都std::vector不允许编译器排除指向该存储的其他 non-const指针。例如，double *data控制块中的glob。

C++ 没有为库实现者提供一种方法来向编译器提供不同std::vectors的存储不重叠的信息。 它们不能使用__restrict（即使在支持该扩展的编译器上），因为这可能会破坏采用向量元素地址的程序。请参阅C99 文档restrict。

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

但是编译器不能在运行时在循环外进行求和吗？

不，再次因为潜在的混叠。它不知道 store intoglob[i+0..3]不会修改 的内容v1[0..2]，因此每次通过 store into 之后的循环都会从 v1 和 v2 重新加载glob。

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

编译器可以检查glob.data() + 0 .. N-3与 中的任何一个都不重叠v1/v1.data() + 0 .. 2，并为这种情况制作不同版本的循环，将三个comb()结果提升到循环之外。

这是一些编译器在自动矢量化时所做的有用的优化，如果它们不能证明缺少别名；在您的情况下，gcc 不检查重叠显然是一个错过的优化，因为它会使函数运行得更快。但问题是编译器是否可以合理地猜测它是否值得发出在运行时检查重叠的 asm，并且有 2 个不同版本的同一循环。通过配置文件引导的优化，它会知道循环很热（运行多次迭代），并且值得花额外的时间。但是没有它，编译器可能不想冒使代码膨胀太多的风险。

ICC19（Intel的编译器），事实上确实在这里做这样的事情，但它的怪异：如果你看的开始assemble_vec（在Godbolt编译探险家），它加载数据指针从glob，然后添加8，再减去指针，产生一个常数8。然后它在运行时分支8 > 784（未采用）然后-8 < 784（采用）。看起来这应该是重叠检查，但它可能两次使用相同的指针而不是 v1 和 v2？( 784 = 8*100 - 16 = sizeof(double)*N - 16)

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

在函数体的其他地方，有一个使用 3x addpd（压缩双精度）的向量化版本，只是存储/重新加载部分重叠的 128 位向量。这将导致存储转发停顿，但无序执行可能能够隐藏这一点。它在运行时在每次都会产生相同结果的计算上进行分支，并且从不使用该循环，这真的很奇怪。闻起来像虫子。

如果glob[]是静态数组，您仍然会遇到问题。因为编译器不知道v1/v2.data()没有指向那个静态数组。

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

在实践中，这并没有使吊起comb()了GCC，铛，或ICC -O3。但它确实为MSVC。（我读过 MSVC 不进行基于类型的严格别名优化，但它不会glob.data()在循环内重新加载，因此它以某种方式发现存储双精度不会修改指针。但 MSVC 确实定义了*(int*)my_floatfor类型双关，与其他 C++ 实现不同。）

为了测试，我把它放在 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 的遗漏优化。