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

Question

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

我使用了谷歌基准测试库并编译了-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循环快.这是测试代码(仅包括用于简洁的循环手册):

#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-th元素设置为i并检查值N + 1是否包含,我得到相同的结果.

Answer 1

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

\n\n

海湾合作委员会 6.2：

\n\n

\n
• std::none_of展开 4 次 -> ~30\xc2\xb5s
\n
• 手动for、量程for和迭代器根本没有展开 -> ~45\xc2\xb5s
\n

\n\n

正如 Corristo 所建议的，结果取决于编译器 - 这是完全有道理的。Clang 3.9 展开除范围之外的所有内容for循环之外的所有内容，尽管程度不同。

\n\n

铿锵3.9

\n\n

\n
• `std::none_of' 展开 8 次 -> ~30\xc2\xb5s
\n
• 手动的for展开 5 次 -> ~35\xc2\xb5s
\n
• 范围for根本没有展开 -> ~60\xc2\xb5s
\n
• 迭代器展开 8 次 -> ~28\xc2\xb5s
\n

\n\n

所有代码均使用-std=c++14 -O3.

\n