我为一个结构写了一个(qsort兼容的)比较函数,里面有一些无符号字段:
typedef struct {
int a;
unsigned b;
} T;
int cmp(T t1, T t2)
{
// Decreasing order in "a"
if (t1.a < t2.a) return +1;
if (t1.a > t2.a) return -1;
// Increasing order in "b"
if (t1.b < t2.b) return -1;
if (t1.b > t2.b) return +1;
return 0;
}
有没有办法编写这个函数,而不需要每个字段进行两次比较？我不能使用这个t1.b - t2.b技巧,因为无符号整数的减法包装.
我愿意接受使用GCC扩展的答案.
当您可能忽略这个答案时：如果编译器将为 Keit 的答案甚至原始 OP 的代码生成无分支代码（Keit 的代码被视为condition ? ~0 : 0，OP 的代码将生成CMOV），则所有有关分支的推理都是无用的。
当然，您可以针对没有SETcc指令的 CPU CMOVcc。在这种情况下，是的，我会避免使用减法进行分支（如果可能）（进行小型性能测试以确定long long和之间哪个更快double）。如果您的其他先决条件和范围限制不是问题，您甚至可以使用简单的整数数学。
CMOVcc和/或SETcc（或等效）指令。
您不需要精确返回+1和-1，任何正值或负值都可以很好地工作（假设您想优化此函数以减少跳跃，数学运算相对便宜）。如果我们可以对平台特定的有符号整数实现（2 的补码）和无符号/有符号转换做出假设，那么删除分支（引入廉价减法）的第一步是：
int cmp(T t1, T t2) {
if (t2.a != t1.a)
return t2.a - t1.a;
if (t1.b < t2.b)
return -1;
return (int)(t1.b - t2.b);
}
unsigned要删除第二个分支，我们可以依赖（而不是signed）整数数学的明确定义行为：t1.b - t2.b将换行（当t1.b小于时t2.b）然后(int)(t1.b - t2.b)将是负数，并且if可以省略第二个分支。有了这个假设，代码可以是：
int cmp(T t1, T t2) {
if (t2.a != t1.a)
return t2.a - t1.a;
return (int)(t1.b - t2.b);
}
注意 1：第二次优化仅适用于您的情况，因为您按降序排序，T.b那么这不是一般规则。
注 2：这里您正在使用复制的结构。编译器可能会优化您的代码以删除T副本，但不需要这样做，那么 IMO 您应该检查生成的代码或使用T*指针cmp如果可能）。广泛的副本将使我们在这里可能做的任何其他微观优化消失。
我认为需要一些解释，如果我们试图减少（避免据我所知是不可能的）分支，那么我们必须考虑可见和不可见的分支（否则没有理由启动这种可能的微优化）。
分支
每个条件（如t2->b > t1->b）都是用分支编译的。让我从 Keith 的回答中挑选一些不错的代码：
((t2.a > t1.a) - (t2.a < t1.a))
||
((t2.b > t1.b) - (t2.b < t1.b))
编译器t2.a > t1.a会产生这样的结果：
008413FE mov eax,dword ptr [t2] ; Load t2.a in EAX
00841401 cmp eax,dword ptr [t1] ; Compare EAX with t1.a
00841404 jle cmp+32h (0841412h) ; Go to set result to not true
00841406 mov dword ptr [ebp-0C4h],1 ; Result for t2.a > t1.a is 1 (true)
00841410 jmp cmp+3Ch (084141Ch) ; Go to perform t2.a < t1.a
00841412 mov dword ptr [ebp-0C4h],0 ; Result for t2.a > t1.a is 0 (false)
为第二部分生成了类似的代码t2.a < t1.a。||然后对( )的右侧重复相同的代码(t2.b > t1.b) - (t2.b < t1.b)。让我们计算一下分支：最快的代码路径对于每个子表达式有五个分支（ jle，jmp在第一部分中，jge，在第二部分中），加上一个用于短路的额外跳转（总共六个分支）。最慢的一个甚至还少。它比带有许多s 的原始实现更糟糕。jmp||if
为了进行比较，让我们看看与减法相比生成了什么：
; if (t2.a != t1.a)
00F313FE mov eax,dword ptr [t2] ; Load t2.a
00F31401 cmp eax,dword ptr [t1] ; Compare with t1.a
00F31404 je cmp+2Eh (0F3140Eh) ; If they are equal then go work with T.b
; return t2.a - t1.a;
00F31406 mov eax,dword ptr [t2] ; Load t2.a
00F31409 sub eax,dword ptr [t1] ; Subtract t1.a
00F3140C jmp cmp+34h (0F31414h) ; Finished
这是我们最好的代码路径，只有两个分支。我们看第二部分：
; return (int)(t1.b - t2.b);
00F3140E mov eax,dword ptr [ebp+0Ch] ; Load t1.b
00F31411 sub eax,dword ptr [ebp+14h] ; Subtract t2.b
这里没有更多的分支机构。我们最快和最慢的代码路径总是具有相同数量的分支。
减法
为什么减法有效？让我们看看Suma 在评论中挑选的简单值和一些边缘情况。比方说：
t1.a = 1;
t2.a = 10;
t1.b = 10;
t2.b = 1;
然后我们有：
t2.a - t1.a == 10 - 1 == 9。原始代码中要求的正数 ( if (t1.a < t2.a) return +1;)。相反的情况是微不足道的。这里我们假设有符号整数数学将换行。
(int)(t1.b - t2.b) == 10 - 1 == 9。T.a根据需要为正数（和 的逆序T.b）。由于边缘情况，这需要更多解释。想象一下t1.b是UINT_MAX并且t2.b是0。t1.b - t2.b仍然是UINT_MAX，并且必须转换为int，它的位模式是，恰好是a 的0xFFFFFFFF位模式。结果又正确了。请注意，这里我们假设两件重要的事情：有符号数以 2 的补码表示，无符号到有符号的转换只是用新的给定类型重新解释原始内存值（不进行显式计算）。-1signed int
正如 Suma 所指出的，当数字很大时就会出现问题，如果你想要完整int和unsigned int范围，那么你可以简单地将它们转换为double：
int cmp(T t1, T t2) {
if (t2.a != t1.a)
return (int)((double)t2.a - t1.a);
return (int)((double)t1.b - t2.b);
}
生成的汇编代码摘录：
; return (double)t2.a - (double)t1.a;
01361926 cvtsi2sd xmm0,dword ptr [t2] ; Load t2.a
0136192B cvtsi2sd xmm1,dword ptr [t1] ; Load t1.a
01361930 subsd xmm0,xmm1 ; Subtract t1.a to t2.a
01361934 cvttsd2si eax,xmm0 ; Convert back
01361938 jmp cmp+88h (01361988h)
通过这种方式，唯一不能使用的元组是INT_MINfort1.a和INT_MAXfor t2.a。