Bagaimana cara menulis bit-mask yang dapat dipelihara, cepat, waktu kompilasi di C ++?

Saya punya beberapa kode yang kurang lebih seperti ini:

#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 melakukan hal yang cerdas dan mengkompilasi ini menjadi satu andinstruksi (yang kemudian disisipkan di tempat lain):

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

Tetapi setiap versi GCC yang saya coba mengkompilasi ini menjadi kekacauan besar yang mencakup penanganan kesalahan yang seharusnya DCE secara statis. Dalam kode lain, ia bahkan akan menempatkan important_bitspadanan sebagai data sesuai dengan kode!

.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*, ...)

Bagaimana saya harus menulis kode ini sehingga kedua kompiler dapat melakukan hal yang benar? Jika gagal, bagaimana saya harus menulis ini agar tetap jelas, cepat, dan mudah dipelihara?

Versi terbaik adalah c ++ 17:

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

Kemudian

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

kembali c ++ 14, kita bisa melakukan trik aneh ini:

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;
}

atau, jika kita terjebak dengan c ++ 11, kita bisa menyelesaikannya secara rekursif:

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 dengan semua 3 - Anda dapat mengganti CPP_VERSION mendefinisikan, dan mendapatkan perakitan identik.

Dalam praktiknya, saya akan menggunakan yang paling modern yang saya bisa. 14 ketukan 11 karena kita tidak memiliki rekursi dan karenanya panjang simbol O (n ^ 2) (yang dapat meledakkan waktu kompilasi dan penggunaan memori kompilator); 17 mengalahkan 14 karena kompiler tidak harus menghilangkan kode-mati dari array itu, dan trik array itu jelek.

Dari jumlah tersebut 14 adalah yang paling membingungkan. Di sini kita membuat array anonim semua 0s, sedangkan sebagai efek samping mengkonstruksi hasil kita, kemudian membuang array tersebut. Array yang dibuang memiliki angka 0 di dalamnya yang sama dengan ukuran paket kami, ditambah 1 (yang kami tambahkan sehingga kami dapat menangani paket kosong).

Penjelasan rinci tentang apa itu c ++ 14versi sedang dilakukan. Ini adalah trik / peretasan, dan fakta bahwa Anda harus melakukan ini untuk memperluas paket parameter dengan efisiensi di C ++ 14 adalah salah satu alasan mengapa ekspresi lipat ditambahkanc ++ 17.

Paling baik dipahami dari dalam ke luar:

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

ini hanya diperbarui rdengan 1<<indexesuntuk indeks tetap. indexesadalah paket parameter, jadi kita harus mengembangkannya.

Sisa pekerjaannya adalah menyediakan paket parameter untuk diperluas indexesdi dalamnya.

Satu langkah keluar:

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

di sini kita mentransmisikan ekspresi kita ke void, menunjukkan kita tidak peduli tentang nilai kembaliannya (kita hanya ingin efek samping dari pengaturan r- dalam C ++, ekspresi seperti a |= bjuga mengembalikan nilai yang mereka setel a).

Kemudian kami menggunakan operator koma ,dan 0membuang void"nilai", dan mengembalikan nilainya 0. Jadi ini adalah sebuah ekspresi yang nilainya 0dan sebagai efek samping dari menghitung 0set sedikit di r.

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

Pada titik ini, kami memperluas paket parameter indexes. Jadi kami mendapatkan:

 {
    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),
  }

di {}. Penggunaan ,ini bukan untuk operator koma, melainkan pemisah elemen array. Ini sizeof...(indexes)+1 0s, yang juga mengatur bit rsebagai efek samping. Kami kemudian menetapkan {}instruksi konstruksi array ke array discard.

Selanjutnya kita mentransmisikan discardke void- kebanyakan kompiler akan memperingatkan Anda jika Anda membuat variabel dan tidak pernah membacanya. Semua kompiler tidak akan mengeluh jika Anda mentransmisikannya ke void, ini semacam cara untuk mengatakan "Ya, saya tahu, saya tidak menggunakan ini", jadi ini menekan peringatan.

Pengoptimalan yang Anda cari tampaknya berupa loop peeling, yang diaktifkan di -O3, atau secara manual dengan -fpeel-loops. Saya tidak yakin mengapa ini berada di bawah lingkup pengelupasan loop daripada pengulangan loop, tetapi mungkin tidak mau membuka gulungan dengan aliran kontrol nonlokal di dalamnya (karena ada, berpotensi, dari pemeriksaan rentang).

Secara default, GCC berhenti untuk dapat mengupas semua iterasi, yang tampaknya diperlukan. Secara eksperimental, meneruskan -O2 -fpeel-loops --param max-peeled-insns=200(nilai defaultnya adalah 100) menyelesaikan pekerjaan dengan kode asli Anda: https://godbolt.org/z/NNWrga

jika hanya menggunakan C ++ 11 adalah suatu keharusan (&a)[N]adalah cara untuk menangkap array. Ini memungkinkan Anda untuk menulis satu fungsi rekursif tanpa menggunakan fungsi pembantu sama sekali:

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;
}

menugaskannya ke 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;
}

Uji

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

Keluaran

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

seseorang benar-benar harus menghargai kemampuan C ++ untuk menghitung apa pun yang dapat dihitung pada waktu kompilasi. Itu pasti masih mengejutkan saya ( <> ).

Untuk versi C ++ 14 dan C ++ 17 yakk yang lebih baru, jawaban yakk sudah luar biasa mencakupnya.

Saya akan mendorong Anda untuk menulis EnumSettipe yang tepat .

Menulis dasar EnumSet<E>dalam C ++ 14 (dan seterusnya) berdasarkan std::uint64_titu sepele:

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;
};

Ini memungkinkan Anda untuk menulis kode sederhana:

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

    flags &= IMPORTANT;
}

Di C ++ 11, ini membutuhkan beberapa konvolusi, tetapi tetap memungkinkan:

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;
};

Dan dipanggil dengan:

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;
}

Bahkan GCC anddengan -O1 mudahnya menghasilkan instruksi di godbolt :

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

Sejak C ++ 11 Anda juga dapat menggunakan teknik TMP klasik:

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;
}

Tautan ke Compiler Explorer: https://godbolt.org/z/Gk6KX1

Keuntungan dari pendekatan ini dibandingkan fungsi template constexpr adalah bahwa itu berpotensi sedikit lebih cepat untuk dikompilasi karena aturan Chiel .

Ada beberapa ide yang jauh untuk 'pintar' di sini. Anda mungkin tidak membantu pemeliharaan dengan mengikuti mereka.

adalah

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

jauh lebih mudah untuk menulis daripada

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

?

Maka tidak ada sisa kode yang diperlukan.