Penggunaan struktur data persisten dalam bahasa non-fungsional

Bahasa-bahasa yang murni fungsional atau hampir-fungsional murni mendapat manfaat dari struktur data yang persisten karena tidak dapat diubah dan cocok dengan gaya pemrograman fungsional yang stateless.

Tetapi dari waktu ke waktu kita melihat pustaka dari struktur data yang persisten untuk bahasa (berbasis negara, OOP) seperti Java. Klaim yang sering didengar dalam mendukung struktur data yang persisten adalah bahwa karena mereka tidak dapat diubah, mereka aman untuk digunakan .

Namun, alasan bahwa struktur data persisten aman-thread adalah bahwa jika satu thread adalah untuk "menambahkan" elemen ke koleksi persisten, operasi mengembalikan koleksi baru seperti aslinya tetapi dengan elemen yang ditambahkan. Karenanya utas lainnya melihat koleksi asli. Kedua koleksi ini memiliki banyak keadaan internal, tentu saja - itu sebabnya struktur yang persisten ini efisien.

Tetapi karena utas yang berbeda melihat keadaan data yang berbeda, tampaknya struktur data yang persisten tidak cukup untuk menangani skenario di mana satu utas membuat perubahan yang terlihat oleh utas lainnya. Untuk ini, tampaknya kita harus menggunakan perangkat seperti atom, referensi, memori transaksional perangkat lunak, atau bahkan kunci klasik dan mekanisme sinkronisasi.

Lalu mengapa, apakah imutabilitas PDS disebut-sebut sebagai sesuatu yang bermanfaat untuk "keamanan benang"? Apakah ada contoh nyata di mana PDS membantu dalam sinkronisasi, atau menyelesaikan masalah konkurensi? Atau PDS hanyalah cara untuk menyediakan antarmuka stateless ke objek dalam mendukung gaya pemrograman fungsional?

Struktur data yang persisten / tidak dapat diubah tidak menyelesaikan masalah konkurensi sendiri, tetapi mereka membuat penyelesaiannya lebih mudah.

Pertimbangkan utas T1 yang melewatkan set S ke utas T2 lainnya. Jika S bisa berubah, T1 memiliki masalah: Ia kehilangan kendali atas apa yang terjadi dengan S. Thread T2 dapat memodifikasinya, jadi T1 tidak dapat mengandalkan sama sekali pada konten S. Dan sebaliknya - T2 tidak dapat memastikan bahwa T1 tidak memodifikasi S sementara T2 beroperasi di atasnya.

Salah satu solusinya adalah dengan menambahkan semacam kontrak pada komunikasi T1 dan T2 sehingga hanya satu dari utas yang diizinkan untuk memodifikasi S. Ini rawan kesalahan dan membebani desain dan implementasi.

Solusi lain adalah T1 atau T2 mengkloning struktur data (atau keduanya, jika tidak terkoordinasi). Namun, jika S tidak persisten, ini adalah operasi O (n) yang mahal .

Jika Anda memiliki struktur data yang persisten, Anda bebas dari beban ini. Anda dapat meneruskan struktur ke utas lain dan Anda tidak perlu peduli apa fungsinya dengannya. Kedua utas memiliki akses ke versi asli dan dapat melakukan operasi sewenang-wenang di atasnya - itu tidak mempengaruhi apa yang dilihat utas lainnya.

Lihat juga: struktur data persisten vs tidak berubah .

Lalu mengapa, apakah imutabilitas PDS disebut-sebut sebagai sesuatu yang bermanfaat untuk "keamanan benang"? Apakah ada contoh nyata di mana PDS membantu dalam sinkronisasi, atau menyelesaikan masalah konkurensi?

Manfaat utama dari PDS dalam hal ini adalah Anda dapat memodifikasi sebagian data tanpa membuat semuanya unik (tanpa menyalin semuanya secara mendalam, sehingga bisa dikatakan). Itu memiliki banyak manfaat potensial selain memungkinkan Anda untuk menulis fungsi-fungsi murah tanpa efek samping: menanamkan salinan dan data yang disisipkan, sistem undo sepele, fitur pemutaran ulang sepele dalam game, pengeditan sepele yang tidak merusak, keamanan pengecualian sepele, dll. Dll. Dll.

