Untuk pertanyaan tentang buffer (dering)

"Jika Anda menemukan biaya pengembangan arsitektur berlebihan, pertimbangkan berapa banyak arsitektur yang salah dapat dikenakan biaya"

- Saya tidak ingat persis sumbernya

Suatu kali, "dahulu sekali, di satu galaksi yang jauh," saya membeli buku indah Charles Weatherly "Etudes for Programmers", dalam pengantar yang penulis memperkuat kebutuhan untuk mempelajari contoh dan tugas pendidikan sebelum memulai pemrograman independen. Saya sangat menyarankan agar Anda menemukan buku ini, membaca kata pengantar (dan tanpa berhenti, membaca sisanya dan menyelesaikan masalah yang diberikan di dalamnya), karena saya tidak bisa lebih baik membuktikan perlunya praktik semacam itu. Bahkan jika Anda mengikuti rekomendasi saya, dan mendapatkan banyak pengetahuan dan keterampilan praktis saat membaca buku, Anda dapat kembali dan membaca posting ini, karena ini dikhususkan untuk beberapa masalah lain. Dan jika Anda tidak mengikuti rekomendasi saya, maka semakin Anda harus pergi di bawah kucing.

Belum lama berselang di sebuah pos di mana saya memarahi saya menyatakan pendapat saya tentang satu RTOS domestik, saya menyebutkan bahwa implementasi buffer cincin di perpustakaan mcucpp yang terkenal (dan dalam aspek-aspek tertentu, benar-benar luar biasa) tidak dapat dianggap ideal. Saya akan mencoba menjelaskan sudut pandang saya dan membayangkan implementasi ideal (sejauh mungkin di dunia nyata). Catatan - teks yang ditawarkan kepada Anda terletak pada "belum selesai" untuk beberapa waktu, dan kemudian kasus yang nyaman muncul.

Kami terus mengembangkan perpustakaan untuk bekerja dengan perangkat periferal, dan kami berada di baris berikutnya untuk manajemen memori dan buffering (ya, kami masih melanjutkan operasi persiapan, tetapi tanpa mereka dengan cara apa pun). Dari mana datangnya kebutuhan untuk mengatur buffer dan hewan seperti apa itu? Faktanya adalah bahwa bagian penting dari pinggiran memiliki kecepatan terbatas dan proses transmisi, dimulai dengan satu atau lain cara, memerlukan waktu tertentu, dan kadang-kadang sangat signifikan dibandingkan dengan membuat bagian lain dari informasi untuk transmisi. Tentu saja, sebelum waktu ini berlalu, transmisi berikutnya tidak dapat dilakukan dan, karenanya, tidak dapat dimulai.

Kami memiliki casing klasik pasangan penulis-pembaca dengan kecepatan berbeda. Sangat tidak mungkin untuk menyelesaikan masalah ini secara umum, karena "dengan kelebihan kecil, tetapi tidak nol, dari aliran permintaan di atas aliran layanan, ukuran antrian cenderung tak terhingga," dan tak terhingga secara fundamental mustahil. Tetapi kasus khusus masalah, ketika kita memiliki semburan permintaan lokal, tetapi rata-rata aliran layanan mampu mengatasi beban, memori buffer kapasitas yang cukup dapat dipecahkan. Mari kita perhatikan frasa “kapasitas yang memadai”, kita nanti akan belajar bagaimana menghitungnya, selama fakta bahwa ini pada dasarnya memungkinkan sudah cukup bagi kita.

Apakah memori penyangga merupakan persyaratan mutlak, tentu saja tidak. Untuk informasi yang ditransmisikan, Anda dapat menggunakan catatan pemblokiran, tetapi dengan informasi yang diterima itu agak buruk, itu harus ditambahkan di suatu tempat sebelum diproses, jika Anda tidak mengambil langkah-langkah yang sesuai dalam protokol tingkat atas (ekspresi ajaib xon / xoff tidak dilahirkan dari awal), yang tidak selalu memungkinkan dan, dalam hal apa pun, biasanya mengarah pada batasan signifikan dari laju transmisi. Ada juga implementasi perangkat keras buffer internal di perangkat periferal (setidaknya untuk satu elemen), tetapi ini tidak selalu dilakukan dan ukuran buffer sangat terbatas dari atas.

