Mengapa kita membutuhkan Heap jika semuanya dapat dilakukan dengan lebih efisien di Stack?

24

Ini sebenarnya agak terkait dengan pertanyaan yang saya tanyakan kemarin tentang mengapa baik Stack dan Heap diperlukan dalam aplikasi yang kita gunakan hari ini (dan mengapa kita tidak bisa hanya pergi dengan Heap daripada keduanya, untuk memiliki yang sederhana & standar tunggal yang harus dilalui).

Namun, banyak tanggapan menunjukkan bahwa tumpukan tidak tergantikan karena fakta bahwa ratusan (atau ribuan) kali lebih cepat daripada mencoba mengalokasikan / merujuk Heap. Saya tahu ada masalah dengan alokasi penyimpanan dinamis jika kita menghapus Heap, tetapi bukankah ada cara untuk mengatasi hal ini, atau mungkin, cara untuk meningkatkan Stack sehingga dapat menangani alokasi memori dinamis?

stack heap Dark Templar
sumber
4
Dua kutipan dari pertanyaan Anda sebelumnya: "Kelemahan terpenting adalah memiliki ruang terbatas, dan dengan demikian menyimpan benda-benda besar di dalamnya, atau mencoba menggunakannya untuk benda-benda berumur panjang, keduanya merupakan gagasan buruk" dan "tumpukan adalah cara yang sangat efisien struktur untuk mengelola data yang mematuhi aturan LIFO (terakhir masuk pertama keluar) ".
Cascabel
2
Premis Anda salah - tidak semuanya dapat dilakukan dengan lebih efisien di stack. Ini tidak bertentangan dengan jawaban yang Anda terima - bahwa apa yang dapat dilakukan pada stack dapat dilakukan jauh lebih cepat di sana.
Ingo
... dengan asumsi perangkat keras Anda memiliki tumpukan, atau pengalamatan relatif-tumpukan.
Ritch Melton
3
Saya yakin. Saya katakan lakukan itu.
JeffO

Jawaban:

25

Masalah dengan tumpukan adalah bahwa Anda tidak dapat "membebaskan" memori kecuali jika berada di atas tumpukan. Misalnya, Anda mengalokasikan 3 hal dengan berbagai ukuran:

a = allocate(2000000); // 2000000 bytes
b = allocate(1);
c = allocate(5000000);

Tumpukan akan ada adi bagian bawah, bdi tengah, dan cdi atas. Ini menjadi masalah jika kita ingin bebas b:

free(b); // b is not on top! We have to wait until c is freed!

Solusinya adalah untuk memindahkan semua data setelah bdan bergeser jika begitu setelah itu a. Ini berfungsi, tetapi akan membutuhkan 50.000.000 salinan dalam kasus ini - sesuatu yang akan jauh lebih lambat daripada tumpukan.

Ini sebabnya kami memiliki tumpukan. Meskipun alokasi mungkin lebih lambat daripada tumpukan ( O(log n)vs O(1)), tumpukan memungkinkan membebaskan memori di lokasi yang sewenang-wenang menjadi cepat - O(log n), dibandingkan dengan tumpukanO(n)

Pubby
sumber
4
Terkait dengan ini adalah bahwa Facebook tidak menghapus konten dari disk-nya ketika Anda memintanya untuk menghapusnya, itu hanya menghilangkan pointer ke sana. Jelas bahwa overhead dari mencoba defragment atau mencoba menemukan celah yang setara pada disk terlalu memakan waktu pada tingkat yang mereka tulis data, jadi mereka hanya menambahkan semuanya pada tanda air yang tinggi pada disk.
Paul Tomblin
Disk Facebook bisa dilihat sebagai tumpukan. Dan saya cukup yakin mereka memiliki semacam pengumpulan sampah untuk disk mereka.
deadalnix
2
@deadalnix Sebenarnya itu adalah contoh menggunakan tumpukan besar bukan tumpukan yang biasanya digunakan untuk jumlah memori yang lebih besar. Facebook adalah kasus khusus. Data ditambahkan jauh lebih cepat daripada yang dihapus sehingga deallokasi tidak membuat perbedaan yang signifikan terhadap tingkat pertumbuhan - Anda dapat dengan sengaja memasukkan kebocoran memori dalam desain untuk mendapatkan alokasi O (1).
Tom Clarkson
7
@PaulTomblin Alasan utama FB tidak menghapus konten adalah agar mereka dapat menambangnya untuk keuntungan mereka ...
quant_dev
5
Facebook doesn't remove content from its disk when you ask it to remove it, it just removes the pointer to it- Yang pada dasarnya adalah apa yang terjadi ketika Anda melakukan penghapusan file biasa pada sistem operasi apa pun.
Robert Harvey
5

