c++ - 在 C 或 C++ 中的位图上高效执行 bool 表达式

Question

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

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

解决方案在速度方面应该是高效的，并且不应该改变位图结构。 bool 表达式到另一个结构的转换不必是内存高效或快速的，因为它可以被缓存(至少在我当前的用例中)。使用转换后的 bool 表达式减少位图应该既快速又节省内存。

注意事项:

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

Answer 1

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

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

下一个提高速度的方法是展开循环。分支指令浪费执行周期(可用于数据指令)并且可能清除指令流水线，浪费时间重新加载它。

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

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

核心算法如下:

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:线程和并行处理。

除非您的位图很大，否则维护多个执行线程或并行执行的开销可能会超过 yield 。例如，如果与另一个 CPU 核心同步的开销是 200 毫秒，而无中断地处理位图是 1000 毫秒，那么您在单个位图上使用并行处理浪费了时间(1200 毫秒让另一个核心处理位图)。

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

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

如果您从外部源(如数据库)获取位图，此 I/O 将成为您的瓶颈。这是您应该优化或假脱机的部分。