Mengatasi isu performa Gleam yang berusia 3 tahun dengan arena Rust

• Pada struktur Document rekursif di formatter Gleam, alokasi heap individual yang berulang diganti dengan referensi berbasis arena, menyelesaikan isu peningkatan performa yang tersisa selama 3 tahun
• Box<Self> diganti dengan &Self yang disimpan di arena, dan pemeriksaan lifetime Rust memastikan data internal tidak direferensikan setelah arena dihapus
• Ratusan Document yang berulang seperti keyword bahasa dan koma dialokasikan sekali saja lalu digunakan ulang, sehingga waktu eksekusi pretty printer turun dari 13ms menjadi 9,8ms, lebih cepat 24%
• Total waktu eksekusi gleam format, termasuk pembacaan source dan parsing, juga berkurang 13%, sementara penggunaan memori puncak turun sekitar 10% dari 8,4MB menjadi 7,6MB
• Karena fungsi dan call site harus diubah secara luas agar meneruskan arena, diperlukan pekerjaan manual sebesar +2963/-1032, tetapi pengurangan alokasi individual yang repetitif berhasil meningkatkan kecepatan sekaligus menurunkan penggunaan memori

---

Biaya alokasi pada struktur Document rekursif

• Pretty printer Gleam menggunakan struktur data Document rekursif yang merepresentasikan bagaimana kode dicetak dan di mana harus dipisah saat melewati batas baris
• Variant utamanya terdiri dari String yang berisi string untuk dicetak, Break yang mendefinisikan string sebelum dan sesudah line break, Group yang mengelompokkan beberapa dokumen, Nest yang menambah indentasi saat line break, dan lainnya
• Daftar [1, 2] juga direpresentasikan dengan kombinasi String, Break, Nest, dan Group
  • Jika muat di baris saat ini, dicetak dalam satu baris seperti [1, 2]
  • Jika melewati batas baris, dipisah menjadi beberapa baris sesuai Break yang ditentukan, diberi indentasi, dan koma terakhir juga dicetak
• Variant yang menyimpan Document lain di dalamnya, seperti Nest, sebelumnya menggunakan Box<Self>, sehingga setiap dokumen bertingkat harus dialokasikan secara individual di heap, dan pekerjaan ini bisa memakan bagian signifikan dari waktu eksekusi
• Algoritme dasar pretty printer Gleam dapat dilihat di makalah Strictly Pretty

Mengganti Box dengan referensi arena

