Tree Borrows

 (plf.inf.ethz.ch)
1 puan yazan GN⁺ 2025-07-10 | 1 yorum | WhatsApp'ta paylaş
  • Rust dilindeki unsafe kod optimizasyonu sınırlarını aşmak için yeni bir bellek modeli olan Tree Borrows öneriliyor
  • Mevcut Stacked Borrows yaklaşımının pratik Rust kodunda sık kullanılan çeşitli kalıplara izin verememesi sorununu Tree Borrows, ağaç yapısıyla çözüyor ve daha gerçekçi, daha esnek kurallar sunuyor
  • Tree Borrows, Stacked Borrows'a göre gerçek dünyadaki kod test vakalarının %54 daha fazlasını geçiriyor
  • Başlıca Rust bellek güvenliği ve optimizasyon olanaklarını (özellikle read-read reordering gibi) büyük ölçüde korurken, modern Rust borrow checker'ın gelişmiş özelliklerini de yansıtıyor
  • Ağaç tabanlı durum makinesi modelini tanıtarak Rust optimizasyonu ve güvenlik doğrulama araştırmaları için önemli bir kilometre taşı ortaya koyuyor

Rust'un sahiplik sistemi ve unsafe kodun sınırları

  • Rust, sahiplik tabanlı tip sistemi sayesinde bellek güvenliği ve veri yarışı önleme gibi güçlü garantiler sunar
  • Ancak Rust'ta bir unsafe escape hatch bulunur; bu durumda güvenlik doğrulaması derleyiciden geliştiriciye geçer
  • Derleyici, güçlü optimizasyonlar için pointer alias kurallarından yararlanmak ister; ancak hatalı unsafe kod bu optimizasyonları etkisiz bırakabilir

Stacked Borrows ve sınırları

  • Daha önce Stacked Borrows adlı model, unsafe kodda “yanlış davranış”ı tanımlayıp optimizasyon için ölçüt sunuyordu
  • Ancak bu yaklaşım, gerçek Rust kodunda yaygın olan çeşitli unsafe kalıplara izin veremiyor ve yakın zamanda eklenen Rust borrow checker özelliklerini de yansıtamıyordu

Tree Borrows'un ortaya çıkışı

  • Tree Borrows, bellek izinlerini Stacked (yığın) yapı yerine ağaç yapısıyla izleyen yeni bir modeldir
  • Böylece pratik Rust kodundaki daha fazla kalıbı güvenli biçimde kabul eder ve borrow kurallarının esnekliğini ve gerçek dünyaya uygulanabilirliğini önemli ölçüde artırır
  • 30.000 popüler Rust crate değerlendirmesinde, Stacked Borrows'a göre %54 daha fazla test vakasını geçmiştir

Tree Borrows'un özellikleri ve avantajları

  • Mevcut Stacked Borrows'un ana optimizasyonlarını (ör. read-read reorderings) büyük ölçüde korur
  • Buna ek olarak modern Rust borrow checker'ın gelişmiş özelliklerini de (ör. alışılmadık borrow kalıpları, karmaşık pointer işlemleri vb.) yansıtabilir
  • Ağaç tabanlı durum makinesi modelini tanıtarak güvenlik ile optimizasyon olanakları arasında denge kurar

Sonuç ve önemi

  • Tree Borrows, Rust derleyicisinin unsafe kod işleme ve optimizasyon araştırmaları için yeni bir ölçüt ortaya koyuyor
  • Pratik Rust kodunu ve modern borrow checker politikalarını kapsayan gerçekçi ve sağlam bir bellek modeli olarak değerlendiriliyor
  • İlgili makale, artifact ve kaynak kod kamuya açık; bunun Rust derleyici ve doğrulama araştırma topluluğu üzerinde büyük etkisi olması bekleniyor

İlgili okumalar

