c++ 模板化无分支int max/min函数

hjzp0vay  于 2023-10-21  发布在  其他
关注(0)|答案(6)|浏览(176)

我试图写一个无分支函数来返回两个整数的MAX或MIN,而不需要求助于if(或?:).使用the usual technique我可以很容易地做到这一点,对于给定的单词大小:

inline int32 imax( int32 a, int32 b )
{
    // signed for arithmetic shift
    int32 mask = a - b;
    // mask < 0 means MSB is 1.
    return a + ( ( b - a ) & ( mask >> 31 ) );
}

现在,假设arguendo,我真的是在这种有序处理器上编写这种应用程序,这是必要的,我的问题是,是否有一种方法可以使用C++模板将其推广到所有大小的int。
当然,>>31步骤只适用于int32,虽然我可以复制int8,int16和int64的函数重载,但似乎我应该使用模板函数。但是我如何得到模板参数的大小(以 * 位为单位)?
还有比这更好的方法吗?我可以强制签名掩码T吗?如果T是无符号的,掩码移位步骤将不起作用(因为它将是逻辑移位而不是算术移位)。

template< typename T > 
inline T imax( T a, T b )
{
    // how can I force this T to be signed?
    T mask = a - b;
    // I hope the compiler turns the math below into an immediate constant!
    mask = mask >> ( (sizeof(T) * 8) - 1 );
    return a + ( ( b - a ) & mask );
}

而且,做了上面的事情,我可以防止它被用于任何东西,但一个整数类型(例如,没有浮点数或类)?

nr9pn0ug

nr9pn0ug1#

**编辑:**这个答案来自C11之前。从那时起,C11和更高版本提供了make_signed<T>和更多作为标准库的一部分

一般来说,看起来不错,但为了100%的可移植性,请将8替换为CHAR_BIT(或numeric_limits<char>::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;

编辑:IIRC,有符号的右移位不一定是**算术。这是很常见的,我用过的每一个编译器都是如此。但我相信,在有符号类型上,右移是否是算术运算,标准留给编译器决定。在我的标准草案副本中,写有以下内容:
E1 >> E2的值是E1右移E2位位置。如果E1为无符号类型,或者E1为有符号类型且为非负值,则结果的值为E1除以2的E2次幂所得商的整数部分。如果E1具有带符号类型和负值,则结果值是实现定义的
但正如我所说,它将在我见过的每一个编译器上工作:-p。

vlurs2pr

vlurs2pr2#

tl;dr

为了实现你的目标,你最好这样写:

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

长版本

我实现了max()的“naive”实现以及您的无分支实现。它们都没有模板化,我使用int 32只是为了保持简单,就我所知,Visual Studio 2017不仅使天真的实现无分支,而且还产生了更少的指令。
下面是相关的Godbolt(请检查实现以确保我做对了)。请注意,我使用/O2优化进行编译。
无可否认,我的assembly-fu并不是那么好,所以虽然NaiveMax()少了5条指令,也没有明显的分支(老实说,内联我不确定发生了什么),但我想运行一个测试用例来明确地显示天真的实现是否更快。
所以我做了一个测试。这是我运行的代码。Visual Studio 2017(15.8.7)带有“default”Release编译器选项。

#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.它适用于unsigned类型。
1.它甚至适用于浮动类型。
1.它准确地表达了您的意图,而不需要注解您的代码来描述位旋转正在做什么。
1.这是一个众所周知的可识别模式,因此大多数编译器都知道如何优化它,使其更具可移植性。(这是我的直觉,只有编译器的个人经验才能让我感到惊讶。我愿意承认我错了。)

qkf9rpyu

qkf9rpyu3#

这里有另一种无分支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;
}
iklwldmw

iklwldmw4#

您可能需要查看Boost.TypeTraits库。为了检测一个类型是否有签名,你可以使用is_signed trait。您还可以查看enable_if/disable_if以删除某些类型的重载。

e3bfsja2

e3bfsja25#

我不知道这个位掩码技巧工作的确切条件是什么,但你可以做一些事情,比如

#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]signedstd::is_fundamental等。https://en.cppreference.com/w/cpp/types

egdjgwm8

egdjgwm86#

除了tloch 14的回答“tl; dr”,也可以在数组中使用索引。这避免了“无分支最小/最大”的笨拙的位混洗;它也可以推广到所有类型。

template<typename T> constexpr T OtherFastMax(const T &a, const T &b)
{
    const T (&p)[2] = {a, b};
    return p[a>b];
}

相关问题