Oleh karena itu, kami masih akan mengimplementasikan buffer program, yang wajar jika menggunakan metode FIFO (yaitu, antrian) untuk mengatur buffer tersebut, dan antrian tersebut, paling baik diimplementasikan pada buffer cincin dengan dua pointer. Ketika saya menulis "terbaik", ini tidak berarti sama sekali bahwa implementasi lain (misalnya, antrian referensi) tidak mungkin, atau memiliki kelemahan fatal selain fatal. Ungkapan ini hanya berarti bahwa implementasinya tidak akan terlalu rumit dan cukup efektif, walaupun yang lain mungkin memiliki kelebihan yang tidak dapat disangkal darinya, yang mana mereka harus membayar untuk sesuatu, karena DarZaNeBy.

Karena sangat tidak mungkin bahwa model MK Anda akan memiliki implementasi perangkat keras dari perangkat serba guna (modul periferal individu dapat memiliki buffer cincinnya sendiri, tetapi tidak ada hubungannya dengan topik tulisan ini), kami harus membuat buffer cincin dalam memori linier (diterapkan pada vektor, ini, secara umum, satu-satunya objek alami dalam memori yang dapat dialamatkan), dan untuk ini, indeks buffer (atau mungkin bahkan dua indeks, tetapi lebih lanjut tentang itu nanti) akan diperlukan. Menurut pendapat saya, buffer melingkar dengan dua pointer (indeks) adalah satu-satunya cara yang dapat diterima untuk mengimplementasikan antrian pada vektor, tetapi ada sudut pandang yang berbeda tentang masalah ini dan saya melihat dengan mata kepala sendiri sebuah implementasi dalam gaya “x1 = x2; x2 = x3; ... x8 = simbol baru ", jika Anda mau, saya tidak akan mempertimbangkan eksotis semacam itu. Fakta bahwa fragmen yang diberikan mungkin memiliki hak untuk eksis dalam situasi tertentu yang sangat terbatas tidak membuatnya diterima secara umum.

Kami akan mempertimbangkan implementasi yang benar dari modul program untuk mengatur pointer, dan untuk mulai dengan, perhatikan kata pertama dalam definisi. Perbedaan antara kode yang benar dan salah bukan hanya karena kode yang benar tidak mengandung kesalahan, meskipun ini merupakan persyaratan mutlak. Bahkan kode yang sepenuhnya menjalankan fungsinya mungkin salah jika tidak dapat dipahami, atau jika ada opsi yang tidak kurang jelas, tetapi berjalan lebih cepat, atau dieksekusi dengan cepat, tetapi ditulis lebih jelas, sehingga konsep kebenaran agak relatif. Kami melanjutkan pertimbangan kami terhadap contoh implementasi buffer kami, yang akan memungkinkan kami untuk menunjukkan perbedaan antara berbagai tingkat kebenaran.

Sebelum beralih ke esensi, satu poin penting tentang pembahasan lebih lanjut. Maksud saya, kompiler Anda selalu dihidupkan pada tingkat otpimisasi non-nol (-O2), jadi kami tidak perlu memikirkan perbaikan kecil seperti 1) modifikasi awalan versus postfix, atau 2) menggunakan hasil operasi sebelumnya, atau 3) perbedaan antara kenaikan dan penambahan unit dan seterusnya - kita mengasumsikan bahwa kompiler akan melakukan banyak hal untuk kita. Tentu saja, ini bukan asumsi yang ketat, tetapi kalau tidak kita harus terjun ke perut assembler, yang pada zaman kita bukanlah arus utama.

Biarkan saya mengingatkan Anda bahwa kami diperintahkan untuk menerapkan indeks (pointer) dari buffer cincin, yaitu, kita perlu membuat perilaku variabel yang secara berurutan berjalan melalui serangkaian nilai, dari beberapa awal hingga akhir . Segera berasumsi bahwa nilai awal akan nol, jika tidak kita akan segera harus menulis kode yang kurang lebih benar, dan ini bertentangan dengan tujuan pendidikan dan kami tidak terburu-buru, dan yang terakhir adalah Max.

Perilaku variabel ini dapat diimplementasikan menggunakan konstruksi berikut:

volatile int Counter = 0; Counter = (++Counter) % (Max+1); 

