在C或C++中高效执行位图上的布尔表达式

Question

用C或C++在位图上执行布尔表达式的最有效方法是什么？例如，假设我有一个4位位图(a, b, c, d)。现在，假设我有一个简单的布尔表达式，比如(a AND b) OR (c AND d)。我应该如何表示布尔表达式，以便有效地将其应用于位图？我正在寻找一个可以应用于任何布尔表达式的通用解决方案，而不仅仅是作为示例给出的解决方案。换句话说，我正在寻找某种方法将布尔表达式"编译"到另一个数据结构中，该数据结构可用于有效地将位图简化为布尔值。

位图结构是对数据库的记录进行筛选操作的结果。每条记录都有自己的位图，位图中的每一位都是单个过滤规则的结果。布尔表达式用于组合这些筛选规则，以决定记录是否应包含在数据库查询的结果中。布尔运算最多可以组合64个单独的过滤规则，因此如果需要，位图可以表示为unsigned long long int。

该解决方案在速度方面应该是高效的，并且不应该改变位图结构。将布尔表达式转换为另一个结构不一定要节省内存，也不一定要快速，因为它可以缓存（至少在我当前的用例中是这样）。使用转换后的布尔表达式减少位图应该既快速又节省内存。

注意：

• 布尔表达式仅使用嵌套的AND和OR运算（没有IF语句）
• 该解决方案应假定64位CPU可用
• 该解决方案不应依赖于CPU（除了64位寻址）
• 该解决方案不应假定任何其他特定硬件（例如GPU）的可用性
• 所有位图都在内存中
• 可以有大量的位图（数十亿）
• 位图一次更新一个

Answer 1

在位图上使用AND或or运算的最有效方法是使用硬件辅助。许多图形处理器可以对两个位图执行操作。对此没有C++标准库操作。

您需要对位图中的每个位、字节、字或双字执行操作。

下一个快速高效的方法是展开循环。分支指令浪费了执行周期（可用于数据指令），可能会清空指令管道，浪费重新加载它的时间。

您还可以通过有效地使用处理器的数据缓存来提高一些效率。加载一堆变量，执行操作，存储结果，重复。

您还应该使用处理器的字大小分组提取。32位处理器喜欢一次获取32位。因此，这将为您提供8组4位像素，这些像素通过一次提取加载。否则，您将不得不一次获取8位，这将导致8位的4次获取，而32位的1次获取。

以下是核心算法：

uint8_t * p_bitmap_a = &Bitmap_A[0];
uint8_t * p_bitmap_b = &Bitmap_B[0];
uint8_t * p_bitmap_c = &Bitmap_C[0];
// C = A AND B
for (unsigned int i = 0; i < bitmap_size / 4; ++i)
{
  uint32_t  a = *((uint32_t*) p_bitmap_a);
  uinte2_t  b = *((uint32_t*) p_bitmap_b);
  uint32_t  c = a & b;
  *((uint32_t *) p_bitmap_c) = c;
  p_bitmap_a += sizeof(uint32_t);
  p_bitmap_b += sizeof(uint32_t);
  p_bitmap_c += sizeof(uint32_t);
}

编辑1:
您的处理器可能提供了有助于操作的说明。例如，ARM7处理器可以用一条指令从内存加载许多寄存器。研究处理器指令集。您可能必须使用内联汇编语言来利用处理器特定的指令。

编辑2:线程&并行处理。

除非位图很大，否则维护多个执行线程或并行执行的开销可能会超过好处。例如，如果与另一个CPU核心同步的开销为200ms，而不间断地处理位图的开销为1000ms，则对单个位图使用并行处理浪费了时间（让另一个核心处理位图需要1200ms）。

如果你有很多位图，你可以通过使用并行处理或多线程来获得一些时间：

1. 一个线程将位图从数据库中提取到内存（缓冲区）中
2. 另一个线程处理位图并将其存储到传出缓冲区
3. 第三个进程将缓冲的位图写入数据库

如果您从外部源（如数据库）获取位图，则此I/O将成为您的瓶颈。这是您应该优化的部分或阀芯。

Answer 2

如果位图被保证始终为4位，则它们将适合字符的低4位，并且任何位图都只有16个可能的值。

对于一个特定的布尔表达式，您可以针对十六个可能的位组合中的每一个对其进行求值，从而得到一组十六个结果位。将它们组装成16位int：位0中的false、false、false、false，位1中的false、false、false、true，依此类推

现在，对于任意位图与任意布尔值，您的检查变为：

1. 将位图视为4位int，计算1 << (4 bit int)
2. 取该移位的结果，并使用C++&运算符来测试布尔运算缓存的16位int值

这将为false返回== 0，为true返回!= 0。

将其简化为两条指令：shift和and是我所能看到的最快的指令

这假设您在一个over上应用的布尔运算数量相当少，每个布尔测试的设置将是昂贵的，但由于您谈论的是数十亿位图，我假设您将在许多位图上使用相同的布尔运算。

Answer 3

您可以将表达式表示为二叉树，也可以为这两种类型的节点使用两个类。您也可以使用该操作对每个节点进行参数化，但这几乎不值得。也许您还可以使用一个输入创建一个Not节点。节点的输入要么在位图中，要么在其他节点中，所以我为前一种情况创建了一个子类，它将位图中的索引作为参数。您可以通过为And节点编写value函数并完成Or节点来完成此代码。

typedef unsigned long long Bitmap;
Bitmap bitmap;
struct Node {
  virtual bool value()=0;
};
struct AbsNode : public Node {
  int bit;
  bool value() {return (bitmap>>bit)&1; }
}
struct AndNode : public Node {
  Node *operandA, *operandB;
  etc.
}