AST’lerin ve Diğer Derleyici Veri Yapılarının Düzleştirilmesi

• Arena veya region, derleyiciler ve derleyici benzeri sistemler için basit ve etkili bir tekniktir.
• Soyut sözdizimi ağaçlarını (AST) arena kullanarak düzleştirmek, performansı artırabilir ve kullanım kolaylığı sağlayabilir.
• Düzleştirme, AST düğümlerini tek bir diziye paketlemek ve pointer yerine dizi indeksleri kullanmak anlamına gelir.
• Düzleştirilmiş AST’ler, daha iyi locality, daha küçük referanslar, daha ucuz tahsis ve serbest bırakma gibi avantajlar sunar.
• Düzleştirilmiş AST’ler bellek yönetimini basitleştirebilir ve kullanışlı deduplikasyonu mümkün kılabilir.
• Performans sonuçları, düzleştirilmiş yorumlayıcı sürümünün normal sürümden 2.4 kat daha hızlı olabileceğini gösteriyor.
• AST’nin düz temsili kullanılarak özyineleme kaldırılabilir ve doğrusal taramadan yararlanılarak performans daha da artırılabilir.
• Bu makale, programlama dili yorumlayıcısında veri yapısı düzleştirme ile elde edilen performans kazanımlarını tartışıyor.
• Ek olarak düzleştirilmiş yorumlayıcı, özyinelemeli yorumlayıcıya kıyasla 1.2 saniyeye karşı 1.3 saniye ile %8.2 performans artışı gösteriyor.
• Bu teknik, özünde bytecode yorumlayıcısı fikrini yeniden keşfediyor ve Expr yapısı bytecode komutları olarak kullanılıyor.
• LuaJIT, Sorbet type checker, Oil shell gibi projeler ve veri yapısı düzleştirme üzerine diğer yazılar anılıyor.
• Video oyunları, serileştirilmiş veri işleme, veri odaklı tasarım ve entity-component system gibi alanlarda da düzleştirme ve locality optimizasyonuna benzer kavramlar ortaya çıkıyor.
• Makale, Rust ile yazılmış oyuncak bir "hesap makinesi" dilinde aynı tekniği uygulayan Inanna Malick’in yazısını incelemeyi öneriyor.
• Rust’ta bu tekniği kullanmanın sınırlamaları da tartışılıyor; örneğin Expr yapısının içine başka Expr’leri inline olarak gömememe kısıtı bulunuyor.
• Performans karşılaştırmaları, M1 Max işlemci ve 32GB belleğe sahip bir MacBook Pro’da, macOS 13.3.1 ve Rust 1.69.0 çalıştırılan ortamda yapıldı.

[GN⁺]

Hacker News yorumu

• Blender, hızlı ve kayıpsız dosya yükleme ve kaydetme için diskte ve bellekte aynı gösterimi kullanır.
• Verimli satır içi işaretleme ayrıştırması için pulldown-cmark içinde düzleştirilmiş bir AST kullanılır.
• Düzleştirilmiş AST gösterimi, düğüm sayısı veya yığın derinliğinden bağımsız olarak O(1) ağaç dönüşümüne olanak tanır.
• pulldown-cmark'ın performansı, diğer CommonMark ayrıştırıcılarıyla karşılaştırıldığında olağanüstüdür.
• Warren Abstract Machine (WAM), Prolog için düzleştirilmiş gösterimi heap üzerinde kullanır.
• AST düzleştirme, Lisp gibi dillerde zaten kullanılan bir kavramdı.
• Düğümleri yeniden boyutlandırılabilir dizide saklamak bellek ayırma sorunlarına yol açabilir, ancak sayfa boyutlu bloklarda havuzlama yapılarak bu hafifletilebilir.
• AST düğümlerinin kod içinde nasıl temsil edildiğine dikkat edilmeli ve gereksiz padding'den kaçınılmalıdır.
• Pointer yerine indeks kullanmak daha küçük ve daha hızlı kod sağlayabilir.
• Belirli senaryolarda yararlı olan özel bellek ayırıcıları kullanılarak düzleştirilmiş bellek uygulanabilir.
• Bellek kısıtlı ortamlarda JavaScript ayrıştırıcısı ve yorumlayıcısı gerçekleştirmek için kompakt AST yapıları kullanılmıştır.