dan justru kode tersebut yang dapat kita lihat dalam banyak kasus (yaitu, sangat sering). Apa yang salah - yah, pertama, untuk beberapa waktu (dari melakukan operasi kenaikan hingga penetapan hasil) variabel kami akan lebih besar dari nilai maksimum yang diijinkan dan, jika pada saat itu terjadi interupsi yang perlu memperhitungkan nilai variabel ini, maka saya pribadi memprediksi Saya tidak menganggap hasilnya. Karena itu, kami menulis ulang program:

 int Counter=0; Counter = (Counter + 1) % (Max + 1); 

Kami telah menghilangkan satu kesalahan, dan kode tersebut (selanjutnya saya maksudkan kode "executable" berarti kode yang dapat dieksekusi yang dihasilkan oleh kompiler) tidak menjadi lebih lama dan dijalankan tidak lagi (pada kenyataannya, ia mengeksekusi lebih cepat, tetapi hanya karena dalam versi pertama kata volatile digunakan sepenuhnya berlebihan dalam hal ini), dan belum menjadi kurang jelas (lebih tepatnya, bahkan lebih jelas, tetapi ini adalah masalah selera).

Catatan yang diperlukan tentang volatile - direktif ini diperlukan jika kita ingin menghindari optimasi kode yang mengarah pada eksekusi yang salah, dan dalam kasus khusus ini (ketika nilai variabel tidak berubah di luar ruang lingkup modul dan tidak ada entri berurutan di dalamnya) itu (direktif ) sepenuhnya berlebihan. Saya sangat menyarankan Anda melihat kode yang dihasilkan untuk kedua opsi di godbolt.org. Mengapa Anda tidak boleh menyalahgunakan arahan volatile, tidak seperti kata kunci statis, yang direkomendasikan untuk digunakan sedapat mungkin. Yah, pertama, kami melarang pengoptimalan, yaitu, kode pasti tidak akan menjadi lebih cepat (kemungkinan besar, itu akan menjadi lebih besar dan lebih lambat, tetapi kami lebih suka formulasi yang ketat). Dan kedua, dalam kasus khusus ini, kata ini menyesatkan, karena dalam kaitannya dengan program kami, nilai penghitung sama sekali tidak dapat berubah di luar kendali kami. Dalam sebuah program yang membaca nilainya - yaitu, dalam implementasi buffer cincin itu sendiri, Anda dapat mempertimbangkan penghitung sebagai bisa berubah di luar modul, dan itu dipertanyakan, oleh karena itu atribut ini sama sekali tidak berlaku untuk penghitung. Jika satu variabel harus ditafsirkan berbeda dalam modul yang berbeda, layanan kami harus digabungkan, jika kita berbicara tentang pengorganisasian bagian kritis, misalnya, ketika menerapkan transaksi atau operasi atom, maka arahan ini tidak memberikan apa-apa sama sekali.

Kami kembali ke kode dan melihat bahwa programnya masih salah - ada apa - dan faktanya itu bukan apa yang kita butuhkan (lihat uraian tugas), tetapi sesuatu yang lain (menghitung sisa divisi), hanya hasilnya cocok Yah, kami pikir begitu (saya tidak berpikir begitu, tetapi penulis kode pasti), bahwa hasilnya bertepatan, pada kenyataannya, dalam kasus umum, mereka tidak bertepatan, kami hanya beruntung dengan kisaran variabel (nilai positif). Selain itu, proses mengeksekusi kode lebih lama daripada yang bisa dilakukan, karena dalam kasus terbaik kami memiliki operasi divisi integer (jika itu adalah bagian dari perintah arsitektur kami), dan itu dilakukan dengan cara tidak berarti dalam satu siklus prosesor (nilai karakteristik 10 siklus) untuk arsitektur 8-bit), dan dalam kasus terburuk, kita akan melihat panggilan prosedur pembagian dari pustaka standar (dan juga, jika divisi pendek), maka waktu eksekusi akan menjadi puluhan siklus clock.

Jadi mengapa pendekatan yang benar-benar salah seperti itu masih mungkin untuk bertemu sangat sering. Di sini dari audiens mereka mengatakan kepada saya bahwa dengan nilai Max + 1, yang merupakan kekuatan dua, kompiler akan menebak alih-alih operasi pembagian, menempatkan operasi penggandaan bitwise pada topeng yang sesuai (sama dengan Max), yang akan dilakukan dengan sangat cepat dan semuanya akan baik-baik saja.

Saya setuju dengan pernyataan ini dan mengambil pendekatan ini, jika bukan karena keadaan berikut:

