优化:为什么<比多个更贵!=

Question

我有一个2d的字符数组,我需要做一些操作.在某些情况下,我需要检查字符是否是啊.我过去通过检查字符是否与其他任何字符(仅有5个其他字符)相同来完成此操作.但是,我最近有一个想法,我可以检查字符是否是<'j'以获得相同的结果,希望更少的汇编指令.

在我说的一些地方,它确实导致了一个小的加速,但在其他地方,它导致了相当大的减速.任何想法为什么会这样？与= in 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')

VS

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

Answer 1

如果我正确理解了您的问题,您似乎希望检查数组列的所有元素是否在字符'a'和'h'之间并且是相同的,并且您希望优化此过程.

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

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

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

.基于标志寄存器(英特尔处理器)执行跳转命令(另一个时钟周期)

现在这对于处理器来说就像操作一样简单,但由于你有堆叠比较操作,所以这些检查所需的时间会累积(特别是内存访问所需的时钟周期).

因此,为了减少这些比较所需的时间,需要减少比较次数.请记住,字符'a'到'h'的ascii值介于0x61和0x68之间(十进制97到104).您可以通过以下方式确定角色是否在大约三个比较操作中的'a'到'h'之间:

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

只检查列的一个值,并使用这个bit-twiddling技巧来确定列中的所有元素是否相同:

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

"xor"('^')比较采用单个时钟周期,添加也是如此,如果任意两个列实体之间存在任何差异,则操作将导致非零结果.此方法应随着列元素的数量增加线性时间,并且作为额外的好处,优化编译器可能能够在操作期间将'arr [r] [c]'保留在其中一个寄存器中.