AST ve Derleyici Veri Yapısı Düzleştirme

 (cs.cornell.edu)
3 puan yazan GN⁺ 2023-07-04 | 1 yorum | WhatsApp'ta paylaş
  • AST’yi işaretçilerle bağlanmış bir nesne grafiği olarak tutmak yerine tek bir dizi ve indekslerle ifade etmek, derleyici tarzı veri yapılarının bellek yerleşimini ve yönetimini basitleştirir
  • Rust örneği, Box<Expr>’i ExprRef ile değiştirip ExprPool’a add/get eklemek gibi küçük bir değişiklikle düzleştirilmiş AST’yi uygular
  • Yaklaşık 100 milyon AST düğümü oluşturup hemen yorumlayan mikro benchmark’ta standart uygulama 3,1 saniye, düzleştirilmiş uygulama 1,3 saniye sürerek 2,4× hızlandı
  • Performans farkı; ardışık bellek yerleşiminin getirdiği yerellikten, 64 bit işaretçiler yerine 32 bit indeksler kullanan daha küçük referanslardan, ucuz ayırmadan ve havuz düzeyinde serbest bırakmadan kaynaklanır
  • Dizide çocukların ebeveynden önce yer alması özelliğinden yararlanıldığında, özyinelemeli ağaç dolaşımı doğrusal yürütmeye dönüşür ve bytecode yorumlayıcıya yakın bir biçime ilerler

Düzleştirmenin temel fikri

  • Arena veya region, modern dil uygulamalarında yaygın olarak kullanılır; burada ele alınan yöntem ise tek bir türü barındıran arena’yı basit bir dizi gibi kullanan veri yapısı düzleştirmedir
  • Çok işaretçili veri yapılarında işaretçileri dizi indeksleriyle değiştirme tekniğidir; ana örnek AST olsa da diğer derleyici veri yapılarına da uygulanabilir
  • Örnek kod flatcalc deposunda bulunur; standart uygulama ile düzleştirilmiş uygulama arasındaki fark branch karşılaştırmasında görülebilir
  • Kod değişikliği küçük olsa da mikro benchmark’ta 2,4× hız artışı görülmüştür; performansın dışında kodun kullanılabilirliği açısından da avantajları vardır

Standart AST gösterimi

  • Örnek dil, yalnızca tamsayı literallerini ve dört ikili aritmetik operatörü destekleyen çok basit bir aritmetik ifade dilidir
    • Olası program örnekleri 42, 0 + 14 * 3, (100 - 16) / 2 şeklindedir
  • Rust gösterimi BinOp ve Expr enum’larından oluşur
    • Expr::Binary(BinOp, Box<Expr>, Box<Expr>)
    • Expr::Literal(i64)
  • Rust’taki Box<Expr>, Expr’i gösteren bir işaretçiye karşılık gelir ve C’deki Expr* ile benzer bir rol oynar
  • Parser, çıktı formatlayıcı ve yorumlayıcı tipik yapıdadır; yorumlayıcı Expr üzerinde özyinelemeli bir metot olarak yazılır
  • Aritmetik semantik, tüm ifadelerin sonunda i64 olarak değerlendirilmesi üzerine kuruludur
    • Toplama, çıkarma ve çarpma wrapping işlemleri kullanır
    • Sıfıra bölme, checked_div kullanılarak 0 döndürecek şekilde ele alınır
  • Sabit PRNG seed kullanan rastgele program üreticisiyle, parse etme ve çıktı maliyeti olmadan AST işleme performansı ölçülür

AST’yi dizi ve indekslere dönüştürmek

  • Düzleştirme iki değişiklikten oluşur
    • Expr nesneleri heap’te ayrı ayrı ayırmak yerine tek bir ardışık dizide saklanır
    • Çocuk düğümler, işaretçi yerine dizi içindeki indekslerle referanslanır
  • Rust örneğinde ExprPool, Vec<Expr> için bir newtype olarak tanımlanır
