在C++中，当涉及到从容器中删除几个元素时，有一个'erase-remove' idiom，并且有关于另一种“resize-remove”方式的讨论，例如here。人们说'erase-remove'比'resize-remove'更好，但根据我的测试，后者在向量上（稍微）更快。那么，当涉及到向量时，我应该使用“resize-remove”吗？
下面是我的基准测试代码：
#include <benchmark/benchmark.h>
#include <algorithm>
#include <functional>
#include <iostream>
#include <random>
#include <vector>
using namespace std;
constexpr size_t N_ELEMS = 1000000;
constexpr int MAX_VAL = N_ELEMS / 10;
constexpr int THRESH = MAX_VAL / 5 * 3;
static vector<int> generate_input() {
vector<int> nums(N_ELEMS);
std::random_device rd;
std::mt19937 gen(rd());
std::uniform_int_distribution<> dist(0, N_ELEMS);
std::generate(nums.begin(), nums.end(), std::bind(dist, std::ref(gen)));
return std::move(nums);
}
static void bm_erase_remove(benchmark::State &state) {
for (auto _ : state) {
state.PauseTiming();
auto nums = generate_input();
state.ResumeTiming();
nums.erase(std::remove_if(nums.begin(), nums.end(),
[](int x) { return x < THRESH; }),
nums.end());
benchmark::DoNotOptimize(nums);
}
}
BENCHMARK(bm_erase_remove);
static void bm_resize_remove(benchmark::State &state) {
for (auto _ : state) {
state.PauseTiming();
auto nums = generate_input();
state.ResumeTiming();
nums.resize(std::distance(
nums.begin(), std::remove_if(nums.begin(), nums.end(),
[](int x) { return x < THRESH; })));
benchmark::DoNotOptimize(nums);
}
}
BENCHMARK(bm_resize_remove);
BENCHMARK_MAIN();输出：
$ g++ main.cpp -lbenchmark -O3 -pthread
$ ./a.out
2023-05-24T20:07:22+08:00
Running ./a.out
Run on (16 X 3193.91 MHz CPU s)
CPU Caches:
L1 Data 32 KiB (x8)
L1 Instruction 32 KiB (x8)
L2 Unified 512 KiB (x8)
L3 Unified 16384 KiB (x1)
Load Average: 0.16, 0.14, 0.16
-----------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------
bm_erase_remove 822789 ns 759162 ns 838
bm_resize_remove 818217 ns 754749 ns 935使用clang++时，差异更大：
$ clang++ main.cpp -lbenchmark -O3 -pthread
$ ./a.out
Load Average: 0.25, 0.18, 0.17
-----------------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------------
bm_erase_remove 1165085 ns 1074667 ns 611
bm_resize_remove 958856 ns 884584 ns 782额外信息：
g++的版本是13.1.1，clang++的版本是15.0.7- 我在WSL上使用Arch Linux，内核版本是
5.15.90.1-microsoft-standard-WSL2 - CPU型号为
AMD Ryzen 7 6800H with Radeon Graphics
**更新：**有趣的是，当我单独运行基准测试时（使用benchmark_filter选项），结果是等效的。这是因为缓存吗？如果是，缓存机制是如何工作的？
**UPDATE（2023/5/25）：**如果两个BENCHMARK语句被交换，则显示完全相反的结果。
1条答案
按热度按时间ar5n3qh51#
它们的性能差不多，这是因为
std::remove_if是唯一一个修改数组的函数，而不同之处在于其他函数，std::vector::resize创建了一个realloc来适应新的大小（std::distance只返回大小，所以它可以忽略不计），而std::vector::erase只是采用了容器，使它稍微快一点。正如@Peter Cordes “实际上保证不会重新分配” 所指出的那样，如果新的大小较小，
std::vector::resize不会调整向量的大小，因此区别应该是erase（vs，clang）执行的额外移动（vs，clang）和resize（vs，clang）不执行的。为了能够测量差异，
generate_input()需要为所有测试返回相同的向量，在您的实现中，每个调用都返回一个新的随机向量，这使得无法区分运行差异和向量变化。因此，@463035818_is_not_a_number提出了一个有趣的观点，但出于与前面相同的原因，这些函数之间没有区别。这并不意味着情况是一样的，对于一个结构体来说，一个坏分支的代价要大得多，这使得
std::remove_if成为优化的主要目标，请参见下面的windows图。所有图均来自50次运行，绿色是最佳运行和平均值之间的范围，红色是平均值到最差结果的范围，这是为了显示运行间的方差。
i5-1155G7 + 3200MHz RAM on manjaro with clang-13 and -O3
1600X + 1067MHz RAM on windows 10 (22H2) with vs2022 and /O2
1600X + 1067MHz RAM on windows 10 (22H2) with clang-16 and -O3 -pthread
1600X + 1067MHz RAM on ubuntu 22 with clang-13 and -O3
在vs中，似乎有一个优化 bug（？），这使得
simple_remove的表现不如u32和u64。以及重建情节的代码。