Komputer Anda bukan versi cepat PDP-11
Halo, Habr!
Nama saya Anton Dovgal, saya adalah pengembang C (dan tidak hanya) di Badoo.
Saya menemukan sebuah artikel oleh David Chiznell, seorang peneliti di Universitas Cambridge, di mana ia membantah pendapat yang diterima secara umum bahwa C adalah bahasa tingkat rendah, dan argumennya sepertinya cukup menarik bagi saya.
Mengingat kerentanan yang baru ditemukan,
Meltdown dan Specter harus meluangkan waktu untuk mencari tahu alasan terjadinya mereka. Kedua kerentanan ini mengeksploitasi eksekusi spekulatif instruksi oleh prosesor dan memungkinkan penyerang menerima hasil melalui saluran pihak ketiga. Kerentanan dalam fitur prosesor, bersama dengan beberapa yang lain, ditambahkan sehingga programmer C terus percaya bahwa mereka memprogram dalam bahasa tingkat rendah, meskipun ini tidak terjadi selama beberapa dekade.
Produsen prosesor tidak sendirian dalam hal ini. Pengembang kompiler C / C ++ juga berkontribusi.
Apa itu bahasa tingkat rendah?
Ilmuwan komputer Amerika dan pemenang Hadiah Turing pertama Alan Perlis memberikan definisi berikut:
"Bahasa pemrograman tingkat rendah jika program yang ditulis di atasnya memerlukan perhatian terhadap yang tidak esensial."
Meskipun definisi ini mengacu pada C, itu tidak memberikan pemahaman tentang apa yang orang ingin lihat dalam bahasa tingkat rendah. Berbagai properti membuat orang menganggap bahasanya rendah. Bayangkan skala bahasa pemrograman dengan assembler di satu ujung dan antarmuka ke komputer Enterprise di ujung lainnya. Bahasa tingkat rendah lebih dekat dengan besi, sedangkan bahasa tingkat lebih tinggi lebih dekat dengan cara orang berpikir.
Agar “lebih dekat dengan perangkat keras”, bahasa harus menyediakan abstraksi yang cocok dengan abstraksi platform target. Mudah untuk membuktikan bahwa C adalah bahasa tingkat rendah dalam PDP-11. Eksekusi berurutan dari program, ruang alamat datar, bahkan operator sebelum dan sesudah kenaikan, jatuh sempurna pada mode pengalamatan PDP-11.
Emulator PDP-11 cepat
Alasan utama untuk kerentanan Specter dan Meltdown adalah bahwa pembuat prosesor tidak hanya membuat prosesor cepat, mereka membuat prosesor cepat dengan antarmuka PDP-11. Ini penting karena memungkinkan programmer C untuk terus percaya bahwa bahasa mereka dekat dengan perangkat keras.
Kode C memberikan otomat abstrak berurutan sebagian besar (hingga C11, itu sepenuhnya berurutan, jika ekstensi non-standar dikecualikan). Membuat utas baru adalah panggilan ke fungsi perpustakaan, operasi yang cukup mahal. Oleh karena itu, prosesor, yang ingin terus mengeksekusi kode C, bergantung pada level-level parallelism (ILP). Mereka menganalisis operasi tetangga dan melakukan operasi independen secara paralel. Ini sangat menyulitkan prosesor dan mengarah pada peningkatan konsumsi daya, tetapi memungkinkan programmer untuk menulis sebagian besar kode berurutan. Sebaliknya, prosesor grafis (GPU) mencapai kinerja tinggi dengan cara lain: mereka memerlukan penulisan program paralel.
Konkurensi tinggi pada level perintah adalah penyebab langsung Specter dan Meltdown. Prosesor Intel modern mengeksekusi hingga 180 instruksi secara bersamaan (tidak seperti mesin C berurutan abstrak, yang mengharapkan instruksi sebelumnya dijalankan sebelum yang berikutnya dimulai). Heuristik khas kode C menunjukkan bahwa rata-rata ada satu cabang untuk setiap tujuh instruksi. Jika Anda ingin agar pipa instruksi tetap lengkap, maka Anda perlu menebak 25 cabang berikutnya. Ini, pada gilirannya, menambah kerumitan - prosesor pertama-tama menghitung cabang yang salah duga, dan kemudian melempar hasil perhitungan, yang secara negatif memengaruhi konsumsi energi. Data yang dilemparkan ini memiliki hasil tidak langsung yang terlihat, yang digunakan dalam serangan Specter dan Meltdown.
Mengganti nama register menghabiskan banyak energi dan area chip pada prosesor modern. Itu tidak dapat dimatikan atau konsumsi energinya berkurang, yang membuatnya tidak nyaman di era
silikon yang gelap , ketika transistor rendah, tetapi transistor yang terlibat adalah sumber daya yang berharga. Perangkat ini tidak ada dalam GPU, di mana konkurensi dicapai dengan menggunakan utas alih-alih mencoba paralel mengeksekusi kode sekuensial awalnya. Jika instruksi tidak memiliki dependensi yang perlu dibangun kembali, maka tidak perlu mengganti nama register juga.
Pertimbangkan bagian fundamental lain dari desain C: memori datar. Itu tidak ada selama beberapa dekade. Prosesor modern sering memiliki tiga level caching antara register dan memori utama, sehingga mengurangi waktu yang diperlukan untuk mengakses yang terakhir.
Cache disembunyikan dari pemrogram dan oleh karena itu tidak dapat diakses dari C. Penggunaan cache yang efektif adalah salah satu cara untuk mempercepat eksekusi kode pada prosesor modern, namun itu sepenuhnya tersembunyi dari mesin abstrak dan pemrogram dipaksa untuk mengandalkan pengetahuan tentang detail implementasi cache (misalnya, bahwa keduanya selaras 64-bit). nilai dapat muncul dalam satu baris cache) untuk menulis kode yang efisien.
Optimasi C
Salah satu karakteristik umum yang dikaitkan dengan bahasa tingkat rendah adalah kecepatan. Secara khusus, mereka harus mudah diterjemahkan ke dalam kode cepat tanpa kompiler yang rumit. Argumen bahwa kompiler yang cukup pintar dapat membuat bahasa cepat sering diabaikan oleh pendukung C ketika mereka berbicara tentang bahasa lain.
Sayangnya, menggunakan terjemahan sederhana, Anda tidak bisa mendapatkan kode cepat dari C.
Arsitek prosesor melakukan upaya heroik untuk membuat chip yang dapat mengeksekusi kode C dengan cepat. Tetapi tingkat kinerja yang diharapkan oleh pemrogram dapat dicapai hanya dengan bantuan optimasi yang sangat rumit yang dilakukan oleh kompiler.
Compiler Dentang (termasuk bagian yang sesuai dari LLVM) adalah sekitar 2 juta baris kode. Untuk analisis dan transformasi kode, yang diperlukan untuk mempercepat C, diperlukan sekitar 200.000 baris kode (tidak termasuk komentar dan baris kosong).
Misalnya, untuk memproses sejumlah besar data dalam C, Anda perlu menulis loop yang memproses setiap elemen secara berurutan. Untuk pelaksanaan optimal siklus ini pada prosesor modern, kompiler harus menentukan bahwa iterasi siklus tidak saling tergantung. Batasan kata kunci dapat membantu dalam kasus ini - ini memastikan bahwa menulis ke satu pointer tidak akan mengganggu pembacaan dari pointer lain. Informasi dalam C ini jauh lebih terbatas daripada dalam bahasa seperti Fortran, yang merupakan alasan utama bahwa C tidak dapat mendorongnya keluar dari komputasi kinerja tinggi.
Setelah kompiler menentukan bahwa iterasi tidak tergantung satu sama lain, langkah selanjutnya adalah upaya untuk mengubah hasilnya, karena throughput prosesor modern empat hingga delapan kali lebih tinggi untuk kode vektor daripada kode skalar. Bahasa tingkat rendah untuk prosesor semacam itu akan memiliki jenis vektor sendiri dengan panjang sewenang-wenang. Jenis tersebut hadir dalam representasi LLVM menengah, karena selalu lebih mudah untuk membagi operasi besar dengan vektor menjadi beberapa yang kecil daripada membangun operasi vektor yang lebih besar.
Pada titik ini, pengoptimal harus bersaing dengan aturan memori C. C memastikan bahwa struktur dengan awalan yang sama dapat digunakan secara bergantian, dan menyediakan akses ke bidang bidang offset bidang struktur dalam bahasa. Ini berarti bahwa kompiler tidak dapat mengubah urutan bidang dalam struktur atau menambahkan perataan untuk meningkatkan vektorisasi (misalnya, mengubah struktur dari array ke array struktur atau sebaliknya). Ini biasanya bukan masalah dalam bahasa tingkat rendah, di mana dimungkinkan untuk mengontrol lokasi bidang dalam struktur, tetapi itu membuat tugas mempercepat C. lebih sulit.
C juga membutuhkan perataan di akhir struktur, karena memastikan bahwa tidak ada perataan dalam array. Alignment adalah bagian yang agak rumit dari spesifikasi C, yang berinteraksi buruk dengan bagian bahasa lainnya. Misalnya, Anda harus dapat membandingkan dua struktur menggunakan metode perbandingan tanpa tipe (yaitu, fungsi memcmp ()), sehingga salinan struktur juga harus disejajarkan. Dalam beberapa kasus, menyalin keberpihakan membutuhkan waktu yang cukup lama.
Pertimbangkan dua optimasi dasar yang dihasilkan oleh kompiler C:
SROA (penggantian skalar agregat, penggantian skalar agregat) dan
pembukaan loop .
SROA sedang berusaha mengganti struktur dan array ukuran tetap dengan variabel terpisah. Ini memungkinkan kompiler untuk memproses akses kepada mereka secara independen satu sama lain dan mengabaikan operasi, jika jelas bahwa hasilnya tidak digunakan. Dalam beberapa kasus, efek tidak langsung dari pengoptimalan ini adalah untuk menghapus perataan.
Optimasi kedua, membuka loop, mengubah loop dengan kondisi menjadi kondisi dengan loop berbeda di kedua cabang. Ini mengubah urutan eksekusi yang bertentangan dengan pernyataan bahwa programmer tahu apa yang akan dieksekusi dalam bahasa tingkat rendah. Dan ini juga menciptakan masalah serius dengan bagaimana C menangani variabel tidak terdefinisi dan perilaku tidak terdefinisi.
Dalam C, variabel yang tidak diinisialisasi memiliki nilai yang tidak ditentukan, yang dapat berbeda dengan setiap panggilan. Ini penting karena memungkinkan Anda menerapkan daur ulang halaman memori yang malas. Misalnya, di FreeBSD, implementasi malloc () memberi tahu sistem bahwa halaman tidak lagi digunakan, dan sistem menggunakan entri pertama di halaman sebagai bukti bahwa ini bukan masalahnya. Banding ke memori yang baru dialokasikan dapat memperoleh nilai lama, maka sistem operasi dapat menggunakan kembali halaman memori, dan kemudian menggantinya dengan halaman yang diisi dengan nol saat berikutnya Anda menulis ke tempat lain di halaman. Panggilan kedua ke tempat yang sama pada halaman akan mendapatkan nilai nol.
Jika kondisi menggunakan nilai yang tidak ditentukan, maka hasilnya juga tidak ditentukan - apa pun bisa terjadi. Bayangkan loop terbuka optimasi di mana loop dijalankan nol kali. Dalam aslinya, seluruh loop adalah kode mati. Dalam versi terbuka sekarang ada kondisi dengan variabel yang mungkin tidak diinisialisasi.
Akibatnya, kode mati dapat dikonversi menjadi perilaku yang tidak terdefinisi. Ini hanyalah salah satu dari banyak optimasi yang, ketika lebih teliti mengeksplorasi semantik C, tidak dapat diandalkan.
Pada akhirnya, Anda dapat membuat kode C berjalan cepat, tetapi hanya setelah menghabiskan ribuan tahun manusia membuat kompiler yang cukup pintar. Tetapi ini hanya mungkin jika aturan bahasa tertentu dilanggar. Pembuat kompiler memungkinkan pemrogram C untuk membayangkan bahwa mereka menulis kode yang "dekat dengan perangkat keras", tetapi mereka harus membuat kode mesin yang berperilaku berbeda sehingga pemrogram terus percaya bahwa mereka menulis dalam bahasa cepat.
Memahami C
Salah satu atribut dasar dari bahasa tingkat rendah adalah bahwa pemrogram dapat dengan mudah memahami bagaimana mesin bahasa abstrak ditransfer ke mesin fisik. Ini jelas terjadi pada PDP-11, di mana ekspresi C diterjemahkan ke dalam satu atau dua instruksi. Demikian pula, kompiler memasukkan variabel ke dalam slot tumpukan dan mengkonversi tipe sederhana menjadi dapat dimengerti untuk PDP-11.
Sejak itu, implementasi C menjadi jauh lebih rumit - untuk mempertahankan ilusi bahwa C mudah dipindahkan ke platform perangkat keras dan berjalan cepat. Pada 2015, survei antara programmer C, penulis kompiler, dan anggota komite standardisasi menunjukkan bahwa ada
masalah dalam memahami C. Misalnya, bahasa ini memungkinkan implementasi untuk menambahkan perataan ke struktur (tetapi tidak ke array) untuk memastikan bahwa semua bidang disejajarkan dengan benar untuk platform target. Jika Anda mengisi struktur ini dengan nol dan kemudian tentukan nilai untuk beberapa bidang, apakah akan ada nol dalam bit pelurusan? Menurut survei, 36% yakin akan melakukannya, dan 29% tidak tahu jawabannya. Bergantung pada kompiler dan tingkat optimasi, ini mungkin benar (atau tidak).
Ini adalah contoh yang cukup sepele, tetapi banyak programmer baik memberikan jawaban yang salah atau tidak bisa menjawab sama sekali.
Jika Anda menambahkan pointer, semantik C menjadi semakin membingungkan.
Model BCPL cukup sederhana: semua artinya adalah kata-kata. Setiap kata adalah data atau alamat dalam memori. Memori adalah susunan rata sel yang diindeks berdasarkan alamat.
Model C memungkinkan implementasi untuk platform yang berbeda, termasuk arsitektur tersegmentasi, di mana pointer dapat terdiri dari ID segmen dan offset, serta mesin virtual dengan pengumpul sampah. Spesifikasi C membatasi operasi penunjuk yang diizinkan untuk menghindari masalah dengan sistem tersebut. Tanggapan untuk
Laporan Cacat 260 menyebutkan asal dari pointer:
“Implementasi dapat mengikuti asal set bit dan menangani yang mengandung nilai yang tidak terdefinisi berbeda dari yang mengandung bit tertentu. "Mereka dapat menangani pointer berbeda tergantung pada asalnya, bahkan jika mereka sama dalam hal nilai bit mereka."
Sayangnya, kata "asal" tidak ada dalam spesifikasi C11, sehingga kompiler memutuskan sendiri apa artinya. GCC dan Dentang, misalnya, berbeda dalam apakah penunjuk yang dikonversi ke integer dan kembali mempertahankan asalnya. Compiler dapat memutuskan bahwa dua pointer ke hasil malloc () selalu memberikan hasil negatif ketika membandingkan, bahkan jika mereka menunjuk ke alamat yang sama.
Kesalahpahaman ini tidak sepenuhnya bersifat akademis. Misalnya, kerentanan telah diamati, yang merupakan hasil meluap dari integer yang ditandatangani (perilaku tidak terdefinisi dalam C) atau
mendereferensi pointer sebelum mengeceknya untuk NULL , meskipun faktanya kompilator diberitahu bahwa pointer tidak boleh NULL.
Jika ada masalah seperti itu, sulit untuk mengharapkan seorang programmer untuk sepenuhnya memahami bagaimana program C diterjemahkan ke arsitektur yang sesuai.
Memperkenalkan prosesor bukan untuk C
Patch yang diusulkan untuk melindungi dari Specter dan Meltdown menyebabkan degradasi kinerja yang parah, membatalkan semua pencapaian arsitektur mikro selama dekade terakhir. Mungkin sudah waktunya untuk berhenti berpikir tentang cara membuat kode C lebih cepat, dan alih-alih memikirkan model pemrograman baru pada prosesor yang dirancang untuk kecepatan.
Ada banyak contoh arsitektur yang belum berfokus pada kode C tradisional dan dari mana untuk mendapatkan inspirasi. Sebagai contoh, prosesor yang berorientasi multithreading seperti Sun / Oracle UltraSPARC Tx tidak memerlukan banyak cache untuk membuat aktuator mereka sibuk. Prosesor penelitian telah memperluas konsep ini ke sejumlah besar rangkaian perangkat keras yang direncanakan. Gagasan utamanya adalah bahwa, dengan utas yang cukup, prosesor dapat menjeda utas yang menunggu data dan mengisi aktuator dengan instruksi dari utas lainnya. Masalahnya adalah bahwa program C biasanya memiliki sedikit utas.
SVE ARM (Ekstensi Skalar Vektor, ekstensi skalar vektor) adalah karya serupa lainnya dari Berkeley, yang menawarkan tampilan pada antarmuka yang ditingkatkan antara program dan perangkat keras. Blok vektorisasi reguler mengimplementasikan operasi dengan vektor dengan ukuran tetap dan mengharapkan kompiler untuk mengadaptasi algoritma ke ukuran yang ditentukan. Sebaliknya, antarmuka SVE meminta programmer untuk secara independen menggambarkan tingkat paralelisme dan mengharapkan perangkat keras untuk menyesuaikannya dengan aktuator yang tersedia. Menggunakan ini dalam C sulit karena vektorizer otomatis perlu menghitung paralelisme berdasarkan loop dalam kode.
Tembolok itu besar, tetapi ini bukan satu-satunya alasan kompleksitasnya. Protokol dukungan
koherensi cache adalah salah satu komponen paling kompleks dari prosesor modern. Sebagian besar kesulitan berasal dari keharusan mempertahankan bahasa di mana data dapat dibagi dan diubah. Sebagai contoh yang berlawanan, kita dapat menggunakan mesin abstrak bergaya Erlang, di mana setiap objek bersifat lokal atau tidak berubah. Protokol koherensi cache untuk sistem seperti itu hanya akan memiliki dua kasus: data yang dapat diubah dan data bersama. Cache aliran program yang ditransfer ke prosesor lain harus dinonaktifkan secara eksplisit, tetapi ini adalah operasi yang relatif jarang.
Objek yang tidak dapat diubah dapat menyederhanakan cache lebih banyak lagi, dan juga membuat beberapa operasi lebih murah. Dalam proyek Maxwell dari Sun Labs, tercatat bahwa objek dalam cache dan objek yang baru dibuat hampir selalu sama. Jika benda mati sebelum dikeluarkan dari cache, maka Anda tidak dapat menulisnya ke memori utama dan dengan demikian menghemat konsumsi energi. Proyek Maxwell mengusulkan pengumpul sampah yang bekerja di cache dan memungkinkan Anda mendaur ulang memori dengan cepat. Dengan objek yang tidak dapat diubah pada tumpukan dan tumpukan yang dapat berubah, pengumpul sampah menjadi mesin keadaan yang sangat sederhana, yang mudah diimplementasikan dalam perangkat keras dan memungkinkan Anda untuk secara efisien menggunakan cache yang relatif kecil.
Prosesor yang dirancang hanya untuk kecepatan, dan bukan untuk pertukaran antara kecepatan dan dukungan C, mungkin harus mendukung sejumlah besar thread, memiliki blok vektorisasi besar dan model memori yang lebih sederhana. Akan sulit untuk mengeksekusi kode C pada prosesor seperti itu, oleh karena itu, mengingat volume kode C lama di dunia, tidak mungkin untuk sukses secara komersial.
Di bidang pengembangan perangkat lunak, ada mitos bahwa pemrograman paralel itu sulit. Alan Kay akan sangat terkejut mendengar ini: ia mengajar anak-anak untuk menggunakan model aktor, yang dengannya mereka menulis program di lebih dari 200 aliran. Ini juga tidak diketahui oleh programmer Erlang, yang sering menulis program dengan ribuan komponen paralel. Lebih tepat mengatakan bahwa pemrograman paralel sulit dalam bahasa dengan mesin abstrak seperti C. Dan jika Anda memperhatikan dominasi perangkat keras paralel (dari prosesor multi-core ke GPU multi-core), maka ini hanyalah cara lain untuk mengatakan bahwa C tidak cocok untuk perangkat keras modern. menyediakan.