Orang dapat membayangkan suatu struktur data yang akan bertahan tetapi bisa berubah. Misalnya, Anda bisa mengambil daftar tertaut, diwakili oleh pointer ke simpul pertama, dan operasi prependen yang akan mengembalikan daftar baru, yang terdiri dari simpul kepala baru ditambah daftar sebelumnya. Karena Anda masih memiliki referensi ke kepala sebelumnya, Anda dapat mengakses dan memodifikasi daftar ini, yang sementara itu juga tertanam di dalam daftar baru. Meskipun mungkin, paradigma seperti itu tidak menawarkan manfaat dari struktur data yang persisten dan tidak dapat diubah, misalnya, tentu saja tidak secara aman di-thread thread. Namun, itu mungkin memiliki kegunaan selama pengembang tahu apa yang mereka lakukan, misalnya untuk efisiensi ruang. Perhatikan juga bahwa sementara struktur mungkin bisa berubah pada tingkat bahasa di mana tidak ada yang mencegah kode memodifikasinya,

Singkatnya cerita, tanpa kekekalan (dipaksakan oleh bahasa atau oleh konvensi), kegigihan struktur data kehilangan sebagian manfaatnya (keamanan utas) tetapi tidak yang lain (efisiensi ruang untuk beberapa skenario).

Adapun contoh dari bahasa non-fungsional, Java String.substring()menggunakan apa yang saya sebut struktur data persisten. String diwakili oleh array karakter plus offset awal dan akhir dari berbagai array yang sebenarnya digunakan. Saat substring dibuat, objek baru kembali menggunakan array karakter yang sama, hanya dengan offset awal dan akhir yang dimodifikasi. Karena Stringtidak dapat diubah, itu (sehubungan dengan substring()operasi, bukan yang lain) adalah struktur data persisten yang tidak berubah.

Ketidakberubahan struktur data adalah bagian yang relevan dengan keamanan utas. Ketekunan mereka (penggunaan kembali potongan yang ada saat struktur baru dibuat) relevan dengan efisiensi ketika bekerja dengan koleksi tersebut. Karena tidak dapat diubah, operasi seperti menambahkan item tidak mengubah struktur yang ada tetapi mengembalikan yang baru, dengan elemen tambahan ditambahkan. Jika setiap kali seluruh struktur disalin, dimulai dengan koleksi kosong dan menambahkan 1000 elemen satu per satu untuk berakhir dengan koleksi 1000-elemen, akan membuat objek sementara dengan 0 + 1 + 2 + ... + 999 = 500.000 elemen total yang akan menjadi pemborosan besar. Dengan struktur data yang persisten, ini dapat dihindari karena koleksi 1 elemen digunakan kembali dalam elemen 2, yang digunakan kembali dalam elemen 3 elemen dan seterusnya,

Saya diakui bias sebagai orang yang menerapkan konsep-konsep seperti itu di C ++ oleh bahasa dan sifatnya, serta domain saya, dan bahkan cara kami menggunakan bahasa. Tetapi mengingat hal-hal ini, saya pikir desain abadi adalah aspek yang paling tidak menarik ketika datang untuk menuai sebagian besar manfaat yang terkait dengan pemrograman fungsional, seperti keselamatan benang, kemudahan penalaran tentang sistem, menemukan lebih banyak penggunaan kembali untuk fungsi (dan menemukan kita bisa gabungkan mereka dalam urutan apa pun tanpa kejutan yang tidak menyenangkan), dll.

Ambil contoh C ++ sederhana ini (diakui tidak dioptimalkan karena kesederhanaan untuk menghindari mempermalukan diri sendiri di depan para ahli pemrosesan gambar di luar sana):

