Apa tujuan tumpukan? Mengapa kita membutuhkannya?

Jadi saya sedang belajar MSIL sekarang untuk belajar men-debug aplikasi C # .NET saya.

Saya selalu bertanya-tanya: apa tujuan tumpukan itu?

Hanya untuk menempatkan pertanyaan saya dalam konteks:
Mengapa ada transfer dari memori ke tumpukan atau "memuat?" Di sisi lain, mengapa ada transfer dari stack ke memori atau "penyimpanan"? Mengapa tidak menempatkan semuanya dalam memori saja?

• Apakah karena lebih cepat?
• Apakah ini karena berbasis RAM?
• Untuk efisiensi?

Saya mencoba memahami ini untuk membantu saya memahami kode CIL jauh lebih dalam.

UPDATE: Saya sangat menyukai pertanyaan ini sehingga menjadikannya subjek blog saya pada 18 November 2011 . Terima kasih atas pertanyaannya!

Saya selalu bertanya-tanya: apa tujuan tumpukan itu?

Saya berasumsi Anda maksud tumpukan evaluasi bahasa MSIL, dan bukan tumpukan per-thread yang sebenarnya saat runtime.

Mengapa ada transfer dari memori ke stack atau "loading?" Di sisi lain, mengapa ada transfer dari stack ke memori atau "penyimpanan"? Mengapa tidak menempatkan semuanya dalam memori saja?

MSIL adalah bahasa "mesin virtual". Kompiler seperti kompiler C # menghasilkan CIL , dan kemudian pada saat runtime kompiler lain yang disebut kompiler JIT (Just In Time) mengubah IL menjadi kode mesin aktual yang dapat dieksekusi.

Jadi pertama-tama mari kita jawab pertanyaan "mengapa memiliki MSIL?" Mengapa tidak hanya membuat kompiler C # menulis kode mesin?

Karena lebih murah melakukannya dengan cara ini. Misalkan kita tidak melakukannya dengan cara itu; misalkan setiap bahasa harus memiliki generator kode mesin sendiri. Anda memiliki dua puluh bahasa berbeda: C #, JScript .NET , Visual Basic, IronPython , F # ... Dan anggaplah Anda memiliki sepuluh prosesor yang berbeda. Berapa banyak pembuat kode yang harus Anda tulis? 20 x 10 = 200 generator kode. Itu banyak pekerjaan. Sekarang anggaplah Anda ingin menambahkan prosesor baru. Anda harus menulis pembuat kode untuk itu dua puluh kali, satu untuk setiap bahasa.

Lebih jauh lagi, ini adalah pekerjaan yang sulit dan berbahaya. Menulis generator kode yang efisien untuk chip yang bukan keahlian Anda adalah pekerjaan berat! Desainer kompiler ahli dalam analisis semantik bahasa mereka, bukan pada alokasi register efisien dari set chip baru.

Sekarang anggaplah kita melakukannya dengan cara CIL. Berapa banyak generator CIL yang harus Anda tulis? Satu per bahasa. Berapa banyak kompiler JIT yang harus Anda tulis? Satu per prosesor. Total: 20 + 10 = 30 generator kode. Selain itu, generator bahasa-ke-CIL mudah untuk ditulis karena CIL adalah bahasa yang sederhana, dan generator kode-CIL ke mesin juga mudah ditulis karena CIL adalah bahasa yang sederhana. Kami menyingkirkan semua seluk-beluk C # dan VB dan yang lainnya dan "menurunkan" semuanya ke bahasa sederhana yang mudah untuk menulis jitter.

Memiliki bahasa perantara menurunkan biaya memproduksi kompiler bahasa baru secara dramatis . Ini juga menurunkan biaya mendukung chip baru secara dramatis. Anda ingin mendukung chip baru, Anda menemukan beberapa ahli pada chip itu dan minta mereka menulis jitter CIL dan Anda selesai; Anda kemudian mendukung semua bahasa tersebut di chip Anda.

OK, jadi kami telah menetapkan mengapa kami memiliki MSIL; karena memiliki bahasa perantara menurunkan biaya. Lalu mengapa bahasa itu "mesin tumpukan"?

