Którą implementację zestawu bitów należy użyć dla uzyskania maksymalnej wydajności?

Obecnie próbuję implementować różne algorytmy w kompilatorze Just In Time (JIT). Wiele algorytmów działa na mapach bitowych, bardziej znanych jako zestawy bitów.Którą implementację zestawu bitów należy użyć dla uzyskania maksymalnej wydajności?

W C++ istnieją różne sposoby implementacji bitsetu. Jako prawdziwy programista w C++, wolałbym użyć czegoś ze STL. Najważniejszym aspektem jest wydajność. Niekoniecznie potrzebuję dynamicznie skalowalnego bitsetu.

Jak widzę, istnieją trzy możliwe opcje.

I. Jedną opcją byłoby użycie std::vector<bool>, która została zoptymalizowana pod kątem miejsca. Wskazuje to również, że dane nie muszą być ciągłe w pamięci. Myślę, że może to zmniejszyć wydajność. Z drugiej strony, posiadanie jednego bitu dla każdej wartości bool może poprawić szybkość, ponieważ jest bardzo przyjazne dla pamięci podręcznej.

II. Inną opcją byłoby zamiast tego użycie std::vector<char>. Gwarantuje to, że dane są ciągłe w pamięci i łatwiej jest uzyskać dostęp do poszczególnych elementów. Jednak korzystanie z tej opcji jest dziwne, ponieważ nie ma być bitsetem.

III. Trzecią opcją byłoby użycie rzeczywistego std::bitset. Fakt, że nie jest on dynamicznie skalowalny, nie ma znaczenia.

Który powinienem wybrać, aby uzyskać maksymalną wydajność?

Źródło

2012-07-29 Man of One Way

Benchmark! [Powiązane.] (Http://www.youtube.com/watch?v=wg4trPZFUwc) –

Istnieje również [Bitowy bit bitow.Dynamiczny] (http://www.boost.org/doc/libs/1_50_0/libs/ dynamic_bitset/dynamic_bitset.html) do rozważenia. Ale tak naprawdę nie ma sposobu, aby stwierdzić, która wydajność ma najlepszą wydajność bez znajomości schematu użytkowania. Na przykład: jeśli twoja kolekcja jest mała i często uzyskiwany dostęp do 'wektora ' może dać ci szybszy dostęp, niż zestawy bitów, ponieważ nie musisz robić bitshifting/maskowania. Jednak w przypadku mniejszej dostępności/większej większej liczby braków pamięci podręcznej ze względu na większy ślad pamięci może zabić tę korzyść. – Grizzly

Na ryzyko wskazania czegoś, co jest ewidentne: std :: bitset jest przydzielany na stosie i w większości przypadków jest dość ograniczony w maksymalnym rozmiarze. Nie wiem jednak nic o ilości danych, które trzeba przechowywać. – identity

Najlepszym sposobem jest porównanie go, ponieważ każda sytuacja jest inna.

Nie użyłbym std::vector<bool>. Spróbowałem raz, a występ był okropny. Mogę poprawić wydajność mojej aplikacji, po prostu używając zamiast tego std::vector<char>.

Naprawdę nie porównywałem std::bitset z std::vector<char>, ale jeśli miejsce nie jest problemem w twoim przypadku, wybrałbym std::vector<char>. Używa 8 razy więcej miejsca niż bitset, ale ponieważ nie musi wykonywać operacji bitowych, aby uzyskać lub ustawić dane, powinno być szybsze.

Oczywiście, jeśli potrzebujesz przechowywać dużo danych w zestawie bitset/wektorze, może być korzystne użycie zestawu bitów, ponieważ pasowałoby to do pamięci podręcznej procesora.

Najprostszym sposobem jest użycie typedef i ukrycie implementacji. Zarówno bitset, jak i wektor obsługują operator [], więc powinno być łatwo zmienić jedną implementację na drugą.

Źródło

2012-07-29 20:21:02 Patrick

'operator []' są do siebie wystarczająco podobne, ale konstruktorzy nie. –

@MooingDuck: True. Używam typedef, aby uprościć migrację z jednego typu do drugiego, ale nie po to, aby było to łatwe. Używam też typedef do kolekcji, więc mogę ukryć prawdziwą implementację (list, wektor, deque, ...), która redukuje prawdziwe zmiany kodu o około 90%, jeśli kiedykolwiek zmienię typ kontenera. – Patrick

Możesz być również zainteresowany tym (trochę przestarzałe) Papier: http://www.cs.up.ac.za/cs/vpieterse/pub/PieterseEtAl_SAICSIT2010.pdf

Źródło

2014-01-03 19:58:47

Krótko mówiąc, oto wniosek z tego artykułu: "Pokazaliśmy, że' boost :: dynamic_bitset' jest znacznie bardziej efektywne niż większość innych implementacji pod względem szybkości realizacji, podczas gdy implementacja używa 'std :: vector 'przewyższa inne implementacje pod względem wydajności pamięci." – davidhigh

I odpowiedział na podobne pytanie niedawno w tym forum. Polecam mój BITSCAN library. Właśnie wydałem wersję 1.0. BITSCAN został specjalnie zaprojektowany do szybkiego skanowania bitowego.

klasy A BitBoard owija liczbę różne implementacje dla typowych operacji, takich jak BSF, BSR lub popcount 64-bitowych słów (vel bitboards). Klasy BitBoardN, BBIntrin i BBSentinel rozszerzają skanowanie bitów na ciągi bitów. Ciąg bitów w BITSCAN to tablica bitboardów. Podstawową klasą opakowania dla łańcucha bitów jest BitBoardN. BBIntrin rozszerza BitBoardN przy użyciu wewnętrznych kompilacji Windows na 64 bitach.BBIntrin jest przenośny do POSIX przy użyciu odpowiednich równoważnych funkcji asm.

Użyłem BITSCAN do wdrożenia szeregu wydajnych rozwiązań do rozwiązywania problemów kombinatorycznych NP w domenie wykresu. Zazwyczaj macierz sąsiedztwa wykresu oraz zestawy wierzchołków są kodowane jako ciągi bitów, a typowe obliczenia są wykonywane przy użyciu masek bitowych. Kod prostych obiektów kodowanych bitem jest dostępny w GRAPH. Dostępne są również przykłady korzystania z BITSCAN i GRAPH.

Porównanie BITSCAN i typowych implementacjach w STL (bitset) i BOOST (dynamic_bitset) można znaleźć tutaj: http://blog.biicode.com/bitscan-efficiency-at-glance/

Źródło

2014-07-22 18:39:28 chesslover

Którą implementację zestawu bitów należy użyć dla uzyskania maksymalnej wydajności?

Odpowiedz

Powiązane problemy