Jak napisać łatwą w utrzymaniu, szybką i kompilującą maskę bitową w C ++?

Mam kod mniej więcej taki:

#include <bitset>

enum Flags { A = 1, B = 2, C = 3, D = 5,
             E = 8, F = 13, G = 21, H,
             I, J, K, L, M, N, O };

void apply_known_mask(std::bitset<64> &bits) {
    const Flags important_bits[] = { B, D, E, H, K, M, L, O };
    std::remove_reference<decltype(bits)>::type mask{};
    for (const auto& bit : important_bits) {
        mask.set(bit);
    }

    bits &= mask;
}

Clang> = 3.6 robi inteligentną rzecz i kompiluje to do pojedynczej andinstrukcji (która jest następnie wstawiana wszędzie indziej):

apply_known_mask(std::bitset<64ul>&):  # @apply_known_mask(std::bitset<64ul>&)
        and     qword ptr [rdi], 775946532
        ret

Ale każda wersja GCC, którą próbowałem, kompiluje to do ogromnego bałaganu, który obejmuje obsługę błędów, która powinna być statycznie DCE. W innym kodzie nawet umieści important_bitsodpowiednik jako dane zgodnie z kodem!

.LC0:
        .string "bitset::set"
.LC1:
        .string "%s: __position (which is %zu) >= _Nb (which is %zu)"
apply_known_mask(std::bitset<64ul>&):
        sub     rsp, 40
        xor     esi, esi
        mov     ecx, 2
        movabs  rax, 21474836482
        mov     QWORD PTR [rsp], rax
        mov     r8d, 1
        movabs  rax, 94489280520
        mov     QWORD PTR [rsp+8], rax
        movabs  rax, 115964117017
        mov     QWORD PTR [rsp+16], rax
        movabs  rax, 124554051610
        mov     QWORD PTR [rsp+24], rax
        mov     rax, rsp
        jmp     .L2
.L3:
        mov     edx, DWORD PTR [rax]
        mov     rcx, rdx
        cmp     edx, 63
        ja      .L7
.L2:
        mov     rdx, r8
        add     rax, 4
        sal     rdx, cl
        lea     rcx, [rsp+32]
        or      rsi, rdx
        cmp     rax, rcx
        jne     .L3
        and     QWORD PTR [rdi], rsi
        add     rsp, 40
        ret
.L7:
        mov     ecx, 64
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:.LC1
        xor     eax, eax
        call    std::__throw_out_of_range_fmt(char const*, ...)

Jak napisać ten kod, aby oba kompilatory działały właściwie? W przeciwnym razie jak mam to napisać, aby było jasne, szybkie i możliwe do utrzymania?

Najlepsza wersja to c ++ 17:

template< unsigned char... indexes >
constexpr unsigned long long mask(){
  return ((1ull<<indexes)|...|0ull);
}

Następnie

void apply_known_mask(std::bitset<64> &bits) {
  constexpr auto m = mask<B,D,E,H,K,M,L,O>();
  bits &= m;
}

z powrotem w c ++ 14, możemy zrobić tę dziwną sztuczkę:

template< unsigned char... indexes >
constexpr unsigned long long mask(){
  auto r = 0ull;
  using discard_t = int[]; // data never used
  // value never used:
  discard_t discard = {0,(void(
    r |= (1ull << indexes) // side effect, used
  ),0)...};
  (void)discard; // block unused var warnings
  return r;
}

lub, jeśli utknęliśmy c ++ 11możemy to rozwiązać rekurencyjnie:

constexpr unsigned long long mask(){
  return 0;
}
template<class...Tail>
constexpr unsigned long long mask(unsigned char b0, Tail...tail){
  return (1ull<<b0) | mask(tail...);
}
template< unsigned char... indexes >
constexpr unsigned long long mask(){
  return mask(indexes...);
}

Godbolt ze wszystkimi 3 - możesz przełączyć CPP_VERSION zdefiniować i uzyskać identyczny montaż.

W praktyce użyłbym najnowocześniejszego, jak tylko potrafię. 14 pokonuje 11, ponieważ nie mamy rekursji, a zatem O (n ^ 2) długości symbolu (co może spowodować eksplozję czasu kompilacji i wykorzystania pamięci kompilatora); 17 bije 14, ponieważ kompilator nie musi usuwać tej tablicy martwego kodu, a ta sztuczka tablicowa jest po prostu brzydka.