• ini hanya mungkin untuk Mach yang ditentukan secara statis pada tahap kompilasi,
• ini hanya terjadi ketika optimasi diaktifkan,
• ini hanya terjadi ketika Mach memenuhi kondisi ini,
• ini tidak terjadi untuk semua jenis kardinal.

Selain itu, dalam kasus khusus ini (ketika variabel didefinisikan sebagai tanda), di samping perintah mengalikan (logis) dengan mask, perintah perbandingan dengan nol dan cabang untuk nilai negatif akan dihasilkan, dan meskipun cabang ini tidak akan pernah untuk jangkauan kami itu akan dieksekusi, itu akan memakan ruang dalam memori (dan dalam kasus fungsi yang dapat diganti, itu akan memakan waktu beberapa kali) dan itu akan memakan waktu untuk melakukan operasi perbandingan, jika Anda tidak percaya, sekali lagi kita ikuti situs yang ditunjukkan dan lihat sendiri. Argumen lain yang mendukung para kardinal yang tidak bertanda tangan, yang baru-baru ini saya baktikan seluruh pos.

Oleh karena itu, jika kita ingin menggunakan perkalian logis dengan topeng (diperoleh dengan mengoptimalkan perhitungan sisanya), maka kita harus menulis ulang modul sesuai:

 typedef uint8_t Counter_t; typedef int8_t sCounter_t; static inline Counter_t NextCounter(const Counter_t Counter) { #if IS_POWER2(Max + 1) return (Counter + 1) & Max #else return (Counter + 1) % (Max + 1); #endif }; 

Dalam versi ini, semuanya sangat jelas dan dapat dikontrol dan semuanya benar (meskipun sejumlah kekurangan tetap ada, tetapi sekarang jelas dan tidak tertutup), oleh karena itu benar, meskipun lebih benar dan kami sekarang akan mencari mereka. Kelemahan utama, menurut pendapat saya, adalah pelanggaran prinsip KISS, karena penggunaan operasi sisanya oleh divisi benar-benar mengabaikan prinsip ini. Karena itu, kita sekarang akan menghancurkan semua kekurangan dengan satu pukulan (jangan khawatir tentang nasib mereka, mereka akan terlahir kembali 100.500 kali, karena tidak semua programmer untuk Arduino membaca posting saya).

Tapi pertama-tama, sedikit penyimpangan ke samping. Bagaimana kita bisa menerapkan pemeriksaan untuk kekuatan dua (angka biner dapat direpresentasikan sebagai {0} 1 {0}) yang baru saja kita gunakan


Dan bagaimana kita dapat mengimplementasikan verifikasi bahwa angka adalah urutan unit {0} 1 {1} yang benar dalam notasi biner - satu opsi sudah jelas

 #define IsRightSequence(N) IsPower2 ((N) + 1) 

dan yang kedua sepele

 #define IsRightSequence(N) ( (((N) + 1) & (N)) == 0) 

Catatan: Saya tidak dapat membantu tetapi mengingat teorema yang luar biasa: "Angka transendental dalam tingkat transendental selalu transendental, kecuali jika yang dibicarakan jelas atau sepele."

Dan bagaimana kita dapat memverifikasi bahwa angka adalah urutan unit {0} 1 {1} {0}

 #define IsSequence(N) IsPower2( (N) ^ ((N) << 1)) 

Dan akhirnya - cara memilih bit yang paling tidak signifikan (saya tidak tahu mengapa ini mungkin diperlukan, tetapi akan berguna)

 #define LowerBit(N) ((((N) - 1) ^ (N)) & (N)). 

Tapi dia datang dengan apa yang bisa berguna

 #define IsRightSequence(N) (IsSequence(N) && (LowerBit(N) == 1)) 

Pengamatan yang aneh - makro ini tidak sepenuhnya benar, ternyata 0 adalah kekuatan dua dan urutan yang benar (tentu saja, urutan yang juga), yang agak aneh. Tapi 1 adalah semua objek ini dengan benar, jadi nol, sepertinya, hanya perlu dipertimbangkan secara terpisah. Properti lain yang menarik dari makro ini adalah bahwa kami tidak membuat asumsi tentang panjang argumen, yaitu, mereka bekerja dengan benar dengan semua tipe kardinal.

Ada buku yang luar biasa, "Trik untuk Pemrogram," di mana Anda dapat menemukan makro yang disebutkan dan banyak tugas yang sama menyenangkan dan instruktif lainnya, saya sangat merekomendasikan membacanya, terutama karena tidak ada terlalu banyak surat di dalamnya.

Tetapi kembali ke indeks buffer cincin kami. Kami memberikan solusi yang tepat, tetapi berjanji lebih benar lagi, yang berarti bahwa solusi terakhir kami memiliki kekurangan (siapa yang meragukannya). Salah satunya - panjang buffer harus ditentukan secara statis pada tahap kompilasi, yang kedua - dalam hal panjang yang tidak berhasil, waktu eksekusi sangat panjang dan masih ada sejumlah kesalahan dalam sepotong program yang relatif kecil, yang membuat kita mengingat lelucon tentang 4 kesalahan dalam menulis kata "lebih". Kami akan menghilangkan semuanya (beberapa akan dibiarkan nanti) dan segera, untuk itu, akhirnya, kami akan menulis solusi untuk masalah awal seperti:

 static inline Counter_t NextCounter(const Counter_t Counter) { if ((Counter + 1) > Max) { return 0; } else { return Counter + 1; }; }; 

(Seperti yang sudah Anda pahami, saya adalah pendukung kurung Mesir dan tidak ada yang bisa dilakukan mengenai hal itu).

Mari kita perhatikan fakta bahwa kita hanya menulis ulang kondisi masalah dari bahasa alami dalam bahasa pemrograman yang dipilih, sehingga ternyata menjadi sangat jelas dan dapat dimengerti. Apakah mungkin untuk memperbaikinya - tidak diragukan lagi, tetapi hanya dari sudut pandang kecepatan kode, karena tidak ada kekurangan lain untuk solusi ini (tidak ada kekurangan yang jelas, sebenarnya ada dan kami akan berhasil menghilangkannya).

Mari kita evaluasi kompleksitas komputasi dari solusi ini - penambahan dengan kesatuan (1) dan perbandingan (2) selalu, kemudian menetapkan nol (1) (jarang) atau menambahkan (1) (hampir selalu) - yang memberikan 1 + 2 + 1 + Δ ~ 4 dasar operasi dan memori nol. Ada kemungkinan bahwa kompiler yang baik dalam mode yang tepat akan membuat optimasi tertentu dan mengurangi waktu eksekusi kode, tetapi lebih baik kita melakukannya secara eksplisit. Berikut adalah opsi berikut:

 static inline Counter_t NextCouner(const Counter_t Counter) { register sCounter_t Tmp; Tmp = (Counter + 1); if (Tmp > Max) { Tmp = 0; }; return Tmp; }; 

Kami mengevaluasi kompleksitas - penambahan dan perbandingan selalu, menetapkan nol (jarang) - sekitar 3 operasi dan satu elemen memori. Bahkan, versi sebelumnya juga memiliki satu elemen memori (implisit), jadi kami memiliki keuntungan bersih dalam satu operasi dasar. Selain itu, versi sebelumnya memiliki dua kelemahan lagi - 1) melanggar prinsip KERING (menghitung kenaikan satu dua kali) dan 2) memiliki lebih dari satu titik keluar, yang tidak baik. Kami juga tidak kehilangan pengertian, yaitu, kami berhasil membunuh sekelompok kelinci dengan satu tembakan, dan kami juga tidak menghabiskan kartrid apa pun - itu hanya cerita dalam gaya Baron Munchausen.

