Zig'de bellek açısından verimli enum dizileri

 (alic.dev)
3 puan yazan GN⁺ 2023-09-19 | 1 yorum | WhatsApp'ta paylaş
  • Boyutları farklı variant'ları olan enum/tagged union yapıları büyük miktarda depolandığında, en büyük variant'a göre alan ayrılması nedeniyle Vec·HashMap içinde padding ve parçalanma maliyeti artar
  • Zig, comptime ve tip yansıması sayesinde alan boyutu·hizalama·discriminant bilgilerini inceleyip, enum kapsayıcılarını bellek yerleşimine göre jenerik biçimde dönüştürebilir
  • Basit bir Vec<Enum> yaklaşımında her öğe en büyük variant kadar yer kaplar; SoA ise tag padding'ini azaltır ama değer alanındaki variant fragmentation sorununu ortadan kaldırmaz
  • Aynı boyuttaki variant'ları gruplayan dense AoVA, örnek enum'da 15 vektörü 2·4·8 baytlık 3 kümeye indirir; ancak aynı allocation içinde birden fazla variant karıştığında tür güvenli iterasyon zorlaşır
  • Rust proc macro'ları tip boyutu·hizalama bilgilerine erişmekte zorlanır ve generic dizi uzunluğu hesaplamasında da kısıtlarla karşılaşır; bu yüzden Zig'in tipe duyarlı staging yaklaşımı, sistem kodunda bellek verimliliğinin bileşenler arasında daha iyi birleştirilebildiğini gösterir

Rust enum dizileri neden alan israf eder

  • Boyutları farklı variant'lara sahip enum/tagged union türleri, en büyük variant'ı barındırabilecek kadar bellek ayırmak zorundadır
  • Örnek Foo enum'u u8, u16, u32, u64 variant'larına sahiptir ve tag ile hizalama nedeniyle tür boyutu 16 bayt olur
  • Bu tür enum'lar Vec ya da HashMap içinde çok sayıda tutulduğunda, her öğe en büyük variant'a göre yer kaplar; bu da padding ve parçalanmayı artırır
  • Tag'i ayrı bir allocation'da tutan struct of arrays(SoA) dönüşümü bazı padding maliyetlerini azaltabilir, ancak variant boyutu farklarından doğan değer alanı parçalanmasını tamamen gidermez
  • Rust'ta da belirli bir enum için özel veri yapısı yazılabilir; ancak rastgele bir enum için mümkün olan en bellek verimli jenerik veri yapısını kurmak zordur, hatta pratikte neredeyse imkânsızdır
    • proc macro'lar üçüncü taraf tipler veya type alias'lara #[derive] eklemekte zorlanır ve bileşenlenebilirlikleri düşüktür
    • Tip farkındalığı yoktur; generic_const_expr tabanlı dolaylı çözümler ise ayrıntılı where koşullarını çağrı grafiğine yayar ve generic type parameter'larla iyi uyuşmaz

Derleyici AST'lerinde sorunun daha belirgin olmasının nedeni

  • Verimli enum dizilerine yönelik en büyük motivasyonlardan biri, derleyici AST'lerinin bellek kullanımıdır
  • Büyük AST'ler derleme sırasında bellek gecikmesine ve cache eviction'a yol açarak frontend performansına ciddi maliyet getirir
  • Chandler Carruth'un Carbon compiler videosunda, parse edilmiş clang AST'sinin kaynak koddan sık sık 50 kat fazla bellek tüketebildiği belirtilir
  • Rust'ta ifade düğümlerini temsil eden örnek yapı bir Expr enum'udur
    • Unit
    • Number
    • Binary(Operation, ExprId, ExprId)
    • Ident(Symbol)
    • Eval(ExprId, ExprSlice)
    • BlockExpression(ExprId, StatementSlice)
  • OCaml'da çalışma zamanı sistemi ve GC bellek yönetimini üstlendiği için, açık indirection olmadan özyinelemeli veri tipleri ifade edilebilir
  • Rust'taki Vec<Expr> içinde tüm öğeler sizeof(Enum) kadar yer kaplar; buna en büyük variant boyutu, tag ve padding dahildir

