Функция Templatized branchless int max/min

Ответ 1

Как правило, хорошо выглядит, но для 100% -ной переносимости замените это 8 на CHAR_BIT (или numeric_limits:: max()), так как не гарантируется, что символы являются 8-битными.

Любой хороший компилятор будет достаточно умным, чтобы объединить все математические константы во время компиляции.

Вы можете заставить его подписаться, используя библиотеку признаков типов. который обычно выглядит примерно так (предполагая, что ваша библиотека numeric_traits называется numeric_traits):

typename numeric_traits<T>::signed_type x;

Пример рулонного числа numeric_traits заголовка может выглядеть следующим образом: http://rafb.net/p/Re7kq478.html (есть много возможностей для добавления, но вы получаете идея).

или еще лучше, используйте boost:

typename boost::make_signed<T>::type x;

EDIT: IIRC, подписанные сдвиги вправо не должны быть арифметическими. Это обычное дело, и, конечно, дело в каждом компиляторе, который я использовал. Но я считаю, что стандарт оставляет его компилятором независимо от того, являются ли правильные сдвиги арифметическими или нет на подписанном типе. В моей копии проекта стандарта написано:

Значение E1 → E2 равно E1 правые позиции бит E2. Если E1 имеет неподписанный тип, или если E1 имеет подписанный тип и неотрицательное значение, значение результата интегральная часть частного E1 делится на величину 2, поднятую до мощность E2. Если E1 имеет подписанный тип и отрицательное значение, в результате значение определяется реализацией.

Но, как я уже сказал, он будет работать на каждом компиляторе, который я видел: -p.

Ответ 2

Вот еще один подход для нестационарных max и min. Что приятно в том, что он не использует никаких трюков, и вам не нужно ничего знать о типе.

template <typename T> 
inline T imax (T a, T b)
{
    return (a > b) * a + (a <= b) * b;
}

template <typename T> 
inline T imin (T a, T b)
{
    return (a > b) * b + (a <= b) * a;
}

Ответ 3

Вы можете посмотреть в библиотеке Boost.TypeTraits. Для определения того, подписан ли тип, вы можете использовать is_signed. Вы также можете посмотреть enable_if/disable_if для удаления перегрузок для определенных типов.

Ответ 4

ТЛ; др

Для достижения ваших целей вам лучше всего написать это:

template<typename T> T max(T a, T b) { return (a > b) ? a : b; }

Длинная версия

Я реализовал как "наивную" реализацию max() так и вашу реализацию без ответвлений. Оба они не были шаблонными, и вместо этого я использовал int32 просто для простоты, и, насколько я могу судить, Visual Studio 2017 не только делала простую реализацию без ветвлений, но и вырабатывала меньше инструкций.

Вот соответствующий Godbolt (и, пожалуйста, проверьте реализацию, чтобы убедиться, что я все сделал правильно). Обратите внимание, что я компилирую с оптимизацией /O2.

Надо признать, что мой ассемблер-фу не так NaiveMax() велик, поэтому, хотя в NaiveMax() было на 5 инструкций меньше и никаких явных ветвлений (и, честно говоря, я не уверен, что происходит), я хотел запустить тестовый пример, чтобы окончательно показать, является ли Наивная реализация была быстрее или нет.

Итак, я построил тест. Вот код, который я запустил. Visual Studio 2017 (15.8.7) с опциями компилятора выпуска по умолчанию.

#include <iostream>
#include <chrono>

using int32 = long;
using uint32 = unsigned long;

constexpr int32 NaiveMax(int32 a, int32 b)
{
    return (a > b) ? a : b;
}

constexpr int32 FastMax(int32 a, int32 b)
{
    int32 mask = a - b;
    mask = mask >> ((sizeof(int32) * 8) - 1);
    return a + ((b - a) & mask);
}

int main()
{
    int32 resInts[1000] = {};

    int32 lotsOfInts[1'000];
    for (uint32 i = 0; i < 1000; i++)
    {
        lotsOfInts[i] = rand();
    }

    auto naiveTime = [&]() -> auto
    {
        auto start = std::chrono::high_resolution_clock::now();

        for (uint32 i = 1; i < 1'000'000; i++)
        {
            const auto index = i % 1000;
            const auto lastIndex = (i - 1) % 1000;
            resInts[lastIndex] = NaiveMax(lotsOfInts[lastIndex], lotsOfInts[index]);
        }

        auto finish = std::chrono::high_resolution_clock::now();
        return std::chrono::duration_cast<std::chrono::nanoseconds>(finish - start).count();
    }();

    auto fastTime = [&]() -> auto
    {
        auto start = std::chrono::high_resolution_clock::now();

        for (uint32 i = 1; i < 1'000'000; i++)
        {
            const auto index = i % 1000;
            const auto lastIndex = (i - 1) % 1000;
            resInts[lastIndex] = FastMax(lotsOfInts[lastIndex], lotsOfInts[index]);
        }

        auto finish = std::chrono::high_resolution_clock::now();
        return std::chrono::duration_cast<std::chrono::nanoseconds>(finish - start).count();
    }();

    std::cout << "Naive Time: " << naiveTime << std::endl;
    std::cout << "Fast Time:  " << fastTime << std::endl;

    getchar();

    return 0;
}

И вот вывод я получаю на своей машине:

Naive Time: 2330174
Fast Time:  2492246

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

Конечно, в зависимости от вашего компилятора или платформы, эти цифры могут быть разными. Это стоит проверить себя.

Ответ

Вкратце, может показаться, что лучший способ написать шаблонную функцию max() ответвлений - это, вероятно, сделать ее простой:

template<typename T> T max(T a, T b) { return (a > b) ? a : b; }

Есть дополнительные преимущества у наивного метода:

1. Это работает для неподписанных типов.
2. Это даже работает для плавающих типов.
3. Он выражает именно то, что вы намереваетесь, вместо того, чтобы комментировать код, описывающий то, что делает бит-тиддлинг.
4. Это хорошо известный и узнаваемый шаблон, поэтому большинство компиляторов точно знают, как его оптимизировать, чтобы сделать его более переносимым. (Это мое внутреннее предчувствие, только подкрепленное личным опытом составителей, которые меня удивляют. Я буду готов признать, что я здесь не прав.)

Ответ 5

Я не знаю, каковы точные условия для этого трюка с битовой маской, но вы можете сделать что-то вроде

#include<type_traits>

template<typename T, typename = std::enable_if_t<std::is_integral<T>{}> > 
inline T imax( T a, T b )
{
   ...
}

Другими полезными кандидатами являются std::is_[un]signed, std::is_fundamental и т.д. Https://en.cppreference.com/w/cpp/types