Stack adalah per-thread, Heap adalah proses-lebar

Jika memiliki 100 utas, semua item pekerjaan pemrosesan saya masukkan ke dalam antrian, di mana tepatnya saya mengalokasikan item kerja sehingga 100 thread mana pun dapat melihatnya?

Ada jenis memori lain juga

Misalnya file yang dipetakan memori, memori bersama, I / O dipetakan (mode kernel). Argumen efisiensi agak diperdebatkan dalam situasi ini.

JBRWilkinson
sumber
4

Tumpukan adalah struktur LIFO (last-in-first-out), ke atas di mana pointer referensi disimpan (biasanya didukung oleh perangkat keras). Setelah mengatakan ini, apa pun yang Anda coba alokasikan pada stack bukan heap harus menjadi variabel lokal di setiap fungsi, di bagian atas tumpukan ini. Jadi, alasan utama terhadap tumpukan adalah bahwa rutin utama () Anda perlu melakukan pra-alokasi semua struktur data yang digunakan program Anda (yang dimaksudkan untuk ada selama durasi lengkap program Anda) sebelumnya karena semua struktur data dialokasikan dalam panggilan fungsi akhirnya akan dihapus ketika panggilan fungsi kembali dan frame atau catatan aktivasi mereka muncul dari tumpukan.

Alex
sumber
3
LIFO, bukan FIFO.
Pubby
kadang-kadang juga disebut FILO;)
oenone
3

Tumpukan bekerja sangat baik untuk alokasi memori yang mematuhi aturan Last in First out (LIFO), yaitu, Anda membebaskan memori dalam urutan terbalik yang tepat yang Anda alokasikan. LIFO adalah pola alokasi memori yang sangat umum, mungkin yang paling umum. Tapi itu bukan satu-satunya pola, atau bahkan satu-satunya pola umum. Untuk menulis program efisien yang dapat mengatasi berbagai masalah, kita harus membuat pola yang kurang umum, bahkan jika itu berarti infrastruktur yang lebih kompleks.

Jika saya bisa mendapatkan semua meta untuk paragraf: Anda adalah pemula, sebagai pemula Anda menghargai kesederhanaan, dan aturan hitam dan putih. Namun, sebagai pemula, Anda hanya memiliki pandangan lubang intip dari berbagai masalah dan kendala yang harus ditampung oleh program komputer. Anda memasuki teknologi yang telah dikembangkan secara aktif selama 75 tahun. Tidak ada yang salah dengan bertanya mengapa hal itu terjadi, tetapi jawabannya umumnya adalah "Ya, kami mencoba metode yang sederhana dan mudah, 50 tahun yang lalu, dan ternyata tidak bekerja dengan baik untuk seluruh kelas masalah, jadi kami harus melakukan sesuatu yang lebih rumit ". Seiring kemajuan teknologi, kesederhanaan umumnya harus memberi jalan kepada efisiensi dan fleksibilitas.

Charles E. Grant
sumber
0

Sebagai contoh lain, penutupan. Jika Anda menumpuk pop, maka Anda dapat kehilangan catatan aktivasi penutupan Anda. Jadi jika Anda ingin agar fungsi anonim dan datanya tetap ada, Anda harus menyimpannya di tempat lain selain tumpukan runtime.

segera
sumber
0

Di antara banyak alasan lain untuk mengalokasikan penyimpanan tumpukan.

Jika Anda ingin meneruskan alamat objek kembali ke program panggilan, Anda tidak boleh melewati alamat variabel stack, karena, penyimpanan stack akan digunakan kembali dan mungkin ditimpa oleh fungsi selanjutnya yang disebut. Anda perlu mendapatkan penyimpanan yang diperlukan menggunakan malloc () untuk memastikannya tidak akan ditimpa oleh panggilan ke fungsi berikutnya.

Anda dapat meneruskan alamat item tumpukan dari fungsi Anda ke fungsi yang Anda panggil, karena Anda dapat menjamin item itu ada sampai program Anda "mengembalikan ()". Tetapi segera setelah fungsi Anda kembali, semua penyimpanan stack siap diperebutkan.

James Anderson
sumber