Perhatikan bahwa saya tidak menggunakan if ( (Tmp = Counter + 1) > Max) , meskipun berisi instruksi eksplisit ke kompiler untuk mencoba tidak melakukan transfer yang berlebihan. Ini bumbu dalam bentuk yang paling terang-terangan, saya hanya tidak suka nilai yang dikembalikan oleh operator penugasan dan mencoba untuk menghindari menggunakannya. Saya tidak bisa menjelaskan alasan perasaan kuat ini, menurut Freud, ini kemungkinan besar trauma psikologis di masa kecil. Kompiler modern cukup mampu melakukan optimasi sederhana sendiri, dan selain itu, saya juga menambahkan kualifikasi register, sehingga kode untuk versi saya dan yang benar (dari sudut pandang bahasa C) akan cocok. Namun demikian, saya sama sekali tidak membatasi kebebasan Anda untuk menggunakan metode yang tampaknya lebih disukai untuk Anda.

Kami terus meningkatkan, karena tidak ada batas untuk kesempurnaan, dan kami belum mencapainya. Untuk mencapainya, kita sedikit merumuskan kembali masalah asli dan hanya menyisakan persyaratan variabel dalam kisaran nilai, tanpa menunjukkan arah perubahan. Pendekatan ini memungkinkan Anda untuk menulis ulang program sebagai berikut

 static inline Counter_t NextCouner(const Counter_t Counter) { register Counter_t Tmp; Tmp = (Counter - 1); if (Tmp < 0) { Tmp = ; }; return Tmp; }; 

