C语言高效数组掩码

Question

我有两个BOOL的三维数组，我想在它们之间进行掩码。我的意思是创建第三个数组:third[i][j][k] = first[i][j][k] && second[i][j][k]，对于每个I,j,k

1. 我使用c语言(可能是汇编语言)
2. 我需要遮罩操作尽可能快
3. 可以假设第一个和第二个有相同的大小。
4. 如果它可以提高性能，我可能会重新排列数据从数组到其他数据排列。

编辑:每个数组维度为100

谢谢!

Answer 1

我在评论中提到了这一点，但这里有一些工作代码(希望)。我没有测试它，也没有通过编译器提供它。这只是为了这个想法)。如果你有一个100x100x100的数组，你试图建模为位掩码，那么你可以这样做:

// Create two bitmasks
const unsigned int BITS_PER_BYTE = 8;
const unsigned int DIM = 100;
const unsigned int BITS_PER_VALUE = BITS_PER_BYTE * sizeof(unsigned long);
const unsigned long MASK_SIZE = (DIM * DIM * DIM) / BITS_PER_VALUE;
unsigned long bitmask1[MASK_SIZE] = {0};
unsigned long bitmask2[MASK_SIZE] = {0};
unsigned long bitmask_result[MASK_SIZE];
// Set the two bitmasks, this is probably sub-optimal but you
// mention that setting bitmasks isn't supposed to be overly performant
// set bitmask1 (repeat something similar for bitmask2)
for (int i = 0; i < DIM; ++i)
  for (int j = 0; j < DIM; ++j)
    for (int k = 0; k < DIM; ++k) {
      // set bitmask[i][j][k] to 1
      unsigned int offset = DIM*DIM*i + DIM*j + k;
      unsigned int long_offset = offset / BITS_PER_VALUE;
      unsigned int bit_offset  = offset % BITS_PER_VALUE;
      // XXX SET THIS TO WHATEVER VALUE YOU HAVE, 1 FOR true and 0
      // FOR false. I'M SETTING EVERYTHING TO TRUE FOR THE SAKE OF
      // EXAMPLE
      bitmask1[long_offset] = 1 << bit_offset;
    }
// Now to actually compare:
for (int i = 0; i < MASK_SIZE; ++i) {
  bitmask_result[i] = bitmask1[i] & bitmask2[i];
// and that's it. bitmask_result will now have your answers. decompose
// the bitmask by doing the reverse of the above set loop

Answer 2

您知道，将数据安排在内存中，以便所有计算可以在一个(非常优化的，SSE等)循环中完成，这将有所帮助。然而，考虑到您正在访问大量内存来执行非常非常快的操作，因此优化不会太多。而且，如果你选择重新排列内存，排列过程可能会比计算本身慢。

看着这个问题，我想起了Charles Petzold在《Beautiful Code》一书中的一篇文章。您可以为循环的每一行的每个值生成代码模式(100种不同的代码模式)，仅在相应的位值为1时生成赋值，然后根据正在处理的行的位值"跳转"到正确的实现。你需要为不同的蒙版使用位域。您将3嵌套循环转换为2嵌套循环，并为内部循环优化代码(不算太坏)，必须使用其他实用程序(或只是普通的C/c++)为内部循环的不同值生成代码本身。你应该阅读这一章来理解它。很整洁。

Answer 3

我想说只有分析才能回答你的问题，我不会为你这样做，但我会简单地使用for循环，只有在执行失败时才会费心进一步查看。

不要过早优化