'更正'无符号整数比较

Question

所以,我们都知道C/C++有符号/无符号比较规则-1 > 2u == true,我有一种情况,我希望有效地实现'正确'的比较.

我的问题是,考虑到人们熟悉的众多架构,这样做更有效率.显然英特尔和ARM的权重更高.

鉴于:

int x;
unsigned int y;
if (x < y) {}

推广是否更好:

x < y  =>  (int64)x < (int64)y

或者更好地进行2次比较,即:

x < y  =>  (x < 0 || x < y)

前者意味着零扩展,符号扩展和一个比较+分支,后者不需要符号扩展操作,而是需要2个连续的cmp +分支.
传统智慧认为分支比符号扩展更昂贵,这将是管道,但在第一种情况下扩展和单一比较之间存在停滞,而在第二种情况下,我可以想象一些架构可能会对这两种比较进行管道传输. ,然后是2个条件分支？

存在另一种情况,其中无符号值是比带符号类型更小的类型,这意味着可以使用单个零扩展到有符号类型的长度,然后进行单个比较...在这种情况下,它更可取使用extend + cmp版本,还是2比较方法仍然是首选？

英特尔？臂？其他？我不确定这里是否有正确的答案,但我希望听到人们的回答.如今,低水平的性能很难预测,特别是在英特尔和ARM上越来越多.

编辑:

我应该补充一点,有一个明显的解决方案,其中类型的大小等于体系结构的宽度; 在这种情况下,显然2比较解决方案是优选的,因为促销本身不能有效地执行.显然,我的int示例满足32位体系结构的这种条件,您可以将思想实验转换short为适用于32位平台的练习.

编辑2:

对不起,我忘了u在-1 > 2u!> _ <

编辑3:

我想修改这种情况,假设比较的结果是一个实际的分支,结果不是作为布尔值返回的.这就是我喜欢的结构外观; 虽然这确实提出了一个有趣的观点,即当结果是bool与分支时,存在另一组排列.

int g;
void fun(int x, unsigned in y) { if((long long)x < (long long)y) g = 10; }
void gun(int x, unsigned in y) { if(x < 0 || x < y) g = 10; }

当您遇到if;)时,这会产生通常隐含的预期分支;)

Answer 1

好吧,你已经正确地描述了这种情况:C/C++无法与单个比较进行完全签名的int/unsigned int比较.

如果升级到int64比做两次比较要快,我会感到惊讶.根据我的经验,编译器非常善于意识到像这样的子表达式是纯粹的(没有副作用),因此不需要第二个分支.(您也可以使用按位或者明确地选择退出短路(x < 0) | (x < y).)相比之下,我的经验是编译器不会对大于本机字大小的整数进行太多特殊情况优化,因此(int64)x < (int64)y实际上很可能做一个完整的int比较.

最重要的是,没有任何咒语可以保证在任何处理器上产生最好的机器代码,但是对于最常见的处理器上最常见的编译器,我猜两种比较形式并不比促销更快. -int64表格.

编辑:关于Godbolt的一些问题证实,在ARM32上,GCC为int64方法提供了太多机制.VC在x86上也是如此.但是,对于x64,int64方法实际上是一条指令更短(因为促销和64位比较是微不足道的).然而,流水线操作可能会使实际表现成为两种方式.https://godbolt.org/g/wyG4yC

Answer 2

你必须根据具体情况来判断.签名类型将在程序中使用的原因有以下几种:

1. 因为实际上你需要在计算或输出中有负数.
2. "邋typing的打字",这意味着程序员只需int在他们的程序中输入所有内容而不需要太多考虑.
3. 意外签名.程序设计实际上并不想要有符号数字,但最终却是通过隐式类型促销或使用整数常量(例如0类型)来实现它们int.

在1)的情况下,算术应该用带符号的算术进行.然后,您应该转换为包含最大期望值所需的最小可能类型.

假定例如,一个值可以从具有范围-10000到10000.然后,您需要使用16位带符号类型来表示它.然后,平台独立使用的正确类型是int_fast16_t.

的int_fastn_t和uint_fastn_t类型需要的类型是至少一样大Ñ但是编译器被允许选择一个较大的类型,如果它提供了更快的代码/更好的对准.

2)通过学习stdint.h和停止懒惰来治愈.作为程序员,总是需要考虑程序中声明的每个变量的大小和签名.这必须在声明时完成.或者,如果您稍后获得某种启示,请返回并更改类型.

如果你不仔细考虑这些类型,你将绝对肯定地写出许多,通常是微妙的错误.这在C++中尤其重要,C++比C更挑剔类型的正确性.

当使用"草率类型"时,实际的预期类型通常是无符号的而不是签名的.考虑这个草率的打字示例:

for(int i=0; i<n; i++)

在这里使用signed int完全没有意义,所以你为什么这么做？您很可能正在遍历数组或容器,然后使用正确的类型size_t.

或者,如果您知道n可以容纳的最大大小,例如100,那么您可以使用最合适的类型:

for(uint_fast8_t i=0; i<100; i++)

3)也通过研究治愈.值得注意的是,这些语言中存在隐式促销的各种规则,例如通常的算术转换和整数提升.

