为什么 std::none_of 比手动循环快？

Question

我使用 i) for 循环，ii) 基于范围的 for 循环和 iii) 迭代器，针对三种不同的手动实现对 std::none_of 的性能进行了基准测试。令我惊讶的是，我发现虽然所有三个手动实现花费的时间大致相同，但 std::none_of 明显更快。我的问题是 - 为什么会这样？

我使用了 Google 基准库并用 -std=c++14 -O3 编译。运行测试时，我将进程的亲和性限制为单个处理器。我使用 GCC 6.2 得到以下结果：

Benchmark                  Time           CPU Iterations
--------------------------------------------------------
benchmarkSTL           28813 ns      28780 ns      24283
benchmarkManual        46203 ns      46191 ns      15063
benchmarkRange         48368 ns      48243 ns      16245
benchmarkIterator      44732 ns      44710 ns      15698

在 Clang 3.9 上，std::none_of 也比手动 for 循环更快，尽管速度差异较小。下面是测试代码（为简洁起见，只包括手册 for 循环）：

#include <algorithm>
#include <array>
#include <benchmark/benchmark.h>
#include <functional>
#include <random>

const size_t N = 100000;
const unsigned value = 31415926;

template<size_t N>
std::array<unsigned, N> generateData() {
    std::mt19937 randomEngine(0);
    std::array<unsigned, N> data;
    std::generate(data.begin(), data.end(), randomEngine);
    return data;
}

void benchmarkSTL(benchmark::State & state) {
    auto data = generateData<N>();
    while (state.KeepRunning()) {
        bool result = std::none_of(
            data.begin(),
            data.end(),
            std::bind(std::equal_to<unsigned>(), std::placeholders::_1, value));
        assert(result);
    }
}

void benchmarkManual(benchmark::State & state) {
    auto data = generateData<N>();
    while (state.KeepRunning()) {
        bool result = true;
        for (size_t i = 0; i < N; i++) {
            if (data[i] == value) {
                result = false;
                break;
            }
        }
        assert(result);
    }
}

BENCHMARK(benchmarkSTL);
BENCHMARK(benchmarkManual);

BENCHMARK_MAIN();

请注意，使用随机数生成器生成数据是无关紧要的。将第 i 个元素设置为 i 并检查是否包含值 N + 1 时，我得到相同的结果。

Answer 1

经过更多调查，我将尝试回答我自己的问题。正如 Kerrek SB 所建议的，我查看了生成的汇编代码。最重要的是，与其他三个版本相比，GCC 6.2 在展开 std::none_of 中隐含的循环方面做得更好。

海湾合作委员会 6.2:

std::none_of 展开 4 次 -> ~30µs
手动 for、范围 for 和迭代器根本没有展开 -> ~45µs

正如 Corristo 所建议的，结果依赖于编译器——这非常有道理。 Clang 3.9 展开了除范围 for 循环之外的所有内容，尽管程度不同。

铿锵声 3.9

`std::none_of' 展开 8 次 -> ~30µs
手动 for 展开 5 次 -> ~35µs
范围 for 根本没有展开 -> ~60µs
迭代器展开 8 次 -> ~28µs

所有代码都是用-std=c++14 -O3编译的。

为什么 std::none_of 比手动循环快？

Why is std::none_of faster than a hand rolled loop?

c++

stl-algorithm