Tree Borrows

 (plf.inf.ethz.ch)
1 poin oleh GN⁺ 2025-07-10 | 1 komentar | Bagikan ke WhatsApp
  • Mengusulkan Tree Borrows, model memori baru untuk Rust yang mengatasi batas optimasi kode unsafe
  • Tree Borrows menyelesaikan masalah pendekatan Stacked Borrows yang tidak dapat mengizinkan berbagai pola yang sering dipakai dalam kode Rust dunia nyata dengan struktur pohon, sehingga memberikan aturan yang lebih realistis dan fleksibel
  • Tree Borrows meloloskan 54% lebih banyak kasus uji kode dunia nyata dibandingkan Stacked Borrows
  • Sambil tetap mempertahankan sebagian besar keamanan memori dan kemungkinan optimasi utama Rust, terutama read-read reordering, model ini juga mencerminkan fitur-fitur lanjutan dari borrow checker Rust modern
  • Dengan memperkenalkan model mesin status berbasis pohon, pendekatan ini menjadi tonggak penting bagi riset optimasi Rust dan verifikasi keamanan

Sistem kepemilikan Rust dan batas kode unsafe

  • Rust memberikan jaminan kuat seperti keamanan memori dan pencegahan data race melalui sistem tipe berbasis kepemilikan
  • Namun Rust memiliki unsafe escape hatch, dan dalam kasus ini tanggung jawab verifikasi keamanan berpindah dari compiler ke pengembang
  • Compiler ingin memanfaatkan aturan alias pointer untuk optimasi yang kuat, tetapi optimasi semacam ini bisa menjadi tidak efektif karena kode unsafe yang salah

Stacked Borrows dan keterbatasannya

  • Sebelumnya, model bernama Stacked Borrows digunakan untuk mendefinisikan 'perilaku yang salah' pada kode unsafe dan memberikan acuan optimasi
  • Namun pendekatan ini tidak dapat mengizinkan berbagai pola unsafe yang umum dalam kode Rust nyata, dan juga tidak mencerminkan fitur borrow checker Rust yang diperkenalkan belakangan

Munculnya Tree Borrows

  • Tree Borrows adalah model baru yang melacak izin memori dengan struktur pohon alih-alih struktur stack
  • Dengan ini, model tersebut dapat mengizinkan lebih banyak pola kode Rust praktis secara aman, serta sangat meningkatkan fleksibilitas aturan borrow dan penerapannya di dunia nyata
  • Dalam evaluasi terhadap 30.000 crate Rust populer, model ini meloloskan 54% lebih banyak kasus uji dibandingkan Stacked Borrows

Fitur dan keunggulan Tree Borrows

  • Mempertahankan sebagian besar optimasi utama dari Stacked Borrows yang sudah ada, seperti read-read reorderings
  • Selain itu, model ini juga dapat mencerminkan fitur lanjutan dari borrow checker Rust modern, seperti pola borrow yang tidak terstruktur dan manipulasi pointer yang kompleks
  • Dengan memperkenalkan model mesin status berbasis pohon, model ini menyeimbangkan keamanan dan kemungkinan optimasi

Kesimpulan dan makna pentingnya

  • Tree Borrows menghadirkan standar baru bagi penanganan kode unsafe dan riset optimasi pada compiler Rust
  • Model ini dinilai sebagai model memori yang realistis dan tangguh yang mencakup kode Rust praktis serta kebijakan borrow checker modern
  • Makalah terkait, artefak, dan source code telah dipublikasikan, dan diperkirakan akan memberi pengaruh besar pada komunitas riset compiler Rust dan verifikasi

Bacaan terkait