struct ExprPool(Vec<Expr>);
  • Önceki işaretçi rolünü, 32 bit tamsayı tabanlı ExprRef üstlenir
struct ExprRef(u32);
  • Temel tip değişikliği, Binary’nin çocuk alanlarını Box<Expr> yerine ExprRef yapmak olur
enum Expr {
    Binary(BinOp, ExprRef, ExprRef),
    Literal(i64),
}
  • ExprPool’a yeni bir Expr ekleyen add ve ExprRef ile Expr bulan get yardımcıları eklenir
  • Parser doğrudan Expr döndürmez; düğümü ExprPool’a ekledikten sonra ExprRef döndürür
  • Yorumlayıcı da artık Expr metodu değil, ExprPool metodu olur; pattern matching’den önce self.get(expr) ile referansı dereference eder
  • Tüm değişiklik, Box<Expr>’i ExprRef ile değiştirmek ve gerekli noktalara add ile get koymak kadar küçüktür

Performans avantajları

  • Düzleştirilmiş AST’nin başlıca avantajı bellek yerelliğidir
    • Standart işaretçi tabanlı Expr, bellek parçalanması riski taşır
    • Düzleştirilmiş Expr, ardışık bir bellek bölgesinde yoğun biçimde durur; böylece veri cache’i ve prefetcher daha iyi çalışabilir
    • Yeterince akıllı bir bellek ayırıcı benzer bir etki yaratabilir; ancak sıkı paketlenmiş bir dizi kullanmak belirsizliği azaltır
  • Referans boyutu da küçülür
    • Standart işaretçiler modern mimarilerde 64 bittir
    • 4.294.967.295 veya daha az AST düğümü gerekiyorsa 32 bit referans yeterlidir
    • Referans başına %50 alan tasarrufu mümkündür ve işaretçisi çok olan AST’lerde toplam bellek kullanımının azalmasını sağlayabilir
    • Daha küçük veri yapılarında 16 bit veya 8 bit referanslar da mümkündür
  • Ayırma maliyeti düşer
    • Her düğüm için malloc çağırmaya gerek yoktur
    • Yeterli bellek önceden ayrılmışsa tail pointer’ı artıran bump allocation ile yeni Expr alanı oluşturulabilir
  • Serbest bırakma havuz düzeyinde yapılabilir
    • Tek tek Expr’lerin serbest bırakılmadığı varsayımı vardır
    • Birçok dil uygulamasında AST’ler birlikte oluşturulup birlikte yok olma eğilimindedir
    • Standart AST’de işaretçileri takip ederek her düğümü serbest bırakmak gerekirken, düzleştirilmiş AST’de tüm ExprPool tek seferde serbest bırakılabilir
  • Arena allocation tanıtımlarında ucuz serbest bırakma çoğu zaman başlıca neden olarak vurgulanır; ancak derleyici ortamında AST derlemenin sonuna kadar tutulabileceğinden, serbest bırakma en az önemli neden de olabilir

Kod kullanılabilirliği açısından avantajlar

  • Düzleştirme ömür yönetimini basitleştirir
    • n düğümlü bir AST, n ayrı ömür yerine tek bir AST ömrü olarak düşünülebilir
    • Rust’ta bu basitleştirme kodun lifetime ifadelerini de doğrudan etkiler
    • &Expr’lerin lifetime’larını yönetmek yerine u32 olan ExprRef aktarılıp ExprPool’un ömrüne dayanılabilir
  • Aynı basitlik, C++ gibi manuel bellek yönetimi yapılan dillerde de uygulanabilir
  • Düzleştirilmiş dizi yinelenenleri kaldırmayı uygulamayı kolaylaştırır
    • hash consing veya daha basit bir yöntemle aynı ifadenin tekrar oluşturulması önlenebilir
    • Örneğin 0’dan 127’ye kadar sık kullanılan Literal ifadeleri ExprPool’un ilk 128 yuvasına rezerve edilebilir
    • Tamsayı literali 42 gerektiğinde yeni Expr oluşturmak yerine ExprRef(42) döndürülebilir
  • İşaretçi tabanlı gösterimde de benzer işlem mümkündür; ancak yardımcı bir veri yapısına ihtiyaç duyulması daha olasıdır