1 yorum

 
GN⁺ 2025-07-10
Hacker News görüşleri

  • Son dönemde Ralf Jung’un blog yazısı daha fazla bağlam sunuyor bağlantı
    Bonus: Rust’ın yürütme semantiğini Rust’ın bir lehçesiyle açıkça tanımlamayı amaçlayan araştırma grubunun yakın tarihli sunumu da tavsiye edilir YouTube

  • Derleyici açısından, pointer aliasing ile ilgili tür sisteminin güçlü garantilerinden yararlanarak güçlü optimizasyonlar yapılabildiği iddia ediliyor; pratikte bunun ne kadar etkili olduğunu merak ediyorum
    Linus Torvalds uzun zamandır C’nin strict aliasing kurallarının pek faydalı olmadığını, hatta sorun çıkardığını savunuyor
    Onun örnek yazısı da ilgi çekici
    Rust’ın özünde C’den kökten farklı olup olmadığını merak ediyorum; kişisel deneyimime göre, özellikle unsafe devreye girince çok da farklı hissettirmiyor

    • C’nin strict aliasing kurallarının gerçekten kötü olduğunu düşünüyorum
      Rust’ta önerilen kurallar çok daha farklı; derleyici açısından da daha kullanışlı, programcı açısından da daha az yük getiriyor
      Dil içinden vazgeçme seçeneği olarak raw pointer kullanılabiliyor ve kodu denetleyebilen araçlar da var
      Sonuçta her dil tasarımında olduğu gibi bu da bir uzlaşma
      Rust sanki bu optimizasyon alanında yeni bir denge bulmuş gibi görünüyor; bu kararın sonucunu zaman gösterecek

    • Rust’ın aliasing kuralları C’den çok farklı
      C’de restrict anahtar sözcüğü neredeyse yalnızca fonksiyon parametrelerinde anlamlı ve tür tabanlı aliasing (type-based aliasing) pratikte ya pek kullanılmıyor ya da kullanımı zor
      Rust’ta lifetime, mutability gibi özellikler ayrıntılı biçimde ifade edilebiliyor ve bellek, türün kendisinden bağımsız olarak çeşitli şekillerde güvenli biçimde ele alınabiliyor
      Özellikle iç içe geçen &mut referanslar oluşmadığı sürece, belleği birden fazla çakışmayan &mut parçaya bölerek kullanabilmek önemli

    • Bunun pratikte performansı ne kadar etkilediğine dair daha geniş bir analiz görmek isterim
      Bunu anlamanın kolay yolu, derleyicide LLVM’e aliasing bilgisini aktaran kısmı tamamen çıkarıp performansı karşılaştırmak olur
      noalias anotasyonunun çalışma zamanında yaklaşık %5 performans artışı sağladığı yönünde bir iddia da var; ilgili yorum burada bulunabilir (veri eski olsa da)

    • Linus’un derleyiciler hakkında söylediklerini biraz temkinli değerlendirmek gerekir
      OS çekirdeği ve derleyiciler tamamen farklı alanlar
      Günümüzde alias analizi gerçekten güçlü performans artışlarının merkezinde yer alıyor
      En büyük kazançlar basit sezgilerden geliyor; karmaşık alias sorguları ise tek başlarına çok kullanışlı değil
      Kuramsal olarak kusursuz bir alias analizinin performansı ne kadar artıracağını deneysel olarak görmek isterdim ama sıradan kodlarda bile sınırın yaklaşık %20 civarında olacağını tahmin ediyorum
      Elbette çok ileri optimizasyonlar için (örneğin veri yerleşimi dönüşümleri) alias analizi olmadan işe başlamaya bile cesaret edilemeyen bir durum var

    • C’nin strict aliasing’i ile Rust’ın aliasing’i kavramsal olarak farklı
      C’de esas olan tür tabanlı analiz (TBAA) ve Rust bunu bilinçli olarak benimsemedi

  • Stacked Borrows hakkında daha önce 2020 ve 2018’de de başlıklar açılmıştı
    2020 başlığı
    2018 başlığı

  • Tree Borrows belirtimini birkaç yıl önce Nevin’in sitesinde okumuştum; karmaşık sorunları bile zarif biçimde çözmesi beni etkilemişti
    Gerçek deneyimime göre Tree Borrows, Stacked Borrows altında mümkün olmayan makul kodlara izin veriyor
    Rust standart kütüphanesindeki örnek kod da bakmaya değer

  • Rust’ın veya yeni nesil bir PL’nin, özellikleri ve amaçları farklı olan birden fazla borrow checker uygulaması arasından seçim yapılabilen bir yöne evrilip evrilemeyeceğini merak ediyorum; örneğin derleme hızı, çalışma zamanı hızı, algoritmik esneklik gibi

    • Rust zaten borrow checker uygulamalarını değiştirmeyi destekliyor
      Kapsam tabanlı modelden non-lexical yapıya geçti ve Polonius adlı deneysel bir uygulama da seçenek olarak mevcut
      Yeni uygulama hazır olduğunda eski sürümün özellikle korunmasına gerek duyulmuyor
      Rc, RefCell gibi çalışma zamanında denetim yapan yapılarla daha esnek kullanım da mümkün

    • affine type (Rust’ın kullandığı), linear type, etki sistemleri, dependent type, biçimsel ispat gibi pek çok yaklaşım zaten var
      Her yöntemin uygulama maliyeti, performansı, geliştirme deneyimi gibi farklı özellikleri bulunuyor
      Rust dışında da üretkenliği koruyarak kaynakların otomatik yönetimiyle tür sistemini birleştirme yönünde bir eğilim var

    • Aslında ihtiyaç duyulan şey, fonksiyonların precondition’larını hassas biçimde ifade edebilen ve ara koşulların ispatını da mümkün kılan separation logic
      Rust’ın yaklaşımı, insanların gerçekte istediği yaygın değişmezleri sistematik hale getirip güçlü optimizasyonları güvence altına almak

    • Borrow checker’ın sonucunun false negative içerip false positive içermemesi mi gerektiğini merak ediyorum
      Eğer öyleyse, birden fazla uygulamayı thread’ler üzerinde paralel çalıştırıp en hızlı sonucun kullanılması da mümkün olabilir mi diye düşünüyorum

    • Birden fazla borrow checker uygulamasına aynı anda izin vermek, ekosistemin bölünmesine yol açabileceği için arzu edilir görünmüyor

  • Makaledeki Rust kodunu gerçekten test ettim ve güncel kararlı derleyicide reddedilmediğini doğruladım
    Örnek kod:

    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, miri’nin çalışma zamanı modeli
      miri’de yukarıdaki kodu çalıştırırsanız *x = 10; satırında hata bildirir, ama write(x); için hata oluşmaz
      rustc ise tür sistemi açısından y bir *mut olduğu için her iki sürümü de reddetmek için bir neden görmez

  • Makalede unsafe kodun sorunu olarak aşağıdaki örnek veriliyor:

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

    Bunun gerçekten mümkün olup olmadığını merak ediyorum
    Aynı değişkene birden fazla mutable referansı pointer üzerinden vermek açıkça UB gibi görünüyor; bir şeyi yanlış anlayıp anlamadığımı merak ediyorum

    • Bu araştırmanın özü, UB’nin (tanımsız davranışın) sınırlarını kesin biçimde tanımlamak
      Yukarıdaki kod Rust derleyicisi tarafından kabul edilse bile kuralları ihlal ediyor
      Peki hangi kuralları?

  • borrow checker’dan geçen kod yasaldır

  • unsafe, yasa dışı/UB durumları da ifade edebilir

  • borrow checker’ın kapsadığından daha geniş ama yine de yasal olan bir kurallar kümesi vardır
    Bu araştırmanın amacı o sınırı titizlikle tanımlamak
    Stacked Borrows makalesi daha basit ama gerçek unsafe kod için sınırlayıcıydı; Tree Borrows ise daha geniş bir güvenli alanı kabul ediyor

    • “Birden fazla mutable referans pointer’ının aynı anda var olamayacağı” açık, ama bunun tam olarak hangi kuralı ihlal ettiğine dair net bir ifade yok
      Tree Borrows tam da böyle bir tanım öneriyor
      “Kod böyle bir şey yapabilir” denmesi, gerçekten o kodu yazıp çalıştırabileceğiniz ama Tree Borrows gibi bir tanım olmadan bunun neden yanlış olduğuna dair sağlam bir gerekçe kurmanın zor olduğu anlamına geliyor
      Aslında siz de Tree Borrows gibi açık kurallara duyulan ihtiyacı zaten kabul ediyor gibisiniz

    • unsafe kod pratikte gerçekten bu şekilde yazılabiliyor ve mesele tam da bunun UB olması
      Örnek: playground bağlantısı

    • Bağlamı görmek isterseniz, makaledeki hemen sonraki paragrafın başlangıcı niyeti çok iyi ortaya koyuyor

Rust derleyicisi geliştiricileri aliasing optimizasyonları istiyorsa, yukarıdaki gibi karşı örnek kodları dışlamanın bir yoluna ihtiyaçları var

  • Evet, mesele tam olarak bu
    Birden fazla mutable referansın yasak olması kuralına uymak zor ve unsafe, Rust’ın lifetime sisteminin güvence altına aldığından çok daha fazlasına izin verebiliyor

  • Yazarlardan biri olan Neven Villani, 2010 Fields madalyası sahibi Cédric Villani’nin oğlu
    Aklıma “armut dibine düşer” benzetmesi geliyor

    • Bir de “qualities’nin de tree’den borrow edildiği söylenebilir” diye espri yapmak istedim

    • Ben bir dönem babasıyla da (Fields madalyası sahibi olanla) yakın ofislerde çalıştım
      siyasete girmesinden önceydi

  • Bu model gerçekten harika
    Ben de geliştirdiğim dilde bunu uygulamayı planlıyorum

  • Bu bir deja vu olamaz
    Sanki bu gönderiyi her 2-3 ayda bir tekrar tekrar görüyorum

    • Makale birkaç yıla yayılan bir hazırlık sürecinin ardından nihayet resmen yayımlandı