// Inputs an image and outputs a new one with the specified size.
Image resized_image(const Image& src, int new_w, int new_h)
{
     Image dst(new_w, new_h);
     for (int y=0; y < new_h; ++y)
     {
         for (int x=0; x < new_w; ++x)
              dst[y][x] = src.sample(x / (float)new_w, y / (float)new_h);
     }
     return dst;
}

Sementara implementasi dari fungsi itu bermutasi status lokal (dan sementara) dalam bentuk dua variabel counter dan gambar lokal sementara untuk output, ia tidak memiliki efek samping eksternal. Ini input gambar dan output yang baru. Kita bisa multithread ke konten hati kita. Mudah untuk dipikirkan, mudah untuk diuji secara menyeluruh. Ini pengecualian-aman karena jika ada yang melempar, gambar baru secara otomatis dibuang dan kita tidak perlu khawatir tentang mengembalikan efek samping eksternal (tidak ada gambar eksternal yang dimodifikasi di luar ruang lingkup fungsi, jadi untuk berbicara).

Saya melihat sedikit yang bisa didapat, dan berpotensi banyak yang hilang, dengan menghasilkan Image tidak berubah dalam konteks di atas, dalam C ++, kecuali untuk berpotensi membuat fungsi di atas lebih sulit untuk diimplementasikan, dan mungkin sedikit kurang efisien.

Kemurnian

Jadi fungsinya murni (bebas dari eksternal efek samping ) sangat menarik bagi saya, dan saya menekankan pentingnya memberi mereka sering kepada anggota tim bahkan di C ++. Tetapi desain yang tidak dapat diubah, diterapkan pada umumnya tidak ada konteks dan nuansa, hampir tidak menarik bagi saya karena, mengingat sifat imperatif bahasa, sering berguna dan praktis untuk dapat bermutasi beberapa objek temporer lokal dalam proses efisien (keduanya untuk pengembang dan perangkat keras) menerapkan fungsi murni.

Menyalin Struktur Berat yang Murah

Properti kedua yang paling berguna yang saya temukan adalah kemampuan untuk dengan murah menyalin struktur data yang sangat besar di sekitar ketika biaya melakukannya, seperti yang sering dikeluarkan untuk membuat fungsi murni mengingat sifat input / output yang ketat, akan non-sepele. Ini tidak akan menjadi struktur kecil yang dapat ditampung di tumpukan. Mereka akan menjadi besar, struktur yang kuat, seperti keseluruhan Sceneuntuk video game.

Dalam hal itu penyalinan overhead dapat mencegah peluang untuk paralelisme yang efektif, karena mungkin sulit untuk memaralelkan fisika dan rendering secara efektif tanpa mengunci dan menghambat satu sama lain jika fisika bermutasi adegan yang renderer secara bersamaan mencoba menggambar, sementara secara bersamaan memiliki fisika dalam menyalin seluruh adegan permainan hanya untuk menghasilkan satu frame dengan fisika yang diterapkan mungkin sama-sama tidak efektif. Namun, jika sistem fisika 'murni' dalam arti bahwa itu hanya memasukkan adegan dan menghasilkan yang baru dengan fisika yang diterapkan, dan kemurnian seperti itu tidak datang pada biaya overhead menyalin astronomi, itu bisa dengan aman beroperasi secara paralel dengan penyaji tanpa menunggu yang lain.

Jadi kemampuan untuk dengan murah menyalin data yang sangat besar dari keadaan aplikasi Anda dan menghasilkan versi yang baru dan dimodifikasi dengan biaya minimal untuk pemrosesan dan penggunaan memori dapat benar-benar membuka pintu baru untuk kemurnian dan paralelisme yang efektif, dan di sana saya menemukan banyak pelajaran untuk dipelajari dari bagaimana struktur data persisten diimplementasikan. Tetapi apa pun yang kita buat menggunakan pelajaran seperti itu tidak harus sepenuhnya gigih, atau menawarkan antarmuka yang tidak dapat diubah (mungkin menggunakan copy-on-write, misalnya, atau "builder / transient"), untuk mencapai kemampuan ini menjadi murah. untuk menyalin dan memodifikasi hanya bagian dari salinan tanpa menggandakan penggunaan memori dan akses memori dalam pencarian kami untuk paralelisme dan kemurnian dalam fungsi / sistem / pipa kami.

