Apakah mungkin untuk memprediksi secara statis kapan harus membatalkan alokasi memori --- hanya dari kode sumber?

Memori (dan kunci sumber daya) dikembalikan ke OS pada titik deterministik selama eksekusi program. Alur kontrol suatu program dengan sendirinya cukup untuk mengetahui di mana, pasti, sumber daya yang diberikan dapat dialokasikan. Sama seperti bagaimana seorang programmer manusia tahu di mana harus menulis fclose(file)ketika program selesai dengan itu.

GC menyelesaikan ini dengan mencari tahu secara langsung selama runtime ketika aliran kontrol dijalankan. Tetapi sumber kebenaran yang sebenarnya tentang aliran kontrol adalah sumbernya. Jadi secara teoritis, harus dimungkinkan untuk menentukan di mana memasukkan free()panggilan sebelum kompilasi dengan menganalisis sumber (atau AST).

Penghitungan referensi adalah cara yang jelas untuk mengimplementasikan ini, tetapi mudah untuk menghadapi situasi di mana pointer masih dirujuk (masih dalam cakupan) namun tidak lagi diperlukan. Ini hanya mengkonversi tanggung jawab deallocating pointer secara manual ke tanggung jawab untuk mengelola secara manual ruang lingkup / referensi ke pointer tersebut.

Sepertinya mungkin untuk menulis sebuah program yang dapat membaca sumber program dan:

1. memprediksi semua permutasi aliran kontrol program --- dengan akurasi yang sama seperti menonton eksekusi langsung program
2. melacak semua referensi ke sumber daya yang dialokasikan
3. untuk setiap referensi, lintasi seluruh aliran kontrol selanjutnya untuk menemukan titik paling awal bahwa referensi dijamin tidak akan pernah direferensikan
4. pada saat itu, masukkan pernyataan deallokasi di baris kode sumber itu

Apakah ada sesuatu di luar sana yang sudah melakukan ini? Saya tidak berpikir Rust atau C ++ smart pointer / RAII adalah hal yang sama.

Ambil contoh (buat-buat) ini:

void* resource1;
void* resource2;

while(true){

    int input = getInputFromUser();

    switch(input){
        case 1: resource1 = malloc(500); break;
        case 2: resource2 = resource1; break;
        case 3: useResource(resource1); useResource(resource2); break;
    }
}

Kapan harus bebas dipanggil? sebelum malloc dan menetapkan ke resource1kita tidak bisa karena itu bisa disalin resource2, sebelum menetapkan kepada resource2kita tidak bisa karena kita mungkin mendapat 2 dari pengguna dua kali tanpa campur tangan 1.

Satu-satunya cara untuk memastikan adalah dengan menguji sumber daya1 dan sumber daya2 untuk melihat apakah mereka tidak sama dalam kasus 1 dan 2 dan membebaskan nilai lama jika tidak. Ini pada dasarnya penghitungan referensi di mana Anda tahu hanya ada 2 kemungkinan referensi.

RAII secara otomatis tidak sama, tetapi memiliki efek yang sama. Ini memberikan jawaban yang mudah untuk pertanyaan "bagaimana Anda tahu kapan ini tidak dapat diakses lagi?" dengan menggunakan ruang lingkup untuk mencakup area ketika sumber daya tertentu sedang digunakan.

Anda mungkin ingin mempertimbangkan masalah serupa "bagaimana saya bisa tahu program saya tidak akan mengalami kesalahan ketik saat runtime?". Solusi untuk ini adalah tidak memprediksi semua jalur eksekusi melalui program tetapi dengan menggunakan sistem anotasi dan inferensi tipe untuk membuktikan bahwa tidak mungkin ada kesalahan seperti itu. Rust adalah upaya untuk memperluas properti bukti ini ke alokasi memori.

Dimungkinkan untuk menulis bukti tentang perilaku program tanpa harus menyelesaikan masalah penghentian, tetapi hanya jika Anda menggunakan anotasi untuk membatasi program. Lihat juga bukti keamanan (sel4 dll.)

Ya, ini ada di alam liar. ML Kit adalah kompiler berkualitas produksi yang memiliki strategi yang dijelaskan (kurang lebih) sebagai salah satu opsi manajemen memori yang tersedia. Ini juga memungkinkan untuk penggunaan GC konvensional atau hibridisasi dengan penghitungan referensi (Anda dapat menggunakan heap profiler untuk melihat strategi mana yang benar-benar akan menghasilkan hasil terbaik untuk program Anda).

Retrospektif pada manajemen memori berbasis wilayah adalah artikel oleh penulis asli Kit ML yang membahas keberhasilan dan kegagalannya. Kesimpulan akhirnya adalah bahwa strategi itu praktis ketika menulis dengan bantuan profiler tumpukan.

(Ini adalah ilustrasi yang bagus tentang mengapa Anda biasanya tidak melihat pada Masalah Pemutusan untuk jawaban atas pertanyaan-pertanyaan teknik praktis: kami tidak ingin atau perlu menyelesaikan kasus umum untuk sebagian besar program yang realistis.)

