Halo, Habr!
Hari ini kami menerbitkan terjemahan studi yang menarik tentang bekerja dengan memori dan petunjuk dalam C ++. Materi ini sedikit akademis, tetapi jelas akan menarik bagi pembaca buku-buku
Galowitz dan
Williams .
Ikuti iklannya!
Di sekolah pascasarjana, saya terlibat dalam pembangunan struktur data terdistribusi. Oleh karena itu, abstraksi yang mewakili remote pointer sangat penting dalam pekerjaan saya untuk membuat kode yang bersih dan rapi. Pada artikel ini, saya akan menjelaskan mengapa pointer pintar diperlukan, katakan bagaimana saya menulis objek pointer jarak jauh di C ++ untuk perpustakaan saya, pastikan bahwa mereka bekerja persis seperti pointer C ++ biasa; ini dilakukan menggunakan objek tautan jauh. Lebih lanjut saya akan menjelaskan dalam kasus apa abstraksi ini gagal karena alasan sederhana bahwa pointer saya sendiri (sejauh ini) tidak mengatasi tugas-tugas yang dapat dilakukan pointer biasa. Saya harap artikel ini akan menarik minat pembaca yang terlibat dalam pengembangan abstraksi tingkat tinggi.
API Tingkat Rendah
Saat bekerja dengan komputer terdistribusi atau dengan perangkat keras jaringan, Anda sering memiliki akses baca dan tulis ke sepotong memori melalui API C. Salah satu contoh dari jenis ini adalah
MPI API untuk komunikasi satu arah. API ini menggunakan fungsi yang membuka akses langsung untuk membaca dan menulis dari memori node lain yang terletak di cluster terdistribusi. Begini tampilannya dengan cara yang sedikit disederhanakan.
void remote_read(void* dst, int target_node, int offset, int size); void remote_write(void* src, int target_node, int offset, int size);
Pada
offset yang ditunjukkan ke segmen memori bersama dari node target,
remote_read sejumlah byte dari itu, dan
remote_write menulis sejumlah byte.
API ini sangat bagus karena memberi kami akses ke primitif penting yang berguna bagi kami untuk mengimplementasikan program yang berjalan di sekelompok komputer. Mereka juga sangat baik karena mereka bekerja sangat cepat dan akurat mencerminkan kemampuan yang ditawarkan pada tingkat perangkat keras: akses memori langsung jarak jauh (RDMA). Jaringan superkomputer modern, seperti
Cray Aries dan
Mellanox EDR , memungkinkan kami menghitung bahwa keterlambatan membaca / menulis tidak akan melebihi 1-2 Ξs. Indikator ini dapat dicapai karena kartu jaringan (NIC) dapat membaca dan menulis langsung ke RAM, tanpa menunggu CPU jarak jauh untuk bangun dan menanggapi permintaan jaringan Anda.
Namun, API semacam itu tidak begitu baik dalam hal pemrograman aplikasi. Bahkan dalam kasus API sederhana seperti yang dijelaskan di atas, tidak ada biaya apa pun untuk secara tidak sengaja menghapus data, karena tidak ada nama terpisah untuk setiap objek tertentu yang disimpan dalam memori, hanya satu buffer besar yang berdekatan. Selain itu, antarmuka tidak diketik, yaitu, Anda kehilangan bantuan nyata lainnya: ketika kompiler bersumpah, jika Anda menuliskan nilai dari jenis yang salah di tempat yang salah. Kode Anda hanya akan berubah menjadi salah, dan kesalahan akan menjadi yang paling misterius dan bersifat bencana. Situasinya bahkan lebih rumit karena pada kenyataannya
API ini sedikit lebih rumit, dan ketika bekerja dengan mereka, sangat mungkin untuk secara keliru mengatur ulang dua atau lebih parameter.
Pointer yang Dihapus
Pointer adalah level abstraksi yang penting dan perlu saat membuat alat pemrograman tingkat tinggi. Menggunakan pointer secara langsung kadang-kadang sulit, dan Anda dapat melakukan banyak bug, tetapi pointer adalah blok bangunan mendasar dari kode. Struktur data dan bahkan tautan C ++ sering menggunakan pointer di bawah tenda.
Jika kita berasumsi bahwa kita akan memiliki API yang mirip dengan yang dijelaskan di atas, maka lokasi unik dalam memori akan ditunjukkan oleh dua "koordinat": (1)
peringkat atau ID proses dan (2) offset yang dibuat untuk bagian bersama dari memori jauh yang ditempati oleh proses dengan peringkat ini . Anda tidak dapat berhenti di situ dan membuat struktur yang lengkap.
template <typename T> struct remote_ptr { size_t rank_; size_t offset_; };
Pada tahap ini, sudah dimungkinkan untuk merancang API untuk membaca dan menulis ke remote pointer, dan API ini akan lebih aman daripada yang kami gunakan sebelumnya.
template <typename T> T rget(const remote_ptr<T> src) { T rv; remote_read(&rv, src.rank_, src.offset_, sizeof(T)); return rv; } template <typename T> void rput(remote_ptr<T> dst, const T& src) { remote_write(&src, dst.rank_, dst.offset_, sizeof(T)); }
Blok transfer terlihat sangat mirip, dan di sini saya menghilangkannya untuk singkatnya. Sekarang, untuk nilai membaca dan menulis, Anda dapat menulis kode berikut:
remote_ptr<int> ptr = ...; int rval = rget(ptr); rval++; rput(ptr, rval);
Ini sudah lebih baik daripada API asli, karena di sini kami bekerja dengan objek yang diketik. Sekarang tidak mudah untuk menulis atau membaca nilai dari jenis yang salah atau hanya menulis bagian dari suatu objek.
Aritmatika Pointer
Aritmetika pointer adalah teknik paling penting yang memungkinkan seorang programmer untuk mengelola koleksi nilai dalam memori; jika kita menulis sebuah program untuk pekerjaan yang didistribusikan dalam memori, mungkin kita akan beroperasi dengan koleksi nilai yang besar.
Apa artinya menambah atau mengurangi pointer yang dihapus dengan satu maksud? Opsi paling sederhana adalah dengan mempertimbangkan aritmatika dari pointer yang dihapus sebagai aritmatika dari pointer biasa: p + 1 secara sederhana menunjuk ke
sizeof(T) berikutnya
sizeof(T) selaraskan memori setelah p dalam segmen bersama dari peringkat asli.
Meskipun ini bukan satu-satunya definisi yang mungkin dari aritmatika remote pointer, ini telah paling aktif diadopsi baru-baru ini, dan remote pointer yang digunakan dengan cara ini terkandung dalam perpustakaan seperti
UPC ++ ,
DASH dan BCL. Namun, bahasa
Unified Parallel C (UPC), yang telah meninggalkan warisan yang kaya di komunitas spesialis komputasi kinerja tinggi (HPC), berisi definisi aritmatika pointer yang lebih rumit [1].
Menerapkan aritmatika pointer dengan cara ini sederhana, dan itu hanya melibatkan mengubah offset pointer.
template <typename T> remote_ptr<T> remote_ptr<T>::operator+(std::ptrdiff_t diff) { size_t new_offset = offset_ + sizeof(T)*diff; return remote_ptr<T>{rank_, new_offset}; }
Dalam hal ini, kami memiliki kesempatan untuk mengakses array data dalam memori yang didistribusikan. Jadi, kita dapat mencapai bahwa setiap proses dalam program SPMD akan melakukan operasi tulis atau baca pada variabelnya dalam array yang diarahkan oleh penunjuk jarak jauh [2].
void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { rput(ptr + my_rank(), my_rank()); } }
Juga mudah untuk mengimplementasikan operator lain, memberikan dukungan untuk set lengkap operasi aritmatika yang dilakukan dalam aritmatika pointer biasa.
Pilih nullptr
Untuk pointer reguler, nilai
nullptr adalah
NULL , yang biasanya berarti mengurangi
#define menjadi 0x0, karena bagian ini dalam memori tidak mungkin digunakan. Dalam skema kami dengan remote pointer, kami dapat memilih nilai pointer tertentu sebagai
nullptr , sehingga membuat lokasi ini dalam memori tidak digunakan, atau menyertakan anggota Boolean khusus yang akan menunjukkan apakah pointer tersebut nol. Terlepas dari kenyataan bahwa membuat lokasi tertentu dalam memori yang tidak terpakai bukanlah jalan keluar terbaik, kami juga akan mempertimbangkan bahwa ketika menambahkan hanya satu nilai Boolean, ukuran penunjuk jarak jauh akan berlipat ganda dari sudut pandang sebagian besar penyusun dan tumbuh dari 128 hingga 256 bit untuk mempertahankan keselarasan. Ini terutama tidak diinginkan. Di perpustakaan saya, saya memilih
{0, 0} , yaitu offset 0 dengan pangkat 0, sebagai nilai
nullptr .
Dimungkinkan untuk mengambil opsi lain untuk
nullptr yang juga berfungsi. Selain itu, dalam beberapa lingkungan pemrograman, seperti UPC, pointer sempit diterapkan yang masing-masing berukuran 64 bit. Dengan demikian, mereka dapat digunakan dalam operasi perbandingan atom dengan pertukaran. Ketika bekerja dengan pointer sempit, Anda harus berkompromi: pengidentifikasi offset atau pengidentifikasi peringkat harus sesuai dalam 32 bit atau kurang, dan ini membatasi skalabilitas.
Tautan yang Dihapus
Dalam bahasa seperti Python, pernyataan braket berfungsi sebagai gula sintaksis untuk memanggil metode
__setitem__ dan
__getitem__ , tergantung pada apakah Anda membaca objek atau menulisnya. Dalam C ++,
operator[] tidak membedakan mana dari
kategori nilai yang dimiliki objek dan apakah nilai yang dikembalikan akan langsung jatuh di bawah baca atau tulis. Untuk mengatasi masalah ini, struktur data C ++ mengembalikan tautan yang menunjuk ke memori yang terkandung dalam wadah, yang dapat ditulis atau dibaca. Implementasi
operator[] untuk
std::vector mungkin terlihat seperti ini.
T& operator[](size_t idx) { return data_[idx]; }
Fakta paling signifikan di sini adalah bahwa kami mengembalikan entitas tipe
T& , yang merupakan tautan C ++ mentah yang dapat digunakan untuk menulis, dan bukan entitas tipe
T , yang hanya mewakili nilai dari data sumber.
Dalam kasus kami, kami tidak dapat mengembalikan tautan C ++ mentah, karena kami merujuk ke memori yang terletak di node lain dan tidak terwakili dalam ruang alamat virtual kami. Benar, kita dapat membuat objek referensi khusus kita sendiri.
Tautan adalah objek yang berfungsi sebagai pembungkus di sekitar penunjuk, dan melakukan dua fungsi penting: tautan dapat dikonversi ke nilai tipe
T , dan Anda juga dapat menetapkannya ke nilai tipe
T Jadi, dalam kasus referensi jarak jauh, kita hanya perlu mengimplementasikan operator konversi implisit yang membaca nilai, dan juga membuat operator penugasan yang menulis ke nilai tersebut.
template <typename T> struct remote_ref { remote_ptr<T> ptr_; operator T() const { return rget(ptr_); } remote_ref& operator=(const T& value) { rput(ptr_, value); return *this; } };
Dengan demikian, kita dapat memperkaya penunjuk jarak jauh kita dengan fitur-fitur canggih yang baru, dengan kehadiran yang dapat disamakan persis seperti petunjuk biasa.
template <typename T> remote_ref<T> remote_ptr<T>::operator*() { return remote_ref<T>{*this}; } template <typename T> remote_ref<T> remote_ptr<T>::operator[](ptrdiff_t idx) { return remote_ref<T>{*this + idx}; }
Jadi sekarang kami telah memulihkan seluruh gambar yang menunjukkan bagaimana Anda dapat menggunakan remote pointer seperti biasa. Kita dapat menulis ulang program sederhana di atas.
void write_array(remote_ptr<int> ptr, size_t len) { if (my_rank() < len) { ptr[my_rank()] = my_rank(); } }
Tentu saja, API penunjuk baru kami memungkinkan kami untuk menulis program yang lebih kompleks, misalnya, fungsi untuk melakukan pengurangan paralel berdasarkan pohon [3]. Implementasi yang menggunakan kelas pointer jarak jauh kami lebih aman dan lebih bersih daripada yang biasanya diperoleh menggunakan API C yang dijelaskan di atas.
Biaya yang timbul saat runtime (atau ketiadaan!)
Namun, berapa biayanya bagi kita untuk menggunakan abstraksi tingkat tinggi seperti itu? Setiap kali kita mengakses memori, kita memanggil metode dereferencing, mengembalikan objek perantara yang membungkus pointer, lalu kita memanggil operator konversi atau operator penugasan yang mempengaruhi objek perantara. Berapa biayanya kami pada saat runtime?
Ternyata jika Anda dengan hati-hati menunjuk kelas pointer dan referensi, maka tidak akan ada overhead untuk abstraksi ini pada saat runtime - kompiler C ++ modern menangani objek-objek perantara dan pemanggilan metode dengan embedding agresif. Untuk mengevaluasi berapa biaya abstraksi seperti itu, kita dapat mengkompilasi program contoh sederhana dan memeriksa bagaimana perakitan akan pergi untuk melihat objek dan metode apa yang akan ada saat runtime. Dalam contoh yang dijelaskan di sini dengan reduksi berbasis pohon yang dikompilasi dengan kelas-kelas dari remote pointer dan referensi, kompiler modern mengurangi reduksi berbasis-pohon menjadi beberapa
remote_write dan
remote_write [4]. Tidak ada metode kelas yang dipanggil, tidak ada objek referensi saat runtime.
Interaksi dengan pustaka struktur data
Pemrogram C ++ yang berpengalaman ingat bahwa pustaka templat C ++ standar menyatakan: Wadah STL harus mendukung
pengalokasi C ++ khusus . Allocator memungkinkan Anda untuk mengalokasikan memori, dan kemudian memori ini dapat dirujuk menggunakan jenis pointer yang dibuat oleh kami. Apakah ini berarti Anda cukup membuat "pengalokasi jarak jauh" dan menghubungkannya untuk menyimpan data dalam memori jauh menggunakan wadah STL?
Sayangnya tidak. Agaknya, untuk alasan kinerja, standar C ++ tidak lagi membutuhkan dukungan untuk tipe referensi khusus, dan di sebagian besar implementasi pustaka standar C ++ mereka benar-benar tidak didukung. Jadi, misalnya, jika Anda menggunakan libstdc ++ dari GCC, Anda dapat menggunakan pointer khusus, tetapi hanya tautan C ++ normal yang tersedia untuk Anda, yang tidak memungkinkan Anda untuk menggunakan wadah STL dalam memori jarak jauh. Beberapa pustaka template C ++ tingkat tinggi, misalnya,
Agensi , yang menggunakan tipe pointer khusus dan tipe referensi, berisi implementasi sendiri dari beberapa struktur data dari STL yang benar-benar memungkinkan Anda untuk bekerja dengan tipe referensi jarak jauh. Dalam hal ini, programmer mendapatkan lebih banyak kebebasan dalam pendekatan kreatif untuk menciptakan jenis pengalokasi, pointer dan tautan, dan, di samping itu, mendapatkan koleksi struktur data yang secara otomatis dapat digunakan dengannya.
Konteks yang luas
Dalam artikel ini, kami telah membahas sejumlah masalah yang lebih luas dan belum terselesaikan.
- Alokasi memori . Sekarang kita dapat mereferensikan objek dalam memori jarak jauh, bagaimana cara kita memesan atau mengalokasikan memori jarak jauh seperti itu?
- Dukungan untuk objek . Bagaimana dengan penyimpanan dalam memori jauh dari objek-objek semacam itu yang lebih rumit daripada int? Apakah dukungan rapi untuk tipe kompleks mungkin? Dapatkah tipe sederhana didukung pada saat yang sama tanpa membuang sumber daya pada serialisasi?
- Merancang struktur data terdistribusi . Sekarang setelah Anda memiliki abstraksi ini, struktur data dan aplikasi apa yang dapat Anda buat dengannya? Abstraksi apa yang harus digunakan untuk distribusi data?
Catatan
[1] Di UPC, pointer memiliki fase yang menentukan peringkat apa yang akan diarahkan oleh pointer setelah bertambah satu. Karena fase, array yang didistribusikan dapat dienkapsulasi dalam pointer, dan pola distribusi di dalamnya bisa sangat berbeda. Fitur-fitur ini sangat kuat, tetapi mungkin tampak ajaib bagi pengguna pemula. Meskipun beberapa ace UPC benar-benar lebih suka pendekatan ini, pendekatan berorientasi objek yang lebih masuk akal adalah dengan menulis kelas pointer jarak jauh sederhana terlebih dahulu dan kemudian memastikan bahwa data dialokasikan berdasarkan pada struktur data yang dirancang khusus untuk ini.
[2] Sebagian besar aplikasi dalam HPC ditulis dalam gaya
SPMD , nama ini berarti "satu program, data berbeda." API SPMD menawarkan fungsi atau variabel
my_rank() yang memberi tahu proses mengeksekusi program peringkat atau ID unik, berdasarkan yang dapat bercabang dari program utama.
[3] Berikut ini adalah pengurangan pohon sederhana yang ditulis dalam gaya SPMD menggunakan kelas pointer jarak jauh. Kode ini diadaptasi berdasarkan program yang awalnya ditulis oleh rekan saya
Andrew Belt .
template <typename T> T parallel_sum(remote_ptr<T> a, size_t len) { size_t k = len; do { k = (k + 1) / 2; if (my_rank() < k && my_rank() + k < len) { a[my_rank()] += a[my_rank() + k]; } len = k; barrier(); } while (k > 1); return a[0]; }
[4] Hasil kompilasi dari kode di atas
dapat ditemukan di sini .