Pada pandangan pertama, tidak ada yang berubah banyak, tetapi, bagaimanapun, kami mendapat keuntungan dalam waktu. Tentu saja, bukan karena fakta bahwa operasi penurunan oleh satu bekerja lebih cepat daripada operasi peningkatan olehnya (meskipun saya mendengar versi yang sama), tetapi karena kekhasan perbandingan. Jika dalam versi sebelumnya saya menganggap perbandingan sebagai 2 operasi dasar (pertama kita kurangi dan kemudian membuat keputusan), maka dalam hal ini hasil dari operasi sebelumnya digunakan untuk membuat keputusan secara langsung dan perbandingan mengambil satu operasi dasar, yang mengarah ke dua operasi selalu dan satu tugas (jarang) dan kami menyelamatkan satu operasi (tanpa kehilangan apa pun), seperti kata pepatah, "agak sepele, tapi bagus." Apakah solusi yang dihasilkan ideal - sayangnya, tidak. Ini sedikit lebih rendah daripada solusi dengan masker (yang membutuhkan tepat 2 operasi dasar) dalam hal kecepatan dan ini mungkin satu-satunya kelemahan.

Ada solusi yang bahkan lebih cepat - cukup meningkatkan (menurunkan) nilai penghitung dan tidak melakukan hal lain, tetapi hanya mungkin dalam satu-satunya kasus ketika nilai maksimum bertepatan dengan nilai yang paling representatif dalam jenis yang diterima. Untuk penghitung 8-bit (yaitu, dari tipe uint8_t), itu akan menjadi 255, maka kita cukup menulis Counter = Counter + 1 dan mengambil kata saya untuk itu bahwa menulis Counter + = 1 atau ++ Counter sepenuhnya opsional, walaupun banyak yang dan mereka akan menulis dan akan sepenuhnya benar. Jika kita tidak serius mempertimbangkan versi tentang perlunya menyimpan karakter (karena opsi pertama adalah yang terpanjang), maka ini tidak masuk akal, setidaknya jika kita menulis program untuk arsitektur ARM atau AVR (untuk yang lain saya tidak periksa, saya menduga hasilnya akan menjadi sama) di bawah kompiler GCC (penulis memahami bahwa mereka sedang menulis program di editor lingkungan pemrograman terintegrasi, ini hanya sebuah revolusi pidato dari masa lalu ketika komputer besar dan memori kecil), dan dengan pengoptimalan dihidupkan di tingkat mana pun, karena kode yang diberikan akan benar-benar identik.

Kompiler modern sangat, sangat maju dalam hal optimasi dan menghasilkan kode yang sangat bagus, tentu saja, jika Anda telah mengaktifkan mode yang sesuai. Meskipun saya siap untuk setuju bahwa konstruksi bahasa tersebut tidak membahayakan, dan dapat berguna dalam kondisi tertentu, satu-satunya hal yang saya perhatikan adalah bahwa ekspresi Counter ++ (dalam kasus khusus ini, tentu saja) harus dihindari dengan jelas, karena ini dimaksudkan untuk situasi yang sama sekali berbeda dan dapat menimbulkan kode lebih lambat, meskipun opsional.

Pertanyaan lain adalah bahwa buffer 256-elemen tidak selalu dapat diterima, tetapi jika Anda memiliki cukup memori, mengapa tidak. Dengan implementasi ini, jika Anda dapat menyelaraskan buffer ke batas halaman, maka akses ke elemen dapat dilakukan dengan sangat cepat dengan menghilangkan operasi pemindahan dari indeks ke indeks (kata kunci gabungan akan memberi tahu Anda penerapan fitur seperti itu, saya tidak akan membawanya agar tidak belajar buruk), tetapi ini sudah merupakan keputusan yang sangat, sangat spesifik dengan keterikatan yang kuat pada arsitektur, yang sangat dekat dengan trik dalam arti kata yang terburuk, dan ini bukan gaya kita.

