Coroutine dalam Bahasa C (2000)
(chiark.greenend.org.uk)- Saat kode produsen dan konsumen saling bertukar data, jika salah satunya dibalik menjadi bentuk callee, struktur algoritme yang semula terlihat mudah tenggelam dalam transisi status
- Coroutine ala Knuth adalah model di mana dua rutin menyimpan posisi eksekusinya dan saling menyerahkan kontrol, tetapi dalam struktur pemanggilan berbasis stack milik C, hal ini sulit diimplementasikan secara langsung dengan cara yang portabel
- Trik inti artikel ini adalah memanfaatkan sintaks C yang memungkinkan
caseditempatkan di subblokswitch, serta makro__LINE__, untuk membuat mesin status implisit yang masuk kembali ke posisi setelahreturn - Dengan makro
crBegin,crReturn, dancrFinish, struktur loop asli dekompresor dan parser dapat dipertahankan, tetapi variabel lokal yang harus dipertahankan harus berupastatic, dancrReturntidak boleh ditempatkan di dalamswitcheksplisit atau pada baris yang sama - Dalam kode nyata, karena batasan reentrancy dan multithreading, diperlukan versi perbaikan yang meneruskan struktur konteks;
coroutine.hmenyediakan makroscryang sederhana dan makroccryang reentrant
Masalah struktur saat menghubungkan produsen dan konsumen
- Dalam program besar, sering kali satu kode membuat data dan kode lain mengonsumsinya; pada titik ini, menentukan mana yang menjadi caller dan mana yang menjadi callee membuat desain menjadi sulit
- Contohnya terdiri dari dua rutin kecil
- Kode dekompresi run-length membaca input dengan
getchar()dan mengeluarkan karakter satu per satu denganemit() - Kode parser membaca karakter dengan
getchar(); rangkaian alfabet diproses sebagaiWORD, sedangkan karakter lain sebagaiPUNCT
- Kode dekompresi run-length membaca input dengan
- Jika dilihat terpisah, kedua rutin ini alami, tetapi agar keluaran
emit()dari dekompresor langsung menjadi inputgetchar()bagi parser, diperlukan struktur untuk menghubungkan keduanya - Ini juga bisa diselesaikan dengan pipe antara dua proses atau dua thread
emit()milik dekompresor menulis ke pipe, dangetchar()milik parser membaca dari sisi sebaliknya- Cara ini sederhana dan kuat, tetapi berat dan kurang portabel, sehingga sering kali orang tidak ingin membagi pekerjaan sederhana ke dalam thread
Hilangnya keterbacaan akibat penulisan ulang fungsi
- Solusi tradisional adalah menulis ulang salah satu ujung kanal komunikasi menjadi bentuk fungsi yang dapat dipanggil
- Jika dekompresor diubah menjadi fungsi yang mengembalikan satu karakter pada setiap pemanggilan, parser yang ada dapat memanggil
decompressor()alih-alihgetchar() - Sebaliknya, jika parser diubah menjadi fungsi yang dipanggil setiap kali menerima satu karakter, kode dekompresi yang ada cukup memanggil
parser()alih-alihemit() - Tidak perlu mengubah keduanya; mengubah satu sisi saja sudah cukup untuk menghubungkannya, tetapi kode yang ditulis ulang menjadi jauh lebih sulit dibaca dibanding aslinya
- Pada dekompresor dan parser asli, alur algoritme tampak alami di dalam loop
- Bentuk yang ditulis ulang bergantung pada variabel status
staticdan transisi statusswitch, sehingga format kompresi atau tata bahasa parser sulit dibaca dari kode
- Tujuannya adalah menghubungkan keduanya tanpa membalik dan menulis ulang salah satu sisi seperti mesin status eksplisit
Coroutine ala Knuth dan keterbatasan C
- Solusi coroutine Donald Knuth membuang pembedaan caller dan callee, lalu memperlakukan dua proses sebagai entitas setara yang bekerja sama
- Prinsip pemanggilan model ini berbeda dari pemanggilan fungsi biasa
- Posisi eksekusi saat ini disimpan di lokasi terpisah, bukan di stack
- Eksekusi melompat ke posisi terakhir yang disimpan oleh rutin lain
- Saat dekompresor memancarkan karakter, ia menyimpan program counter-nya sendiri dan berpindah ke posisi tersimpan milik parser
- Saat parser membutuhkan karakter berikutnya, ia menyimpan program counter-nya sendiri dan berpindah ke posisi tersimpan milik dekompresor
- Kontrol bolak-balik di antara dua rutin sebanyak yang diperlukan
- Cara ini bagus secara teoretis, tetapi dalam praktiknya hanya mungkin dilakukan di bahasa assembly
- Bahasa tingkat tinggi seperti C bergantung pada struktur berbasis stack, sehingga dalam perpindahan kontrol antar fungsi, salah satu harus menjadi caller dan yang lain callee
- Dalam kode C yang portabel, pendekatan coroutine murni sama kurang praktisnya dengan solusi pipe Unix
Meniru “return and continue” di C
- Perilaku yang dibutuhkan di C adalah return and continue, yaitu fungsi callee melakukan
return, lalu pada pemanggilan berikutnya melanjutkan eksekusi tepat setelahreturntersebut - Misalnya, idealnya fungsi berbentuk
for (i = 0; i < 10; i++) return i;akan mengembalikan 0 sampai 9 secara berurutan saat dipanggil 10 kali - Implementasi pertama menggunakan variabel status dan
goto- Label ditempatkan di awal fungsi dan setelah setiap
return - Variabel
stateyang dipertahankan antar pemanggilan menunjuk ke label tempat melanjutkan berikutnya - Pada awal fungsi,
switch(state)berpindah ke label yang sesuai - Tepat sebelum
return, label tujuan untuk pemanggilan berikutnya disimpan kestate
- Label ditempatkan di awal fungsi dan setelah setiap
- Cara ini berfungsi, tetapi pengelolaan label bersifat manual sehingga membebani pemeliharaan
- Setiap kali menambahkan
return, harus membuat label baru dan menambahkannya juga keswitchawal - Saat menghapus
return, label yang bersesuaian juga harus dihapus - Konsistensi antara badan fungsi dan daftar
switchharus terus dijaga
- Setiap kali menambahkan
Mesin status yang disembunyikan dengan Duff’s device
- Duff’s device yang terkenal di C memanfaatkan sintaks yang memungkinkan pernyataan
caseyang berpasangan denganswitchditempatkan juga di dalam subbloknya - Jika sifat ini diterapkan pada trik coroutine, alih-alih
switchmemilihgotomana yang akan dieksekusi,switchitu sendiri bertindak seperti lompatan masuk kembali - Bentuk dasarnya adalah sebagai berikut
static int statemenyimpan titik lanjut berikutnya- Di awal fungsi, masuk melalui
switch(state) { case 0: ... } - Tepat sebelum
return, nilaicaseberikutnya disimpan kestate - Label
casetersebut ditempatkan tepat setelahreturn
- Jika dibungkus dengan makro, ini menjadi antarmuka yang tampak seperti coroutine
crBegin: menyembunyikanstatic int state=0; switch(state) { case 0:crReturn: menyimpanstate, mengembalikan nilai, lalu menempatkan labelcasedi posisi yang samacrFinish: menutup blok yang terbuka
crReturndibungkus dengando ... while(0), sehingga tidak menimbulkan masalah sintaks meski digunakan tanpa kurung kurawal di antaraifdanelse- Pada awalnya nomor status harus diberikan langsung seperti
crReturn(1, i), tetapi dengan memakai makro ANSI C__LINE__, nomor baris sumber saat ini dapat digunakan sebagai nilai status - Setelah perbaikan ini, cukup menulis
crReturn(x), tetapi ada aturan tambahan: jangan menaruh duacrReturnpada satu baris
Aturan penggunaan makro dan contoh
- Coroutine berbasis makro mengandaikan beberapa aturan
- Bungkus badan fungsi dengan
crBegindancrFinish - Variabel lokal yang harus dipertahankan melewati
crReturndideklarasikan sebagaistatic - Jangan pernah memasukkan
crReturnke dalam pernyataanswitcheksplisit - Pada implementasi berbasis
__LINE__, jangan menaruh duacrReturnpada baris yang sama
- Bungkus badan fungsi dengan
- Contoh dekompresor mempertahankan struktur loop asli, hanya menggunakan
crReturn(c)alih-alihemit(c)saat memancarkan karakter - Contoh parser kembali ke caller dengan
crReturn()saat membutuhkan karakter baru, lalu pada pemanggilan berikutnya melanjutkan eksekusi dalam keadaan karakter baru telah diterima di parameterc - Ada sedikit perubahan struktur pada parser
- Karena karakter pertama sudah berada di
csaat fungsi dimasuki,crReturnyang setara dengangetchar()di awal loop asli dipindahkan ke akhir loop - Jika diinginkan, dapat juga ditetapkan bahwa parser memerlukan pemanggilan inisialisasi
- Karena karakter pertama sudah berada di
- Tidak perlu mengubah kedua rutin menjadi makro coroutine; satu sisi saja bisa diubah sementara sisi lain tetap menjadi caller
- Hasilnya, penggabungan ANSI C, preprocessor, dan sintaks
switchyang jarang dipakai memungkinkan pengiriman data antara produsen dan konsumen tanpa menulis ulang menjadi mesin status eksplisit
Konflik antara standar coding dan kejelasan algoritme
- Teknik ini sangat melanggar standar coding umum
- Kurung kurawal yang tidak berpasangan berada di dalam makro
- Menggunakan
casedi dalam subblok crReturnmenyembunyikanswitch,return, dancasedi dalam satu makro
- Makro yang menyembunyikan struktur sintaks dapat dianggap merusak kejelasan menurut standar coding
- Namun fungsi yang ditulis ulang sebagai mesin status eksplisit juga terdiri dari blok-blok kecil
case STATEdan transisi status, sehingga secara visual tidak jauh berbeda dari fungsi yang menderetkan blok labelgoto - Semakin panjang fungsinya, semakin besar kerusakan yang ditimbulkan penulisan ulang mesin status terhadap struktur algoritme asli
- Teknik ini adalah kompromi yang menyembunyikan sebagian struktur sintaks demi menampilkan struktur algoritme dengan lebih baik
Versi perbaikan yang reentrant dan kode yang disediakan
- Implementasi mainan yang sederhana bergantung pada variabel
static, sehingga tidak reentrant dan juga tidak cocok untuk multithreading - Dalam aplikasi nyata, fungsi yang sama harus dapat dipanggil dari beberapa konteks, dan tiap konteks harus dapat melanjutkan eksekusi dari setelah
returnterakhirnya - Cara perbaikannya adalah meneruskan pointer struktur konteks sebagai parameter tambahan
- Status lokal dan variabel status coroutine semuanya diletakkan sebagai anggota struktur
- Variabel seperti penghitung loop juga harus diakses seperti
ctx->i, bukani - Kode menjadi sedikit lebih jelek, tetapi masalah reentrancy hilang sementara struktur keseluruhan rutin tetap dipertahankan
- Pengguna C++ dapat membuat coroutine sebagai anggota kelas dan menaruh status yang setara dengan variabel lokal di dalam kelas, sehingga scope dapat ditangani lebih alami
coroutine.hyang disediakan mengimplementasikan trik coroutine ini sebagai sekumpulan makro yang telah didefinisikan- Makro berprefiks
scradalah bentuk sederhana yang memakai variabelstatic - Makro berprefiks
ccradalah bentuk lanjutan yang reentrant - Dokumentasi detail disertakan dalam komentar di dalam file header
- Makro berprefiks
- Visual C++ 6 tidak menyukai trik ini karena pada pengaturan debug default “Program Database for Edit and Continue”, makro
__LINE__diperlakukan secara aneh- Untuk mengompilasi program yang memakai coroutine di VC++ 6, Edit and Continue harus dimatikan
- Di pengaturan proyek, pada tab “C/C++”, kategori “General”, pengaturan “Debug info”, pilih opsi selain “Program Database for Edit and Continue”
- File header tersedia dengan lisensi MIT
Referensi terkait dan penggunaan nyata
- The Art of Computer Programming, Volume 1, Section 1.4.2 karya Donald Knuth membahas coroutine dalam bentuk murninya
- Diskusi Tom Duff tentang Duff’s device memuat hal yang mengisyaratkan bahwa ia mungkin pernah memikirkan trik coroutine serupa secara independen, dan dalam pembaruan 2005-03-07 Tom Duff mengonfirmasinya lewat komentar blog
- Kode protokol SSH milik PuTTY menggunakan trik coroutine ini dalam praktik
- Kasus PuTTY berada pada tingkat C hacking yang kuat dan jarang terlihat dalam kode produksi serius
1 komentar
Opini Hacker News
Saat mencoba mengurangi kompleksitas API di proyek C, saya beberapa kali kembali ke halaman ini, dan menurut saya penjelasan tentang alur kontrol-nya sangat bagus
Ini juga membantu saya berpikir lebih jelas tentang penyimpanan status di dalam/di luar stack serta perbedaan keterbacaan antarpendekatan
Kesimpulan saya sekarang adalah sebaiknya pengguna library-lah yang menentukan apakah akan memakai coroutine C. Misalnya, Mongoose(https://github.com/cesanta/mongoose) menangani asinkron lewat event callback; untuk library seperti ini, jauh lebih nyaman membungkusnya dengan primitive thread/task masing-masing sistem daripada mencoba mem-port-nya ke coroutine C lintas platform yang legendaris, atau lebih buruk lagi, ke
std::thread[1] https://www.chiark.greenend.org.uk/~sgtatham/putty/
[2] https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
Coroutine adalah konsep yang benar-benar keren, dan khususnya video-video coroutine C++ dari CppCon yang terutama dipresentasikan orang-orang Microsoft juga menyenangkan untuk ditonton. Hook “abstraksi berbiaya negatif” juga cukup bagus
Beberapa tahun lalu teman-teman di Meta mulai memakai coroutine C++, tetapi mereka mengatakan kepada saya bahwa akhirnya itu adalah kesalahan besar. Mereka harus berhadapan dengan bug implementasi compiler, dan pelacakannya pasti cukup berantakan. Di Google, kami menunggu orang-orang hebat yang mengintegrasikannya dengan benar ke google3/ memberi tahu bahwa sekarang sudah boleh dipakai
Tulisan ini menjelaskan
gototerstruktur berbasis macro sebagai strategi implementasi coroutine C melalui Duff's device [1]. Intinya adalah pernyataancasebisa diletakkan hampir di mana saja di dalam blokswitch; caranya membungkus seluruh fungsi denganswitch, menyimpan posisi terakhir coroutine return dalam variabelstatic, lalu memberi label setiapcoReturnsebagaicaseTulisan Sustrik tentang coroutine C juga mungkin menarik [2]
[1] https://en.wikipedia.org/wiki/Duff%27s_device
[2] https://250bpm.com/blog:48/index.html
co_yield,co_return, danco_awaityang tersebar di mana-mana dalam kode C++ punya kelebihan dan kekuranganKelebihannya dibanding cara internal google3 adalah, saat membaca kode, sifat asinkron tiap bagiannya terlihat jelas. Sebagian programmer Google hidup tanpa mengetahui model threading di atas tingkat branch, lalu belakangan membuat bug serius
Kekurangannya lebih sederhana. Karena banyak kode “mungkin saja asinkron”, seiring waktu seluruhnya menjadi asinkron hanya karena programmer menulis dalam mode itu. Memilih antara spinlock dan mutex yang yield seharusnya ditentukan oleh ukuran critical section dan kondisi threading saat itu, tetapi ketika mengejar keterbacaan dan konsistensi, seluruh proyek mudah condong ke satu sisi
Saya ingin tahu lebih banyak tentang implementasi bahasa threading yang tidak menjadikan salah satu sisi sebagai default, dan yang mengoptimalkan eksekusi berikutnya berdasarkan profil eksekusi sebelumnya tanpa perubahan kode atau bug
lc-addrlabels.hSaya juga memakai fitur label lokal GCC sehingga sepenuhnya menghindari penggunaan
__LINE__, dan bahkan bisa menaruh beberapacoReturndalam satu bariscasestatement bisa dipakai hampir di mana saja di dalam blokswitch, tetapi fitur itu sendiri hampir pasti adalah fitur yang disengajaSeperti juga disebutkan di bagian bawah tulisan, Duff juga menyadari bahwa coroutine bisa dibuat di atasnya, tetapi ia menganggap gagasan itu “menjijikkan”
Jika
switchdi C dianggap seperti pattern matching yang kurang ekspresif, “fallthrough” mudah terlihat seperti bug, padahal bukan. Itu satu keluarga dengan computedgotoseperti di Fortran, tetapi lebih nyaman karena nilainya tidak harus berurutan dan label tidak harus semuanya didaftarkan di bagian atas. Setelah menuliskannya, rasanya malah lebih mirip computedCOMEFROMPernyataan “bahasa tingkat tinggi yang banyak dipakai tidak mendukung coroutine” mungkin benar pada tahun 2000, tetapi sekarang banyak bahasa seperti C++20, Lua, Python, Ruby dan lainnya mendukungnya
yieldjuga sudah ada saat itu atau tidak lama setelahnyaUsulan perbaikan di akhir tulisan, yaitu “menambahkan pointer struct konteks sebagai argumen fungsi tambahan, dan mendeklarasikan semua status lokal serta variabel status coroutine sebagai elemen struct itu”, terlihat seperti implementasi closure. Sepertinya pihak yang dipanggil dijadikan lambda dan menggunakan variabel/konteks/status eksternal untuk menentukan apa yang dilakukan atau dengan nilai apa; saya penasaran apakah pemahaman ini benar
Metode
switchmemang tidak sangat jarang, tetapi biasanya ada pointer status yang diteruskan ke fungsi inisialisasi dan fungsi coroutineSaya sering memakai metode ini di proyek embedded; satu coroutine menangani akselerasi/deselerasi motor, sementara coroutine lain hanya memberi tahu arah mana yang harus ditempuh, dan seterusnya. Saya juga pernah memakainya di pustaka jaringan[1]. Di pustaka standar juga ada fungsi coroutine seperti
strtok()[2]Untuk membuatnya tetap bisa dikelola, tidak perlu sampai memperkenalkan neraka makro, tetapi saya belum pernah merasa senang membaca alur
switch/case[1]: https://github.com/REONTeam/libmobile/blob/master/relay.c#L3...
[2]: https://manpages.debian.org/bookworm/manpages-dev/strtok.3.e...
Ada juga Simon Tatham's Portable Puzzle Collection dari penulis yang sama
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
Jika ini terlihat seperti ilmu hitam C, tulisan dari penulis yang sama tentang membuat struktur kontrol arbitrer dengan makro juga layak dibaca: https://www.chiark.greenend.org.uk/~sgtatham/mp/
Coroutine memang menarik, tetapi dalam kode nyata penggunaan thread sungguhan juga perlu dipertimbangkan. Prosesor modern punya banyak core, tetapi coroutine sering kali hanya memakai satu core
Ini juga masalah nyata. Hingga belum lama ini, qemu yang banyak memakai coroutine mengirim sebagian besar I/O block device ke satu thread, dan ini menimbulkan masalah performa. Kevin Wolf dan orang lain memperbaikinya selama bertahun-tahun sehingga qemu modern memakai beberapa thread untuk I/O, dan pekerjaan ini dijadwalkan masuk ke RHEL 9.4
Coroutine adalah cara menstrukturkan eksekusi single-thread, dan berguna dengan sendirinya. Pola produsen-konsumen pada contoh di artikel adalah contoh yang bagus; menghubungkan stream ke parser bukanlah algoritma paralel, jadi thread tidak berguna untuk menuliskannya
Memakai paradigma single-thread untuk pekerjaan yang bisa dijalankan paralel tentu saja tidak efisien, tetapi coroutine bukanlah paralelisme versi orang miskin, melainkan struktur kontrol yang bermakna secara independen. Coroutine juga bisa digabungkan secara produktif dengan thread, seperti event loop di server web yang, bersama dispatcher, merangkai coroutine di antara berbagai event blocking; jika runtime memparalelkan dengan menjalankan satu thread per core, koordinasi antar-thread bisa diperkecil menjadi sekadar memeriksa kedalaman tiap antrean kerja dan meneruskan permintaan ke sisi yang lebih lengang
Gagasan coroutine dipakai ketika ada suatu pekerjaan lokal dan data sinkron, dan lebih mudah mengekspresikannya dalam bentuk terbalik: fungsi melakukan loop atas sesuatu lalu “mendorong” hasilnya ke konsumen abstrak di tempat lain, alih-alih paradigma fungsional tempat pemanggil “menarik” loop dalamnya
Setelah itu, coroutine hampir tidak pernah dipindahkan antar-scheduler, dan data juga hampir tidak pernah dibagi antar-coroutine dari scheduler yang berbeda
Coroutine memungkinkan gaya pemrograman konkuren yang nyaman tanpa perlu lock sama sekali melalui cooperative scheduling. Biasanya latensi penjadwalan menjadi lebih besar, tetapi throughput bisa menjadi cukup tinggi karena overhead operasi atomik/lock hilang dan timer tidak terus-menerus memutus eksekusi untuk preemptive scheduling
Versi C++ dari pendekatan ini: https://www.codeproject.com/Tips/29524/Generators-in-C
Saya juga memakainya di Sciter saya sebagai jaga-jaga, dan ini bekerja cukup baik serta praktis
Cara untuk mencapai ini secara modular dan aman mungkin adalah effect handler. Mirip dengan
yielddi Python, tetapi bisa mengembalikan nilai, dan cakupannya tidak terbatas pada pemanggilan fungsi melainkan seperti exception. Jika belum familier, tulisan ini menjadi motivasi yang bagusSetiap fungsi yang ditulis dalam gaya langsung dapat melakukan “effect” ketika kontrol harus pergi ke tempat lain. Di sini,
c=getchar()danemit(c)adalah kasus seperti ituLalu kontrol berpindah ke effect handler, dan dalam kasus ini mungkin pemanggil kedua fungsi yang menentukan apa yang dilakukan berikutnya. Misalnya, ketika decompressor mengeluarkan karakter, karakter itu diteruskan ke kode parser dan dilanjutkan; setelah berjalan sampai parser mengatakan membutuhkan lebih banyak, decompressor dilanjutkan lagi
Effect dapat diimplementasikan secara efisien, terutama jika continuation dibatasi agar hanya bisa dipanggil sekali. OCaml adalah salah satu contohnya. Ini memungkinkan kode gaya langsung sekaligus keamanan tipe/memori, dan juga sangat berguna dalam lingkungan konkuren
Contohnya ada di sini: https://effekt-lang.org/docs/casestudies/lexer
Sama sekali tidak setuju dengan bagian yang mengatakan “trik ini tentu saja melanggar semua standar coding… saya akan berargumen bahwa standar coding-nya yang salah”
Bukan standar coding yang keliru karena menolak kode ini; kode ini hanyalah trik yang lucu. Rekayasa perangkat lunak berskala besar adalah soal menghilangkan kejutan dan membuat kode yang tetap bisa dibaca oleh orang kurang tidur yang dipanggil untuk debugging pukul 3 pagi. Kita tidak bisa berharap programmer selalu mengingat empat aturan dasar itu
Saya juga sulit menerima klaim bahwa menyembunyikan elemen penting seperti
switch,return, dancasedi dalam macro “obfuscation” membuat struktur sintaksis menjadi kabur tetapi menonjolkan struktur algoritmik. Program yang baik harus membuat struktur sintaksis dan struktur algoritmik sama-sama jelas, dan pendekatan ini tidak memenuhi itu. Menurut saya, cara Rust membuat mesin status implisit dalam fungsiasyncseharusnya menjadi model di siniDi dunia C, operator kondisional ternary pun dianggap terlalu merangsang, dan C99 diperlakukan seperti barang baru. Di dunia C++, satu-satunya alasan untuk melarang template metaprogramming adalah karena standar yang dipakai memungkinkan hal yang sama dilakukan dengan
constexpr