Karena mesin stack secara konseptual sangat sederhana untuk penulis kompiler bahasa untuk menangani. Stack adalah mekanisme sederhana dan mudah dipahami untuk menggambarkan komputasi. Mesin stack juga secara konsep sangat mudah untuk penulis kompiler JIT untuk berurusan dengan. Menggunakan tumpukan adalah abstraksi yang disederhanakan, dan karena itu sekali lagi, ini menurunkan biaya kami .

Anda bertanya "mengapa punya setumpuk sama sekali?" Mengapa tidak melakukan semuanya langsung dari memori? Baiklah, mari kita pikirkan tentang itu. Misalkan Anda ingin membuat kode CIL untuk:

int x = A() + B() + C() + 10;

Misalkan kita memiliki konvensi yang "menambahkan", "panggilan", "toko" dan seterusnya selalu mengambil argumen mereka dari tumpukan dan meletakkan hasilnya (jika ada) di tumpukan. Untuk menghasilkan kode CIL untuk C # ini kami hanya mengatakan sesuatu seperti:

load the address of x // The stack now contains address of x
call A()              // The stack contains address of x and result of A()
call B()              // Address of x, result of A(), result of B()
add                   // Address of x, result of A() + B()
call C()              // Address of x, result of A() + B(), result of C()
add                   // Address of x, result of A() + B() + C()
load 10               // Address of x, result of A() + B() + C(), 10
add                   // Address of x, result of A() + B() + C() + 10
store in address      // The result is now stored in x, and the stack is empty.

Sekarang misalkan kita melakukannya tanpa tumpukan. Kami akan melakukannya dengan cara Anda, di mana setiap opcode mengambil alamat operandnya dan alamat di mana ia menyimpan hasilnya :

Allocate temporary store T1 for result of A()
Call A() with the address of T1
Allocate temporary store T2 for result of B()
Call B() with the address of T2
Allocate temporary store T3 for the result of the first addition
Add contents of T1 to T2, then store the result into the address of T3
Allocate temporary store T4 for the result of C()
Call C() with the address of T4
Allocate temporary store T5 for result of the second addition
...

Anda lihat bagaimana ini terjadi? Kode kita menjadi semakin besar karena kita harus secara eksplisit mengalokasikan semua penyimpanan sementara yang biasanya dengan konvensi tinggal ditumpuk . Lebih buruk lagi, opcode kita sendiri menjadi semakin besar karena mereka semua sekarang harus mengambil sebagai argumen alamat yang akan mereka tulis hasilnya, dan alamat masing-masing operan. Instruksi "add" yang tahu bahwa ia akan mengambil dua hal dari stack dan meletakkan satu hal dapat berupa satu byte tunggal. Instruksi tambahan yang mengambil dua alamat operan dan alamat hasil akan sangat besar.

Kami menggunakan opcode berbasis tumpukan karena tumpukan memecahkan masalah umum . Yaitu: Saya ingin mengalokasikan beberapa penyimpanan sementara, gunakan segera dan kemudian singkirkan segera setelah saya selesai . Dengan membuat asumsi bahwa kita memiliki tumpukan yang kita miliki, kita dapat membuat opcode sangat kecil dan kodenya sangat singkat.

PEMBARUAN: Beberapa pemikiran tambahan

Kebetulan, ide ini menurunkan biaya secara drastis dengan (1) menetapkan mesin virtual, (2) menulis kompiler yang menargetkan bahasa VM, dan (3) menulis implementasi VM pada berbagai perangkat keras, bukan ide baru sama sekali . Itu tidak berasal dari MSIL, LLVM, bytecode Java, atau infrastruktur modern lainnya. Implementasi paling awal dari strategi ini yang saya ketahui adalah mesin pcode dari tahun 1966.

Yang pertama saya secara pribadi mendengar konsep ini adalah ketika saya belajar bagaimana implementor Infocom berhasil membuat Zork berjalan pada begitu banyak mesin yang berbeda dengan sangat baik. Mereka menentukan mesin virtual yang disebut mesin- Z dan kemudian membuat emulator mesin-Z untuk semua perangkat keras yang mereka inginkan untuk menjalankan game mereka. Ini memiliki manfaat tambahan yang sangat besar bahwa mereka dapat menerapkan manajemen memori virtual pada sistem 8-bit primitif; sebuah gim bisa lebih besar daripada yang bisa masuk ke dalam memori karena mereka bisa saja memasukkan kode dari disk ketika mereka membutuhkannya dan membuangnya ketika mereka perlu memuat kode baru.

