查找两个之间的最大值，选择哪个实现

我正试图弄清楚，在找到两者之间的最大值时，哪个实现比其他实现更有优势。作为一个例子，让我们检查两个实现：

实施1:

int findMax (int a, int b)
{
return (a > b) ? a : b; 
}

//组件输出：(gcc 11.1(

push    rbp
mov     rbp, rsp
mov     DWORD PTR [rbp-4], edi
mov     DWORD PTR [rbp-8], esi
mov     eax, DWORD PTR [rbp-4]
cmp     eax, DWORD PTR [rbp-8]
jle     .L2
mov     eax, DWORD PTR [rbp-4]
jmp     .L4 .L2:
mov     eax, DWORD PTR [rbp-8] .L4:
pop     rbp
ret

实现2:

int findMax(int a, int b)
{
int diff, s, max;
diff = a - b;
s = (diff >> 31) & 1;

max = a - (s * diff);

return max;
}

//组件输出：(gcc 11.1(

push    rbp
mov     rbp, rsp
mov     DWORD PTR [rbp-20], edi
mov     DWORD PTR [rbp-24], esi
mov     eax, DWORD PTR [rbp-20]
sub     eax, DWORD PTR [rbp-24]
mov     DWORD PTR [rbp-4], eax
mov     eax, DWORD PTR [rbp-4]
shr     eax, 31
mov     DWORD PTR [rbp-8], eax
mov     eax, DWORD PTR [rbp-8]
imul    eax, DWORD PTR [rbp-4]
mov     edx, eax
mov     eax, DWORD PTR [rbp-20]
sub     eax, edx
mov     DWORD PTR [rbp-12], eax
mov     eax, DWORD PTR [rbp-12]
pop     rbp
ret

第二个生成了更多的汇编指令，但第一个有条件跳转。只是想弄清楚两者是否都一样好。

首先，您需要启用编译器优化(以下内容我使用了-O2(。您应该将其与std::max进行比较。然后这个：

#include <algorithm>
int findMax (int a, int b)
{
return (a > b) ? a : b; 
}
int findMax2(int a, int b)
{
int diff, s, max;
diff = a - b;
s = (diff >> 31) & 1;

max = a - (s * diff);

return max;
}
int findMax3(int a,int b){
return std::max(a,b);
}

结果在：

findMax(int, int):
cmp     edi, esi
mov     eax, esi
cmovge  eax, edi
ret
findMax2(int, int):
mov     ecx, edi
mov     eax, edi
sub     ecx, esi
mov     edx, ecx
shr     edx, 31
imul    edx, ecx
sub     eax, edx
ret
findMax3(int, int):
cmp     edi, esi
mov     eax, esi
cmovge  eax, edi
ret

您的第一个版本产生了与std::max相同的程序集，而您的第二个变体则做得更多。实际上，在尝试优化时，您需要指定优化的目的。有几个选项通常需要权衡：运行时、内存使用率、可执行文件的大小、代码的可读性等。通常情况下，您无法同时获得所有选项。

当有疑问时，不要重新发明轮子，而是使用现有的已经优化的std::max。不要忘记，你编写的代码不是CPU的指令，而是对程序应该做什么的高级抽象描述。编译器的工作是找出如何最好地实现这一点。

最后但同样重要的是，你的第二个变体实际上已经坏了。参见此处使用-O2 -fsanitize=signed-integer-overflow编译的示例，结果为：

/app/example.cpp:13:10: runtime error: signed integer overflow: -2147483648 - 2147483647 cannot be represented in type 'int'

你应该喜欢正确性而不是速度。当最快的代码出错时，它就不值钱了。正因为如此，可读性才是下一个。难以阅读和理解的代码也难以纠正。我只能在编译器的帮助下发现您代码中的问题，而std::max(a,b)不太可能导致未定义的行为(即使是这样，至少这不是您的错；(。

对于两个int，您可以使用您可能在学校学到的技术计算max(a, b)，而无需分支：

a ^ ((a ^ b) & -(a < b));

但没有一个理智的人会在他们的代码中写下这一点。始终使用std::max，并相信编译器会选择最佳方式。您可能会发现，它采用了上述int参数，并适当设置了优化。尽管我认为，总的来说，比较和跳跃可能是最好的方式，即使是以管道转储为代价。

使用std::max为编译器提供了最佳的优化提示。

实施1在CISCCPU上表现良好，类似于现代x64 AMD/Intel CPU
实现2在类似nVIDIA或AMD Graphics的RISCGPU上表现良好
术语"；表现良好"；只有在紧密的循环中才有意义

相关内容

最新更新

热门标签：