memprediksi semua permutasi dari aliran kontrol program

Disinilah letak masalahnya. Jumlah permutasi sangat besar (dalam praktiknya tidak terbatas) untuk setiap program non-sepele, sehingga waktu dan memori yang dibutuhkan akan membuat ini benar-benar tidak praktis.

Masalah penghentian membuktikan ini tidak mungkin dalam semua kasus. Namun, masih mungkin dalam banyak kasus, dan pada kenyataannya, dilakukan oleh hampir semua penyusun untuk kemungkinan mayoritas variabel. Ini adalah bagaimana kompiler dapat mengatakan aman untuk hanya mengalokasikan variabel pada stack atau bahkan register, daripada penyimpanan heap jangka panjang.

Jika Anda memiliki fungsi murni atau semantik kepemilikan yang benar-benar bagus, Anda dapat memperluas analisis statis lebih lanjut, meskipun itu menjadi lebih mahal untuk dilakukan sehingga semakin banyak cabang yang diambil oleh kode Anda.

Jika seorang programmer atau tim menulis seluruh program, masuk akal bahwa poin desain dapat diidentifikasi di mana memori (dan sumber daya lainnya) harus dibebaskan. Jadi, ya, analisis statis dari desain mungkin cukup dalam konteks yang lebih terbatas.

Namun, ketika Anda memfaktorkan DLL, API, kerangka kerja pihak ketiga, (dan juga ikut-ikutan), itu bisa sangat sulit (bahkan, tidak mungkin dalam semua kasus) bagi programmer yang menggunakan alasan yang benar tentang entitas apa yang memiliki memori dan memori apa. kapan terakhir kali menggunakannya. Tersangka bahasa biasa kami tidak cukup mendokumentasikan transfer kepemilikan memori objek dan array, dangkal dan dalam. Jika seorang programmer tidak dapat menjelaskan hal itu (secara statis atau dinamis!) Maka kompiler kemungkinan besar tidak dapat melakukannya. Sekali lagi, ini disebabkan oleh fakta bahwa transfer kepemilikan memori tidak ditangkap dalam pemanggilan metode atau oleh antarmuka, dll., Jadi, tidak, tidak mungkin untuk memprediksi secara statis kapan atau di mana dalam kode untuk melepaskan memori.

Karena ini adalah masalah serius, banyak bahasa modern memilih pengumpulan sampah, yang secara otomatis mendapatkan kembali memori beberapa saat setelah referensi langsung terakhir. Namun, GC memiliki biaya kinerja yang signifikan (terutama untuk aplikasi waktu nyata), jadi bukan obat yang universal. Selanjutnya, Anda masih dapat memiliki kebocoran memori menggunakan GC (misalnya koleksi yang hanya tumbuh). Namun, ini adalah solusi yang bagus untuk sebagian besar latihan pemrograman.

Ada beberapa alternatif (beberapa muncul).

Bahasa Rust membawa RAII ke ekstrem. Ini memberikan konstruksi linguistik yang menentukan transfer kepemilikan dalam metode kelas dan antarmuka secara lebih rinci, misalnya objek yang ditransfer-ke vs dipinjam-oleh antara penelepon dan callee, atau dalam objek yang lebih lama. Ini memberikan tingkat keamanan waktu kompilasi yang tinggi terhadap manajemen memori. Namun, itu bukan bahasa yang sepele untuk dijemput, dan juga bukan tanpa masalah itu (misalnya saya tidak berpikir desainnya sepenuhnya stabil, hal-hal tertentu masih sedang diuji coba, dan dengan demikian, berubah).

Swift dan Objective-C pergi rute lain, yang sebagian besar penghitungan referensi otomatis. Penghitungan referensi menjadi masalah dengan siklus, dan, ada tantangan programmer yang signifikan, misalnya, terutama dengan penutupan.

Jika suatu program tidak bergantung pada input yang tidak diketahui maka ya, itu harus dimungkinkan (dengan peringatan bahwa itu mungkin tugas yang kompleks dan mungkin memakan waktu lama; tetapi itu juga berlaku untuk program tersebut). Program semacam itu akan sepenuhnya dapat dipecahkan pada waktu kompilasi; dalam istilah C ++, mereka bisa (hampir) sepenuhnya terdiri dari constexprs. Contoh sederhana akan menghitung 100 digit pi pertama atau untuk mengurutkan kamus yang dikenal.

Membebaskan memori, secara umum, sama dengan masalah penghentian - jika Anda tidak dapat secara statis mengetahui apakah suatu program akan berhenti (secara statis), Anda juga tidak dapat memastikan apakah itu akan membebaskan memori (secara statis).

function foo(int a) {
    void *p = malloc(1);
    ... do something which may, or may not, halt ...
    free(p);
}

https://en.wikipedia.org/wiki/Halting_problem

Yang mengatakan, Rust sangat bagus ... https://doc.rust-lang.org/book/ownership.html