Czy jest jakaś przewaga manipulacji bitami w stylu c nad std :: bitset?

17

Pracuję prawie wyłącznie w C ++ 11/14, i zwykle kulą się, gdy widzę taki kod:

std::int64_t mArray;
mArray |= someMask << 1;

To tylko przykład; Mówię ogólnie o manipulacji bitami. Czy w C ++ jest naprawdę sens? Powyższe jest zniekształcające i podatne na błędy, a użycie std::bitsetpozwala na:

  1. łatwiej modyfikować rozmiar według std::bitsetpotrzeb, dostosowując parametr szablonu i pozwalając implementacji zająć się resztą, oraz
  2. poświęcaj mniej czasu na zastanawianie się, co się dzieje (i być może popełnianie błędów) i pisz std::bitsetw sposób podobny do std::arrayinnych kontenerów danych.

Moje pytanie brzmi; czy jest jakiś powód, aby nie używać std::bitsettypów prymitywnych, innych niż kompatybilność wsteczna?

ilościowo
źródło
Rozmiar a std::bitsetjest ustalany w czasie kompilacji. To jedyna wada, o której myślę.
rwong
1
@rwong Mówię o std::bitsetmanipulacji bitami w stylu c (np. int), która jest również naprawiona w czasie kompilacji.
ilościowo
Jednym z powodów może być starszy kod: kod został napisany, gdy std::bitsetnie był dostępny (lub znany autorowi) i nie było powodu, aby przepisać kod, aby go użyć std::bitset.
Bart van Ingen Schenau
Osobiście uważam, że kwestia uczynienia „operacji na zbiorze / mapie / tablicy zmiennych binarnych” łatwymi do zrozumienia dla wszystkich jest nadal w dużej mierze nierozwiązana, ponieważ w praktyce stosuje się wiele operacji, których nie można sprowadzić do prostych operacji. Istnieje również zbyt wiele sposobów reprezentowania takich zestawów, z których bitsetjeden jest, ale mały wektor lub zestaw ints (indeksu bitów) również może być uzasadniony. Filozofia C / C ++ nie ukrywa złożoności wyboru przed programistą.
rwong

Odpowiedzi:

12

Z logicznego (nietechnicznego) punktu widzenia nie ma przewagi.

Każdy zwykły kod C / C ++ może być zawinięty w odpowiedni „konstrukt biblioteki”. Po takim opakowaniu kwestia „czy to jest bardziej korzystne niż to” staje się dyskusyjnym pytaniem.

Z punktu widzenia szybkości C / C ++ powinien umożliwiać konstruowaniu biblioteki generowanie kodu, który jest tak samo wydajny, jak zwykły kod, który pakuje. Jest to jednak uzależnione od:

  • Inlining funkcji
  • Sprawdzanie czasu kompilacji i eliminacja niepotrzebnego sprawdzania czasu wykonywania
  • Eliminacja martwego kodu
  • Wiele innych optymalizacji kodu ...

Używając tego rodzaju nietechnicznego argumentu, wszelkie „brakujące funkcje” mogą być dodawane przez każdego i dlatego nie są liczone jako wady.

Jednak wbudowanych wymagań i ograniczeń nie można obejść za pomocą dodatkowego kodu. Poniżej argumentuję, że rozmiar std::bitsetjest stałą czasową kompilacji, a zatem, chociaż nie jest liczony jako wada, wciąż jest to coś, co wpływa na wybór użytkownika.


Z estetycznego punktu widzenia (czytelność, łatwość konserwacji itp.) Istnieje różnica.

Jednak nie jest oczywiste, że std::bitsetkod natychmiast wygrywa nad zwykłym kodem C. Należy przyjrzeć się większym fragmentom kodu (a nie próbce zabawki), aby stwierdzić, czy użycie std::bitsetpoprawiło ludzką jakość kodu źródłowego.


Szybkość manipulacji bitami zależy od stylu kodowania. Styl kodowania wpływa zarówno na manipulację bitami C / C ++, jak również ma zastosowanie std::bitset, jak wyjaśniono poniżej.


Jeśli ktoś pisze kod, który używa operator []do odczytu i zapisu jeden bit na raz, będzie musiał to zrobić wiele razy, jeśli będzie więcej niż jeden bit do manipulacji. To samo można powiedzieć o kodzie w stylu C.

Jednak bitsetma też inne podmioty, takie jak operator &=, operator <<=itp, które działa na pełnej szerokości bitset. Ponieważ leżące u jego podstaw maszyny mogą często działać w trybie 32-bitowym, 64-bitowym, a czasem 128-bitowym (z SIMD) na raz (w tej samej liczbie cykli procesora), kod zaprojektowany jest tak, aby korzystać z takich operacji wielobitowych może być szybszy niż „pętlowy” kod manipulacji bitami.

Ogólna idea nazywa się SWAR (SIMD w rejestrze) i jest podtematem przy manipulowaniu bitami.


Niektórzy dostawcy C ++ mogą implementować bitsetSIMD między 64-bitami a 128-bitami. Niektórzy dostawcy mogą tego nie robić (ale mogą to zrobić). Jeśli trzeba wiedzieć, co robi biblioteka dostawcy C ++, jedynym sposobem jest przyjrzenie się dezasemblacji.


Jeśli chodzi o to, czy std::bitsetma ograniczenia, mogę podać dwa przykłady.

  1. Rozmiar std::bitsetmusi być znany w czasie kompilacji. Aby stworzyć tablicę bitów o dynamicznie wybranym rozmiarze, trzeba będzie użyć std::vector<bool>.
  2. Obecna specyfikacja C ++ dla std::bitsetnie zapewnia sposobu wyodrębnienia kolejnego wycinka N bitów z większego bitsetz M bitów.

