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

Question

我正在尝试编写一个无分支函数来返回两个整数的MAX或MIN而不求助于if(或？:).使用通常的技术,我可以很容易地为给定的字大小做到这一点:

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步仅适用于int32s,当然,虽然我可以对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 );
}

并且,完成上述操作后,我可以阻止它被用于除整数类型之外的任何东西(例如,没有浮点数或类)吗？

Answer 1

通常,看起来不错,但是为了100%可移植性,用CHAR_BIT(或numeric_limits :: max())替换8,因为不能保证字符是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的商除以提升到功率E2的数量2的积分.如果E1具有带符号类型和负值,则结果值是实现定义的.

但正如我所说,它将适用于我见过的每个编译器:-p.

Answer 2

太长了；博士

为了实现你的目标，你最好这样写：

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

长版

我实现了“天真的”实现max()以及您的无分支实现。它们都没有模板化，我使用 int32 只是为了让事情变得简单，据我所知，Visual Studio 2017 不仅使简单的实现成为无分支的，而且还产生了更少的指令。

这是相关的Godbolt（请检查实施以确保我做得正确）。请注意，我正在使用 /O2 优化进行编译。

诚然，我的汇编符并不是那么好，所以虽然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. 这是一种众所周知且可识别的模式，因此大多数编译器都会确切地知道如何优化它，使其更加可移植。（这是我的直觉，仅得到令我惊讶的编译器个人经验的支持。我愿意承认我在这里错了。）