SoA ve AoVA ile parçalanmayı azaltmak

  • Basit bir 3-variant enum'da üyeler 8·16·32 bit boyutlarında olduğunda, sıradan Vec 32 bitlik variant ve hizalama koşullarına uyum sağlamak için tüm öğelere büyük alan ayırır
  • Yaygın bir iyileştirme, tagged index gibi yöntemlerle enum variant'ının kendisini küçük tutmaktır
    • Rust compiler'ın tagged_index crate'i
    • small-string optimization örnekleri
    • Dil çalışma zamanları, GC, derleyiciler, oyun motorları ve OS kernel gibi yüksek performanslı kodlarda sık görülen bir optimizasyondur
  • Kapsayıcıyı değiştirip discriminant ile değeri ayrı allocation'larda tutan SoA yaklaşımı da mümkündür
    • self-hosted Zig compiler bu yöntemi kullanır
    • Tag'den kaynaklanan padding azalır, ancak union değer koleksiyonunda hâlâ variant fragmentation kalır
  • Zig'in staged compilation modeli, rastgele tipler için SoA dönüşümü yapan kapsayıcıların jenerik olarak kurulmasına imkân verir
  • Rust ise soa_derive gibi proc macro'lara bağımlıdır; ayrıca üçüncü taraf tipin kaynağını değiştirmeden #[derive] ekleyememe kısıtı vardır

Variant başına dizi ve boyuta göre kümelendirme

  • Değer alanındaki parçalanmayı daha da azaltmak için her variant için bir vektör tutulabilir
  • Ekleme sırasında, enum tag'i ile ilgili variant dizisindeki index'i birlikte taşıyan bir tagged index döndürülür
  • Bu desen array of variant arrays(AoVA) olarak adlandırılır
  • AoVA, Rust'ta proc macro ile, Zig'de ise comptime ile uygulanabilir
  • Variant sayısı fazlaysa ve aynı boyuta sahip birden çok variant varsa, variant başına vektör yaklaşımı aşırı sayıda vektör üretir
    • Örnek Foo enum'unda 15 variant vardır
    • Variant başına vektör yaklaşımı 15 ek vektör gerektirir
    • Yeniden ayırma ve sistem çağrısı sayısı artabilir; amortization açısından da naive Vec'e göre daha fazla bellek gerekebilir
    • Vektörler bellekte rastgele dağılabildiğinden cache conflict olasılığı artabilir
    • AoVA kapsayıcısının kendisi de çok bellek kullanarak onu içeren struct'ı şişirebilir
  • Boyuta göre gruplandığında, örnek enum 2 bayt, 4 bayt, 8 bayt olmak üzere üç kümeye ayrılır
    • c_2: Vec<[u8; 2]>, A ile D arasını depolar
    • c_4: Vec<[u8; 4]>, E ile I arasını depolar
    • c_8: Vec<[u8; 8]>, J ile O arasını depolar
  • Dense AoVA yaklaşımı toplam vektör sayısını %80 azaltabilir
  • Farklı variant'lar aynı allocation içinde tutulduğunda, vektör üzerinde tür güvenli biçimde iterasyon yapmak zorlaşır
    • Erişim yalnızca ekleme sırasında üretilen tagged pointer üzerinden mümkündür
    • Kör iterasyon gerektirmeyen, flattened index tabanlı ağaç yapılarında bu kabul edilebilir bir trade-off olabilir
  • Tür güvenli iterasyon gerekiyorsa, padding maliyetini üstlenip tag yeniden eklenebilir
  • Padding çok büyükse her variant dizisine SoA dönüşümü uygulanabilir; ancak bu kez vektör sayısı iki katına çıkar

