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