C数组中进行位运算的最有效方法是什么？

Question

我有一个类似于C数组的数据结构：

char byte_array[10];

还有一个作为掩模的：

char byte_mask[10];

我想通过按位运算符在每个字节上对第一个数组和第二个数组进行操作，得到另一个数组作为结果。

怎样才能以最高效的方式完成这个任务？

谢谢您的回答。

- Álvaro

Answer 1

for ( i = 10 ; i-- > 0 ; )
    result_array[i] = byte_array[i] & byte_mask[i];

• 反向遍历可以预加载处理器缓存行。
• 在比较中包含减量可以节省一些指令。

这适用于所有数组和处理器。但是，如果您知道您的数组是单词对齐的，则更快的方法是将其转换为较大的类型并进行相同的计算。

例如，假设 n=16 而不是 n=10。那么这将更快：

uint32_t* input32 = (uint32_t*)byte_array;
uint32_t* mask32 = (uint32_t*)byte_mask;
uint32_t* result32 = (uint32_t*)result_array;
for ( i = 4 ; i-- > 0 ; )
    result32[i] = input32[i] & mask32[i];

（当然，您需要一个适当的类型来表示 uint32_t，如果 n 不是2的幂，则需要清除开头和/或结尾，以使32位内容对齐。）

（变化：问题明确要求将结果放置在单独的数组中，但修改原始数组可能会更快。）

- Jason Cohen

---

等等，缓存预取器反向工作更好吗？我以为它只能向前预取。 - Crashworks

担心预加载处理器缓存行似乎是一种严重的过早优化。 - Trent

@Trent -- 这个问题的重点是优化。同时，反向遍历没有变慢，因此你可以这样做。@Crashworks -- 请记住，缓存行是对齐的，通常在大的边界上对齐，所以通常需要拉取比您请求的字节更早的字节。 - Jason Cohen

任何关于缓存的声明都将是特定于处理器的。我没有看到原帖中说明这段代码将在哪种硬件上执行。 - Trent

很好的回答，Jason。对于对齐的情况，我还想再提供一种选择：如果处理器支持，可以使用向量操作。例如，在x86上使用SSE。GCC和Intel C++都支持内置函数，使得像上面那样“向量化”循环变得容易。可以搜索“gcc sse intrinsics”以获取一些好的链接。 - sstock

Answer 2

如果希望程序更快，确保byte_array的长度是4的倍数（64位系统上为8的倍数），然后：

char byte_array[12];
char byte_mask[12];
/* Checks for proper alignment */
assert(((unsigned int)(void *)byte_array) & 3 == 0);
assert(((unsigned int)(void *)byte_mask) & 3 == 0);
for (i = 0; i < (10+3)/4; i++) {
  ((unsigned int *)(byte_array))[i] &= ((unsigned int *)(byte_mask))[i];
}

这比逐字节处理快得多。

（请注意，这是就地突变；如果您还想保留原始byte_array，则显然需要将结果存储在另一个数组中。）

- antti.huima

---

10/4 == 2，因此只处理8个字符。此外，在某些非x86架构上，由于未对齐的内存访问，这可能会引发总线错误。 - bk1e

bk1e: 你说得对，i < 10/4 是错误的。关于总线错误的评论也是正确的。我会编辑回答。 - Antti Huima

如果它不是4/8的倍数，就使用达夫设备 :) - Brian

Answer 3

\#define CHAR_ARRAY_SIZE    (10)
\#define INT_ARRAY_SIZE     ((CHAR_ARRAY_SIZE/ (sizeof (unsigned int)) + 1)

typedef union _arr_tag_ {

    char          byte_array [CHAR_ARRAY_SIZE];
    unsigned int  int_array [INT_ARRAY_SIZE]; 

} arr_tag;

现在是用于掩码的int_array。这可能适用于32位和64位处理器。

arr_tag arr_src, arr_result, arr_mask;

for (int i = 0; i < INT_ARRAY_SIZE; i ++) {
    arr_result.int_array [i] = arr_src.int_array[i] & arr_mask.int_array [i];
}

试试这个，代码看起来也很简洁。

- Alphaneo