Dari laporan pengembang senior Sergey Murylyov, Anda dapat mempelajari tentang wadah asosiatif multi-utas untuk perpustakaan standar, yang sedang dikembangkan sebagai bagian dari WG21. Sergey berbicara tentang pro dan kontra dari solusi populer untuk masalah ini dan jalur yang dipilih oleh pengembang.
- Anda mungkin sudah menebak dari judul bahwa laporan hari ini adalah tentang bagaimana kami, dalam kerangka Kelompok Kerja 21, membuat wadah kami mirip dengan std :: unordered_map, tetapi untuk lingkungan multi-utas.
Dalam banyak bahasa pemrograman - Java, C #, Python - ini sudah ada dan cukup banyak digunakan. Tetapi dalam C ++ tercinta, tercepat dan paling produktif kami, ini tidak terjadi. Tetapi kami berkonsultasi dan memutuskan untuk melakukan hal seperti itu.
Sebelum Anda menambahkan sesuatu ke standar, Anda perlu memikirkan bagaimana orang akan menggunakannya. Kemudian untuk membuat antarmuka yang lebih benar, yang kemungkinan besar akan diadopsi oleh panitia - lebih disukai tanpa amandemen. Sehingga pada akhirnya tidak akan ada yang mereka lakukan satu hal, tapi ternyata yang lain.
Opsi yang paling terkenal dan banyak digunakan adalah caching komputasi berat besar. Ada layanan Memcached yang cukup terkenal yang hanya menyimpan respons server web dalam memori. Jelas bahwa Anda dapat melakukan hal yang kira-kira sama di sisi aplikasi Anda, jika Anda memiliki wadah asosiatif yang kompetitif. Kedua pendekatan memiliki pro dan kontra mereka. Tetapi jika Anda tidak memiliki wadah seperti itu, Anda harus membuat sepeda sendiri atau menggunakan semacam Memcached.
Kasus penggunaan populer lainnya adalah deduplikasi acara. Saya pikir banyak di ruangan ini menulis semua jenis sistem terdistribusi dan tahu bahwa antrian yang didistribusikan sering digunakan untuk berkomunikasi antara komponen, seperti Apache Kafka dan Amazon Kinesis. Mereka dibedakan oleh fitur sedemikian rupa sehingga mereka dapat mengirim satu pesan ke satu konsumen beberapa kali. Ini disebut setidaknya sekali pengiriman, yang berarti jaminan pengiriman setidaknya sekali: lebih banyak mungkin, lebih sedikit tidak.
Pertimbangkan ini dalam kehidupan nyata. Bayangkan bahwa kita memiliki backend dari beberapa ruang obrolan atau jejaring sosial tempat perpesanan berlangsung. Ini dapat mengarah pada fakta bahwa seseorang menulis pesan dan seseorang kemudian menerima pemberitahuan push di ponsel mereka beberapa kali. Jelas bahwa jika pengguna melihat ini, mereka tidak akan senang karenanya. Dikatakan bahwa masalah ini dapat diselesaikan dengan wadah multi-ulir yang begitu indah.
Kasus berikutnya yang jarang digunakan adalah ketika kita hanya perlu menyimpan sesuatu di sisi server, beberapa metadata untuk pengguna. Sebagai contoh, kita dapat menghemat waktu ketika pengguna terakhir diautentikasi, untuk memahami kapan waktu berikutnya ia harus ditanyai nama pengguna dan kata sandinya.
Opsi terakhir pada slide ini adalah statistik. Dari aplikasi kehidupan nyata, contoh penggunaan di mesin virtual dari Facebook dapat diberikan. Mereka membuat mesin virtual keseluruhan untuk mengoptimalkan PHP dan di mesin virtual mereka, mereka mencoba menuliskan argumen yang dengannya mereka dipanggil ke tabel hash multi-utas untuk semua fungsi bawaan. Dan jika mereka memiliki hasil dalam cache, maka mereka mencoba untuk langsung memberikannya dan tidak menghitung apa pun.
Menambahkan sesuatu yang besar dan rumit ke standar tidak mudah dan tidak cepat. Sebagai aturan, jika sesuatu yang besar ditambahkan, ia akan melewati spesifikasi teknis. Saat ini, standar banyak bergerak untuk memperluas dukungan multithreading di perpustakaan standar. Dan secara khusus, proposal P0260R3 tentang antrian multithreaded akan ada di sana sekarang. Proposal ini adalah tentang struktur data yang sangat mirip dengan kami, dan keputusan desain kami sangat mirip dalam banyak hal.
Sebenarnya, salah satu konsep dasar desain mereka adalah bahwa antarmuka mereka berbeda dari std :: antrian standar. Apa gunanya Jika Anda melihat antrian standar, maka untuk mengekstrak elemen darinya, Anda perlu melakukan dua operasi. Anda perlu melakukan operasi depan untuk menghitung, dan operasi pop untuk menghapus. Jika kami bekerja di bawah kondisi multithreading, maka kami mungkin memiliki semacam operasi pada antrian antara dua panggilan ini, dan mungkin terjadi bahwa kami mempertimbangkan satu elemen dan menghapus yang lain, yang tampaknya secara konsep tidak benar. Oleh karena itu, dua panggilan ini diganti di sana dengan satu, dan beberapa panggilan lagi dari kategori coba tekan dan coba pop ditambahkan. Tetapi ide umumnya adalah bahwa wadah multi-berulir tidak akan sama dengan antarmuka normal.
Antrian multithreaded juga memiliki banyak implementasi berbeda yang menyelesaikan beberapa tugas berbeda. Tugas yang paling umum adalah tugas produsen dan konsumen, ketika kami memiliki beberapa utas yang menghasilkan beberapa tugas dan ada beberapa utas yang mengambil tugas dari antrian dan memprosesnya.
Kasus kedua adalah ketika kita hanya perlu memiliki semacam antrian yang disinkronkan. Dalam hal produsen dan konsumen, kami mendapatkan antrian yang terbatas pada bagian atas dan bawah. Jika kita mencoba, secara relatif, untuk mengekstrak dari antrian kosong, maka kita masuk ke keadaan menunggu. Dan hal yang sama kira-kira terjadi jika kita mencoba menambahkan sesuatu yang tidak sesuai dengan ukuran antrian.
Juga dalam proposal ini dijelaskan bahwa kami memiliki antarmuka yang dibuat secara terpisah yang memungkinkan kami untuk membedakan implementasi yang kami miliki di dalam kunci, atau bebas kunci. Fakta bahwa di sini di mana-mana dalam proposal ini ditulis bebas kunci, pada kenyataannya, itu ditulis dalam buku sebagai menunggu gratis. Ini berarti bahwa algoritma kami berfungsi untuk sejumlah operasi tetap. Kunci gratis di sana berarti sedikit berbeda, tetapi bukan itu intinya.
Mari kita lihat diagram khas tentang bagaimana implementasi tabel hash kita mungkin terlihat jika diblokir. Kami memilikinya dibagi menjadi beberapa segmen. Setiap segmen, sebagai suatu peraturan, mengandung beberapa jenis kunci, seperti Mutex, Spinlock, atau sesuatu yang bahkan lebih rumit. Dan selain Mutex atau Spinlock, itu juga berisi tabel hash biasa, yang dilindungi oleh bisnis ini.
Dalam gambar ini, kami memiliki tabel hash, yang dibuat pada daftar. Bahkan, dalam implementasi referensi kami, kami menulis tabel hash dengan pengalamatan terbuka untuk alasan kinerja. Pertimbangan kinerja pada dasarnya sama dengan mengapa std :: vector lebih cepat daripada std :: list karena vektor, secara relatif, disimpan secara berurutan dalam memori. Ketika kita mengikutinya, kita memiliki akses sekuensial, yang di-cache dengan baik. Jika kita menggunakan beberapa jenis lembaran, maka kita akan memiliki semua jenis lompatan antara bagian memori yang berbeda. Dan semuanya, sebagai suatu peraturan, berakhir dengan fakta bahwa kita kehilangan produktivitas.
Pada awalnya, ketika kita ingin menemukan sesuatu di tabel hash ini, kita mengambil kode hash dari kunci. Anda dapat mengambil modulo dan melakukan sesuatu yang lain sehingga kita mendapatkan nomor segmen, dan di segmen yang kita cari, seperti dalam tabel hash biasa, tetapi pada saat yang sama, tentu saja, kita mengambil kunci.
Ide-ide utama desain kami. Tentu saja, kami juga membuat antarmuka yang tidak cocok dengan std :: unordered_map. Alasannya adalah ini. Sebagai contoh, dalam std biasa :: unordered_map kita memiliki hal yang luar biasa seperti iterator. Pertama, tidak semua implementasi dapat mendukungnya secara normal. Dan yang dapat mendukung, sebagai suatu peraturan, adalah beberapa jenis implementasi bebas kunci yang memerlukan pengumpulan sampah atau semacam smart pointer yang membersihkan memori di belakangnya.
Selain itu, ada beberapa jenis operasi lain yang kami buang. Bahkan, iterator, mereka ada di banyak tempat. Misalnya, mereka berada di Jawa. Tapi, anehnya, mereka tidak melakukan sinkronisasi di sana. Dan jika Anda mencoba untuk melakukan sesuatu dengan mereka dari utas yang berbeda, maka mereka dapat dengan mudah masuk ke keadaan tidak valid, dan Anda bisa mendapatkan pengecualian di Jawa, dan jika Anda menulis ini di plus, maka ini kemungkinan besar akan perilaku tidak terdefinisi, yang bahkan lebih buruk . Dan omong-omong, pada topik perilaku tidak terdefinisi: menurut pendapat saya, kawan-kawan dari Facebook di kebodohan perpustakaan mereka, yang diposting di open source di GitHub, melakukan hal itu. Baru saja menyalin antarmuka dengan Java dan mendapatkan iterator yang luar biasa.
Kami juga tidak memiliki keluhan memori, yaitu, jika kami menambahkan sesuatu ke wadah dan mengambil memori untuk itu, kami tidak akan mengembalikannya, bahkan jika kami menghapus semuanya. Prasyarat lain untuk keputusan ini adalah bahwa kita memiliki tabel hash dengan pengalamatan terbuka di dalamnya. Ini bekerja pada struktur data linier, yang seperti vektor tidak mengembalikan memori.
Momen konseptual berikutnya adalah bahwa dalam keadaan apa pun kita tidak akan pernah memberikan kepada siapa pun tautan luar dan petunjuk ke objek internal. Ini tepat dilakukan untuk mencegah perlunya pengumpulan sampah, dan bukan untuk menegakkan penunjuk pintar. Jelas bahwa jika kita menyimpan beberapa objek yang cukup besar, menyimpannya dengan nilai di dalamnya akan tidak menguntungkan. Tapi, dalam hal ini, kita selalu bisa membungkusnya dengan semacam smart pointer pilihan kita. Dan, jika kita ingin, misalnya, untuk melakukan semacam sinkronisasi pada nilai-nilai, kita dapat membungkusnya dalam beberapa jenis boost :: syncized_value.
Kami melihat fakta bahwa beberapa waktu lalu, kelas shared_ptr telah dihapus dari metode yang mengembalikan jumlah tautan aktif ke objek ini. Dan kami sampai pada kesimpulan bahwa kami juga perlu membuang beberapa fungsi, yaitu, ukuran, jumlah, kosong, buckets_count, karena begitu kami mengembalikan nilai ini dari fungsi, ia segera tidak lagi valid, karena seseorang dapat ubah momen yang sama.
Pada salah satu pertemuan kami sebelumnya, mereka meminta kami untuk menambahkan semacam mode sehingga kami dapat mengakses wadah kami dalam mode single-threaded, seperti std :: unordered_map biasa. Semantik semacam itu memungkinkan kita untuk membedakan dengan jelas di mana kita bekerja dalam mode multithreaded dan mana tidak. Dan untuk menghindari beberapa situasi yang tidak menyenangkan ketika orang mengambil wadah multi-ulir, berharap semuanya akan baik-baik saja dengan mereka, ambil iterator, dan kemudian tiba-tiba ternyata semuanya buruk.
Pada pertemuan di Hawaii ini, seluruh proposal ditulis menentang kami. :) Kami diberitahu bahwa hal-hal seperti itu tidak memiliki tempat dalam standar, karena ada banyak cara untuk membuat wadah asosiatif multi-utas Anda.
Masing-masing memiliki pro dan kontra - dan tidak jelas bagaimana menggunakan apa yang akhirnya kita berhasil. Biasanya, ini digunakan ketika Anda membutuhkan semacam kinerja ekstrem. Dan sepertinya solusi kemas kami tidak cocok, perlu untuk mengoptimalkan untuk setiap kasus tertentu.
Poin kedua dari proposal ini adalah bahwa antarmuka kami tidak kompatibel dengan fakta bahwa Facebook memposting di GitHub dari perpustakaan standarnya.
Bahkan, tidak ada masalah khusus di sana. Hanya ada pertanyaan dari kategori "Saya belum membaca, tetapi mengutuk." Mereka hanya melihat - antarmuka berbeda, yang berarti tidak kompatibel.
Gagasan proposal juga bahwa tugas-tugas serupa harus diselesaikan dengan bantuan apa yang disebut desain berbasis kebijakan, ketika perlu untuk membuat parameter template tambahan di mana Anda dapat melewatkan sedikit topeng dengan fitur yang ingin kita aktifkan dan yang harus dimatikan. Memang, ini terdengar agak liar dan mengarah pada fakta bahwa kita mendapatkan sekitar 2 implementasi, di mana n adalah sejumlah fitur yang berbeda.
Dalam kode, tampilannya seperti ini. Kami memiliki beberapa jenis parameter dan sejumlah konstanta standar yang dapat dilewati di sana. Anehnya, proposal ini ditolak.
Karena, pada kenyataannya, panitia telah mengambil posisi bahwa hal-hal seperti itu seharusnya ketika antrian multi-threaded melewati SG1. Bahkan tidak ada suara pada masalah ini. Namun ada dua pertanyaan yang diajukan.
Yang pertama. Banyak orang ingin kami di sisi implementasi referensi kami untuk mendukung membaca tanpa mengambil kunci apa pun. Sehingga kita memiliki bacaan yang sepenuhnya tidak menghalangi. Ini benar-benar masuk akal: sebagai aturan, kasus pengguna paling populer adalah caching. Dan sangat bermanfaat bagi kita untuk membaca cepat.
Momen kedua. Semua orang banyak mendengar dari teman sebelumnya yang berbicara tentang desain berbasis kebijakan. Semua orang punya ide - tetapi apa, biarkan saya berbicara tentang ide saya juga! Dan setiap orang memilih untuk memiliki desain berbasis kebijakan. Meskipun saya harus mengatakan, keseluruhan cerita ini telah berlangsung cukup lama, dan di hadapan kami, kolega kami dari Intel, Arch Robinson dan Anton Malakhov melakukan ini. Dan mereka sudah memiliki beberapa proposal tentang hal ini. Mereka hanya menawarkan untuk menambahkan implementasi bebas kunci berdasarkan pada algoritma
SeepOrderedList . Dan mereka juga memiliki desain berbasis kebijakan dengan keluhan memori.
Dan proposal ini tidak suka Kelompok Kerja Evolusi Perpustakaan. Itu dibungkus dengan alasan bahwa kita hanya akan memiliki peningkatan jumlah kata dalam standar yang tidak terbatas. Tidak mungkin untuk melakukan pratinjau yang memadai dan hanya menerapkan dalam kode.
Kami tidak memiliki komentar tentang ide-ide itu sendiri. Kami memiliki komentar, sebagian besar, tentang implementasi referensi. Dan tentu saja, kami memiliki beberapa ide yang dapat diperkenalkan untuk membuatnya lebih jelas. Tapi intinya, lain kali kita akan pergi dengan proposal yang sama. Kami sangat berharap bahwa kami tidak akan memiliki, seperti dengan modul, lima panggilan dengan proposal yang sama. Kami dengan tulus percaya pada diri kami sendiri, dan bahwa mereka akan membiarkan kami pergi ke panggilan berikutnya, dan bahwa Kelompok Kerja Evolusi Perpustakaan akan tetap bersikeras pada pendapat kami dan tidak akan membiarkan kami mendorong desain berbasis kebijakan. Karena lawan kita tidak berhenti. Dia memutuskan untuk membuktikan kepada semua orang bahwa itu perlu. Tetapi seperti yang mereka katakan, waktu akan memberi tahu. Saya memiliki segalanya, terima kasih atas perhatian Anda.