0

I have a 2d array of chars that I need to do some operations on. In some cases, I need to check if character is a-h. I used to accomplish this by checking if the character was not equal to any of the other characters (there are only 5 other characters). However, I recently had the idea that I could instead check if the character was < 'j' to get the same result with hopefully fewer assembly instructions.

In some places I put it, it did result in a small speed-up, but in others it resulted in a rather large slowdown. Any ideas why this is? What is the relative expense of != as opposed to < in if statements?

Here is an example code snippet:

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')
4

3 回答 3

5

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

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

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

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

. 根据标志寄存器执行跳转命令（英特尔处理器）（另一个时钟周期）

现在这几乎是处理器所能获得的最简单的操作，但是由于您有堆叠比较操作，这些检查所需的时间会累积（尤其是内存访问所需的时钟周期。

因此，为了减少这些比较所需的时间，需要减少比较的次数。请记住，字符 '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]”保留在一个寄存器中。

于 2013-08-01T03:40:45.600 回答
1

现代编译器/CPU 使用分支预测来预取候选结果，这些结果有利于某些执行路径而不是其他执行路径。你的编译预测了不同的结果，因此也有不同的结果。结果可能取决于二维数组的内容。此外，在不同的编译器/CPU 上，优势可能会有所不同。搜索分支预测 - 那里有一些很好的答案。

于 2013-08-01T03:44:59.667 回答
1

不要过分关注速度。首先编写一个解决实际的、有意义的任务的程序。完成后，使用分析器确定该程序的哪些部分是最重要的瓶颈。在编写程序来解决实际的、有意义的任务之前，您应该专注于编写可移植的、定义明确的代码，而不是快速的代码。

您的速度概念不在 C 标准中。事实上，这里没有关于速度的保证。有快速编译器和慢速编译器，甚至有快速和慢速 C 解释器。因此，您关于速度的问题是无效的。如果您的 C 编译器在这种情况下不能生成大致相同的代码（在速度方面），那么要么学习如何启用完全优化，要么获得一个新的 C 编译器。

这看起来不便携：

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

在使用 EBCDIC 的系统上'j' - 'i'，您假设为 1 的系统实际上是145 - 137（12）。您的测试包括 11 个额外的非字母字符。我建议strchr("abcdefghi", a[r][c])在您担心性能之前使用。如果您担心它的速度（您不应该担心，因为它是解决实际问题的任何小任务），您可以尝试使用开关将其转换为跳转表：

if (arr[r][c] == arr[r][c+1] && arr[r][c] == arr[r][c+2]) {
    switch (a[r][c]) {
        case 'a': case 'b': case 'c':
        case 'd': case 'e': case 'f':
        case 'g': case 'h': case 'i':
        /* XXX: Insert code that runs when a[r][c] is in "abcdefghi"... */
        break;
    }
}

要衡量这种优化，您可以使用第一段中建议的分析器。

于 2013-08-01T04:10:28.340 回答