Оптимизация ветки для известного более общего пути

Пожалуйста, рассмотрите следующий фрагмент кода:

void error_handling();
bool method_impl();

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

Я знаю, что method_impl() вернет true 99.999% (да, три десятичных знака) того времени, но мой компилятор этого не делает. method() является частично критическим с точки зрения потребления времени.

  • Должен ли я переписать method() (и сделать его менее читаемым), чтобы гарантировать, что скачок может произойти только тогда, когда method_impl() возвращает false? Если да, то как?
  • Должен ли я позволить компилятору выполнить эту работу для меня?
  • Должен ли я позволить предсказанию ветки моего процессора выполнять эту работу для меня?

Ответы

Ответ 1

Основное оборудование уже выполняет эту оптимизацию. Он "не сможет" предсказать его в первый раз, но после того, как он ударит по правильной опции en.wikipedia.org/wiki/Branch_predictor.

Вы можете попробовать применить расширение GCC и проверить, работает ли оно быстрее или нет, но я думаю, что вы вряд ли увидите какую-либо разницу с ним и без него. Прогнозирование ветвлений применяется всегда, это не то, что вы включаете

Ответ 2

Вы можете предложить компилятору, что method_impl() вернет true:

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.

Ответ 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

Заключение

Разница между этими оптимизациями слишком мала, чтобы прийти к какому-либо заключению, кроме: если при оптимизации ветки для известного более распространенного пути можно найти выигрыш в производительности, этот выигрыш слишком мал, чтобы окупить проблему и потерю читабельности.,

Ответ 4

Не зная реализации std:: time(), я бы не сделал много из этого теста. Из ваших собственных результатов кажется, что он доминирует над временем в цикле.

FWIW, я использую, скорее всего,()/маловероятно() самостоятельно при настройке кода. Я не хочу изменять структуру кода, но, читая сборку, я хотел бы видеть, что общий путь является прямой линией распавшихся ветвей. Ключ здесь (для меня) - читаемость сборки. Тот факт, что это то, что будет самым быстрым, является вторичным (самая быстрая возможная ветвь - правильно предсказанная неактивная ветвь).