我应该使用哪个bitset实现最大的性能？ [英] Which bitset implementation should I use for maximum performance?

问题描述

我目前正试图在即时（JIT）编译器中实现各种算法。许多算法对位图进行操作，通常称为位组。

I'm currently trying to implement various algorithms in a Just In Time (JIT) compiler. Many of the algorithms operate on bitmaps, more commonly known as bitsets.

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

In C++ there are various ways of implementing a bitset. As a true C++ developer, I would prefer to use something from the STL. The most important aspect is performance. I don't necessarily need a dynamically resizable bitset.

正如我看到的，有三个可能的选项。

As I see it, there are three possible options.

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

I. One option would be to use std::vector<bool>, which has been optimized for space. This would also indicate that the data doesn't have to be contiguous in memory. I guess this could decrease performance. On the other hand, having one bit for each bool value could improve speed since it's very cache friendly.

II。另一个选择是改为使用 std :: vector< char> 。它保证数据在内存中是连续的，并且更容易访问各个元素。但是，使用此选项感觉很奇怪，因为它不是一个bitset。

II. Another option would be to instead use a std::vector<char>. It guarantees that the data is contiguous in memory and it's easier to access individual elements. However, it feels strange to use this option since it's not intended to be a bitset.

三。第三个选项是使用实际的 std :: bitset 。不能动态调整大小的事实并不重要。

III. The third option would be to use the actual std::bitset. That fact that it's not dynamically resizable doesn't matter.

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

Which one should I choose for maximum performance?

推荐答案

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

Best way is to just benchmark it, because every situation is different.

我不会使用 std :: vector< bool> 。我试过一次，性能是可怕的。我可以通过简单地使用 std :: vector< char> 来改善我的应用程序的性能。

I wouldn't use std::vector<bool>. I tried it once and the performance was horrible. I could improve the performance of my application by simply using std::vector<char> instead.

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

I didn't really compare std::bitset with std::vector<char>, but if space is not a problem in your case, I would go for std::vector<char>. It uses 8 times more space than a bitset, but since it doesn't have to do bit-operations to get or set the data, it should be faster.

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

Of course if you need to store lots of data in the bitset/vector, then it could be beneficial to use bitset, because that would fit in the cache of the processor.

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

The easiest way is to use a typedef, and to hide the implementation. Both bitset and vector support the [] operator, so it should be easy to switch one implementation by the other.

这篇关于我应该使用哪个bitset实现最大的性能？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！