c++ - 优化:为什么 < 比 multiple 更昂贵!=

Question

我有一个二维字符数组，我需要对其进行一些操作。在某些情况下，我需要检查字符是否为 a-h。我曾经通过检查字符是否不等于任何其他字符(只有 5 个其他字符)来完成此操作。然而，我最近有了一个想法，我可以改为检查字符是否 < 'j' 以获得相同的结果，希望汇编指令更少。

在我放置的某些地方，它确实导致了小幅加速，但在其他地方却导致了相当大的减速。任何想法为什么会这样？ != 相对于 if 语句中的 < 的相对开销是多少？

这是一个示例代码片段:

if( arr[r][c] == arr[r][c+1] && arr[r][c] == arr[r][c+2]
         && arr[r][c] != 'q' && arr[r][c] != 'r' && arr[r][c] != 's' && arr[r][c] != 't')

对比

if( arr[r][c] == arr[r][c+1] && arr[r][c] == arr[r][c+2]
         && arr[r][c] < 'j')

Answer 1

如果我没有正确理解你的问题，你似乎希望检查一个数组列的所有元素是否都在字符 'a' 和 'h' 之间并且相同，并且你想优化这个过程。

如果您碰巧知道一些汇编语言，我强烈建议您使用反汇编程序来找出函数在执行期间究竟发生了什么。所有编译器和优化级别都略有不同。但是，用于比较内存中两个值的最少操作包括:

.将内存中的两个变量加载到处理器寄存器(几个时钟周期)

.对两个寄存器中的值进行相等测试(1个时钟周期)

.根据标志寄存器执行跳转命令(intel 处理器)(另一个时钟周期)

现在这对于处理器来说是最简单的操作，但是由于您有堆叠的比较操作，这些检查所需的时间会累积(特别是内存访问所需的时钟周期)。

因此，要减少这些比较所需的时间，就需要减少比较的次数。请记住，字符“a”到“h”的 ascii 值介于 0x61 和 0x68(十进制 97 到 104)之间。您可以通过大约三个比较操作来确定字符是否在“a”到“h”之间:

if(arr[r][c] >= 97 && arr[r][c] <= 104)

只检查该列的一个值并使用这个小技巧来确定该列中的所有元素是否都相同:

if(((arr[r][c] ^ arr[r][c+1]) + (arr[r][c] ^ arr[r][c+2]) + ...*etc*) == 0)

“xor”('^') 比较需要一个时钟周期，加法也是如此，如果任意两个列实体之间存在任何差异，则该操作将产生非零结果。这种方法应该随着列元素的数量增加线性时间，作为额外的好处，优化编译器可能能够在操作期间将“arr[r][c]”保留在其中一个寄存器中。