Kekekalan

Akhirnya ada kekekalan yang saya anggap paling tidak menarik dari ketiganya, tapi itu bisa menegakkan, dengan tangan besi, ketika desain objek tertentu tidak dimaksudkan untuk digunakan sebagai temporaries lokal untuk fungsi murni, dan sebagai gantinya dalam konteks yang lebih luas, yang berharga jenis "kemurnian tingkat objek", seperti dalam semua metode tidak lagi menyebabkan efek samping eksternal (tidak lagi bermutasi variabel anggota di luar lingkup lokal langsung dari metode).

Dan sementara saya menganggapnya sebagai yang paling tidak menarik dari ketiga bahasa ini seperti C ++, ini tentu saja dapat menyederhanakan pengujian dan keamanan utas dan alasan objek yang tidak sepele. Ini dapat menjadi beban untuk bekerja dengan jaminan bahwa suatu objek tidak dapat diberikan kombinasi keadaan unik di luar konstruktornya, misalnya, dan bahwa kita dapat dengan bebas menyebarkannya, bahkan dengan referensi / penunjuk tanpa bersandar pada kesegaran dan membaca. hanya iterator dan handle dan semacamnya, sambil menjamin (well, setidaknya sebanyak yang kami bisa dalam bahasa) bahwa konten aslinya tidak akan dimutasi.

Tetapi saya menemukan ini properti yang paling tidak menarik karena sebagian besar objek yang saya lihat bermanfaat digunakan sementara, dalam bentuk yang bisa berubah, untuk mengimplementasikan fungsi murni (atau bahkan konsep yang lebih luas, seperti "sistem murni" yang mungkin menjadi objek atau rangkaian dari berfungsi dengan efek pamungkas hanya memasukkan sesuatu dan menghasilkan sesuatu yang baru tanpa menyentuh yang lain), dan saya pikir kekekalan yang dibawa ke ekstremitas dalam bahasa yang sangat penting adalah tujuan yang agak kontraproduktif. Saya akan menerapkannya dengan hemat untuk bagian-bagian basis kode di mana itu sangat membantu.

Akhirnya:

[...] akan terlihat bahwa struktur data persisten tidak cukup untuk menangani skenario di mana satu utas membuat perubahan yang terlihat oleh utas lainnya. Untuk ini, tampaknya kita harus menggunakan perangkat seperti atom, referensi, memori transaksional perangkat lunak, atau bahkan kunci klasik dan mekanisme sinkronisasi.

Tentu saja jika desain Anda meminta modifikasi (dalam arti desain pengguna-akhir) agar dapat dilihat oleh banyak utas secara bersamaan ketika mereka terjadi, kami kembali ke sinkronisasi atau setidaknya papan gambar untuk mencari tahu beberapa cara canggih untuk menangani hal ini ( Saya telah melihat beberapa contoh yang sangat rumit yang digunakan oleh para ahli yang berurusan dengan masalah-masalah seperti ini dalam pemrograman fungsional).

Tetapi saya telah menemukan, begitu Anda mendapatkan penyalinan dan kemampuan semacam itu untuk mengeluarkan versi yang dimodifikasi sebagian dari struktur besar yang murah, seperti yang akan Anda peroleh dengan struktur data yang persisten sebagai contoh, ia sering membuka banyak pintu dan peluang yang mungkin Anda miliki. tidak pernah memikirkan sebelumnya untuk memparalelkan kode yang dapat berjalan sepenuhnya secara independen satu sama lain dalam semacam pipa paralel I / O yang ketat. Bahkan jika beberapa bagian dari algoritma harus serial, Anda mungkin menunda pemrosesan itu menjadi satu utas tetapi menemukan bahwa bersandar pada konsep-konsep ini telah membuka pintu dengan mudah, dan tanpa khawatir, sejajar dengan 90% dari pekerjaan besar, misalnya