Apakah ada keuntungan untuk manipulasi bit c-style dibandingkan std :: bitset?

Saya bekerja hampir secara eksklusif di C ++ 11/14, dan biasanya merasa ngeri ketika saya melihat kode seperti ini:

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

Ini hanya sebuah contoh; Saya berbicara tentang manipulasi bit-bijaksana secara umum. Dalam C ++, apakah benar-benar ada gunanya? Di atas membingungkan dan rawan kesalahan, sementara menggunakan std::bitsetmemungkinkan Anda untuk:

1. lebih mudah memodifikasi ukuran std::bitsetsesuai kebutuhan dengan menyesuaikan parameter template dan membiarkan implementasi mengurus sisanya, dan
2. menghabiskan lebih sedikit waktu untuk mencari tahu apa yang terjadi (dan mungkin membuat kesalahan) dan menulis std::bitsetdengan cara yang mirip dengan std::arrayatau wadah data lainnya.

Pertanyaanku adalah; adakah alasan untuk tidak menggunakan std::bitsetlebih dari tipe primitif, selain untuk keterbelakangan-mundur?

Dari sudut pandang logis (non-teknis), tidak ada keuntungan.

Kode C / C ++ biasa dapat dibungkus dengan "pustaka konstruksi" yang sesuai. Setelah pembungkusan seperti itu, masalah "apakah ini lebih menguntungkan dari itu" menjadi pertanyaan yang bisa diperdebatkan.

Dari sudut pandang kecepatan, C / C ++ harus memungkinkan pustaka membangun untuk menghasilkan kode yang seefisien kode polos yang dibungkusnya. Namun ini tunduk pada:

• Fungsi inlining
• Pengecekan waktu kompilasi dan penghapusan pemeriksaan runtime yang tidak perlu
• Penghapusan kode mati
• Banyak optimasi kode lainnya ...

Menggunakan argumen non-teknis semacam ini, "fungsi apa pun yang hilang" dapat ditambahkan oleh siapa saja, dan karenanya tidak dianggap sebagai kerugian.

Namun, persyaratan dan batasan bawaan tidak dapat diatasi dengan kode tambahan. Di bawah ini, saya berpendapat bahwa ukuran std::bitsetadalah konstanta waktu kompilasi, dan oleh karena itu meskipun tidak dihitung sebagai kerugian, itu masih sesuatu yang mempengaruhi pilihan pengguna.

Dari sudut pandang estetika (keterbacaan, kemudahan pemeliharaan, dll), ada perbedaan.

Namun, tidak jelas bahwa std::bitsetkode langsung menang atas kode C polos. Kita harus melihat potongan kode yang lebih besar (dan bukan sampel mainan) untuk mengatakan apakah penggunaan std::bitsettelah meningkatkan kualitas manusia dari kode sumber.

Kecepatan manipulasi bit tergantung pada gaya pengkodean. Gaya pengkodean mempengaruhi manipulasi bit C / C ++, dan sama-sama berlaku std::bitsetjuga, seperti dijelaskan berikut ini.

Jika seseorang menulis kode yang menggunakan operator []membaca dan menulis satu bit pada satu waktu, seseorang harus melakukan ini beberapa kali jika ada lebih dari satu bit yang akan dimanipulasi. Hal yang sama dapat dikatakan tentang kode gaya-C.

Namun, bitsetjuga memiliki operator lain, seperti operator &=, operator <<=, dll, yang beroperasi pada lebar penuh bitset tersebut. Karena mesin yang mendasarinya sering dapat beroperasi pada 32-bit, 64-bit dan kadang-kadang 128-bit (dengan SIMD) pada suatu waktu (dalam jumlah siklus CPU yang sama), kode yang dirancang untuk mengambil keuntungan dari operasi multi-bit tersebut bisa lebih cepat dari kode manipulasi bit "loopy".

Gagasan umum disebut SWAR (SIMD dalam register) , dan merupakan subtopik dengan manipulasi bit.

Beberapa vendor C ++ mungkin menerapkan bitsetantara 64-bit dan 128-bit dengan SIMD. Beberapa vendor mungkin tidak (tetapi mungkin akhirnya melakukannya). Jika ada kebutuhan untuk mengetahui apa yang dilakukan pustaka vendor C ++, satu-satunya cara adalah dengan melihat pembongkaran.

Seperti apakah std::bitsetmemiliki keterbatasan, saya bisa memberikan dua contoh.

1. Ukuran std::bitsetharus diketahui pada waktu kompilasi. Untuk membuat array bit dengan ukuran yang dipilih secara dinamis, kita harus menggunakannya std::vector<bool>.
2. Spesifikasi C ++ saat ini untuk std::bitsettidak menyediakan cara untuk mengekstrak sepotong berturut-turut N bit dari bitsetM bit yang lebih besar .

Yang pertama adalah fundamental, artinya bagi orang yang membutuhkan bitet berukuran dinamis, mereka harus memilih opsi lain.

Yang kedua dapat diatasi, karena seseorang dapat menulis semacam adapter untuk melakukan tugas, bahkan jika standarnya bitsettidak dapat diperluas.

Ada beberapa jenis operasi SWAR lanjutan yang tidak disediakan di luar kotak std::bitset. Orang dapat membaca tentang operasi ini di situs web ini tentang permutasi bit . Seperti biasa, seseorang dapat mengimplementasikan ini sendiri, beroperasi di atas std::bitset.

Mengenai diskusi tentang kinerja.

Satu peringatan: banyak orang bertanya mengapa (sesuatu) dari perpustakaan standar jauh lebih lambat daripada beberapa kode gaya C sederhana. Saya tidak akan mengulangi pengetahuan prasyarat tentang microbenchmarking di sini, tetapi saya hanya memiliki saran ini: pastikan untuk melakukan benchmark dalam "mode rilis" (dengan optimisasi diaktifkan), dan pastikan kode tidak dihilangkan (penghilangan kode mati) atau sedang diangkat dari loop (gerakan kode invarian loop) .

Karena secara umum kita tidak dapat mengatakan apakah seseorang (di internet) melakukan microbenchmarks dengan benar, satu-satunya cara kita bisa mendapatkan kesimpulan yang dapat diandalkan adalah dengan melakukan microbenchmarks kita sendiri, dan mendokumentasikan detailnya, dan menyerahkan kepada publik tinjauan dan kritik. Tidak ada salahnya untuk melakukan microbenchmark yang telah dilakukan orang lain sebelumnya.

Ini tentu saja tidak berlaku dalam semua kasus, tetapi kadang-kadang suatu algoritma mungkin tergantung pada efisiensi tw-bit-style C untuk memberikan keuntungan kinerja yang signifikan. Contoh pertama yang muncul di benak saya adalah penggunaan bitboard , pengkodean integer yang pintar dari posisi permainan papan, untuk mempercepat mesin catur dan sejenisnya. Di sini, ukuran tetap dari tipe integer tidak ada masalah, karena papan catur selalu 8 * 8.

Untuk contoh sederhana, pertimbangkan fungsi berikut (diambil dari jawaban ini oleh Ben Jackson ) yang menguji posisi Connect Four untuk menang:

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