1 komentar

 
GN⁺ 2025-07-10
Pendapat Hacker News

  • Post blog terbaru dari Ralf Jung memberi konteks lebih banyak tautan
    Bonus: presentasi terbaru dari kelompok riset yang mencoba menspesifikasikan semantik eksekusi Rust secara jelas dalam sebuah dialek Rust juga layak ditonton YouTube

  • Ada klaim bahwa dari sudut pandang compiler, jaminan kuat dari sistem tipe terkait pointer aliasing memungkinkan optimisasi yang kuat, tetapi saya penasaran seberapa efektif itu dalam praktik
    Linus Torvalds sudah lama berargumen bahwa aturan strict aliasing di C tidak terlalu berguna dan malah menimbulkan masalah
    Tulisan contohnya juga menarik
    Saya penasaran apakah Rust pada dasarnya memang sangat berbeda dari C, tetapi dari pengalaman pribadi, terutama saat unsafe terlibat, rasanya tidak terlalu berbeda

    • Saya memang merasa aturan strict aliasing di C benar-benar buruk
      Aturan yang diusulkan di Rust jauh berbeda, lebih berguna dari sudut pandang compiler, dan juga lebih ringan bebannya bagi programmer
      Ada opt-out di dalam bahasa lewat penggunaan raw pointer, dan ada juga tool untuk memeriksa kode
      Pada akhirnya, seperti semua desain bahasa, ini adalah kompromi
      Rust tampaknya menemukan keseimbangan baru di area optimisasi ini, dan hasil penilaian itu akan terlihat seiring waktu

    • Aturan aliasing Rust sangat berbeda dari C
      Di C, keyword restrict pada dasarnya hanya bermakna untuk argumen fungsi, dan aliasing berbasis tipe (type-based aliasing) pada praktiknya jarang dipakai atau tidak nyaman digunakan
      Di Rust, lifetime dan mutabilitas bisa diekspresikan dengan rinci, dan memori bisa ditangani dengan aman lewat berbagai cara tanpa bergantung pada tipe itu sendiri
      Hal besar lainnya adalah selama tidak ada referensi &mut yang saling tumpang tindih, memori tetap bisa dimanfaatkan dengan membaginya menjadi beberapa &mut yang tidak overlap

    • Saya ingin melihat analisis yang lebih luas tentang seberapa besar ini benar-benar memengaruhi performa
      Cara sederhananya adalah menghapus seluruh bagian compiler yang menyampaikan informasi aliasing ke LLVM lalu membandingkan performanya
      Ada juga klaim bahwa anotasi noalias meningkatkan performa runtime sekitar 5%, dan ada komentar terkait itu (meski datanya sudah cukup lama)

    • Sebaiknya pernyataan Linus tentang compiler dilihat dengan konteks yang tepat
      Kernel OS dan compiler adalah domain yang sepenuhnya berbeda
      Saat ini analisis alias memang menjadi inti peningkatan performa yang sangat kuat
      Efek terbesar datang dari heuristik sederhana, sementara query alias yang kompleks sendiri kegunaannya tidak terlalu besar
      Secara teoretis saya ingin menguji seberapa besar analisis alias yang sempurna bisa meningkatkan performa, tetapi untuk kode umum pun mungkin batasnya hanya sekitar 20%
      Tentu saja ada batasan bahwa optimisasi yang sangat canggih (misalnya transformasi layout data) bahkan tidak akan dicoba tanpa analisis alias

    • Strict aliasing di C dan aliasing di Rust adalah konsep yang berbeda
      C berfokus pada analisis berbasis tipe (TBAA), dan Rust memang sengaja tidak mengadopsinya

  • Ada thread lama terkait Stacked Borrows pada 2020 dan 2018
    thread 2020
    thread 2018

  • Saya pernah membaca spesifikasi Tree Borrows di situs Nevin beberapa tahun lalu, dan terkesan karena ia menyelesaikan masalah yang rumit dengan elegan
    Dalam pengalaman nyata, Tree Borrows memungkinkan kode yang masuk akal tetapi tidak mungkin di Stacked Borrows
    Contoh kode di pustaka standar Rust juga layak dilihat

  • Saya penasaran apakah Rust atau PL generasi berikutnya bisa berkembang hingga memungkinkan kita memilih di antara beberapa implementasi borrow checker dengan karakteristik dan tujuan berbeda, seperti kecepatan kompilasi, kecepatan runtime, fleksibilitas algoritme, dan sebagainya

    • Rust sebenarnya sudah mendukung pergantian implementasi borrow checker
      Ia sudah berpindah dari yang berbasis scope ke non-lexical, dan ada juga implementasi eksperimental bernama Polonius sebagai opsi
      Jika implementasi baru sudah siap, versi lama tidak perlu dipertahankan
      Untuk fleksibilitas lebih besar, bisa juga memakai Rc, RefCell, dan sebagainya yang membutuhkan pemeriksaan saat runtime

    • Sudah ada banyak pendekatan seperti affine type (dipakai Rust), linear type, sistem efek, dependent type, pembuktian formal, dan lain-lain
      Setiap pendekatan punya karakteristik berbeda dalam biaya implementasi, performa, pengalaman pengembangan, dan sebagainya
      Di luar Rust juga ada kecenderungan mengejar kombinasi antara pengelolaan sumber daya otomatis yang produktif dan sistem tipe

    • Yang sebenarnya dibutuhkan adalah separation logic yang bisa menyatakan precondition fungsi secara presisi dan bahkan membuktikan kondisi perantara
      Pendekatan Rust adalah mensistematisasikan invariant umum yang benar-benar diinginkan orang, sambil menjamin optimisasi yang kuat

    • Saya penasaran apakah hasil borrow checker memang hanya punya false negative dan tidak punya false positive
      Kalau memang begitu, apakah mungkin menjalankan beberapa implementasi secara paralel dalam thread lalu memakai hasil dari yang paling cepat selesai

    • Mengizinkan banyak implementasi borrow checker sekaligus cenderung memecah ekosistem, jadi itu kurang diinginkan

  • Saya benar-benar menguji kode Rust di makalah itu, dan memastikan bahwa compiler stabil terbaru tidak menolaknya
    Contoh kode:

    fn write(x: &mut i32) {*x = 10}

