Man*_*Way 13 c++ compiler-construction performance bitset
我目前正在尝试在即时(JIT)编译器中实现各种算法.许多算法在位图上运行,通常称为位集.
在C++中,有多种方法可以实现bitset.作为一名真正的C++开发人员,我更喜欢使用STL中的东西.最重要的方面是表现.我不一定需要动态可调整大小的bitset.
我认为,有三种可能的选择.
I.一种选择是使用std::vector<bool>,它已针对空间进行了优化.这也表明数据不必在内存中连续.我想这可能会降低性能.另一方面,为每个bool值设置一位可以提高速度,因为它非常缓存友好.
II.另一种选择是使用a std::vector<char>.它保证数据在内存中是连续的,并且更容易访问单个元素.但是,使用此选项感觉很奇怪,因为它不是一个bitset.
III.第三种选择是使用实际的std::bitset.事实上它不能动态调整大小并不重要.
我应该选择哪一个以获得最佳性能？
最好的方法是对它进行基准测试,因为每种情况都不同.
我不会用std::vector<bool>.我尝试了一次,表现很糟糕.我可以通过简单地使用std::vector<char>来改善我的应用程序的性能.
我真的没有比较std::bitset有std::vector<char>,但如果空间不是你的情况有问题,我会去的std::vector<char>.它使用的空间比bitset多8倍,但由于它不需要进行位操作来获取或设置数据,因此它应该更快.
当然,如果你需要在bitset/vector中存储大量数据,那么使用bitset可能是有益的,因为它适合处理器的缓存.
最简单的方法是使用typedef,并隐藏实现.bitset和vector都支持[]运算符,因此应该很容易通过另一个实现切换一个实现.
我最近在这个论坛上回答了类似的问题.我推荐我的BITSCAN库.我刚刚发布了1.0版本.BITSCAN专为快速位扫描操作而设计.
BitBoard类为典型的操作包装了许多不同的实现,例如bsf,bsr或popcount用于64位字(aka位板).类BitBoardN,BBIntrin和BBSentinel将位扫描扩展到位串.BITSCAN中的位字符串是一个位板数组.位串的基础包装类是BitBoardN.BBIntrin通过在64位板上使用Windows编译器内在函数来扩展BitBoardN.通过使用适当的asm等效函数,BBIntrin可以移植到POSIX.
我已经使用BITSCAN为图域中的NP组合问题实现了许多有效的求解器.通常,图的邻接矩阵以及顶点集被编码为比特串,并且使用比特掩码执行典型的计算.GRAPH中提供了简单的bitencoded图形对象的代码.还提供了如何使用BITSCAN和GRAPH的示例.
可以在此处找到BITSCAN与STL(bitset)和BOOST(dynamic_bitset)中的典型实现之间的比较:http: //blog.biicode.com/bitscan-efficiency-at-glance/