为什么 Range-v3 比本例中的 STL 慢？
Why is Range-v3 slower than the STL in this example?
我正在使用 Range-v3 库来执行美化 find_if 并且很好奇为什么 google-benchmark 始终将我的 Range-v3 代码排在我的 std::find_if 方法。 g++ 和 clang 使用 -O3 和 #define NDEBUG.
给出相同的模式
我想到的具体示例是以下使用 STL 的示例：
std::vector<int> lengths(large_number, random_number);
auto const to_find = std::accumulate(lengths.begin(), lengths.end(), 0l) / 2;
auto accumulated_length = 0l;
auto found = std::find_if(lengths.begin(), lengths.end(), [&](auto const &val) {
accumulated_length += val;
return to_find < accumulated_length;
});
auto found_index = std::distance(lengths.begin(), found);
出于此说明的目的，这有些人为设计，但通常会有一个随机生成器用于 to_find 变量和 lengths 向量中的随机值。
使用 Range-v3 库，我得到以下代码
using namespace ranges;
std::vector<int> lengths(large_number, random_number);
auto const to_find = accumulate(lengths, 0l) / 2;
auto found_index = distance(lengths | view::partial_sum()
| view::take_while([=](auto const i) {
return i < to_find;
}));
我的问题是为什么 Range-v3 比 STL 实现慢。我知道这仍然是一个实验性库，但也许代码示例有问题或者我误用了范围概念？
编辑
一个例子google-bench driver（不确定是否正确）
#define NDEBUG
#include <numeric>
#include <vector>
#include <benchmark/benchmark.h>
#include <range/v3/all.hpp>
static void stl_search(benchmark::State &state) {
using namespace ranges;
std::vector<long> lengths(state.range(0), 1l);
auto const to_find = std::accumulate(lengths.begin(), lengths.end(), 0l) / 2;
while (state.KeepRunning()) {
auto accumulated_length = 0l;
auto const found = std::find_if(lengths.begin(), lengths.end(), [&](auto const& val) {
accumulated_length += val;
return to_find < accumulated_length;
});
volatile long val = std::distance(lengths.begin(), found);
}
state.SetBytesProcessed(int64_t(state.iterations()) *
int64_t(state.range(0)) * sizeof(long));
}
static void ranges_search(benchmark::State &state) {
using namespace ranges;
std::vector<long> lengths(state.range(0), 1l);
auto const to_find = accumulate(lengths, 0l) / 2;
while (state.KeepRunning())
{
volatile long val = distance(lengths | view::partial_sum()
| view::take_while([=](auto const& i) {
return i <= to_find;
}));
}
state.SetBytesProcessed(int64_t(state.iterations()) *
int64_t(state.range(0)) * sizeof(long));
}
BENCHMARK(ranges_search)->Range(8 << 8, 8 << 16);
BENCHMARK(stl_search)->Range(8 << 8, 8 << 16);
BENCHMARK_MAIN();
给予
ranges_search/2048 756 ns 756 ns 902091 20.1892GB/s
ranges_search/4096 1495 ns 1494 ns 466681 20.4285GB/s
ranges_search/32768 11872 ns 11863 ns 58902 20.5801GB/s
ranges_search/262144 94982 ns 94892 ns 7364 20.5825GB/s
ranges_search/524288 189870 ns 189691 ns 3688 20.5927GB/s
stl_search/2048 348 ns 348 ns 2000964 43.8336GB/s
stl_search/4096 690 ns 689 ns 1008295 44.2751GB/s
stl_search/32768 5497 ns 5492 ns 126097 44.452GB/s
stl_search/262144 44725 ns 44681 ns 15882 43.7122GB/s
stl_search/524288 91027 ns 90936 ns 7616 42.9563GB/s
使用 clang 4.0.1 和
ranges_search/2048 2309 ns 2307 ns 298507 6.61496GB/s
ranges_search/4096 4558 ns 4554 ns 154520 6.70161GB/s
ranges_search/32768 36482 ns 36454 ns 19191 6.69726GB/s
ranges_search/262144 287072 ns 286801 ns 2438 6.81004GB/s
ranges_search/524288 574230 ns 573665 ns 1209 6.80928GB/s
stl_search/2048 299 ns 298 ns 2340691 51.1437GB/s
stl_search/4096 592 ns 591 ns 1176783 51.6363GB/s
stl_search/32768 4692 ns 4689 ns 149460 52.0711GB/s
stl_search/262144 37718 ns 37679 ns 18611 51.8358GB/s
stl_search/524288 75247 ns 75173 ns 9244 51.9633GB/s
使用 gcc 6.3.1。我的机器有一个 Haswell 一代处理器。两者都是用
编译和执行的
g++ -Wall -O3 -std=c++14 Ranges.cpp -lbenchmark -lpthread && ./a.out
clang++ -Wall -O3 -std=c++14 Ranges.cpp -lbenchmark -lpthread && ./a.out
view::partial_sum 在 int 的范围内产生 int 的范围。如果to_find > INT_MAX，内部累加器会溢出导致UB。在实践中，该算法最有可能遍历整个输入和 returns 结束迭代器。
相反，非范围 v3 方法中的 accumulated_length 是 long。它不会溢出，因此在处理整个输入之前定义了行为 / returns。
如果在通过 partial_sum:
之前将输入范围 transform 转换为 long 范围，则 range-v3 方法将具有正确的行为
auto found_index = distance(lengths
| view::transform(convert_to<long>{}) | view::partial_sum()
| view::take_while([=](auto const i) { return i < to_find; }));
即使有了这个正确性修复，它仍然比在我的测试中使用标准算法慢得多。编译此测试程序：
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
#ifdef USE_RV3
#include <range/v3/core.hpp>
#include <range/v3/algorithm.hpp>
#include <range/v3/numeric.hpp>
#include <range/v3/view.hpp>
#else
#include <algorithm>
#include <numeric>
#endif
int main() {
constexpr size_t large_number = 1UL << 30;
int random_number = 42;
std::vector<int> const lengths(large_number, random_number);
using clock_t = std::chrono::steady_clock;
auto const start = clock_t::now();
#ifdef USE_RV3
auto const to_find = ranges::accumulate(lengths, 0l) / 2;
#else
auto const to_find = std::accumulate(lengths.begin(), lengths.end(), 0l) / 2;
#endif
auto const elapsed1 = clock_t::now() - start;
#ifdef USE_RV3
auto const found_index = ranges::distance(lengths
| ranges::view::transform(ranges::convert_to<long>{})
| ranges::view::partial_sum()
| ranges::view::take_while([=](auto const i) { return !(to_find < i); }));
#else
auto accumulated_length = 0l;
auto found = std::find_if(lengths.begin(), lengths.end(), [&](auto const &val) {
accumulated_length += val;
return to_find < accumulated_length;
});
auto const found_index = std::distance(lengths.begin(), found);
#endif
auto const elapsed2 = clock_t::now() - start;
std::cout << "elapsed1: "
<< std::chrono::duration<double, std::milli>(elapsed1).count()
<< " ms, to_find: " << to_find << "\n"
"elapsed2: "
<< std::chrono::duration<double, std::milli>(elapsed2).count()
<< " ms, result: " << found_index << '\n';
}
和
g++-6 -std=c++14 -Ofast -march=native -DNDEBUG rv3.cpp -I ~/dev/range-v3/include -S -o -
没有和有 -DUSE_RV3 并且比较汇编输出很有趣。通过初始化 elapsed1 生成的代码在这两种情况下是相同的。 elapsed1 和 elapsed2 的初始化之间的中间部分存在显着差异。 gcc 在优化 std 版本方面做得更好：热循环都在一个代码 运行 中，带有用于终止条件的分支。 range-v3 版本更难看，而且跳来跳去；我推测我们需要调整 partial_sum 的实现细节，以使其对优化器更加透明。
我正在使用 Range-v3 库来执行美化 find_if 并且很好奇为什么 google-benchmark 始终将我的 Range-v3 代码排在我的 std::find_if 方法。 g++ 和 clang 使用 -O3 和 #define NDEBUG.
我想到的具体示例是以下使用 STL 的示例：
std::vector<int> lengths(large_number, random_number);
auto const to_find = std::accumulate(lengths.begin(), lengths.end(), 0l) / 2;
auto accumulated_length = 0l;
auto found = std::find_if(lengths.begin(), lengths.end(), [&](auto const &val) {
accumulated_length += val;
return to_find < accumulated_length;
});
auto found_index = std::distance(lengths.begin(), found);
出于此说明的目的，这有些人为设计，但通常会有一个随机生成器用于 to_find 变量和 lengths 向量中的随机值。
使用 Range-v3 库，我得到以下代码
using namespace ranges;
std::vector<int> lengths(large_number, random_number);
auto const to_find = accumulate(lengths, 0l) / 2;
auto found_index = distance(lengths | view::partial_sum()
| view::take_while([=](auto const i) {
return i < to_find;
}));
我的问题是为什么 Range-v3 比 STL 实现慢。我知道这仍然是一个实验性库，但也许代码示例有问题或者我误用了范围概念？
编辑
一个例子google-bench driver（不确定是否正确）
#define NDEBUG
#include <numeric>
#include <vector>
#include <benchmark/benchmark.h>
#include <range/v3/all.hpp>
static void stl_search(benchmark::State &state) {
using namespace ranges;
std::vector<long> lengths(state.range(0), 1l);
auto const to_find = std::accumulate(lengths.begin(), lengths.end(), 0l) / 2;
while (state.KeepRunning()) {
auto accumulated_length = 0l;
auto const found = std::find_if(lengths.begin(), lengths.end(), [&](auto const& val) {
accumulated_length += val;
return to_find < accumulated_length;
});
volatile long val = std::distance(lengths.begin(), found);
}
state.SetBytesProcessed(int64_t(state.iterations()) *
int64_t(state.range(0)) * sizeof(long));
}
static void ranges_search(benchmark::State &state) {
using namespace ranges;
std::vector<long> lengths(state.range(0), 1l);
auto const to_find = accumulate(lengths, 0l) / 2;
while (state.KeepRunning())
{
volatile long val = distance(lengths | view::partial_sum()
| view::take_while([=](auto const& i) {
return i <= to_find;
}));
}
state.SetBytesProcessed(int64_t(state.iterations()) *
int64_t(state.range(0)) * sizeof(long));
}
BENCHMARK(ranges_search)->Range(8 << 8, 8 << 16);
BENCHMARK(stl_search)->Range(8 << 8, 8 << 16);
BENCHMARK_MAIN();
给予
ranges_search/2048 756 ns 756 ns 902091 20.1892GB/s
ranges_search/4096 1495 ns 1494 ns 466681 20.4285GB/s
ranges_search/32768 11872 ns 11863 ns 58902 20.5801GB/s
ranges_search/262144 94982 ns 94892 ns 7364 20.5825GB/s
ranges_search/524288 189870 ns 189691 ns 3688 20.5927GB/s
stl_search/2048 348 ns 348 ns 2000964 43.8336GB/s
stl_search/4096 690 ns 689 ns 1008295 44.2751GB/s
stl_search/32768 5497 ns 5492 ns 126097 44.452GB/s
stl_search/262144 44725 ns 44681 ns 15882 43.7122GB/s
stl_search/524288 91027 ns 90936 ns 7616 42.9563GB/s
使用 clang 4.0.1 和
ranges_search/2048 2309 ns 2307 ns 298507 6.61496GB/s
ranges_search/4096 4558 ns 4554 ns 154520 6.70161GB/s
ranges_search/32768 36482 ns 36454 ns 19191 6.69726GB/s
ranges_search/262144 287072 ns 286801 ns 2438 6.81004GB/s
ranges_search/524288 574230 ns 573665 ns 1209 6.80928GB/s
stl_search/2048 299 ns 298 ns 2340691 51.1437GB/s
stl_search/4096 592 ns 591 ns 1176783 51.6363GB/s
stl_search/32768 4692 ns 4689 ns 149460 52.0711GB/s
stl_search/262144 37718 ns 37679 ns 18611 51.8358GB/s
stl_search/524288 75247 ns 75173 ns 9244 51.9633GB/s
使用 gcc 6.3.1。我的机器有一个 Haswell 一代处理器。两者都是用
编译和执行的g++ -Wall -O3 -std=c++14 Ranges.cpp -lbenchmark -lpthread && ./a.out
clang++ -Wall -O3 -std=c++14 Ranges.cpp -lbenchmark -lpthread && ./a.out
view::partial_sum 在 int 的范围内产生 int 的范围。如果to_find > INT_MAX，内部累加器会溢出导致UB。在实践中，该算法最有可能遍历整个输入和 returns 结束迭代器。
相反，非范围 v3 方法中的 accumulated_length 是 long。它不会溢出，因此在处理整个输入之前定义了行为 / returns。
如果在通过 partial_sum:
transform 转换为 long 范围，则 range-v3 方法将具有正确的行为
auto found_index = distance(lengths
| view::transform(convert_to<long>{}) | view::partial_sum()
| view::take_while([=](auto const i) { return i < to_find; }));
即使有了这个正确性修复，它仍然比在我的测试中使用标准算法慢得多。编译此测试程序：
#include <chrono>
#include <iostream>
#include <random>
#include <vector>
#ifdef USE_RV3
#include <range/v3/core.hpp>
#include <range/v3/algorithm.hpp>
#include <range/v3/numeric.hpp>
#include <range/v3/view.hpp>
#else
#include <algorithm>
#include <numeric>
#endif
int main() {
constexpr size_t large_number = 1UL << 30;
int random_number = 42;
std::vector<int> const lengths(large_number, random_number);
using clock_t = std::chrono::steady_clock;
auto const start = clock_t::now();
#ifdef USE_RV3
auto const to_find = ranges::accumulate(lengths, 0l) / 2;
#else
auto const to_find = std::accumulate(lengths.begin(), lengths.end(), 0l) / 2;
#endif
auto const elapsed1 = clock_t::now() - start;
#ifdef USE_RV3
auto const found_index = ranges::distance(lengths
| ranges::view::transform(ranges::convert_to<long>{})
| ranges::view::partial_sum()
| ranges::view::take_while([=](auto const i) { return !(to_find < i); }));
#else
auto accumulated_length = 0l;
auto found = std::find_if(lengths.begin(), lengths.end(), [&](auto const &val) {
accumulated_length += val;
return to_find < accumulated_length;
});
auto const found_index = std::distance(lengths.begin(), found);
#endif
auto const elapsed2 = clock_t::now() - start;
std::cout << "elapsed1: "
<< std::chrono::duration<double, std::milli>(elapsed1).count()
<< " ms, to_find: " << to_find << "\n"
"elapsed2: "
<< std::chrono::duration<double, std::milli>(elapsed2).count()
<< " ms, result: " << found_index << '\n';
}
和
g++-6 -std=c++14 -Ofast -march=native -DNDEBUG rv3.cpp -I ~/dev/range-v3/include -S -o -
没有和有 -DUSE_RV3 并且比较汇编输出很有趣。通过初始化 elapsed1 生成的代码在这两种情况下是相同的。 elapsed1 和 elapsed2 的初始化之间的中间部分存在显着差异。 gcc 在优化 std 版本方面做得更好：热循环都在一个代码 运行 中，带有用于终止条件的分支。 range-v3 版本更难看，而且跳来跳去；我推测我们需要调整 partial_sum 的实现细节，以使其对优化器更加透明。