我应该使用哪种bitset实现以实现最佳性能？

我目前正试图在即时（JIT）编译器中实现各种算法。许多算法在位图上运行，通常称为位集。我应该使用哪种bitset实现以实现最佳性能？

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

正如我所见，有三种可能的选择。

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

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

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

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

来源

2012-07-29 Man of One Way

基准！ [相关]（http://www.youtube.com/watch?v=wg4trPZFUwc） – 2012-07-29 20:01:24

还有[Boost.Dynamic Bitset]（http://www.boost.org/doc/libs/1_50_0/libs/） dynamic_bitset/dynamic_bitset.html）来考虑。但是认真地说，如果不知道使用模式，就无法确定哪种性能具有最佳性能。例如：如果您的收藏很小并且经常访问'vector '，则可能会让您更快地访问该位集，因为无需进行位移/遮罩。但是，当访问次数较少/较大时，由于内存占用量较大导致缓存未命中数量增加可能会导致这种好处。 – Grizzly 2012-07-29 20:18:28

冒着指出可能很明显的事情的风险：std :: bitset被分配在堆栈上，因此在大多数情况下最大尺寸受到限制。但是，我不知道需要存储的数据量。 – identity 2012-07-29 20:25:55

最好的方法就是对它进行基准测试，因为每种情况都不相同。我不会使用std::vector<bool>。我尝试过一次，表现很糟糕。我可以通过简单地使用std::vector<char>来改善我的应用程序的性能。

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

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

最简单的方法是使用typedef并隐藏实现。 bitset和vector都支持[]运算符，所以应该很容易通过另一个实现切换一个实现。

来源

2012-07-29 20:21:02 Patrick

'operator []'是相似的，但是构造函数不是。 – 2014-07-22 18:41:46

@MooingDuck：的确如此。我使用typedef来简化从一种类型到另一种类型的迁移，但不能使它变得毫不费力。我还为集合使用了typedef，这样我就可以隐藏真正的实现（list，vector，deque，...），如果我更改容器类型，它将减少约90％的实际代码更改。 – Patrick 2014-07-24 12:31:05

您可能也有兴趣在这个（有些过时）纸张： http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

来源

2014-01-03 19:58:47

简而言之，这里是论文的结论：“我们已经表明'boost :: dynamic_bitset'在执行速度方面比大多数其他实现更有效率，而实现使用'std :: vector在内存效率方面，'的性能超过其他实现。“ – davidhigh 2014-07-27 21:06:47

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

甲棋盘类包装为典型的操作，例如BSF，BSR或popcount 64位字（又名位棋盘）多个不同的实施方式。 BitBoardN，BBIntrin和BBSentinel类将位扫描扩展为位串。 BITSCAN中的一个位串是一个位板阵列。位串的基类包装类是BitBoardN。 BBIntrin通过使用64位位平台上的Windows编译器内在函数扩展了BitBoardN。BBIntrin通过使用适当的asm等价函数可以移植到POSIX。

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

BITSCAN和典型的实现之间的STL（位集合）和BOOST（来，dynamic_bitset）的比较可以在这里找到： http://blog.biicode.com/bitscan-efficiency-at-glance/

来源

2014-07-22 18:39:28 chesslover

我应该使用哪种bitset实现以实现最佳性能？

回答

相关问题