C++ 性能 std::array 对比 std::vector
C++ performance std::array vs std::vector
晚上好。
我知道 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 试过了。在这两种情况下，数组版本的运行速度几乎是矢量版本的两倍。
有谁知道为什么？谢谢！
我认为关键是您使用的存储空间太小（六倍），这允许编译器在 std::array 情况下通过将值放入寄存器来完全消除 RAM 存储。如果更优化，编译器可以将堆栈变量存储到寄存器中。这将内存访问减少了一半（只保留写入 glob）。在 std::vector 的情况下，编译器无法执行此类优化，因为使用了动态内存。尝试为 a1, a2, v1, v2
使用更大的尺寸
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标签之后，对于矢量版本，数字是通过less相加的高效的操作码，与使用（更多）SSE 指令的数组版本相比。与数组版本相比，矢量版本还涉及更多的内存查找。这些因素相互结合将导致 std::array 版本的代码比 std::vector 版本的代码执行得更快。
C++ 别名规则不允许编译器证明 glob[i] += stuff 没有修改 const vec v1 {1.0,-1.0,1.0}; 或 v2.[=122 的元素之一=]
std::vector 上的 const 意味着可以假定 "control block" 指针在构造后不会被修改，但是内存仍然是动态分配的，编译器只知道它实际上在静态存储中有一个 const double *。
std::vector 实现中的任何内容都不允许编译器排除一些指向该存储的 other non-const 指针。例如glob.
控制块中的double *data
C++ 没有为库实现者提供一种方法来向编译器提供不同 std::vector 的存储不重叠的信息。 他们可以'不要使用 __restrict（即使在支持该扩展的编译器上），因为这可能会破坏采用矢量元素地址的程序。参见 the C99 documentation for 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 的源操作数两次，另一个常量一次.)
但是编译器不能在 运行 时间在循环外进行一次求和吗？
不，同样是因为潜在的混叠。它不知道 store into glob[i+0..3] 不会修改 v1[0..2] 的内容，所以它在 store into glob.[= 之后每次通过循环从 v1 和 v2 重新加载。 67=]
（它不必重新加载 vector<> 控制块指针，因为基于类型的严格别名规则让它假定存储 double 不会修改 double*.)
编译器 可以 检查 glob.data() + 0 .. N-3 没有与 v1/v1.data() + 0 .. 2 中的任何一个重叠，并为这种情况制作不同版本的循环, 将三个 comb() 结果提升到循环之外。
如果某些编译器不能证明缺少别名，那么在自动矢量化时，这是一个有用的优化；在你的情况下，gcc 不检查重叠显然是一个错过的优化，因为它会使函数 运行 更快。但问题是编译器是否可以合理地猜测值得发出在 运行 时间检查重叠的 asm，并且具有同一循环的 2 个不同版本。通过配置文件引导的优化，它会知道循环很热（运行s 多次迭代），并且值得花费额外的时间。但如果没有它，编译器可能不想冒使代码膨胀太多的风险。
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)
无论如何，它结束了 运行 提升所有 3 comb() 计算的 ..B2.19 循环，并且有趣的是一次使用 4 个标量加载和存储在循环中进行 2 次迭代向 glob[i+0..4] 和 6 addsd（标量双精度）添加指令。
在函数体的其他地方，有一个使用 3x addpd（压缩双精度）的向量化版本，仅存储/重新加载部分重叠的 128 位向量。这将导致存储转发停顿，但乱序执行可能会隐藏这一点。真的很奇怪，它在 运行 时间分支计算每次都会产生相同的结果，并且从不使用该循环。闻起来像虫子。
如果 glob[] 是静态数组，您仍然会遇到问题。因为编译器不知道 v1/v2.data() 没有指向那个静态数组。
我想如果你通过double *__restrict g = &glob[0];访问它，就完全没有问题了。这将向编译器保证 g[i] += ... 不会影响您通过其他指针访问的任何值，例如 v1[0].
实际上，不会 为 gcc、clang 或 ICC -O3 启用 comb() 提升。但它 确实 用于 MSVC。 （我读过 MSVC 没有进行基于类型的严格别名优化，但它没有在循环内重新加载 glob.data() 所以它以某种方式发现存储双精度不会修改指针。但是 MSVC 确实为类型双关定义 *(int*)my_float 的行为，这与其他 C++ 实现不同。）
//__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 风格数组或 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 试过了。在这两种情况下，数组版本的运行速度几乎是矢量版本的两倍。
有谁知道为什么？谢谢！
我认为关键是您使用的存储空间太小（六倍），这允许编译器在 std::array 情况下通过将值放入寄存器来完全消除 RAM 存储。如果更优化，编译器可以将堆栈变量存储到寄存器中。这将内存访问减少了一半（只保留写入 glob）。在 std::vector 的情况下，编译器无法执行此类优化，因为使用了动态内存。尝试为 a1, a2, v1, v2
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标签之后，对于矢量版本，数字是通过less相加的高效的操作码，与使用（更多）SSE 指令的数组版本相比。与数组版本相比，矢量版本还涉及更多的内存查找。这些因素相互结合将导致 std::array 版本的代码比 std::vector 版本的代码执行得更快。
C++ 别名规则不允许编译器证明 glob[i] += stuff 没有修改 const vec v1 {1.0,-1.0,1.0}; 或 v2.[=122 的元素之一=]
std::vector 上的 const 意味着可以假定 "control block" 指针在构造后不会被修改，但是内存仍然是动态分配的，编译器只知道它实际上在静态存储中有一个 const double *。
std::vector 实现中的任何内容都不允许编译器排除一些指向该存储的 other non-const 指针。例如glob.
double *data
C++ 没有为库实现者提供一种方法来向编译器提供不同 std::vector 的存储不重叠的信息。 他们可以'不要使用 __restrict（即使在支持该扩展的编译器上），因为这可能会破坏采用矢量元素地址的程序。参见 the C99 documentation for 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 的源操作数两次，另一个常量一次.)
但是编译器不能在 运行 时间在循环外进行一次求和吗？
不，同样是因为潜在的混叠。它不知道 store into glob[i+0..3] 不会修改 v1[0..2] 的内容，所以它在 store into glob.[= 之后每次通过循环从 v1 和 v2 重新加载。 67=]
（它不必重新加载 vector<> 控制块指针，因为基于类型的严格别名规则让它假定存储 double 不会修改 double*.)
编译器 可以 检查 glob.data() + 0 .. N-3 没有与 v1/v1.data() + 0 .. 2 中的任何一个重叠，并为这种情况制作不同版本的循环, 将三个 comb() 结果提升到循环之外。
如果某些编译器不能证明缺少别名，那么在自动矢量化时，这是一个有用的优化；在你的情况下，gcc 不检查重叠显然是一个错过的优化，因为它会使函数 运行 更快。但问题是编译器是否可以合理地猜测值得发出在 运行 时间检查重叠的 asm，并且具有同一循环的 2 个不同版本。通过配置文件引导的优化，它会知道循环很热（运行s 多次迭代），并且值得花费额外的时间。但如果没有它，编译器可能不想冒使代码膨胀太多的风险。
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)
无论如何，它结束了 运行 提升所有 3 comb() 计算的 ..B2.19 循环，并且有趣的是一次使用 4 个标量加载和存储在循环中进行 2 次迭代向 glob[i+0..4] 和 6 addsd（标量双精度）添加指令。
在函数体的其他地方，有一个使用 3x addpd（压缩双精度）的向量化版本，仅存储/重新加载部分重叠的 128 位向量。这将导致存储转发停顿，但乱序执行可能会隐藏这一点。真的很奇怪，它在 运行 时间分支计算每次都会产生相同的结果，并且从不使用该循环。闻起来像虫子。
如果 glob[] 是静态数组，您仍然会遇到问题。因为编译器不知道 v1/v2.data() 没有指向那个静态数组。
我想如果你通过double *__restrict g = &glob[0];访问它，就完全没有问题了。这将向编译器保证 g[i] += ... 不会影响您通过其他指针访问的任何值，例如 v1[0].
实际上，不会 为 gcc、clang 或 ICC -O3 启用 comb() 提升。但它 确实 用于 MSVC。 （我读过 MSVC 没有进行基于类型的严格别名优化，但它没有在循环内重新加载 glob.data() 所以它以某种方式发现存储双精度不会修改指针。但是 MSVC 确实为类型双关定义 *(int*)my_float 的行为，这与其他 C++ 实现不同。）
//__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 的优化失误。