Mikro benchmark sonuçları

  • Benchmark, yaklaşık 100 milyon AST düğümü içeren rastgele bir program üretip bunu hemen yorumlayıcıya verir
    • Parser ve çıktı formatlayıcı dahil değildir
    • Tek bir programı üretip hemen çalıştırma biçiminde olduğundan gerçekçi bir benchmark değildir
  • Deney koşullarında bazı sınırlamalar vardır
    • Vec<Expr> içinde tüm programı tutmaya yetecek alan önceden rezerve edilir
    • Gerçek ortamlarda arena boyutunu tahmin etmek daha fazla gerekecektir
    • Üretim ve yürütme dışında neredeyse hiç iş olmadığından ucuz ayırma/serbest bırakma avantajı abartılabilir
    • Program CPU cache’ine sığma oranı düşük olacak kadar büyük olduğundan yerellik etkisi olduğundan düşük değerlendirilebilir
  • Hyperfine ile bir dizüstünde 10 çalıştırmanın ortalaması karşılaştırılmıştır
    • Ortam: M1 Max 10 çekirdek 3,2 GHz, 32 GB bellek, macOS 13.3.1, Rust 1.69.0
  • Standart uygulama 3,1 saniye, düzleştirilmiş uygulama 1,3 saniye sürerek 2,4× hız artışı göstermiştir
  • Serbest bırakma maliyetini ayrı görmek için iki uygulamada da deallocation’ı atlayan sürümler oluşturulmuştur
    • Düzleştirilmiş uygulamada no-free sürümü ile standart sürümün süresi neredeyse aynıdır; serbest bırakma süresi büyük değildir
    • Standart uygulama 3,1 saniyeden 1,9 saniyeye düşmüş, yani yaklaşık %38’ini bellek serbest bırakmaya harcıyordu
    • no-free sürümleri karşılaştırıldığında bile düzleştirilmiş uygulama standart uygulamadan 1,5× daha hızlıdır

Düzleştirilmiş gösterimi doğrudan kullanan yorumlayıcı

  • Düzleştirme başlangıçta standart ayırma ve işaretçilerin yerini alan bir iç uygulama değişikliği gibi kullanılsa da dizi gösteriminin özelliklerinden doğrudan yararlanmak da mümkündür
  • Expr değişmezse, önce çocuk düğümleri sonra ebeveyn düğümü oluşturmak gerekir
    • a * b oluşturulurken a ve b, onları referanslayan *’dan ExprPool içinde daha önce yer alır
    • Referans okları dizide her zaman arkadan öne doğru gider, veri akışı ise ileri doğru ilerler
  • Bu değişmezden yararlanarak kökten aşağıya özyinelemeli inmek yerine ExprPool’u baştan sona tarayan bir yorumlayıcı yapılabilir
    • Dolaşım her zaman çocukları ebeveynden önce ziyaret eder
    • Her ifadenin sonucu state vektöründe saklanır
    • İkili ifade, çocuk ExprRef indeksleriyle state’e bakarak değerleri alır
    • En sonunda istenen root’a karşılık gelen sonucu döndürür
  • Bu “extra-flat” yorumlayıcıda özyinelemeli çağrıların yığın yönetimi yoktur ve ExprPool doğrusal olarak dolaşılabilir
  • Buna karşılık büyük state vektörüne rastgele erişim gerektiğinden yerellik açısından dezavantajlı da olabilir
  • Sonuç olarak extra-flat yorumlayıcı 1,2 saniye, özyinelemeli tabanlı düzleştirilmiş yorumlayıcı 1,3 saniye sürerek %8,2 iyileşme sağlamıştır

