我应该使用哪种位集实现来获得最大性能？

Question

我目前正在尝试在即时（JIT）编译器中实现各种算法。许多算法都在位图上运行，通常称为位集。

在 C++ 中，有多种实现位集的方法。作为一名真正的 C++ 开发人员，我更喜欢使用 STL 中的东西。最重要的方面是性能。我不一定需要动态调整大小的位集。

据我所知，有三种可能的选择。

我。一种选择是使用

std::vector<bool>

，它已针对空间进行了优化。这也表明数据在内存中不必是连续的。我想这可能会降低性能。另一方面，为每个布尔值分配一个位可以提高速度，因为它对缓存非常友好。

二.另一种选择是使用

std::vector<char>

。它保证数据在内存中是连续的，并且更容易访问各个元素。然而，使用这个选项感觉很奇怪，因为它并不是一个位集。

三．第三种选择是使用实际的

std::bitset

。它不能动态调整大小这一事实并不重要。

我应该选择哪一个才能获得最佳性能？

Answer 1

最好的方法是对其进行基准测试，因为每种情况都是不同的。

我不会使用

std::vector<bool>

。 我尝试过一次，效果很糟糕。 我可以通过简单地使用

std::vector<char>

来提高应用程序的性能。

我并没有真正将

std::bitset

与

std::vector<char>

进行比较，但如果空间对您来说不是问题，我会选择

std::vector<char>

。 它使用的空间是位集的 8 倍，但由于它不需要执行位操作来获取或设置数据，所以它应该更快。

当然，如果您需要在位集/向量中存储大量数据，那么使用位集可能是有益的，因为它适合处理器的缓存。

最简单的方法是使用 typedef，并隐藏实现。 位集和向量都支持 [] 运算符，因此应该很容易在一种实现之间切换另一种实现。

Answer 2

我最近在这个论坛回答了类似的问题。我推荐我的BITSCAN 库。我刚刚发布了1.0版本。 BITSCAN 专为快速位扫描操作而设计。

BitBoard 类包装了典型操作的许多不同实现，例如 64 位字（又名位板）的 bsf、bsr 或 popcount。 BitBoardN、BBIntrin 和 BBSentinel 类将位扫描扩展到位串。 BITSCAN 中的位串是位板数组。位字符串的基本包装类是 BitBoardN。 BBIntrin 通过在 64 位板上使用 Windows 编译器内部函数来扩展 BitBoardN。通过使用适当的 asm 等效函数，BBIntrin 可移植到 POSIX。

我使用 BITSCAN 为图域中的 NP 组合问题实现了许多高效的求解器。通常，图的邻接矩阵以及顶点集被编码为位串，并且使用位掩码执行典型计算。简单位编码图形对象的代码可在 GRAPH 中找到。还提供了如何使用 BITSCAN 和 GRAPH 的示例。

可以在此处找到 BITSCAN 与 STL (bitset) 和 BOOST (dynamic_bitset) 中的典型实现之间的比较： http://blog.biicode.com/bitscan-efficiency-at-glance/

Answer 3

您可能也对这篇（有些过时的）论文感兴趣： http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

[更新] 之前的链接似乎已损坏，但我认为它指向这篇文章： https://www.researchgate.net/publication/220803585_Performance_of_C_bit-vector_implementations