fn main() {
  let x = &mut 0;
  let y = x as *mut i32;
  //write(x); 
  *x = 10; 
  unsafe {*y = 15 };
}
    • Stacked Borrows adalah model runtime milik miri
      Jika kode di atas dijalankan di miri, ia akan melaporkan error pada *x = 10;, tetapi write(x); tidak memunculkan error
      rustc dari sudut pandang sistem tipe tidak punya alasan menolak kedua versi itu karena y bertipe *mut

  • Di makalah itu, contoh berikut diberikan sebagai masalah pada kode unsafe:

    fn main() {
  let mut x = 42;
  let ptr = &mut x as *mut i32;
  let val = unsafe { write_both(&mut *ptr, &mut *ptr) };
  println!("{val}");
}

    Saya penasaran apakah ini benar-benar mungkin
    Menggunakan beberapa referensi mutable ke variabel yang sama melalui pointer jelas merupakan UB, jadi saya merasa mungkin ada sesuatu yang saya salah pahami

    • Inti riset ini adalah mendefinisikan batas UB (undefined behavior) secara tepat
      Kode di atas melanggar aturan meskipun compiler Rust menerimanya
      Aturan yang mana?

  • Kode yang lolos borrow checker adalah legal

  • unsafe juga bisa mengekspresikan hal yang ilegal/UB

  • Ada himpunan aturan yang lebih luas daripada cakupan borrow checker tetapi tetap legal
    Riset ini bertujuan menetapkan batas itu secara ketat
    Makalah Stacked Borrows lebih sederhana, tetapi punya keterbatasan terhadap kode unsafe nyata, sedangkan Tree Borrows mengakui rentang aman yang lebih luas

    • Jelas bahwa "beberapa pointer referensi mutable tidak bisa ada secara bersamaan", tetapi tidak ada penjelasan yang secara tegas menyebut aturan mana tepatnya yang dilanggar
      Tree Borrows justru mengusulkan definisi seperti itu
      Ungkapan seperti "kode bisa melakukan hal seperti ini" berarti bahwa jika Anda benar-benar membuat dan menjalankan kode itu, sesuatu memang akan terjadi, tetapi tanpa definisi seperti Tree Borrows, sulit menyediakan dasar yang jelas untuk menjelaskan kenapa itu salah
      Sepertinya Anda sendiri juga sudah menerima perlunya aturan yang jelas seperti Tree Borrows

    • Kode unsafe seperti itu memang benar-benar bisa dibuat, dan itulah yang membuatnya UB
      Contoh: tautan playground

    • Jika ingin tahu konteks terkait, bagian awal paragraf berikutnya di makalah itu cukup jelas menunjukkan maksudnya

Jika pengembang compiler Rust menginginkan optimisasi aliasing, mereka perlu cara untuk menyingkirkan kode-kode tandingan seperti di atas

  • Ya, itu memang inti persoalannya
    Sulit mematuhi aturan pelarangan beberapa referensi mutable, dan unsafe mencerminkan bahwa ia bisa mengizinkan jauh lebih banyak hal daripada yang dijamin oleh sistem lifetime Rust

  • Salah satu penulis, Neven Villani, adalah putra dari peraih Fields Medal 2010, Cédric Villani
    Ini mengingatkan saya pada pepatah bahwa buah jatuh tidak jauh dari pohonnya

    • Dan saya juga ingin bercanda bahwa "qualities juga bisa dibilang dipinjam dari tree"

    • Saya juga pernah berkantor cukup dekat dengan ayahnya (peraih Fields Medal)
      Itu sebelum ia terjun ke politik

  • Model ini benar-benar luar biasa
    Saya berencana mengimplementasikannya juga di bahasa yang sedang saya buat

  • Mustahil ini déjà vu
    Rasanya seperti melihat post ini terus muncul setiap 2–3 bulan sekali

    • Makalah ini memang disiapkan selama beberapa tahun, dan akhirnya resmi dipublikasikan sekarang