晚上好。

我知道C样式的数组或std::array并不比 vector 快。我一直都在使用 vector (并且很好地使用它们)。但是,在某些情况下,使用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);

到现在为止还挺好。上面的初始化变量的代码未包含在基准测试中。现在,让我们编写一个函数来组合doublev1v2a1的元素(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。在这两种情况下,数组版本的运行速度几乎都是 vector 版本的两倍。

有人知道为什么吗?谢谢!

最佳答案

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::vector的存储不重叠的信息。 他们不能使用__restrict(即使在支持该扩展的编译器上也是如此),因为这可能会破坏使用 vector 元素地址的程序。参见the C99 documentation for restrict

但是使用const arr a1 {1.0,-1.0,1.0};a2, double 本身可以进入只读静态存储,并且编译器知道这一点。 因此它可以在编译时评估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不会检查重叠部分显然是错过的优化,因为它会使函数运行得更快。但是问题是,编译器是否可以合理地猜测值得散发在运行时检查是否有重叠的asm,并且具有同一循环的2个不同版本。通过配置文件引导的优化,它将知道循环很热(运行许多迭代),并且值得花费额外的时间。但是如果没有这些,编译器可能不想冒过多地膨胀代码的风险。

实际上,ICC19(Intel的编译器)在这里做了类似的事情,但这很奇怪:如果查看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个标量加载并进行了2次迭代,并存储到glob[i+0..4]和6个addsd(标量 double )添加指令中。

在函数体的其他地方,有一个向量化的版本,它使用3x addpd(压缩后的 double ),仅存储/重新加载部分重叠的128位 vector 。这将导致存储转发停顿,但是乱序执行可能能够将其隐藏。真的很奇怪,它在运行时分支到一个计算上,该计算每次都会产生相同的结果,并且从不使用该循环。像 bug 一样闻起来。

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

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

实际上,这无法为gcc,clang或ICC comb()悬挂-O3。但是对于MSVC确实如此。 (我已经读过MSVC不会进行基于类型的严格别名优化,但是它并没有在循环内重新加载glob.data(),因此它已经以某种方式弄清楚了存储 double 不会修改指针。但是MSVC确实定义了行为与其他C++实现不同,用于类型转换的*(int*)my_float。)

为了测试,I put this on 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的优化遗漏。

关于c++ - C++性能std::array vs std::vector,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/54542867/

10-11 22:46
查看更多