Perlu diingat bahwa ketika Anda berbicara tentang MSIL maka Anda berbicara tentang instruksi untuk mesin virtual . VM yang digunakan dalam .NET adalah mesin virtual berbasis stack. Berbeda dengan VM berbasis register, Dalvik VM yang digunakan dalam sistem operasi Android adalah contohnya.

Tumpukan dalam VM adalah virtual, tergantung pada penerjemah atau kompilator just-in-time untuk menerjemahkan instruksi VM menjadi kode aktual yang berjalan pada prosesor. Yang dalam kasus .NET hampir selalu merupakan jitter, set instruksi MSIL dirancang untuk diikutkan sejak awal. Berbeda dengan bytecode Java misalnya, ia memiliki instruksi berbeda untuk operasi pada tipe data tertentu. Yang membuatnya dioptimalkan untuk diartikan. Interpreter MSIL sebenarnya ada, tetapi digunakan dalam .NET Micro Framework. Yang berjalan pada prosesor dengan sumber daya yang sangat terbatas, tidak mampu membeli RAM yang diperlukan untuk menyimpan kode mesin.

Model kode mesin yang sebenarnya dicampur, memiliki tumpukan dan register. Salah satu pekerjaan besar dari optimizer kode JIT adalah menemukan cara untuk menyimpan variabel yang disimpan di stack dalam register, sehingga sangat meningkatkan kecepatan eksekusi. Jitter Dalvik memiliki masalah sebaliknya.

Tumpukan mesin merupakan fasilitas penyimpanan yang sangat mendasar yang telah ada dalam desain prosesor untuk waktu yang sangat lama. Ini memiliki referensi lokalitas yang sangat baik, fitur yang sangat penting pada CPU modern yang mengunyah data jauh lebih cepat daripada yang dapat disediakan RAM dan mendukung rekursi. Desain bahasa sangat dipengaruhi oleh memiliki tumpukan, terlihat mendukung variabel lokal dan ruang lingkup terbatas pada badan metode. Masalah signifikan dengan tumpukan adalah salah satu yang dinamai situs ini.

Ada artikel Wikipedia yang sangat menarik / terperinci tentang hal ini, Keuntungan dari set instruksi mesin stack . Saya perlu mengutip seluruhnya, jadi lebih mudah untuk hanya menaruh tautan. Saya hanya akan mengutip sub-judul

• Kode objek sangat kompak
• Kompiler sederhana / juru bahasa sederhana
• Status prosesor minimal

Untuk menambahkan lebih banyak ke pertanyaan tumpukan. Konsep stack berasal dari desain CPU di mana kode mesin di arithmetic logic unit (ALU) beroperasi pada operan yang terletak di stack. Misalnya operasi multiply dapat mengambil dua operan teratas dari stack, gandakan mereka dan letakkan hasilnya kembali di stack. Bahasa mesin biasanya memiliki dua fungsi dasar untuk menambah dan menghapus operan dari stack; PUSH dan POP. Dalam banyak dsp cpu (prosesor sinyal digital) dan pengontrol mesin (seperti yang mengendalikan mesin cuci) tumpukan terletak pada chip itu sendiri. Ini memberikan akses lebih cepat ke ALU dan menggabungkan fungsionalitas yang diperlukan ke dalam satu chip.

Jika konsep stack / heap tidak diikuti dan data dimuat ke lokasi memori acak ATAU data disimpan dari lokasi memori acak ... itu akan sangat tidak terstruktur dan tidak dikelola.

Konsep-konsep ini digunakan untuk menyimpan data dalam struktur yang telah ditentukan untuk meningkatkan kinerja, penggunaan memori ... dan karenanya disebut struktur data.

Seseorang dapat memiliki sistem yang bekerja tanpa tumpukan, dengan menggunakan gaya kelanjutan pengkodean. Kemudian frame panggilan menjadi kelanjutan yang dialokasikan di tumpukan sampah yang dikumpulkan (pengumpul sampah akan membutuhkan tumpukan).

Lihat tulisan lama Andrew Appel: Mengompilasi dengan Lanjutan dan Pengumpulan Sampah bisa lebih cepat dari Stack Allocation

(Dia mungkin sedikit salah hari ini karena masalah cache)

