“Bukankah ini waktunya, teman-temanku, bagi kita untuk mengayunkan William, Anda tahu, Shakespeare kita? ".
Baru-baru ini saya membaca posting tentang keyboard khusus dan sekali lagi berpikir bahwa akan menyenangkan untuk menulis referensi (yaitu, yang tidak malu untuk menandatangani dengan namanya dan meletakkannya di layar publik) implementasi keyboard. Gagasan ini tidak datang kepada saya untuk pertama kalinya, tetapi entah bagaimana berhenti pada tahap pertama - membaca informasi awal, karena saya ingin membuat tahap ini mudah disesuaikan, nyaman digunakan, universal dan efektif, dan saya tidak suka tawaran "pilih dua".
Catatan yang diperlukan - Saya melihat 4 lapisan implementasi keyboard: 0 - deteksi peristiwa, 1 - pembacaan data, 2 - pembersihan dan penyimpanan data, pembuatan 3 - pesan, 4 - transcoding, dll. Yang paling menjanjikan untuk layer 1 dan layer 0 yang terkait dengannya menurut saya adalah penggunaan templat Anton Chizhov untuk bekerja dengan pin MK (berdasarkan kelas Loki) dan, mungkin, suatu hari nanti, hasil yang dihasilkan tidak akan malu untuk dibagikan, tetapi tentu saja tidak hari ini. Sekarang saya sedang memikirkan layer 2.
Mari kita merumuskan masalah - perlu untuk menyimpan informasi tentang satu set tetap switch yang mengambil salah satu dari dua nilai yang telah ditentukan - "ditutup" dan "tidak ditutup". Kandidat yang paling alami adalah variabel boolean dan perpustakaan bitset, sebagai cara untuk menyimpan satu set. Karena persyaratan efisiensi adalah keharusan kategoris, diinginkan untuk mengevaluasi implementasi modul dari sudut pandang ini.
Pikiran pertama saya adalah melihat kode sumber dan semuanya segera menjadi jelas, tetapi setelah berkenalan singkat dengan mereka, saya menyadari bahwa mempelajari tentang templat orang lain tidak terlalu menarik (dan tidak terlalu produktif). Selain itu, sumber tidak memberikan penilaian yang akurat tentang efektivitas implementasi, karena langsung ditutup ke kompiler. Faktanya, teks sumber masih harus dipelajari, jika tidak mengubahnya menjadi proses yang sangat panjang (kecuali, tentu saja, kami tertarik untuk mencapai hasil tertentu), tetapi ini adalah topik untuk posting yang terpisah.
Oleh karena itu, teknik mempelajari "kotak hitam" diadopsi - kami memberi makan berbagai fragmen kode ke input dan mempertimbangkan assembler yang dihasilkan. Sayangnya, tidak mungkin untuk menggunakan situs godbolt favorit untuk arsitektur AVR yang sudah dikenal, karena tidak ada perpustakaan yang sedang dipelajari dalam implementasi ini. Anda tentu saja dapat menyeretnya dengan pena, tetapi tidak ada jaminan bahwa itu akan menjadi kode sumber yang benar.
Karena itu, kita akan melihat arsitektur yang berbeda. x51 tidak disajikan untuk kompiler gcc, saya tidak pernah menyukai x86, ARM memiliki assembler yang tidak nyaman (untuk seseorang) dan dimengerti, MIPS sangat spesifik dan tidak terlalu umum, semua jenis SPARC bahkan lebih buruk (well, well, saya tidak akan menyinggung siapa pun dengan arsitektur favorit Anda, tidak lebih baik), tetapi ada kandidat besar MSP430, yang didasarkan pada arsitektur PDP dan TI yang jernih dan elegan tidak bisa merusaknya banyak (meskipun orang-orang mencoba). Perpustakaan banyak bit untuk arsitektur ini disajikan, sehingga Anda dapat mulai belajar.
Mari kita mulai, karena kedengarannya tidak sepele, dari awal, yaitu dengan pengumuman orang banyak. Segera kita akan melihat bahwa memori untuk penyimpanan dialokasikan dalam kata-kata empat-byte, terlepas dari fakta bahwa unit alami dalam arsitektur ini adalah kata dua-byte, dan disediakan kerja byte dan byte yang cukup nyaman dan efisien, yang mengarah pada insiden aneh. Anda dapat memahami pembuatnya, penerapan angka 32-bit harus ada di mana-mana dan mengandalkannya secara alami, tetapi dalam hal ini, 8-bit lebih disukai, dan untuk AVR, 8-bit akan menjadi satu-satunya solusi yang masuk akal.
Sebuah pertanyaan yang menarik, tetapi bagaimana Anda bisa menentukan kedalaman bit arsitektur selama proses kompilasi, Anda perlu mencoba melalui uint8_t_fast. Kami mencatat kemungkinan pengoptimalan dan melanjutkan.
Selain mengalokasikan memori, inisialisasi menarik - untuk set global itu dilakukan dengan cara standar - penekanan sebelum memanggil utama, untuk set lokal juga dilakukan dengan cara standar, yaitu, sama sekali tidak jika nilai awal tidak ditentukan secara eksplisit. Nah, dan, seperti biasa, jika mungkin untuk menggambarkan set statis dengan nilai awal di luar fungsi, ini harus digunakan agar tidak menyalakan flag yang tidak perlu dan tidak menghabiskan waktu eksekusi pada mereka. Tapi di sini kami tidak mengharapkan wahyu, kami hanya memeriksa aturan umum.
Mari kita mulai bekerja dengan memodifikasi set, di mana kita telah meninggalkan tanda kurung siku dan mengatur dan mengatur ulang metode. Kita bisa berharap melihat sesuatu seperti ini untuk mengatur elemen n di set M:
M[n / w] |= (1<<(n % w))
di mana w adalah jumlah bit dalam elemen dasar, yang untuk arsitektur tertentu, n didefinisikan secara statis (misalnya, 4) dan optimasi yang disertakan mengarah ke kode bentuk:
bis.w #0x0010, m
Memang, kita melihat kode seperti itu di bagian kanan jendela, dan tidak mungkin ada orang yang mau mengambil risiko serius dengan menyatakan bahwa solusi yang lebih efektif adalah mungkin. Tapi ini hanya untuk kondisi yang ditunjukkan, untuk sewenang-wenang dan gambar benar-benar berubah, untuk metode kami mengamati validasi argumen untuk diterimanya dengan generasi pengecualian yang sesuai, dan untuk kurung kita melihat pembatasan argumen dengan topeng bit dari kisaran yang diperbolehkan dengan perilaku yang tidak dapat ditentukan sepenuhnya dapat diprediksi, kedua kasus cukup konsisten dengan dokumentasi. Nilai negatif diproses dengan benar, karena indeks dianggap sebagai angka yang tidak ditandatangani.
Kami menarik perhatian pada fakta bahwa nilai yang ditetapkan untuk elemen himpunan tidak hanya 0 dan 1, seperti yang diharapkan, tetapi juga bilangan bulat mana aturan “Apa itu unit? Bukan nol ”, ini cukup logis, tetapi kurang tercermin dalam dokumentasi. Agak aneh dilakukan, namun nilai-nilai Boolean akan lebih alami, centang dan teruskan.
Perbandingan kode yang dihasilkan untuk kasus jumlah elemen statis yang tidak ditentukan dari set menunjukkan bahwa efisiensi kode dalam kedua kasus ([] dan metode) sangat dekat dan kecil, karena subrutin dari perpustakaan standar dipanggil untuk menghitung (1 << n), dan subrutin ini bergeser Nomor 32-bit 0x00000001, ditempatkan dalam dua register. Kita tidak dapat melihat teks sumbernya, tetapi fakta dari panggilan itu mengarah pada pemikiran yang menyedihkan. Faktanya adalah bahwa dalam arsitektur yang dipertimbangkan tidak ada pergeseran ke kiri (dan juga tidak ada kanan) dengan jumlah posisi yang sewenang-wenang, seperti dalam semua (banyak) ARM tercinta. Ada pergeseran dengan 1 posisi (akan aneh jika tidak ada sama sekali), ada pergeseran dengan 2,3,4 posisi (tetapi dengan angka yang benar-benar diperbaiki dalam perintah, bukan oleh parameter), ada awalan REPT (tetapi kecepatan eksekusi tetap di berharap yang terbaik). Anda dapat menerapkan pergeseran unit terkecil (ini penting, hanya satu unit), yaitu, memperoleh bit mask dengan jumlah bit dalam waktu yang relatif singkat dengan trik seperti bertukar tetrads, tetapi ini akan menjadi bagian yang sangat tergantung dan, secara umum, lebih baik tidak melakukannya.
Oleh karena itu, metode universal dan cepat adalah menyimpan bit mask dalam array dan indeks, dan pada arsitektur ini juga sangat efisien, kodenya kemudian terlihat seperti ini:
M[n/w] |= BitArray[n %w]
mendapatkan assembler seperti:
bis.b BitArray(r0),M(r1)
Karena kita berbicara tentang pola dan w adalah kelipatan dari ukuran byte, operasi divisi diimplementasikan dengan sangat efisien di sini. Kami mencatat keuntungan yang jelas dari elemen penyimpanan yang diimplementasikan secara minimal: untuk byte, array 8 byte diperlukan untuk byte, -2 * 16 = 32 byte untuk organisasi kata, dan 4 * 32 = 128 byte untuk kata panjang 32 bit untuk menyimpan semua yang diperlukan topeng, mengapa membayar lebih jika hasilnya tidak berubah. Mari kita ingat satu kemungkinan optimasi lagi dan lanjutkan.
Kami mencatat satu fakta lagi - implementasi operasi yang jauh lebih efisien dengan elemen set dimungkinkan jika arsitektur target memiliki wilayah memori bertanda-bit (di sini sekali lagi, ARM yang ditolak sebelumnya dipanggil kembali), di mana operasi instalasi elemen umumnya berubah menjadi BitSetAddr [n] = pumpkin 1, yang diterjemahkan menjadi satu perintah assembler untuk konstanta n, tetapi sudah ada pergeseran yang cukup efektif di sana, sehingga optimasi seperti itu akan lebih berlebihan, terutama dengan mempertimbangkan keterbatasannya. Pada prinsipnya, ada area pengalamatan bit yang serupa di kedua x51 dan AVR, tetapi ada perintah yang efektif hanya untuk nomor elemen konstan, dan dengan kasus umum, semuanya tidak begitu baik (terus terang buruk).
Nah, sekarang perhatikan dengan teliti kode yang dihasilkan dan perhatikan bahwa kami mengamati artefak yang terkait dengan menyimpan set dalam kata-kata ganda. Kompiler untuk operasi memodifikasi elemen set menghasilkan urutan perintah yang membaca kata ganda yang sesuai dari memori menjadi 2 register (saya ingat bahwa kita memiliki register 16-bit), memodifikasi mereka dan mengirimkan hasilnya kembali ke memori. Jika kita mengubah hanya satu elemen, maka mask operasi akan berisi tepat satu dari 32 kemungkinan, nol yang tersisa. Ketika kami menerapkan nomor elemen yang ditentukan secara statis, operasi yang tidak mengubah hasilnya harus dikecualikan pada tahap optimisasi. Sebagai aturan, ini terjadi, tetapi untuk berbagai operan terjadi kesalahan dan artefak formulir bocor ke kode akhir:
bic #0,r0
yang terlihat sangat lucu jika Anda perhatikan bahwa register tidak ditulis kembali ke memori, meskipun sudah dibaca. Sebenarnya, hasil pengoptimalan tidak diatur di mana pun, sehingga dapat berupa apa saja, dan tidak ada yang perlu disinggung, tapi, "tidak rapi bagaimana hasilnya." Kami tidak dapat secara langsung memengaruhi proses ini, jika kami tidak secara serius mempertimbangkan kode sumber kompiler, jadi mari kita bypass - kami akan membantu pengoptimal dengan menyederhanakan tugasnya.
By the way, saya masih tidak dapat menemukan jawaban atas pertanyaan - apakah mungkin dalam C ++ di tingkat makro atau template untuk mendefinisikan implementasi yang berbeda untuk yang ditentukan secara statis pada tahap kompilasi terhadap parameter yang tidak ditentukan secara statis. Jika ada yang tahu cara samurai, beri tahu saya di komentar, saya mencoba constexpr, itu tidak berhasil.
Kami melanjutkan penelitian kami dan menemukan bahwa kompiler mengoptimalkan panggilan secara tidak terkendali ke set (tentu saja, jika optimasi dihidupkan), yaitu, urutan pemasangan / pembersihan berbagai elemen sama sekali tidak dijamin dan sama sekali tidak terhubung dengan urutan operator kode sumber. Tapi saya gagal membuat set volatil, mungkin saya melakukan sesuatu yang salah? Seperti dalam kasus optimasi lokal, panggilan ke fungsi eksternal memaksa kompiler untuk memaksa semua operasi yang disiapkan untuk array global, tetapi ini adalah solusi yang terlalu kuat dan tidak membantu dengan yang lokal. Yah, mungkin tidak ada yang harus dilakukan, dan Anda hanya perlu mempertimbangkan fitur serupa dan tidak menggunakan set untuk mentransfer informasi antara stream menggunakan antarmuka serial (yaitu, perangkat lunak rekan-rekan mereka).
Kesimpulan umum dapat dibuat: penggunaan bitset dalam bentuknya saat ini untuk arsitektur dengan sumber daya terbatas tidak dapat direkomendasikan karena biaya yang berlebihan baik dalam memori maupun dalam runtime. Kemungkinan modifikasi, yang memperhitungkan semua data pada teks komentar, terletak pada Github, semua orang dapat menggunakannya. Sejarah penciptaan mod ini akan segera diposting di Habré, ada momen lucu.
Sebagai kesimpulan, sebuah komentar kecil - implementasi data warehouse "head-on", bahkan pada versi yang dioptimalkan dari set, akan membutuhkan N / 8 byte memori data (untuk 128 switch, 16 byte akan diperlukan) dan meskipun operasi akan membutuhkan O (1) waktu, pengganda akan banyak unit ( dan bahkan hingga 10 atau lebih) siklus MK. Oleh karena itu, dengan mempertimbangkan persyaratan masalah dan memperkenalkan batasan tertentu, kami dapat menawarkan implementasi alternatif penyimpanan data.
Jika kami percaya bahwa tidak lebih dari satu sakelar dapat ditutup kapan saja (kami mengabaikan yang lainnya hingga tombol yang ditekan saat itu terbuka), maka kami dapat memintas satu byte (asalkan tidak ada lebih dari 256 sakelar) dan menulis / membaca akan mengambil siklus prosesor O (1), dan pengganda akan cukup sederhana.
Pendekatan ini mudah untuk memperluas dan menyimpan informasi tentang ditutup secara bersamaan n switch, tetapi Anda tidak boleh membuat n terlalu besar, karena jumlah memori yang diperlukan meningkat, dan waktu untuk melakukan operasi inversi meningkat secara linier dengan peningkatan jumlah elemen dalam set, meskipun tetap O (1) oleh dalam kaitannya dengan jumlah sakelar. Peningkatan waktu yang ditunjukkan dapat dikurangi secara signifikan menggunakan implementasi segitiga dari pohon biner menjadi O (loq2 (n)), tetapi untuk n kecil ini tidak begitu penting. Ya, dan diragukan bahwa kompleksitas penghitungan indeks selanjutnya selama pencarian akan mengimbangi penurunan jumlah iterasi sederhana. Kerugian dari implementasi ini termasuk kemungkinan kegagalan untuk mencatat elemen set, yang harus diproses dalam program panggilan (kami menolak opsi dengan mengubah ukuran buffer segera dan dengan kemarahan - ini bukan untuk solusi bawaan).
Implementasi pendekatan ini akan diberikan di sana.