c++ - 我应该使用哪个 bitset 实现来获得最佳性能？

Question

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

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

在我看来，有三种可能的选择。

我。一种选择是使用 std::vector<bool> ，已针对空间进行了优化。这也表明数据在内存中不必是连续的。我想这可能会降低性能。另一方面，每个 bool 值都有一个位可以提高速度，因为它对缓存非常友好。

二。另一种选择是使用 std::vector<char> .它保证数据在内存中是连续的，并且更容易访问单个元素。然而，使用这个选项感觉很奇怪，因为它不是一个位集。

三。第三种选择是使用实际的 std::bitset .它不是动态调整大小的事实并不重要。

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

Answer 1

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

我不会使用 std::vector<bool> .我试过一次，性能很糟糕。我可以通过简单地使用 std::vector<char> 来提高我的应用程序的性能。而是。

我并没有真正比较 std::bitset与 std::vector<char> ，但如果在您的情况下空间不是问题，我会选择 std::vector<char> .它使用的空间是 bitset 的 8 倍，但由于它不需要进行位操作来获取或设置数据，所以它应该更快。

当然，如果您需要在 bitset/vector 中存储大量数据，那么使用 bitset 可能会有好处，因为它适合处理器的缓存。

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