Saya mencari "interupsi" dan tidak ada yang memasukkan itu sebagai keuntungan. Untuk setiap perangkat yang mengganggu mikrokontroler atau prosesor lain, biasanya ada register yang didorong ke stack, rutin layanan interupsi dipanggil, dan ketika selesai, register dikeluarkan kembali dari stack, dan diletakkan kembali di tempat mereka. adalah. Kemudian penunjuk instruksi dipulihkan, dan aktivitas normal mengambil dari tempatnya, hampir seolah-olah interupsi tidak pernah terjadi. Dengan stack, Anda sebenarnya dapat memiliki beberapa perangkat (secara teoritis) saling mengganggu, dan semuanya hanya berfungsi - karena stack.

Ada juga keluarga bahasa berbasis stack yang disebut bahasa concatenative . Mereka semua (saya percaya) bahasa fungsional, karena stack adalah parameter implisit yang diteruskan, dan juga stack yang diubah adalah pengembalian implisit dari setiap fungsi. Kedua Forth dan Factor (yang baik) adalah contoh, bersama dengan orang lain. Factor telah digunakan mirip dengan Lua, untuk permainan scripting, dan ditulis oleh Slava Pestov, seorang jenius yang saat ini bekerja di Apple. -Nya Google Techtalk di youtube saya telah menyaksikan beberapa kali. Dia berbicara tentang konstruktor Boa, tapi aku tidak yakin apa yang dia maksud ;-).

Saya benar-benar berpikir bahwa beberapa VM saat ini, seperti JVM, Microsoft CIL, dan bahkan yang saya lihat ditulis untuk Lua, harus ditulis dalam beberapa bahasa berbasis stack ini, untuk membuatnya portabel untuk lebih banyak platform. Saya pikir bahasa-bahasa penggabung ini entah bagaimana kehilangan panggilan mereka sebagai kit pembuatan VM, dan platform portabilitas. Bahkan ada pForth, Forth "portabel" yang ditulis dalam ANSI C, yang dapat digunakan untuk portabilitas yang lebih universal. Adakah yang mencoba mengompilasinya menggunakan Emscripten atau WebAssembly?

Dengan bahasa berbasis stack, ada gaya kode yang disebut titik-nol, karena Anda bisa mendaftar fungsi yang akan dipanggil tanpa melewati parameter apa pun (kadang-kadang). Jika fungsi-fungsi tersebut saling cocok dengan sempurna, Anda tidak memiliki apa-apa selain daftar semua fungsi titik nol, dan itu akan menjadi aplikasi Anda (secara teoritis). Jika Anda mempelajari Forth atau Factor, Anda akan melihat apa yang saya bicarakan.

Di Easy Forth , tutorial online bagus yang ditulis dalam JavaScript, berikut adalah contoh kecil (perhatikan "sq sq sq sq" sebagai contoh gaya panggilan titik nol):

: sq dup * ;  ok
2 sq . 4  ok
: ^4 sq sq ;  ok
2 ^4 . 16  ok
: ^8 sq sq sq sq ;  ok
2 ^8 . 65536  ok

Juga, jika Anda melihat sumber halaman web Easy Forth, Anda akan melihat di bagian bawahnya sangat modular, ditulis dalam sekitar 8 file JavaScript.

Saya telah menghabiskan banyak uang untuk hampir setiap buku Forth yang bisa saya dapatkan dalam upaya untuk mengasimilasi Forth, tetapi sekarang saya baru mulai menggosoknya dengan lebih baik. Saya ingin memberikan perhatian kepada mereka yang datang setelah itu, jika Anda benar-benar ingin mendapatkannya (saya menemukan ini terlambat), dapatkan buku tentang FigForth dan terapkan itu. Forths komersial terlalu rumit, dan hal terbesar tentang Forth adalah memungkinkan untuk memahami keseluruhan sistem, dari atas ke bawah. Entah bagaimana, Forth mengimplementasikan seluruh lingkungan pengembangan pada prosesor baru, dan meskipun perluuntuk yang tampaknya lulus dengan C pada segala hal, masih berguna sebagai ritus perikop untuk menulis Keempat dari awal. Jadi, jika Anda memilih untuk melakukan ini, cobalah buku FigForth - beberapa Forths diimplementasikan secara bersamaan pada berbagai prosesor. Semacam Rosetta Stone of Forths.

Mengapa kita memerlukan tumpukan - efisiensi, optimisasi, titik nol, menyimpan register saat interupsi, dan untuk algoritma rekursif itu "bentuk yang tepat."