Zig comptime ile gelen bellek yerleşimi bileşenlenebilirliği

  • Zig prototipi osmium içinde uygulanmıştır
  • Temel mekanizma, alan tipi, bayt boyutu, bit boyutu ve discriminant'ı inceleyen derleyici built-in'leriyle yapılan derleme zamanı yansımasıdır
  • Örnek kod @typeInfo(inner) ile tip türünü denetler ve yalnızca union ise işleme devam eder
    • union alanları üzerinde dolaşır
    • @max(field.alignment, @sizeOf(field.type)) ile gerekli alanı hesaplar
    • Boyut bilgilerini stack-allocated bir vektörde saklar
    • union alanından cluster index'e giden eşlemeyi kurar
    • union değilse compile error üretir
  • Tam kod parçası ilgili kaynakta bulunabilir
  • Aynı örneği Rust proc macro ile kurmak temelde mümkün değildir
    • proc macro'lar tipin size veya alignment bilgisine erişemez
    • Belirli bir enum için cluster hesaplayan const fn üretilebilir, ancak bu generic bir tipin dizi uzunluğunu belirlemek için kullanılamaz
  • Rust'ta jenerik bir kapsayıcı uygulaması, verilen tipin enum mu struct mı olduğuna göre koşullu biçimde değiştirilemez
  • Zig'de kavramsal olarak T.isEnum() sonucuna göre EfficientEnumArray<T> ile EfficientStructArray<T> arasında seçim yapılabilir
  • AoVA uygulaması da enum özelliklerine göre seçilebilir
    • Örneğin, farklı variant'ları birlikte yerleştirmenin ancak vektör sayısını %90'dan fazla azalttığında anlamlı olduğuna karar veren bir özelleştirme yapılabilir
  • Maksimum capacity derleme zamanında biliniyorsa, tip üretim fonksiyonu tagged index için gereken bitwidth değerini belirleyebilir
  • Bu tagged index başka bir veri yapısının, örneğin başka bir enum'un içine girerse, boşta kalan bitler discriminant için kullanılabilir
  • Zig, gereken bit sayısını somut olarak ifade etmeye izin vererek kodun diğer bölümlerinin de bu bilgiyi doğal biçimde kullanmasını sağlayan bileşenlenebilir bellek verimliliği sunar
  • implicit widening integer coercion sayesinde, farklı bitwidth'e sahip API'lerle çalışırken de kullanım kolaylığı korunur
  • Verimlilik ve zero-cost abstraction'ı önemseyen sistem programlama dilleri için, staged programming'e, özellikle de Zig'in comptime yaklaşımına yeniden bakmak gerekir

İlgili okumalar

