为已知的更常见路径优化分支

Question

请考虑以下代码：

void error_handling();
bool method_impl();

bool method()
{
    const bool res = method_impl();
    if (res == false) {
        error_handling();
        return false;
    }
    return true;
}

我知道 method_impl() 会 return true 99.999%（是的，小数点后三位），但我的编译器不会。 method() 在时间消耗方面是部分关键。

我是否应该重写 method()（并降低其可读性）以确保仅在 method_impl() returns false 时才可能发生跳转？如果是，如何？
我应该让编译器为我完成工作吗？
我应该让 CPU 的分支预测为我完成这项工作吗？

Answer 1

您可以建议编译器 method_impl() 将 return 为真：

void error_handling();
bool method_impl();

bool method()
{
    const bool res = method_impl();
    if (__builtin_expect (res, 0) == false) {
        error_handling();
        return false;
    }
    return true;
}

这将适用于 GCC。

Answer 2

底层硬件已经执行了此优化。它会 "fail" 第一次预测它，但在它会命中正确的选项后 en.wikipedia.org/wiki/Branch_predictor.

您可以尝试应用 GCC 扩展并检查使用它是否更快，但我认为您几乎看不出使用它和不使用它有什么区别。总是应用分支预测，它不是你启用的

Answer 3

根据其他答案的建议，我对解决方案进行了基准测试。如果您考虑对这个答案投赞成票，请也对其他答案投赞成票。

基准代码

#include <iostream>
#include <iomanip>
#include <string>

// solutions
#include <ctime>

// benchmak
#include <limits>
#include <random>
#include <chrono>
#include <algorithm>
#include <functional>

//
// Solutions
//
namespace
{
    volatile std::time_t near_futur = -1;
    void error_handling() { std::cerr << "error\n"; }
    bool method_impl() { return std::time(NULL) != near_futur; }

    bool method_no_builtin()
    {
        const bool res = method_impl();
        if (res == false) {
            error_handling();
            return false;
        }
        return true;
    }

    bool method_builtin()
    {
        const bool res = method_impl();
        if (__builtin_expect(res, 1) == false) {
            error_handling();
            return false;
        }
        return true;
    }

    bool method_builtin_incorrect()
    {
        const bool res = method_impl();
        if (__builtin_expect(res, 0) == false) {
            error_handling();
            return false;
        }
        return true;
    }

    bool method_rewritten()
    {
        const bool res = method_impl();
        if (res == true) {
            return true;
        } else {
            error_handling();
            return false;
        }
    }
}

//
// benchmark
//
constexpr std::size_t BENCHSIZE = 10'000'000;
class Clock
{
    std::chrono::time_point<std::chrono::steady_clock> _start;

public:
    static inline std::chrono::time_point<std::chrono::steady_clock> now() { return std::chrono::steady_clock::now(); }

    Clock() : _start(now())
    {
    }

    template<class DurationUnit>
    std::size_t end()
    {
        return std::chrono::duration_cast<DurationUnit>(now() - _start).count();
    }
};

//
// Entry point
//
int main()
{
    {
        Clock clock;
        bool result = true;
        for (std::size_t i = 0 ; i < BENCHSIZE ; ++i)
        {
            result &= method_no_builtin();
            result &= method_no_builtin();
            result &= method_no_builtin();
            result &= method_no_builtin();
            result &= method_no_builtin();
            result &= method_no_builtin();
            result &= method_no_builtin();
            result &= method_no_builtin();
            result &= method_no_builtin();
            result &= method_no_builtin();
        }
        const double unit_time = clock.end<std::chrono::nanoseconds>() / static_cast<double>(BENCHSIZE);
        std::cout << std::setw(40) << "method_no_builtin(): " << std::setprecision(3) << unit_time << " ns\n";
    }
    {
        Clock clock;
        bool result = true;
        for (std::size_t i = 0 ; i < BENCHSIZE ; ++i)
        {
            result &= method_builtin();
            result &= method_builtin();
            result &= method_builtin();
            result &= method_builtin();
            result &= method_builtin();
            result &= method_builtin();
            result &= method_builtin();
            result &= method_builtin();
            result &= method_builtin();
            result &= method_builtin();
        }
        const double unit_time = clock.end<std::chrono::nanoseconds>() / static_cast<double>(BENCHSIZE);
        std::cout << std::setw(40) << "method_builtin(): " << std::setprecision(3) << unit_time << " ns\n";
    }
    {
        Clock clock;
        bool result = true;
        for (std::size_t i = 0 ; i < BENCHSIZE ; ++i)
        {
            result &= method_builtin_incorrect();
            result &= method_builtin_incorrect();
            result &= method_builtin_incorrect();
            result &= method_builtin_incorrect();
            result &= method_builtin_incorrect();
            result &= method_builtin_incorrect();
            result &= method_builtin_incorrect();
            result &= method_builtin_incorrect();
            result &= method_builtin_incorrect();
            result &= method_builtin_incorrect();
        }
        const double unit_time = clock.end<std::chrono::nanoseconds>() / static_cast<double>(BENCHSIZE);
        std::cout << std::setw(40) << "method_builtin_incorrect(): " << std::setprecision(3) << unit_time << " ns\n";
    }
    {
        Clock clock;
        bool result = true;
        for (std::size_t i = 0 ; i < BENCHSIZE ; ++i)
        {
            result &= method_rewritten();
            result &= method_rewritten();
            result &= method_rewritten();
            result &= method_rewritten();
            result &= method_rewritten();
            result &= method_rewritten();
            result &= method_rewritten();
            result &= method_rewritten();
            result &= method_rewritten();
            result &= method_rewritten();
        }
        const double unit_time = clock.end<std::chrono::nanoseconds>() / static_cast<double>(BENCHSIZE);
        std::cout << std::setw(40) << "method_rewritten(): " << std::setprecision(3) << unit_time << " ns\n";
    }
}

基准测试结果

`g++ -std=c++14 -O2 -Wall -Wextra -Werror main.cpp`

               method_no_builtin(): 42.8 ns
                  method_builtin(): 44.4 ns
        method_builtin_incorrect(): 51.4 ns
                method_rewritten(): 39.3 ns

Demo

`g++ -std=c++14 -O3 -Wall -Wextra -Werror main.cpp`

               method_no_builtin(): 32.3 ns
                  method_builtin(): 31.1 ns
        method_builtin_incorrect(): 35.6 ns
                method_rewritten(): 30.5 ns

Demo

结论

这些优化之间的差异太小，无法得出任何结论，除了：如果在为已知的更常见路径优化分支时可以找到性能增益，那么这个增益太小而不值得麻烦以及可读性的损失。

Answer 4

在不知道 std::time() 的实现的情况下，我不会得出太多结论从这个测试。从你自己的结果来看，它似乎支配了循环中的时间。

FWIW，我自己在调优代码时很自由地使用 likely()/unlikely()。我不想改变代码的结构，但在阅读程序集时，我希望看到公共路径是一条由未采用的分支组成的直线。这里的关键（对我而言）是程序集的可读性。这也是最快的事实是次要的（最快的可能分支是正确预测的未采用分支）。

为已知的更常见路径优化分支

Optimizing a branch for a known more-common path

c

c++

optimization

compiler-optimization

基准代码

基准测试结果

`g++ -std=c++14 -O2 -Wall -Wextra -Werror main.cpp`

`g++ -std=c++14 -O3 -Wall -Wextra -Werror main.cpp`

结论