Tentu saja, tidak ada yang melarang kita untuk menulis pembungkus yang akan memanggil metode ini atau itu tergantung pada nilai maksimum (dan minimum, karena banyak metode tidak bekerja dengan nilai non-nol minimum), saya sudah mengusulkan prinsip dasar dari solusi seperti itu, jadi kami akan menawarkan ini sebagai latihan.

Singkatnya, untuk meringkas - kami akan menyatukan berbagai implementasi pekerjaan dengan indeks cincin dan mengevaluasi sifat-sifat mereka.

Baris kedua dalam tanda kurung menunjukkan jumlah nilai ukuran buffer (tidak melebihi 256) yang tersedia untuk implementasi ini, tetapi kami berarti bahwa buffer ukuran 0 tidak menarik bagi kami.

Seperti yang dapat Anda lihat dari tabel ini, DarZaNeBy (ungkapan favorit saya, seperti yang mungkin telah Anda perhatikan), dan kelebihannya dibeli dengan biaya kerugian, satu-satunya hal yang dapat dinyatakan secara jelas adalah bahwa peningkatan dengan verifikasi memiliki pesaing yang lebih sukses dalam bentuk pengurangan dengan verifikasi dan tidak melanjutkan ke putaran berikutnya. dalam kondisi apa pun.

Catatan yang diperlukan - ada bahasa pemrograman di mana kita tidak perlu berpikir tentang implementasi indeks sama sekali, tetapi cukup kita bisa menggunakan tipe interval. Sayangnya, saya tidak dapat menyebut implementasi konstruk ini dalam kode optimal, karena konstruk ini (dan bahasa ini) tidak dimaksudkan untuk optimisasi saat runtime, tetapi sangat disayangkan.

Jadi, kami membuat modul yang tepat (nama yang kuat untuk fungsi inline) untuk bekerja dengan indeks, dan sekarang kami siap untuk mulai menerapkan buffer cincin itu sendiri.

Sebagai permulaan, kita harus memutuskan apa yang sebenarnya kita inginkan dari objek program ini. Sangat penting untuk dapat menempatkan elemen data dalam buffer dan mengekstraknya - dua metode utama, semacam pengambil dan penyetel. Secara teori dimungkinkan untuk membayangkan penyangga tanpa salah satu dari metode ini, atau bahkan tanpa keduanya (hanya sedikit yang dapat dibayangkan secara teoritis), tetapi nilai praktis dari implementasi semacam itu adalah pertanyaan besar. Fungsi berikutnya yang diperlukan - memeriksa informasi - dapat diimplementasikan baik sebagai metode terpisah, atau sebagai nilai khusus (atau atribut) yang dikembalikan dengan membaca. Biasanya mereka lebih suka metode pertama, karena ternyata lebih mudah dimengerti dan tidak terlalu mahal.
Tetapi memeriksa kelengkapan buffer sudah merupakan pertanyaan besar - operasi ini akan membutuhkan waktu tambahan, yang akan selalu dihabiskan untuk merekam, meskipun tidak ada yang memaksa kita untuk menggunakannya - jadi biarkan saja. Kami tidak membutuhkan hal lain dari buffer, mari kita ingat frase ini untuk masa depan.

Kembali ke implementasi. Kami membutuhkan tempat untuk menyimpan elemen antrian dan dua indeks - satu untuk menulis ke buffer dan satu untuk membaca darinya. Bagaimana tepatnya kita akan mendapatkan tempat ini (dan petunjuk-petunjuk ini) adalah topik untuk diskusi terpisah, untuk saat ini, mari kita tinggalkan momen ini dalam kurung dan percaya bahwa kita memilikinya. Beberapa (termasuk penulis buku "Programming for Mathematicians", yang saya hormati, saya sarankan untuk membacanya) juga menggunakan konter tempat yang penuh, tetapi kami tidak akan melakukan ini dan saya akan mencoba menunjukkan mengapa ini jahat.

Pertama, tentang indeks - kami segera melihat bahwa ini adalah indeks, bukan petunjuk, meskipun kadang-kadang saya membiarkan diri saya disebut demikian. ( ), ( )- , , , . ( 256 ), , , ( , 8 , , 4- ), , , ( , ).


