为什么 std::count 比 MSVC 编译器的普通循环慢，但与 GCC 相等?

Question

我正在测试C++标准库算法的性能，遇到了一件奇怪的事情。

这是我的代码来比较 std：：count 与普通循环的性能：

#include <algorithm>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std::chrono;

int my_count(const std::vector<int>& v, int val) {
int num = 0;
for (int i: v) {
if (i == val)
num++;
}
return num;
}
int main()
{
int total_count = 0;
std::vector<int> v;
v.resize(100000000);
// Fill vector
for (int i = 0; i < v.size(); i++) {
v[i] = i % 10000;
}
int val = 1;
{
auto start = high_resolution_clock::now();
total_count += std::count(v.begin(), v.end(), val);
auto stop = high_resolution_clock::now();
std::cout << "std::count time:   " << duration_cast<microseconds>(stop - start).count() << std::endl;
}
{
auto start = high_resolution_clock::now();
total_count += my_count(v, val);
auto stop = high_resolution_clock::now();
std::cout << "my_count   time:   " << duration_cast<microseconds>(stop - start).count() << std::endl;
}
// We need this so the compiler does not prune the code above
std::cout << "Total items: " << total_count << std::endl;
}

有了MinGW，我得到这个：

std::count time:   65827
my_count   time:   64861

使用MSVC，我得到了一个非常奇怪的结果：

std::count time:   65532
my_count   time:   28584

MinGW 结果似乎是合理的，因为据我所知，STL 计数函数如果大致等于普通 for 循环，但 MSVC 结果似乎很奇怪 - 为什么普通 for 循环比 std：：count 快 2 倍以上？

这些结果在我的机器上是可重现的 - 它不是一次发生，而是每次运行代码时都会发生。我什至尝试更改函数顺序，运行多个for循环以避免缓存或分支预测偏差，但我仍然得到相同的结果。

这有什么原因吗？

Answer 1

这是因为 MSVC 对手动编写的代码进行矢量化处理，但无法对std::count执行相同的操作。

矢量化代码的外观如下：

movdqa  xmm5, XMMWORD PTR __xmm@00000001000000010000000100000001
and     rcx, -8
xorps   xmm3, xmm3
xorps   xmm2, xmm2
npad    3
$LL4@my_count:
movdqu  xmm1, XMMWORD PTR [rax]
add     r8, 8
movdqa  xmm0, xmm5
paddd   xmm0, xmm3
pcmpeqd xmm1, xmm4
pand    xmm0, xmm1
pandn   xmm1, xmm3
movdqa  xmm3, xmm0
movdqa  xmm0, xmm5
por     xmm3, xmm1
paddd   xmm0, xmm2
movdqu  xmm1, XMMWORD PTR [rax+16]
add     rax, 32                             ; 00000020H
pcmpeqd xmm1, xmm4
pand    xmm0, xmm1
pandn   xmm1, xmm2
movdqa  xmm2, xmm0
por     xmm2, xmm1
cmp     r8, rcx
jne     SHORT $LL4@my_count

您可以在开始时看到它如何在xmm5寄存器中加载 4 个。此值将用于维护 4 个单独的计数器，用于跟踪第 1、2、3 和第 4 个 DWORD 的结果。计数完成后，这 4 个值将相加以形成函数的结果。

MSVC 矢量化器的问题似乎在于计数器、数据类型和参数类型应该是"兼容的"：

• 返回类型的大小应与数据类型匹配
• 参数类型的大小应等于或小于数据类型

如果不满足其中任何约束，则不会对代码进行矢量化。这是有道理的，因为如果您的数据类型是 32 位宽的，您必须在 32 位计数器上运行才能使它们协同工作，因此如果您的返回类型是 64 位宽，则需要一些额外的操作(这是 GCC 能够做的，但与手动编写的循环相比，这仍然会减慢std::count(。

在这种情况下，应该首选手动编写的循环，因为语义(int返回类型(的细微差异使其更容易矢量化(即使对于生成较短代码的 GCC(。

Answer 2

嗯，这似乎是一个迭代器问题。

我做了一个扩展测试：

#include <algorithm>
#include <vector>
#include <iostream>
#include <chrono>
using namespace std::chrono;

int std_count(const std::vector<int>& v, int val) {
return std::count(v.begin(), v.end(), val);
}
int my_count_for(const std::vector<int>& v, int val) {
int num = 0;
for (int i = 0; i < v.size(); i++) {
if (v[i] == val) {
num++;
}
}
return num;
}
int my_count_for_in(const std::vector<int>& v, int val) {
int num = 0;
for (int i : v) {
if (i == val) {
num++;
}
}
return num;
}
int my_count_iter(const std::vector<int>& v, int val) {
int num = 0;
for (auto i = v.begin(); i < v.end(); i++) {
if (*i == val) {
num++;
}
}
return num;
}

int main()
{
std::vector<int> v;
v.resize(1000000);
// Fill vector
for (int i = 0; i < v.size(); i++) {
v[i] = i % 10000;
}
int val = 1;
int num_iters = 1000;
int total_count = 0;
for (int a = 0; a < 3; a++) {
{
auto start = high_resolution_clock::now();
for (int i = 0; i < num_iters; i++) {
total_count += std_count(v, val);
}
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
std::cout << "std::count time:       " << duration.count() << std::endl;
}
{
auto start = high_resolution_clock::now();
for (int i = 0; i < num_iters; i++) {
total_count += my_count_for(v, val);
}
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
std::cout << "my_count_for time:     " << duration.count() << std::endl;
}
{
auto start = high_resolution_clock::now();
for (int i = 0; i < num_iters; i++) {
total_count += my_count_for_in(v, val);
}
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
std::cout << "my_count_for_in time:  " << duration.count() << std::endl;
}
{
auto start = high_resolution_clock::now();
for (int i = 0; i < num_iters; i++) {
total_count += my_count_iter(v, val);
}
auto stop = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop - start);
std::cout << "my_count_iter time:    " << duration.count() << std::endl;
}
std::cout << std::endl;
}
std::cout << total_count << std::endl;
std::cin >> total_count;
}

这是我得到的：

std::count time:       679683
my_count_for time:     235269
my_count_for_in time:  228185
my_count_iter time:    650714
std::count time:       656192
my_count_for time:     231248
my_count_for_in time:  231050
my_count_iter time:    652598
std::count time:       660295
my_count_for time:     238812
my_count_for_in time:  225893
my_count_iter time:    648812

STL函数不是解决任务的最快方法似乎仍然很奇怪。如果有人知道详细的答案，请与我分享。