• Nest(Box<Self>) yang lama diubah menjadi Nest(&'doc Self), sehingga strukturnya kini mereferensikan Document lain yang disimpan di arena
• Untuk menyimpan referensi, lifetime 'doc untuk data dokumen ditambahkan ke Document, terpisah dari lifetime string 'string
• Implementasinya menggunakan crate typed_arena
  • Saat nilai disimpan di arena dengan alloc, referensi ke nilai tersebut dikembalikan
  • Data yang dialokasikan dapat digunakan selama arena masih hidup
  • Saat arena keluar dari scope, data di dalamnya juga ikut dihapus
• Referensi yang dikembalikan oleh alloc(&self, value: T) -> &mut T tidak dapat hidup lebih lama daripada arena, dan borrow checker Rust mencegah referensi tidak valid setelah arena dihapus

Mengalokasikan dokumen berulang sekali saja untuk digunakan ulang

• Arena dimanfaatkan bukan hanya untuk mereferensikan dokumen lain, tetapi juga untuk meng-cache Document yang berulang di seluruh kode
• Dokumen yang merepresentasikan keyword bahasa seperti String("fn"), String("pub"), dan String("type") tidak perlu lagi dibuat baru setiap kali
• Dokumen seperti Break { unbroken: ", ", broken: "," } yang digunakan di antara item daftar juga dialokasikan sekali lalu digunakan ulang
• Ratusan dokumen kecil yang sebelumnya harus terus dimasukkan ke Box kini bisa dialokasikan masing-masing hanya sekali

API sederhana dan perubahan luas pada call site

• API arena sendiri sederhana, tetapi proses memigrasikan sebagian besar kode lama membutuhkan perubahan yang repetitif
• Fungsi yang sebelumnya hanya memanggil Box::new kini harus menerima argumen arena tambahan untuk mengalokasikan data
• Fungsi seperti format_list diubah agar meneruskan arena yang sama ke subfungsi yang memformat item daftar, serta membuat dokumen bertingkat dengan arena.alloc alih-alih Box::new
• Setelah beberapa hari melakukan pencarian dan penggantian secara hati-hati, pekerjaan diselesaikan dalam pull request berukuran +2963/-1032
• Pekerjaan ini repetitif dan manual, dan LLM tidak digunakan dalam prosesnya

Peningkatan kecepatan dan penggunaan memori puncak

• Saat memformat squirrel, sebuah proyek Gleam nyata, waktu eksekusi pretty printer turun dari 13ms menjadi 9,8ms
  • Jika hanya pretty printer yang dibandingkan, ini berarti peningkatan performa 24%
• Karena gleam format juga membaca dan mem-parsing source code proyek selain melakukan formatting, pretty printer hanya merupakan sebagian dari keseluruhan pekerjaan, tetapi total waktu eksekusi juga berkurang 13%
• Penggunaan memori puncak turun dari 8,4MB menjadi 7,6MB, berkurang sekitar 10%
• Dengan mengurangi jumlah alokasi heap individual melalui arena, formatter menjadi lebih cepat sekaligus menggunakan lebih sedikit memori

[GN⁺]

Pendapat di Lobste.rs

• Jika ingin menurunkan penggunaan memori puncak 10% lagi, layak mempertimbangkan arena lain yang mengembalikan handle opak alih-alih referensi. Handle bisa dibuat 16-bit atau 32-bit, bukan 64-bit, sehingga efektif saat ada banyak alokasi kecil
  Menurut https://donsz.nl/blog/arenas/, crate yang mendukung ini hanya compact_arena, tetapi jika tidak sesuai kebutuhan, implementasinya sendiri juga tidak terlalu sulit

  • Dengan handle opak, data juga bisa disimpan lebih rapat. Proyek pribadi columnar menyimpan daftar Option<T> dengan memisahkan penanda keberadaan sekitar 1 bit per item dan T untuk item yang benar-benar ada
    Sebagai gantinya, ia mengembalikan Option<&T> alih-alih &Option<T>, dan secara lebih umum melakukan rekursi struktural dengan mengikuti referensi, bukan menaruh referensi di dalam rekursi struktural
  • Tulisan itu didasarkan pada survei dua tahun lalu dan tidak mencakup semua crate secara sempurna, jadi kalau menemukan kesalahan atau pustaka baru yang terlewat, silakan kirim PR
    Arena layak dipakai lebih luas, dan jika mengembalikan referensi alih-alih handle atau smart pointer, pattern matching enum rekursif di Rust menjadi sangat nyaman. Biasanya Anda ingin menulis sesuatu seperti if let MyAst::Add(MyAst::Multiply(a, b), c) = expr {} tetapi itu tidak mungkin karena ada box atau pointer di tengah; dengan referensi, pattern matching bisa dilakukan secara transparan tanpa fitur nightly. Jika semua referensi menunjuk ke satu arena, lifetime yang menghubungkan seluruh tree juga tetap konsisten
  • Hasilnya bagus, jadi mereka sedang mempertimbangkan untuk mengalihkan bagian lain compiler ke pendekatan arena juga, dan akan terus mengeksplorasi pendekatan ini

• Pendekatan ini juga cukup mirip dengan yang didukung oleh pretty, pustaka pretty-printing lain dengan gaya Wadler. Hanya saja, karena mendukung beberapa strategi alokasi memori, API-nya bisa terasa agak berat

• Mengejutkan bahwa penulis makalah yang dikutip di artikel itu bekerja di perusahaan IT biasa di Brunswick

  • Itulah daya tarik open source. Keahlian dan mata pencaharian sering kali tidak terlalu berkaitan erat