我應該使用哪種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實現以實現最佳性能？

回答

相關問題