Bytecode yorumlayıcıyla bağlantı

  • Bob Nystrom’ın Reddit yorumu, bu yöntemin aslında bytecode yorumlayıcı fikrini yeniden ürettiği görüşündedir
  • Expr struct’ı bytecode komutu gibi davranır; değişken referansları da u32 ile kodlanmış referanslar gibi yer alır
  • Basit state tablosu stack benzeri bir yapıya çevrilirse, baştan tasarlanmış bir bytecode yorumlayıcıdan neredeyse farklı olmaz
  • Sadece AST veri yapısı değiştirilmiş olsa da ağaç dolaşım biçiminden bytecode biçimine doğal bir geçiş olur

İlgili kaynaklar

İlgili okumalar

1 yorum

 
GN⁺ 2023-07-04
Hacker News yorumları

  • Blender (3D modelleme yazılımı) bu yaklaşımın ilginç bir örneği. Dosya yükleme/kaydetmeyi hızlı ve kayıpsız yapmak için disk üzerindeki gösterimle bellekteki gösterimi aynı kullanıyor
    Yani her şey bir arena içinde ve kaydetme/yükleme, tüm arenayı memcpy etmek gibi. Blender projesinin potansiyel karmaşıklığı ve serileştirme/deserileştirme sorunları düşünülünce harika bir tasarım gibi görünüyor
    Dezavantajı ise eski sürüm dosyalarını da açabilmek gerektiği için veri yapısı tasarımının kolayca katılaşması

    • “Eski sürüm dosyalarını açabilmek gerektiği için veri yapısı tasarımı katılaşıyor” kısmında eksik olan parça, veritabanı migration'larında olduğu gibi veri yapılarını zaman içinde evrimleştirme yöntemi
      Bu dönüşümler yalnızca eski uygulama sürümlerinin verisi yüklenirken çalıştırılır ve ardından güncellenmiş sürümle hemen diske kaydedilirse aynı maliyet tekrar ödenmez
      CRDT bağlamında geliştirilen https://www.inkandswitch.com/cambria/ bu fikrin uygulanmasına bir örnek; doğrudan uygulanabilir olmasa bile iyi bir ilham kaynağı olabilir
    • Benzer prensiple çalışan, şirket içi geliştirilmiş bir G/Ç framework'üne dayanan büyük bir ticari uygulamada çalışmıştım ve gerçekten çok acı vericiydi
      G/Ç framework'ü sevseniz de sevmeseniz de struct'ları olduğu gibi serileştiriyordu; bu yüzden o yapıya sonsuza dek bağlı kalacağımızı bilerek veri yapılarını hep geleceği düşünerek tasarlamak zorundaydık. Karanlık zamanlardı
    • Eski “doc” dönemindeki Microsoft Word de struct'ları doğrudan diske dump eden bir sistem kullanmıyor muydu diye düşünüyorum
      Bu yüzden dönüştürücü yazmak büyük bir mesele olmuştu ve belgelenmemiş Word iç veri yapılarını çözmek gerekmişti diye hatırlıyorum
    • Üzerinde çalıştığım bir PlayStation oyunu da tam olarak böyleydi ve her şey imzalı olduğu için saldırganlar konusunda hiç endişe etmiyorduk
      Diskteki dosyaları değiştirebiliyorsanız zaten cihazı ele geçirmişsiniz demekti. Bu sayede yükleme inanılmaz hızlıydı; her şeyi belleğe okuduktan sonra sadece pointer konumlarını gerçek yükleme adreslerine göre patch ediyorduk
    • Bildiğim kadarıyla Microsoft Word de başlangıçta bu yöntemi kullandı ve dosya formatı evrildikçe bu büyük bir acıya dönüştü

  • Düzleştirilmiş soyut sözdizimi ağaçlarını seviyorum. Özellikle pulldown-cmark'ın inline markup işlemede kullandığı yaklaşımı çok beğeniyorum. Kısa bir açıklama https://fullyfaithful.eu/pulldown-cmark/ adresinde var
    Ham girdi bir düğüm dizisine bölünüyor ve * gibi işaretler vurguya dönüşebileceği ya da eşleşmezse metin olarak kalabileceği için MaybeEmphasis düğümü oluyor
    Sonraki aşamada bir stack kullanılarak düğümler sırayla taranıyor ve olası eşleşmeler aranıyor. Bir eşleşme bulunursa MaybeEmphasis düğümü uygun vurgu düğümüne çevriliyor ve açan düğümle kapatan düğüm arasındaki tüm düğüm dizisi kesilip yeni düğümün alt ağacı yapılıyor
    Bu ağaç dönüşümü oldukça sıra dışı; basit bir uygulama kolayca O(n) olabilir, ancak düzleştirilmiş AST gösteriminde düğüm sayısından ya da stack derinliğinden bağımsız olarak O(1) yapılabiliyor
    Ayrıntılı ağaç gösterimi https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6... içinde; temelde düğüm gövdesiyle birlikte child, next indeksleri tutuluyor. Vurgu eşleştirmesindeki ağaç cerrahisi kodu ise https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6... içinde
    Performansı mükemmel. pulldown-cmark tek başına en hızlı CommonMark parser olmayabilir ama fazlasıyla rekabetçi; örneğin her düğüm için allocation yapan yaklaşımlardan çok daha hızlı

  • Rust'ı öven bir GDC sunumunu hatırladım. Konu, Rust'ın borrow checker yüzünden insanı çıldırtması ya da kodu entity component system ile yapılandırmaya zorlamasıydı
    İlginç olan, karmaşık yaşam süresi sorunları bulunan gerçek örneklerde borrow checker'ın değerinin, sonunda her şeyi dizilere koyup indekslerle başvurarak borrow checker'dan mümkün olduğunca kaçmanın yolunu buldurması olması

    • Bevy oyun motorunu Rust'ta biraz kullanmış biri olarak, entity component system bana çok gelişmiş bir spaghetti code yazıyormuşum hissi verdi
      Nesneler birbirine doğrudan referans vermeyince tip sisteminin faydası ciddi biçimde azalıyor ve kod hakkında akıl yürütmek çok zorlaşıyordu. Çok büyük sistemlerde faydalı olabileceğine inanıyorum ama benim yazdığım küçük programlarda neredeyse engel gibiydi
    • Evet. Rust'ın lifetime sistemi, heap'ten kaçınılan ya da hiç heap olmayan bazı yüksek performanslı programlama alanlarında daha az güçlü kalıyor
      Oyunlar, veritabanları, gömülü sistemler, yüksek başarımlı hesaplama tarzı batch işleri, hatta derleyiciler buna dahil
      Elbette hâlâ aliasing kısıtları var, yani veri yarışı oluşmaz; ama ham pointer'lardan kaynaklanan hatalarla özünde aynı hatalar yine de ortaya çıkabilir
    • Başka bir deyişle, uzun ömürlü entity'lerin belleğe sahip olması ve bunu kısa ömürlü nesnelere ödünç vermesinin zorunlu kılındığı söylenebilir
      Bu süreçte ödünç alan taraf her zaman sahibinden daha kısa yaşar ve sahiplik sürdüğü sürece yalnızca ayrılmış belleğe erişebilir. Sahip olan ölünce bellek serbest bırakılır; ardından artık kimse onu kullanamaz ya da yeniden serbest bırakamaz, böylece use-after-free, double free ve ayrılmamış belleğe erişimden kaçınılmış olur
    • Evet. Arena veya düzleştirilmiş ağaç/graf yapılarından söz edilirken memory safety konusunun sürekli atlandığını görüyorum
      Hatta C'de arena'nın memory safety sorunlarını çözdüğüne dair tuhaf iddialar da var, ama programa göre bu yaklaşım dangling pointer, use-after-free vb. sorunları aynı ölçüde tetikleyebilir
      Aynı sorun, C/C++ ve Rust tarafında biraz farklı şekillerde ortaya çıkıyor
      İki ay önce bu yazıya bıraktığım yorum: https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
      Kısacası avantajları çok gerçek ama dezavantajları da birlikte söylenmeli. Arena'lar memory safety'yi ileriye iterken sahipliği zorlaştırabilir; değişiklik yapma ve liste/vektöre ekleme de daha karmaşık hâle gelir; öte yandan pointer temsili debugger açısından daha elverişlidir
      Bu yazının altında wiki sayfama bağlantı verilmiş; içinde gerçek kod ve ölçümler olduğu için memnuniyetle okudum: https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
    • Pointer'lar bellek uzayı için birer indeksten ibarettir. Rust genel programlama problemlerini çözmeye çalışıyorsa, borrow checker'ın yalnızca bellek uzayına özgü indeksleri değil, tüm indeksleri ele alabilmesi gerekiyormuş gibi görünüyor

  • Prolog terimleri de Warren Abstract Machine (WAM) üzerinde heap'te bu şekilde temsil edilir. Yazıdaki örnekteki gibi +(*(a,b), c) Prolog terimini operatör gösterimiyle yazarsak şöyle olur
    expr(E) :- E = a*b + c.
    Sonra sanal makinenin global stack'i üzerinde düzleştirilmiş bir temsil oluşturulur. Scryer Prolog'da WAM komutlarını ?- wam_instructions(expr/1, Is), maplist(portray_clause, Is). ile görebilirsiniz
    Çıktı put_structure(*,2,x(3))., set_constant(a)., set_constant(b)., put_structure(+,2,x(2))., set_value(x(3))., set_constant(c)., execute(=,2). gibi görünür
    İki bileşik terim de doğrusal hâle getirilir ve heap'te, functor'un ardından argümanların geldiği biçimde yerleştirilir; her biri WAM üzerinde tam olarak bir memory cell kaplar. Argümanlar başka memory cell'leri gösterebilir
    Heap bu tür hücrelerden oluşan bir dizidir ve tüm hücreler aynı somut tipe sahiptir. Örneğin Scryer Prolog hücre başına 8 bayt kullanır; bu da 64 bit mimarilerde hücre erişimi ve güncellemeyi çok verimli kılar

  • “Heap'te rastgele Expr nesneleri ayırmak yerine bunları tek bir bitişik diziye koyup, çocukları pointer yerine o dizinin indeksleriyle referanslamak” düzleştirmeden çok alternatif bir heap temsiline benziyor. AST'nin şekli aslında değişmemiş
    Lisp ailesinde olduğu gibi cons cell'leri ve diğer nesneleri bir diziye koyup bump allocation ve indeks pointer'ları kullanmak, çeşitli dillerde zaten uzun zamandır yapılan bir şey
    Nesneler dizide olduğunda, garbage collector mark aşaması bittikten sonra sweep aşamasında onları dolaşmak daha kolay olur. Mark aşaması graf üzerinde yürüyüp erişilebilir nesneleri bulur; sweep aşaması ise düz dizinin üzerinden geçerek GC bitlerini temizler ve erişilemeyen nesneleri yeniden kullanım için işaretler
    Ciddi sayılabilecek bir Lisp uygulamasında her cons cell için ayrı ayrı malloc çağrıldığını görmek muhtemelen zordur. Böyle bir durumda GC'nin sweep aşaması için ya global bir bağlı listeye koymak ya da yalnızca pointer'ları tutan global bir dizi kullanmak gerekir
    Hafta sonu yapılan oyuncak Lisp projelerinde cons cell'leri malloc ile ayırıp sızdıran ve GC'yi devasa bir TODO olarak bırakan en az iki örnek gördüm
    Hücreler sıkıştırılmış dizi heap'ten gelse bile sonuçta global bir dizi yine ortaya çıkabilir. Örneğin kopyalamayan bir allocator'da generational garbage collection uygularken, genç nesneleri toplayıp hızlı GC döngülerinde sweep etmek için yardımcı bir diziye ekleyebilirsiniz; bu dizi de nursery'yi temsil eder

  • İyi bir yazı, ancak iki tuzak var

    1. Düğümleri yeniden boyutlandırılabilir bir dizide saklarsanız, giriş programı büyüdükçe derleyici daha büyük bir bitişik bellek bloğuna ihtiyaç duyar. Bu blok olabilir de olmayabilir de. Sayfa boyutunda bloklar ayırıp bunları havuz olarak kullanırsanız bu durum aşılabilir
    2. Kodda AST düğümlerini nasıl temsil ettiğinize dikkat etmek gerekir. Örneğin düğümleri union tipiyle saklarsanız, union en büyük üye kadar yer kaplar ve tüm AST düğümlerinin boyutu aynı olmadığından küçük düğümler en büyük düğüm boyutuna göre gereksiz yere padding alır
    • Küçük AST düğümlerinin en büyük AST düğüm boyutu yüzünden gereksiz yere padding alması gerçekten çok iyi bir nokta; bunu kullanıcı tanımlı bit genişlikli tamsayı tipleri hakkındaki blog yazımda da anmıştım: https://alic.dev/blog/custom-bitwidth
      Tagged union da mümkün, ancak bellek kullanımını akıllıca ele almak gerekir
    • Bazen keşke düz bir adres alanına varmış olmasaydık diye düşünüyorum
      “Sanal bellek” tekniği, parçalanmış fiziksel bellek bölgelerini bitişik sanal bellek bölgeleri halinde birleştirmeyi mümkün kılıyor. Eğer sanal adres alanı segmentli olsaydı en başta parçalanma yaşanmazdı ve hiçbir bellek bölgesi diğerleriyle çakışmadan yerinde sürekli büyüyebilirdi
      O zaman realloc() implementasyonu memcpy() yolunu ortadan kaldırabilirdi, ne yazık
    • Vektörü sabit boyutlu parçalara bölmek için rope benzeri bir yapı ve gerçek pointer'lar kullanılabilir. Böylece yeniden tahsis gerekmez
      İç kısım güvenli olmayacaktır ama salt okunur, güvenli bir arayüz mümkün görünüyor. Serbest bırakma O(n) olurdu ama yine de ağaçtan çok daha hızlı olurdu

  • Artık ilk pointer'ın her zaman tam olarak bir sonraki düğümü gösterdiğini biliyorken, düğümde iki pointer (“referans”) daha kalmasına şaşırdım
    https://github.com/rswier/c4 böyle bir yaklaşım kullanıyor. Elbette kod okunabilirliği iyi değil ama daha küçük ve daha hızlı

  • Bellek yönetiminde arena denince, “düzleştirme”den çok doğrudan bir arena allocator akla geliyor
    Aynı ömre sahip çok sayıda öğe tahsis ederken, bir veya daha fazla büyük bellek parçasından daha verimli tahsis yapıp, ortak ömür bittiğinde tek tek öğeleri değil büyük parçayı serbest bırakma yaklaşımıdır
    Yalnızca üst parçadaki alanı sıralı biçimde tüketmek yeterli olduğundan, genel amaçlı heap allocator'lardaki gibi free list gerekmez; bu yüzden tahsis daha verimli olabilir
    Bu bağlamda pointer yerine indeks kullanarak yapılan “düzleştirme”, üst parçaya göre relatif pointer, yani offset kullanmak olarak da görülebilir

  • Belleğin aşırı kısıtlı olduğu gömülü ortamlar için JavaScript parser'ı ve interpreter'ı olan V7'yi (https://github.com/cesanta/v7) geliştirirken böyle kompakt bir AST yapısı kullanmıştım
    Sonradan AST'den bytecode'a derleme aşamasına geçtim ama bir süre boyunca örtük AST'yi yorumlama sırasında doğrudan gezdim

  • https://yaml2sql.netlify.app üzerindeki Yaml to Sql compiler'ımda da benzer bir şey yaptım
    Düzleştirme süreci biraz tuhaf ama eğlenceli ve sonuçta harcanan çabaya değdi
    Örneğin boolean expression düzleştirmesi, denemek isteyenler için iyi bir alıştırmadır: https://github.com/revskill10/yaml2sql/blob/main/app/query.r...