Spośród nich 14 jest najbardziej zagmatwanych. Tutaj tworzymy anonimową tablicę wszystkich zer, tymczasem jako efekt uboczny konstruujemy nasz wynik, a następnie odrzucamy tablicę. Wyrzucona tablica zawiera liczbę 0 równą rozmiarowi naszej paczki, plus 1 (którą dodajemy, abyśmy mogli obsłużyć puste paczki).

Szczegółowe wyjaśnienie, co jest c ++ 14wersja robi. To jest sztuczka / hack, a fakt, że musisz to zrobić, aby rozszerzyć pakiety parametrów z wydajnością w C ++ 14, jest jednym z powodów, dla których wyrażenia fold zostały dodane wc ++ 17.

Najlepiej to zrozumieć od podszewki:

    r |= (1ull << indexes) // side effect, used

to właśnie aktualizuje rsię 1<<indexesza ustaloną indeksu. indexesjest pakietem parametrów, więc będziemy musieli go rozszerzyć.

Reszta pracy polega na dostarczeniu pakietu parametrów do rozszerzenia indexeswewnątrz.

Jeden krok do przodu:

(void(
    r |= (1ull << indexes) // side effect, used
  ),0)

tutaj rzutujemy nasze wyrażenie na void, co oznacza, że ​​nie obchodzi nas jego wartość zwracana (chcemy tylko efektu ubocznego ustawienia r- w C ++ wyrażenia takie jak a |= brównież zwracają wartość, którą ustawili a).

Następnie używamy operatora przecinka ,i 0odrzucamy void„wartość”, a zwracamy wartość 0. Więc to jest wyrażenie, którego wartość jest 0i jako efekt uboczny obliczania 0, ustawia ją nieco r.

  int discard[] = {0,(void(
    r |= (1ull << indexes) // side effect, used
  ),0)...};

W tym momencie rozszerzamy pakiet parametrów indexes. Więc otrzymujemy:

 {
    0,
    (expression that sets a bit and returns 0),
    (expression that sets a bit and returns 0),
    [...]
    (expression that sets a bit and returns 0),
  }

w {}. To użycie nie, jest operatorem przecinka, ale raczej separatorem elementu tablicy. To jest s, które również ustawia bity jako efekt uboczny. Następnie przypisujemy instrukcje konstrukcji tablicy do tablicy .sizeof...(indexes)+1 0r{}discard

Następnie rzucamy discardna void- większość kompilatorów ostrzeże Cię, jeśli utworzysz zmienną i nigdy jej nie przeczytasz. Wszyscy kompilatorzy nie będą narzekać, jeśli rzucisz to na void, jest to rodzaj powiedzenia „Tak, wiem, nie używam tego”, więc to pomija ostrzeżenie.

Optymalizacja, której szukasz, wydaje się być peelingiem w pętli, który jest włączony -O3lub ręcznie za pomocą -fpeel-loops. Nie jestem pewien, dlaczego należy to do zakresu peelingu pętli, a nie rozwijania pętli, ale prawdopodobnie nie chce rozwinąć pętli z nielokalnym przepływem kontrolnym w niej (jak to jest, potencjalnie, z kontroli zasięgu).

Domyślnie jednak GCC przestaje być w stanie usunąć wszystkie iteracje, co najwyraźniej jest konieczne. Eksperymentalnie przekazanie -O2 -fpeel-loops --param max-peeled-insns=200(wartość domyślna to 100) powoduje wykonanie zadania przy użyciu oryginalnego kodu: https://godbolt.org/z/NNWrga

jeśli używanie tylko C ++ 11 jest koniecznością, (&a)[N]jest sposobem na przechwytywanie tablic. Pozwala to na napisanie jednej funkcji rekurencyjnej bez korzystania z funkcji pomocniczych:

template <std::size_t N>
constexpr std::uint64_t generate_mask(Flags const (&a)[N], std::size_t i = 0u){
    return i < N ? (1ull << a[i] | generate_mask(a, i + 1u)) : 0ull;
}

przypisanie go do constexpr auto:

void apply_known_mask(std::bitset<64>& bits) {
    constexpr const Flags important_bits[] = { B, D, E, H, K, M, L, O };
    constexpr auto m = generate_mask(important_bits); //< here
    bits &= m;
}

Test

int main() {
    std::bitset<64> b;
    b.flip();
    apply_known_mask(b);
    std::cout << b.to_string() << '\n';
}

Wynik

0000000000000000000000000000000000101110010000000000000100100100
//                                ^ ^^^  ^             ^  ^  ^
//                                O MLK  H             E  D  B