Selain itu, banyak trik yang meningkatkan kecepatan untuk mendapatkan nilai berikutnya akan menjadi tidak tersedia saat menggunakan pointer. Dan jika Anda juga mempertimbangkan pendapat bahwa pointer lebih sulit untuk dipahami (bukan bahwa pendapat ini tampaknya benar bagi saya, tetapi ada), maka pilihannya adalah indeks yang jelas.

— ( ), . : 1) , 2) , . , , , . , , . ( ) , — . — , .

(«, ») , . — 1) , 2) ( , ) 3) , , 4) 256 , 5) ( ), . , , , , .

Kita hanya perlu menghindari situasi di mana indeks mungkin bertepatan setelah catatan berikutnya (fakta bahwa mereka mungkin bertepatan setelah membaca jelas), dan untuk ini kita perlu membatasi jumlah elemen yang mungkin dalam buffer menjadi 1 kurang dari mungkin. Berikut implementasinya:

 #define NeedOverflowControl YES typedef uint8_t Data_t; static Data_t BufferData[Max]; static Counter_t BufferWriteCounter=0, BufferReadCounter=BufferWriteCounter; void BufferWrite(const data_t Data) { BufferData[BuffWriteCounter] = Data; register counter_t Tmp = NextCount(BufferWriteCounter); #if (NeedOverflowControl == YES) if (Tmp == BufferReadCounter) {BufferOverflow();} else #endif { BufferWriteCounter = Tmp; } }; 

Ada sedikit kesalahan pada fungsi sebelumnya, saya mengusulkan untuk menemukannya dan memperbaikinya sendiri, meskipun ... masih ada, tapi kami akan melanjutkan:

  inline int BufferIsEmpty(void) { return ( BufferReadCounter == BufferWriteCounter ); }; inline int BufferIsFull(void) { return ( BufferReadCounter == NextCounter(BufferWriteCounter) ); }; #define DataSizeIsSmaller (sizeof(data_t) < sizeof(counter_t)) data_t BufferRead(void) { #if DataSizeIsSmaller register data_t Tmp = BufferData[BufferReadCounter]; #else register counter_t Tmp = BufferReadCounter; #endif BufferReadCounter = NextCount(BufferReadCounter); #if DataSizeIsSmaller return Tmp; #else return BufferData[Tmp]; #endif }; 

, ( ) — , , , — , . , , , .

, , — , , , .

, ( )

1) ( — , , — , , ).
(, , )

2) — , .

:

3) 4) , (« »). — , , ( N N+1 ) , ?

3) ,

4) .

— « », - , — . 3, ( ), , .

— , ( , ),

5) — , , , , — , .

— , , .

, , , , , , , , , , , . , 4 , , . MRSW (Multi-Reader Single-Writer) «The Art of Mulpiprocessor Programming» ( , ) ( ) . — , , .

MRMW , «» (, , « » ). , , , , . , , , (, , — , , , ), .

, ( ) , . , , , , , , , .

 typedef uint8_t data_t; static data_t BufferData[Max]; static counter_t BufferWriteCounter=0, BufferReadCounter=WriteCounter; static int8_t BufferHaveData = 0; void BufferWrite(const data_t Data) { if ((BufferWriteCounter == BufferReadCounter) && (BufferHaveDataFlag == 1)) {BufferOverflow();} else { BufferData[BufferWriteCounter] = Data; BufferHaveDataFlag = 1; BufferWriteCounter = NextCounter(BufferWriteCounter); }; }; inline int BufferIsEmpty(void) { return ((BufferReadCounter==BufferWriteCounter) && (BufferHaveDataFlag == 0));}; data_t BufferRead(void) { register counter_t Tmp; Tmp = BufferReadCounter; BufferReadCounter = NextCount(BufferReadCounter); if (BufferReadCount == BufferWriteCounter) { BufferHaveDataFlag = 1; }; return BufferData[Tmp]; }; 

, , , , , .

, ( 0 1, , , ), , , , , , ( ), , ,


, , 0 1, . , , , 0 1. , , , , BufferFullFlag , BufferIsNotEmptyFlag . , KISS , , , , , « ».

, , .

, , .

PS , , :

1. — (, , ), — , , , , .
2. .
3. .
4. 2 .
6. , ( ) , , .
7. ,
   
   

    return ((_writeCount - Atomic::Fetch(&_readCount)) & (size_type)~(_mask)) != 0; 

   
   — , , ,
   
   

    size_type(~(_mask)) 

   
   .

PPS , .