Pierwszy ma podstawowe znaczenie, co oznacza, że ​​ludzie, którzy potrzebują dynamicznych zestawów bitów, muszą wybrać inne opcje.

Drugi można pokonać, ponieważ można napisać jakieś adaptery do wykonania zadania, nawet jeśli standard bitsetnie jest rozszerzalny.


Istnieją pewne typy zaawansowanych operacji SWAR, które nie są dostarczane od razu po wyjęciu z pudełka std::bitset. Na tej stronie można przeczytać o tych operacjach dotyczących permutacji bitów . Jak zwykle można je wdrożyć samodzielnie, działając na zasadzie std::bitset.


Odnośnie dyskusji na temat wydajności.

Jedno ostrzeżenie: wiele osób pyta, dlaczego (coś) ze standardowej biblioteki jest znacznie wolniejsze niż jakiś prosty kod w stylu C. Nie powtórzyłbym tutaj wstępnej wiedzy na temat znakowania mikrobenchowania, ale mam tylko następującą radę: upewnij się, że test porównawczy w „trybie zwolnienia” (z włączonymi optymalizacjami) i upewnij się, że kod nie jest eliminowany (eliminacja martwego kodu) lub nie jest wyciągnięty z pętli (niezmienny ruch kodu) .

Ponieważ generalnie nie jesteśmy w stanie stwierdzić, czy ktoś (w Internecie) prawidłowo robił znaki mikrodruku, jedynym sposobem na uzyskanie wiarygodnego wniosku jest zrobienie własnych znaków mikrodruku i udokumentowanie szczegółów oraz poddanie się publicznej ocenie i krytyce. Ponowne wykonywanie mikrodruków, które inni robili wcześniej, nie zaszkodzi.

rwong
źródło
Problem nr 2 oznacza również, że zestawu bitów nie można używać w żadnej konfiguracji równoległej, w której każdy wątek powinien działać na podzbiorze zestawu bitów.
user239558,
@ user239558 Wątpię, czy ktoś chciałby równolegle korzystać z tego samego std::bitset. Nie ma gwarancji zgodności pamięci (w std::bitset), co oznacza, że ​​nie powinna być dzielona między rdzeniami. Ludzie, którzy muszą udostępniać go między rdzeniami, będą mieli tendencję do budowania własnej implementacji. Gdy dane są współużytkowane przez różne rdzenie, zwykle wyrównuje się je do granicy linii pamięci podręcznej. Niezastosowanie się do tego zmniejsza wydajność i naraża na więcej pułapek bezatomowych. Nie mam wystarczającej wiedzy, aby dać przegląd tego, jak zbudować równoległą implementację std::bitset.
rwong
programowanie równoległe danych zwykle nie wymaga żadnej spójności pamięci. synchronizujesz tylko między fazami. Absolutnie chciałbym przetwarzać zestaw bitów równolegle, myślę, że każdy z dużą bitsetwolą.
user239558,
@ user239558, który brzmi jak sugeruje kopiowanie (odpowiedni zakres bitsetów do przetworzenia przez każdy rdzeń należy skopiować przed rozpoczęciem przetwarzania). Zgadzam się z tym, choć myślę, że każdy, kto myśli o paralelizacji, pomyślałby już o wdrożeniu własnej implementacji. Zasadniczo wiele standardowych bibliotek C ++ jest dostępnych jako implementacje podstawowe; każdy, kto ma poważniejsze potrzeby, sam je wdroży.
rwong
nie, nie ma kopiowania. po prostu uzyskuje dostęp do różnych części statycznej struktury danych. nie jest wymagana synchronizacja.
user239558,
2

Z pewnością nie ma to zastosowania we wszystkich przypadkach, ale czasami algorytm może zależeć od wydajności kręcenia bitów w stylu C, aby zapewnić znaczny wzrost wydajności. Pierwszym przykładem, jaki przychodzi mi do głowy, jest użycie bitboardów , sprytnego kodowania liczb całkowitych pozycji w grze planszowej, do przyspieszenia silników szachowych i tym podobnych. Tutaj ustalony rozmiar typów liczb całkowitych nie stanowi problemu, ponieważ i tak szachownice mają zawsze wartość 8 * 8.

Dla prostego przykładu rozważ następującą funkcję (zaczerpniętą z tej odpowiedzi Bena Jacksona ), która testuje pozycję Connect Four pod kątem zwycięstwa:

// return whether newboard includes a win
bool haswon2(uint64_t newboard)
{
    uint64_t y = newboard & (newboard >> 6);
    uint64_t z = newboard & (newboard >> 7);
    uint64_t w = newboard & (newboard >> 8);
    uint64_t x = newboard & (newboard >> 1);
    return (y & (y >> 2 * 6)) | // check \ diagonal
           (z & (z >> 2 * 7)) | // check horizontal -
           (w & (w >> 2 * 8)) | // check / diagonal
           (x & (x >> 2));      // check vertical |
}
David Zhang
źródło
2
Myślisz, że std::bitsetbędzie wolniej?
ilościowo
1
Cóż, rzut oka na źródło, zestaw bitów libc ++ jest oparty na pojedynczym size_t lub ich tablicy, więc prawdopodobnie skompilowałby się do czegoś zasadniczo równoważnego / identycznego, szczególnie w systemie, w którym sizeof (size_t) == 8 - więc nie, prawdopodobnie nie będzie wolniej.
Ryan Pavlik,