1 yorum

 
GN⁺ 2023-09-19
Hacker News yorumları

  • Depolama verimliliği iyi olan ve öğe dolaşımını da koruyan başka bir strateji var. İlk vektör etiket listesi, ikinci vektör her öğenin bayt ofseti, üçüncüsü ise vektörden çok ikinci vektörün işaret ettiği sıkıştırılmış variant verisi olacak şekilde tutuluyor.
    Böylece yazarın nihai çözümüne göre vektör sayısı yarıya iniyor (6'ya karşı 3), sıralama nedeniyle gerekli olan durumlar dışında padding baytları boşa harcanmıyor ve türden bağımsız olarak veri bellekte sıralı yerleştiği için cache dostu biçimde dolaşılabiliyor. İndeksle öğelere O(1) erişim de mümkün. Genel olarak heterojen veri için Vec benzeri performans özellikleri taşıyor.

    • Bayt ofsetini inline saklamak iyi bir fikir. Ancak ofset bellekte saklanırsa dolaşım sırasında veri bağımlılığı oluşur; bu da cache dostu olsa bile işlemci pipeline'ında ciddi bellek tıkanmalarına yol açabilir.
    • Böyle bir koleksiyonu değiştirmeniz gerekiyorsa, silme, daha büyük bir variant'a değiştirme ve parçalanmayı ele almak için sonunda muhtemelen bellek ayırıcıyı doğrudan kullanırsınız.
    • Ofset boyutu optimize edilmezse küçük T'lere kıyasla oldukça fazla yer kaplayabilir. Örneğin 64 bit size_t ile uint8_t T birleşimi böyle; yalnızca ofset boyutuna dikkat edilirse makul bir yaklaşım gibi görünüyor.

  • Bu AoVA veri yapısının gerçekte nasıl çalıştığını merak ediyorum. Dizi açısından indeks aritmetiğinin artık anlamlı olmayabileceği düşünüldüğünde indeks tabanlı erişimi kaybetmiyor muyuz? Dolaşım da ekleme sırasını korumayacak gibi.
    Bu bağlamda cache özellikleri daha iyi olan TLV(tag-length-value)'nin daha yaygın kullanıldığını düşünüyorum. Uzunluk etiketten çıkarılabilir de; en azından anlamlı bir ileri yönlü dolaşım sağlar. getdents, inotify, Netlink mesajlaşmasına bakın.

    • Şekil 4'ün açıklamasına bakılırsa AoVA örüntüsünün eklenen öğelerin genel sırasının korunması gereken durumlara pek uygun olmadığını kabul etmek gerekir.
      Önceki SoA yerleşimiyle karşılaştırıldığında genel sıra değil, kısmi sıra oluşuyor. Ekleme sırasında enum etiketiyle ilgili variant dizisi içindeki indeksi birlikte içeren etiketli bir indeks döndürülen bir yapı. Bu yüzden sıralı erişim burada kapsam dışı görülüyor gibi. Her öğede global bir indeks saklanırsa sıralı dolaşım geri getirilebilir, ama sıralı rastgele erişime yine de yardımcı olmaz ve kodun epey dallanmalı olması muhtemel.
    • Ekleme sırasında döndürülen “enum etiketi ve ilgili variant dizisi içindeki indeks” özünde bir pointer'dır. Dolaşmak istiyorsanız pointer'ları istediğiniz kullanım sırasına göre bir dizide saklarsınız. Heap'te bellek ayıran bir programın yaptığı şeyle aynı.
      Nesneleri boyutlarına göre saklama yöntemi garbage collector'larda ve genel amaçlı ayırıcılarda da kullanılır. Olası nesne boyutlarının tümünü bilmekten verim kazanılabilir; arena gibi daha basit serbest bırakma yöntemleriyle de verim elde edilebilir.
    • AoVA'nın indeksler için kendi genel sırasına sahip olmaması bazı kullanım durumlarında sorun olabilir, ama burada önerilen AST düğümleri için mutlaka sorun değildir.
      Bu durumda diziler, heap benzeri bir yapının bir bileşeni, yani arena gibi görülebilir. Maliyeti, indeksin (tag_idx, va_for_tag_idx) gibi 2 boyutlu olması gerekmesidir. Ancak etiket sayısı derleme zamanında bilindiğinden, tag_idx üstteki 4~5 bite koyulup va_for_tag_idx kalanını kullanacak şekilde paketlenerek depolama optimize edilebilir. Referans: https://www.cs.cornell.edu/~asampson/blog/flattening.html
    • İndeksin türünü değiştiren dizi yazmaları inanılmaz pahalı olacak gibi.

  • Rust'ın pattern matching'inin kendi depolama yapısına sahip açık, birinci sınıf, hardcode edilmiş bir nesne tipi olmak yerine, rastgele yapıların uyabileceği tip sistemindeki trait benzeri bir biçimde daha fazla ifade edilememesi biraz üzücü.
    Yakın zamanda bu yazıdaki gibi bir AST de, bir opcode/bytecode yorumlayıcısı da uyguladım; Rust enum'larının ikisi için de tamamen ideal olmadığını hissettim. AST'de tüm statement düğümlerine satır numarası/sütun özellikleri eklemek istiyordum; Stmt enum'unun tüm durumlarına satır/sütun koyunca boilerplate kirli hale geliyor, enum'u özgün enum ile satır/sütun özelliklerini birlikte taşıyan yeni bir Stmt struct'ıyla sarmalayınca da çok refactoring gerekiyor ve zarif olmuyordu. Opcode tarafında da pattern matching yapılan bir Rust enum'unun VM opcode yorumlayıcısı performansı açısından ideal encoding olduğu söylenemez, ama dil bu yöne teşvik ediyor ve destructuring pattern özelliği çok çekici. İstenen düşük seviye implementasyonu kullanırken yine de pattern matching özelliğini elde etmeyi sağlayacak tip sistemi iyileştirmelerine yer var gibi görünüyor.

    • Daha somut bir örnek olsa iyi olurdu. Aklıma ilk gelen bir tür yapısal tip sistemi, ama tam olarak bunu mu kastettiğinizden emin değilim.
      https://en.wikipedia.org/wiki/Structural_type_system
    • Bytecode yorumlayıcılarında eski bir teknik, bir sonraki opcode implementasyonuna geçerken dolaylı atlama kullanmaktır. gcc'de bunun için computed goto eklentisi vardı; Rust'ta ise muhtemelen fonksiyon pointer'ları ve tail call optimizasyonunu zorlayacak bir şeye ihtiyaç olurdu.
      Böyle bir dolaylı atlama her opcode implementasyonunun başına koyulursa, CPU'nun OOP nedeniyle sahip olduğu dolaylı atlama tahmincisi farklı opcode sonları için ayrı modeller tutabilir ve tahmin başarı oranı artabilir. Bir sonraki komutun kendisini tahmin etmek zor olsa da, örneğin test'ten sonra branch gelme olasılığı çok daha yüksek olabilir. Ancak stack makinesinde stack'in tepesini register'da saklamak gibi başka tekniklerin daha önemli olacağını düşünüyorum; yukarıdaki tekniğin bugün hâlâ anlamlı olup olmadığından da pek emin değilim.
    • Birçok dilde istediğinize benzer özellikler var. Scala'nın extractor'larına veya F#'ın active view'larına bakın.

  • “Ayrıştırılmış clang AST’si düzenli olarak özgün kaynak koddan 50 kat daha fazla bellek yiyor” ifadesi oldukça büyük görünüyor, ama eksik bağlam ne kadar iyileştirilebileceği. Her token’ın kaynak konumunu korumak ve AST’den düzgünce geri kazanılabilecek kadar bilgi kodlamak gerekiyorsa, özgüne göre ideal artış oranının 1,5 kat mı yoksa 15 kat mı olduğunu merak ediyorum

    • Örneğin bellekte %30 tasarruf mümkünse bu epey büyük haber olur. Ancak derleyicinin gelecekte bakımını zorlaştırıp yalnızca %30 azaltıyorsa pek değerli olmayabilir. Tersine, derleyiciye biraz sert davranmayı gerektirse bile %80 tasarruf sağlanıyorsa denemeye değer
      Kullanıcı dostu ve aynı zamanda derleyici geliştiricileri için de dostu bir dilde ideal kaynak→AST şişme oranının ne olduğunu söylemek zor, ama 50 kat da çalışıyor. Özgün metinde 50 katlık şişme oranı, belirli bir optimizasyonu otomatikleştirmek için motivasyon olarak kullanılıyor. Rust’ın enum vektörleri enum değerlerini otomatik olarak tag ve opak değerlere ayırıp, Zig’de özgün metnin yaptığı gibi dizi-struct biçiminde saklayabilse ilginç olurdu. unsafe kullanımını gizleyecek pek fazla yer de yok gibi
    • Karşılaştırma olarak simdjson tape, özgün belgeden kabaca yalnızca 3 kat büyük. Sayıları tek bir tape slotuna koyarak ya da kaçış dizisi içermeyen dizgeleri kopyalamadan özgün belgedeki konuma referans vererek bunun önemli bir kısmı azaltılabilir
      Çoğunluğu [] karakterlerinden ya da 0, karakterlerinden oluşan belgelerde en yüksek ek yük yaklaşık 8 kat gibi görünüyor
    • Kaynak kod şaşırtıcı derecede yoğundur. Ne kadar iyileşebileceğine dair bir veri olarak, Zig’in kendi ayrıştırıcısının Zig’in kendi ayrıştırıcısını ayrıştırdığı sonuç var
      Kaynak baytları: 139 KiB, token: 24646 adet (120 KiB), AST düğümü: 10998 adet (140 KiB). Her token 5 baytla oldukça minimize edilmiş durumda (1 bayt tag + 4 bayt dosya ofseti) ve AST düğümleri de yoğun ve düzensiz biçimde kodlanmış; bu durumda düğüm başına yaklaşık 13 bayt. Bu minimal kodlamaya rağmen parse tree, kaynak dosya boyutunun neredeyse 2 katı oluyor. Yine de 2 kat, 50 kattan çok daha iyi. Kaynak: zig ast-check -t lib/std/zig/Parse.zig | head -n7
    • Bağlantı verilen sunumu doğrudan izlemek en iyisi. Harika bir sunum. Hatırladığım kadarıyla kesin sayılar vermemişti; muhtemelen o aşamada emin olmak için henüz erkendi. Henüz gerektiğini fark etmedikleri bazı veriler eksik olduğu için sayılar düşük çıkıyor olabilir

  • Bu problem alanı paketleme probleminin bir varyantı gibi geliyor
    Nihai sonuç olan, insanların işlemesi kolay yapıdan başlayıp bellek israfını azaltan, hizalama kurallarına uyan ve uzamsal yerelliği artıran veri yapısı önerileri üretebilsek güzel olurdu. https://en.wikipedia.org/wiki/Packing_problems

  • proc macro’ların derleyiciye bilgi sorabilecek şekilde gelişmesi iyi olurdu. Bunun için ek derleme aşamaları konusunda dikkatli bir tasarım gerekir, ama “bu struct şu trait’i uyguluyor mu”, “somut olarak uygulanmış tüm trait’lerin listesini ver” gibi şeyler proc macro içinde çoğu zaman çok kullanışlı olur

    • Yanlış hatırlamıyorsam derleyici eklentileri iki aşamada çalıştırıyor. İlk aşama tip denetiminden önce AST’yi alıyor ve AST’yi değiştirebiliyor; macro’lar ve bazı clippy lint’leri burada çalışıyor. İkinci aşama ise tip denetiminden sonra, bu yüzden tip bilgilerini alıyor ama değişiklik yapamıyor; diğer clippy lint’leri burada çalışıyor

  • Yazının yalnızca bir kısmını anladım, ama Rust ile spreadsheet motoru yazmak isteyen biri olarak çok ilgili görünüyor. Hücre değerleri için şöyle bir biçim gerekiyor
    pub enum Expr { Number(i32), String(String), Reference(Position), Binary(Box, char, Box), Function(String, Vec), }
    Okumaya ve çalışmaya devam edeceğim; başvurulacak kaynak varsa memnun olurum

    • Burada vurgulanan sorun, variant’ların boyutlarının çok farklı olması ve dizide bu değerlerden çok varsa padding yüzünden boşa giden alanın performansı düşürmesi
      Oyun tarafında sık kullanılan bir teknik, struct dizisini (AoS) dizilerin struct’ına (SoA) bölmektir. Örneğin struct Humans { healths: Vec, ammo: Vec, … } şeklinde tutarsanız, her vektörün i’inci indeksi AoS yerleşimindeki i’inci Human olur. Bu paralel vektörler yalnızca bir örnek; en iyi verimlilik bu değil, çünkü her alan için uzunluk ve kapasite kayıtları yinelenerek israf yaratır. Bu yazı temelde benzer fikri enum’lara otomatik olarak uygulamaya çalışıyor ve Rust’ta bunu aynen yapmak zor. Bu problemin pratikte ne kadar büyük olduğu biraz abartılmış da olabilir. Spreadsheet tarafında bunu şimdilik yalnızca olası bir optimizasyon olarak akılda tutmalı, önce hız için mi yoksa sadelik ve anlaşılabilirlik için mi geliştirdiğine karar vermelisin
    • Eğlenceli bir proje gibi. Genel kullanıcıları hedefliyorsan kullanıcıların sayfanın dört en uç köşesine içerik koyup motorun çöküp çökmediğini kontrol edeceğini varsaymalısın
      1 milyon × 1 milyon hücreye izin verip doldurulmamış tüm hücrelerde null saklarsan bellek tükenir. Bu yüzden hücre içeriklerini seyrek saklama yöntemini düşünebilirsin. Bir yöntem, hashbrown gibi bir hash map implementasyonu kullanmak. Bu yazının noktası düşük seviye ayrıntılar; en baştan hash map ile başlayıp başlangıçtaki bellek kısıtlarını aşarsan şimdilik bunu derinlemesine düşünmene gerek yok
    • Gerçekten Rust ile bir spreadsheet motoru yapmıştım. Açık kaynak değil, ama birkaç tavsiye verebilirim. Bu yazıdaki yöntemden fayda görmeden önce birçok performans problemiyle karşılaşacaksın
      En zor tekil problem değerlendirme stratejisi

  • https://doc.rust-lang.org/reference/type-layout.html#the-alignment-modifiers nasıl olur

  • Örnek kodda bir bug var gibi
    field_map[idx] = svec.len - 1;
    svec zaten son entry olmayan bir yerde size içeriyorsa yanlış olur