如何提高 c 或 c++ 中的多维位数组比较性能

Question

我有以下三维位数组（用于布隆过滤器）：

unsigned char  P_bit_table_[P_ROWS][ROWS][COLUMNS];

P_ROWS 的维度代表独立的两个维位数组（即 P_ROWS[0], P_ROWS1，P_ROWS[2] 是独立的位数组），可以大到 100MB，并且包含独立填充的数据。我正在查找的数据可能位于这些 P_ROWS 中的任何一个中，现在我正在独立搜索它，即 P_ROWS[0] 然后是 P_ROWS1 等等，直到我得到肯定的结果或直到它结束（P_ROWS[n-1]）。这意味着如果 n 是 100，我必须执行此搜索（位比较）100 次（并且此搜索经常执行）。有人建议，如果我可以进行位分组，我可以提高搜索性能（在行主序数组上使用列主序——我不知道如何）。

我确实需要提高搜索性能，因为该程序做了很多工作。

如果需要，我很乐意提供有关我的位表实现的更多详细信息。

抱歉语言不好。

感谢您的帮助。

编辑： 位分组可以按以下格式完成： 假设数组为：

unsigned char P_bit_table_[P_ROWS][ROWS][COLUMNS]={{(a1,a2,a3),(b1,b2,b3),(c1,c2,c3))},
                                                  {(a1,a2,a3),(b1,b2,b3),(c1,c2,c3))},   
                                                  {(a1,a2,a3),(b1,b2,b3),(c1,c2,c3))}};

正如您所看到的，第三维上的所有行都具有相似的数据。分组后我想要的是这样的；所有 a1 都在一个组中（作为一个实体，以便我可以将它们与另一位进行比较以检查它们是否打开或关闭），所有 b1 都在另一组中，依此类推。

Answer 1

重用其他人的算法

有大量的位计算优化包括许多不明显的，例如 Hamming用于查找下一个真或假位的权重和专门算法，与您构建数据的方式相当独立。

重用其他人编写的算法确实可以加快计算和查找速度，更不用说开发时间了。有些算法非常专业，并且使用计算魔法，这会让您摸不着头脑：在这种情况下，您可以相信作者的话（在通过单元测试确认其正确性之后）。

利用 CPU 缓存和多线程

我个人将多维位数组减少到一维，并针对预期的遍历进行了优化。

这样，命中 CPU 缓存的机会就更大。

对于您的情况，我还会深入思考数据的可变性以及是否要对位块加锁。对于 100MB 的数据，如果您能够构建数据和算法以避免争用，您就有可能使用多个线程并行运行算法。

如果您按线程划分数据块的所有权，那么您甚至可能拥有无锁模型，这样就没有两个线程可以读取或写入同一块。这一切都取决于您的要求。

现在是思考这些问题的好时机。但由于没有人比您更了解您的数据和使用情况，因此您必须根据数据和使用模式考虑设计选项。