Answer 3

鉴于您提供的具体设置:

int x;
unsigned int y;

你明显的意图是评估价值是否在x数值上小于y,尊重的标志x,我倾向于把它写成

if ((x < 0) || (x < y)) {}

也就是你的第二种选择.它清楚地表达了意图,并且它可以扩展到更宽的类型,只要y's类型的最大可表示值至少与's类型的最大可表示值一样大x.因此,如果你愿意规定论证将具有那种形式,那么你甚至可以把它写成 - 避免你的眼睛,C++的追随者 - 一个宏.

将两个参数转换为带符号的64位整数类型不是一种可移植的解决方案,因为无法保证这实际上是来自其中一个或的促销.对于更广泛的类型,它也是不可扩展的.intunsigned int

至于你的两个选择的相对表现,我怀疑有很大的不同,但如果它对你很重要,那么你会想要写一个仔细的基准.我可以想象便携式替代方案需要比另一方更多的机器指令,我也可以想象它需要少一个.只有当这样的比较主导了您的应用程序的性能时,单个指令才会以某种方式产生明显的差异.

当然,这是针对您提出的情况而定的.如果你想按照任何顺序处理混合的有符号/无符号比较,对于许多不同的类型,在编译时整理出来,那么基于模板的包装器可以帮助你解决这个问题(这样就不会有使用宏的问题了),但我带你去具体询问比较本身的细节.

Answer 4

两个分支版本肯定会更慢,但实际上这两个分支都没有......也不是x86上的单分支.

例如x86 gcc 7.1将用于C++源代码:

bool compare(int x, unsigned int y) {
    return (x < y); // "wrong" (will emit warning)
}

bool compare2(int x, unsigned int y) {
    return (x < 0 || static_cast<unsigned int>(x) < y);
}

bool compare3(int x, unsigned int y) {
    return static_cast<long long>(x) < static_cast<long long>(y);
}

制作这个组件(godbolt现场演示):

compare(int, unsigned int):
        cmp     edi, esi
        setb    al
        ret

compare2(int, unsigned int):
        mov     edx, edi
        shr     edx, 31
        cmp     edi, esi
        setb    al
        or      eax, edx
        ret

compare3(int, unsigned int):
        movsx   rdi, edi
        mov     esi, esi
        cmp     rdi, rsi
        setl    al
        ret

如果你试图在更复杂的代码中使用它们,它们将在99%的情况下被内联.没有描述它只是猜测,但"通过直觉"我会选择compare3"更快",特别是当在一些代码内部执行时(有趣的是它做了正确的32-> 64促销,即使对于uint论证,而它需要付出相当大的努力才能产生代码调用,与上层32b中的一些混乱进行比较esi......但是当它在更复杂的计算中内联时它可能会摆脱它,它会注意到参数也已经uint64扩展了,所以compare3然后更简单+更短).

......正如我在评论中所说的那样,我没有按照需要这样做的任务,例如我无法想象在有效数据范围未知的地方工作,所以对于我在C /上工作的任务C++非常合适,我完全理解它的工作方式(<对于有符号和无符号类型的定义很明确,导致最短/最快的代码,并且发出警告以使我作为程序员负责验证它,并在需要时适当地改变来源).

Answer 5

您可以做的一个可移植技巧是检查是否可以将两个参数扩大到intmax_tfrom <stdint.h>，这是实现支持的最广泛的整数类型。您可以检查(sizeof(intmax_t) > sizeof(x) && sizeof(intmax_t) >= sizeof(y))，如果是，则进行扩大转换。int这适用于32 位宽和long long int64 位宽的非常常见的情况。

在 C++ 中，您可以通过安全比较模板来检查std::numeric_limits<T>其参数来完成一些聪明的事情。这是一个版本。-Wno-sign-compare（在 gcc 或 clang 上编译！）

#include <cassert>
#include <cstdint>
#include <limits>

using std::intmax_t;
using std::uintmax_t;

template<typename T, typename U>
  inline bool safe_gt( T x, U y ) {
    constexpr auto tinfo = std::numeric_limits<T>();
    constexpr auto uinfo = std::numeric_limits<U>();
    constexpr auto maxinfo = std::numeric_limits<intmax_t>();

    static_assert(tinfo.is_integer, "");
    static_assert(uinfo.is_integer, "");

    if ( tinfo.is_signed == uinfo.is_signed )
      return x > y;
    else if ( maxinfo.max() >= tinfo.max() &&
              maxinfo.max() >= uinfo.max() )
      return static_cast<intmax_t>(x) > static_cast<intmax_t>(y);
    else if (tinfo.is_signed) // x is signed, y unsigned.
      return x > 0 && x > y;
    else // y is signed, x unsigned.
      return y < 0 || x > y;      
  }

int main()
{
  assert(-2 > 1U);
  assert(!safe_gt(-2, 1U));
  assert(safe_gt(1U, -2));
  assert(safe_gt(1UL, -2L));
  assert(safe_gt(1ULL, -2LL));
  assert(safe_gt(1ULL, -2));
}

通过改变两行就可以知道浮点数。