naprawdę trzeba docenić zdolność C ++ do obliczania wszystkiego, co można obliczyć w czasie kompilacji. To na pewno nadal mi się podoba ( <> ).

W przypadku nowszych wersji C ++ 14 i C ++ 17 odpowiedź Yakka już wspaniale to pokrywa.

Zachęcam do napisania odpowiedniego EnumSettypu.

Pisanie podstawowego EnumSet<E>języka w C ++ 14 (wzwyż) na podstawie std::uint64_tjest trywialne:

template <typename E>
class EnumSet {
public:
    constexpr EnumSet() = default;

    constexpr EnumSet(std::initializer_list<E> values) {
        for (auto e : values) {
            set(e);
        }
    }

    constexpr bool has(E e) const { return mData & mask(e); }

    constexpr EnumSet& set(E e) { mData |= mask(e); return *this; }

    constexpr EnumSet& unset(E e) { mData &= ~mask(e); return *this; }

    constexpr EnumSet& operator&=(const EnumSet& other) {
        mData &= other.mData;
        return *this;
    }

    constexpr EnumSet& operator|=(const EnumSet& other) {
        mData |= other.mData;
        return *this;
    }

private:
    static constexpr std::uint64_t mask(E e) {
        return std::uint64_t(1) << e;
    }

    std::uint64_t mData = 0;
};

Pozwala to napisać prosty kod:

void apply_known_mask(EnumSet<Flags>& flags) {
    static constexpr EnumSet<Flags> IMPORTANT{ B, D, E, H, K, M, L, O };

    flags &= IMPORTANT;
}

W C ++ 11 wymaga pewnych zwojów, ale mimo to pozostaje możliwe:

template <typename E>
class EnumSet {
public:
    template <E... Values>
    static constexpr EnumSet make() {
        return EnumSet(make_impl(Values...));
    }

    constexpr EnumSet() = default;

    constexpr bool has(E e) const { return mData & mask(e); }

    void set(E e) { mData |= mask(e); }

    void unset(E e) { mData &= ~mask(e); }

    EnumSet& operator&=(const EnumSet& other) {
        mData &= other.mData;
        return *this;
    }

    EnumSet& operator|=(const EnumSet& other) {
        mData |= other.mData;
        return *this;
    }

private:
    static constexpr std::uint64_t mask(E e) {
        return std::uint64_t(1) << e;
    }

    static constexpr std::uint64_t make_impl() { return 0; }

    template <typename... Tail>
    static constexpr std::uint64_t make_impl(E head, Tail... tail) {
        return mask(head) | make_impl(tail...);
    }

    explicit constexpr EnumSet(std::uint64_t data): mData(data) {}

    std::uint64_t mData = 0;
};

I jest wywoływany przez:

void apply_known_mask(EnumSet<Flags>& flags) {
    static constexpr EnumSet<Flags> IMPORTANT =
        EnumSet<Flags>::make<B, D, E, H, K, M, L, O>();

    flags &= IMPORTANT;
}

Nawet GCC w trywialny sposób generuje andinstrukcję w -O1 godbolt :

apply_known_mask(EnumSet<Flags>&):
        and     QWORD PTR [rdi], 775946532
        ret

Od C ++ 11 możesz również użyć klasycznej techniki TMP:

template<std::uint64_t Flag, std::uint64_t... Flags>
struct bitmask
{
    static constexpr std::uint64_t mask = 
        bitmask<Flag>::value | bitmask<Flags...>::value;
};

template<std::uint64_t Flag>
struct bitmask<Flag>
{
    static constexpr std::uint64_t value = (uint64_t)1 << Flag;
};

void apply_known_mask(std::bitset<64> &bits) 
{
    constexpr auto mask = bitmask<B, D, E, H, K, M, L, O>::value;
    bits &= mask;
}

Link do Compiler Explorer: https://godbolt.org/z/Gk6KX1

Zaletą tego podejścia w porównaniu z funkcją constexpr szablonu jest to, że kompilacja jest potencjalnie nieco szybsza z powodu reguły Chiel .

Jest tu sporo do „sprytnych” pomysłów. Prawdopodobnie nie pomagasz w utrzymaniu, przestrzegając ich.

jest

{B, D, E, H, K, M, L, O};

o wiele łatwiejsze do napisania niż

(B| D| E| H| K| M| L| O);

?

Wtedy żadna reszta kodu nie jest potrzebna.