Array enum yang efisien memori di Zig

 (alic.dev)
3 poin oleh GN⁺ 2023-09-19 | 1 komentar | Bagikan ke WhatsApp
  • Menyimpan enum/tagged union dalam jumlah besar dengan variant berukuran berbeda menyebabkan biaya padding dan fragmentasi membesar di Vec·HashMap, karena ruang harus dicadangkan berdasarkan variant terbesar
  • Zig dapat memeriksa ukuran field, alignment, dan discriminant melalui comptime dan refleksi tipe, lalu mengubah kontainer enum secara generik berdasarkan tata letak memori
  • Vec<Enum> biasa membuat setiap elemen memakai ruang sebesar variant maksimum, dan SoA mengurangi padding tag tetapi masih menyisakan fragmentasi variant pada area nilai
  • Dense AoVA yang mengelompokkan variant dengan ukuran sama, pada enum contoh, mengurangi 15 vektor menjadi 3 klaster 2·4·8 byte, tetapi jika beberapa variant bercampur dalam allocation yang sama, iterasi yang type-safe menjadi sulit
  • Proc macro Rust sulit mengakses informasi ukuran dan alignment tipe, serta terbatas dalam menghitung panjang array generik, sehingga staging yang sadar tipe di Zig lebih jelas menunjukkan komposabilitas efisiensi memori untuk kode sistem

Array enum Rust membuang banyak ruang

  • Enum/tagged union dengan variant berukuran berbeda harus mencadangkan memori yang cukup untuk menampung variant terbesar
  • Enum contoh Foo memiliki variant u8, u16, u32, u64, dan karena tag serta alignment, ukuran tipenya menjadi 16 byte
  • Jika enum seperti ini banyak dimasukkan ke Vec atau HashMap, setiap elemen akan memakai ruang berdasarkan variant terbesar sehingga padding dan fragmentasi membesar
  • Transformasi struct of arrays(SoA) yang menaruh tag pada allocation terpisah dapat mengurangi sebagian padding, tetapi tidak menghilangkan fragmentasi pada area nilai yang muncul dari perbedaan ukuran variant
  • Di Rust juga memungkinkan membuat struktur data khusus untuk enum tertentu secara manual, tetapi membuat struktur data generik yang semaksimal mungkin efisien memori untuk enum arbitrer itu sulit, atau nyaris mustahil dalam praktik
    • Proc macro sulit menambahkan #[derive] ke tipe pihak ketiga atau type alias, dan komposabilitasnya rendah
    • Tidak ada kesadaran tipe, dan solusi berbasis generic_const_expr menyebarkan klausa where yang verbose ke seluruh call graph serta tidak cocok dengan generic type parameter

Mengapa masalah ini menonjol pada AST compiler

  • Salah satu motivasi besar untuk array enum yang efisien adalah penggunaan memori pada AST compiler
  • AST yang besar menimbulkan latensi memori dan cache eviction selama kompilasi, sehingga memberi biaya besar pada performa frontend
  • Dalam video compiler Carbon oleh Chandler Carruth, disebutkan bahwa AST clang hasil parsing sering mengonsumsi memori hingga 50 kali lebih besar daripada source code aslinya
  • Contoh representasi node ekspresi di Rust disusun sebagai enum Expr
    • Unit
    • Number
    • Binary(Operation, ExprId, ExprId)
    • Ident(Symbol)
    • Eval(ExprId, ExprSlice)
    • BlockExpression(ExprId, StatementSlice)
  • OCaml dapat merepresentasikan tipe data rekursif tanpa indirection eksplisit karena runtime system dan GC menangani manajemen memori
  • Di Rust, Vec<Expr> membuat semua elemen memakai ruang sebesar sizeof(Enum), termasuk ukuran variant terbesar, tag, dan padding

Mengurangi fragmentasi dengan SoA dan AoVA

  • Ketika enum 3-variant sederhana memiliki anggota berukuran 8, 16, dan 32 bit, Vec biasa mencadangkan ruang besar untuk semua elemen agar sesuai dengan variant 32 bit dan syarat alignment
  • Perbaikan yang umum adalah memakai tagged index dan sejenisnya agar enum variant itu sendiri tetap kecil
    • crate tagged_index milik Rust compiler
    • contoh small-string optimization
    • Ini adalah optimasi yang sering dipakai di kode berperforma tinggi seperti runtime bahasa, GC, compiler, game engine, dan kernel OS
  • Kita juga bisa mengubah kontainer ke pendekatan SoA yang menyimpan discriminant dan nilai di allocation terpisah
    • Compiler Zig self-hosted memakai pendekatan ini
    • Padding akibat tag berkurang, tetapi collection nilai union masih menyisakan fragmentasi variant
  • Kompilasi bertahap Zig memungkinkan pembuatan kontainer generik yang melakukan transformasi SoA untuk tipe arbitrer
  • Rust harus bergantung pada proc macro seperti soa_derive, dengan keterbatasan bahwa #[derive] tidak bisa ditambahkan tanpa mengubah source type pihak ketiga

Array per variant dan pengelompokan per ukuran

  • Untuk lebih mengurangi fragmentasi pada area nilai, bisa digunakan satu vektor per variant
  • Saat insert, struktur akan mengembalikan tagged index yang memuat tag enum dan index di dalam array variant terkait
  • Pola ini disebut array of variant arrays(AoVA)
  • AoVA dapat diimplementasikan dengan proc macro di Rust, dan dengan comptime di Zig
  • Jika variant sangat banyak dan beberapa variant memiliki ukuran sama, pendekatan satu vektor per variant dapat menambah jumlah vektor secara berlebihan
    • Enum contoh Foo memiliki 15 variant
    • Pendekatan vektor per variant menambah 15 vektor
    • Reallocation dan jumlah system call bisa meningkat, dan mungkin memerlukan memori lebih banyak untuk amortization dibanding Vec naif
    • Vektor-vektor dapat tersebar acak di memori sehingga peluang cache conflict meningkat
    • Kontainer AoVA itu sendiri juga dapat memakai banyak memori dan membengkakkan struct yang memuatnya
  • Jika dikelompokkan berdasarkan ukuran, enum contoh terbagi menjadi tiga klaster: 2 byte, 4 byte, 8 byte
    • c_2: Vec<[u8; 2]> menyimpan A hingga D
    • c_4: Vec<[u8; 4]> menyimpan E hingga I
    • c_8: Vec<[u8; 8]> menyimpan J hingga O
  • Pendekatan dense AoVA dapat mengurangi jumlah total vektor hingga 80%
  • Jika variant berbeda ditempatkan bersama dalam allocation yang sama, vektor menjadi sulit diiterasi secara type-safe
    • Akses hanya bisa dilakukan melalui tagged pointer yang dibuat saat insert
    • Untuk struktur tree berbasis flattened index yang tidak memerlukan blind iteration, ini bisa menjadi trade-off yang dapat diterima
  • Jika iterasi type-safe diperlukan, tag bisa dimasukkan lagi dengan menerima biaya padding
  • Jika padding terlalu besar, transformasi SoA bisa diterapkan pada tiap array variant, tetapi jumlah vektor menjadi dua kali lipat

Komposabilitas tata letak memori yang dihasilkan comptime Zig

  • Prototipe Zig diimplementasikan di osmium
  • Intinya adalah refleksi waktu kompilasi yang memeriksa tipe field, ukuran byte, ukuran bit, dan discriminant melalui built-in compiler
  • Kode contoh memeriksa jenis tipe dengan @typeInfo(inner) dan hanya memproses jika tipenya union
    • Mengiterasi field union
    • Menghitung ruang yang dibutuhkan dengan @max(field.alignment, @sizeOf(field.type))
    • Menyimpan informasi ukuran ke vektor yang dialokasikan di stack
    • Membangun mapping dari field union ke index klaster
    • Jika bukan union, menghasilkan compile error
  • Potongan kode lengkap ada di source terkait
  • Membuat contoh yang sama dengan proc macro Rust pada dasarnya tidak mungkin
    • Proc macro tidak bisa mengakses informasi size atau alignment dari tipe
    • Meski bisa menghasilkan const fn untuk menghitung klaster bagi enum tertentu, hasilnya tidak bisa dipakai untuk menentukan panjang array dari tipe generik
  • Implementasi generic container di Rust sulit berubah secara kondisional berdasarkan apakah tipe yang diberikan adalah enum atau struct
  • Di Zig, secara konseptual dimungkinkan memilih EfficientEnumArray<T> atau EfficientStructArray<T> berdasarkan T.isEnum()
  • Implementasi AoVA juga bisa dipilih sesuai karakteristik enum
    • Misalnya, spesialisasi dapat dibuat hanya jika manfaat menempatkan variant berbeda bersama-sama mengurangi jumlah vektor lebih dari 90%
  • Jika kapasitas maksimum diketahui saat kompilasi, fungsi pembentuk tipe dapat menentukan bitwidth yang dibutuhkan oleh tagged index
  • Jika tagged index ini dimasukkan ke struktur data lain, misalnya ke enum lain, bit yang tersisa bisa dimanfaatkan untuk discriminant
  • Zig memungkinkan penentuan jumlah bit yang dibutuhkan secara spesifik, sehingga bagian lain dari kode dapat memanfaatkan informasi itu secara alami untuk menghasilkan efisiensi memori yang komposabel
  • Berkat implicit widening integer coercion, kemudahan penggunaan tetap terjaga bahkan saat berhadapan dengan API dengan bitwidth berbeda
  • Untuk bahasa pemrograman sistem yang menekankan efisiensi dan zero-cost abstraction, staged programming, khususnya comptime milik Zig, layak dilihat kembali

Bacaan terkait

1 komentar

 
GN⁺ 2023-09-19
Komentar Hacker News

  • Ada strategi lain yang efisien dalam penyimpanan dan tetap mempertahankan iterasi elemen. Vektor pertama adalah daftar tag, vektor kedua adalah offset byte untuk tiap elemen, dan yang ketiga, lebih tepatnya bukan vektor, berisi data variant terkompresi yang ditunjuk oleh vektor kedua
    Dengan begitu jumlah vektornya setengah dari solusi akhir penulis (6 vs 3), tidak membuang byte padding kecuali jika diperlukan karena alignment, dan terlepas dari tipenya, data tersusun berurutan di memori sehingga bisa diiterasi secara ramah cache. Akses O(1) ke elemen berdasarkan indeks juga memungkinkan. Secara keseluruhan, untuk data heterogen, karakteristik performanya mirip Vec

    • Menyimpan offset byte secara inline adalah ide bagus. Namun, jika offset disimpan di memori, proses iterasi akan menimbulkan dependensi data, sehingga meskipun ramah cache, ini bisa menyebabkan stall memori yang serius pada pipeline prosesor
    • Jika koleksi seperti ini perlu diubah, pada akhirnya kemungkinan besar Anda akan memakai allocator memori sendiri untuk menangani penghapusan, perubahan ke variant yang lebih besar, dan fragmentasi
    • Jika ukuran offset tidak dioptimalkan, ruang yang dipakai bisa cukup besar dibandingkan T yang kecil. Misalnya kombinasi size_t 64-bit dan uint8_t T; selama berhati-hati dengan ukuran offset, ini tampak sebagai pendekatan yang masuk akal

  • Saya penasaran bagaimana struktur data AoVA ini sebenarnya bekerja. Dari sudut pandang array, bukankah kita kehilangan akses berbasis indeks, karena aritmetika indeks mungkin tidak lagi bermakna? Iterasi juga tampaknya tidak akan mempertahankan urutan penyisipan
    Dalam konteks ini, saya rasa TLV(tag-length-value) yang punya karakteristik caching lebih baik lebih umum dipakai. Panjang bisa saja diimplikasikan oleh tag, dan setidaknya menyediakan iterasi maju yang bermakna. Lihat getdents, inotify, dan messaging Netlink

    • Melihat caption Gambar 4, pola AoVA sepertinya harus dianggap kurang cocok jika perlu mempertahankan urutan total elemen yang disisipkan
      Dibandingkan layout SoA sebelumnya, yang muncul adalah urutan parsial, bukan urutan total. Saat penyisipan, strukturnya mengembalikan indeks bertag yang memuat tag enum dan indeks di dalam array variant terkait. Jadi akses terurut tampaknya dianggap di luar cakupan di sini. Jika indeks global disimpan pada tiap elemen, iterasi terurut bisa dipulihkan, tetapi itu tetap tidak membantu untuk akses acak terurut, dan kemungkinan akan menjadi kode dengan cukup banyak branching
    • “Tag enum dan indeks di dalam array variant terkait” yang dikembalikan saat penyisipan pada dasarnya adalah pointer. Jika ingin melakukan iterasi, simpan pointer dalam sebuah array sesuai urutan penggunaan yang diinginkan. Itu sama seperti yang dilakukan program yang mengalokasikan memori di heap
      Cara menyimpan objek berdasarkan ukuran juga digunakan pada garbage collector dan allocator serbaguna. Efisiensi bisa diperoleh karena semua ukuran objek yang mungkin sudah diketahui, atau dari cara pembebasan yang lebih sederhana seperti arena
    • Fakta bahwa AoVA tidak memiliki urutan total sendiri atas indeks bisa menjadi masalah untuk sebagian kasus penggunaan, tetapi untuk node AST yang diusulkan di sini, itu belum tentu masalah
      Dalam kasus seperti ini, array-array tersebut bisa dilihat sebagai salah satu komponen struktur mirip heap, yaitu seperti arena. Biayanya adalah indeks harus menjadi dua dimensi seperti (tag_idx, va_for_tag_idx). Namun karena jumlah tag diketahui saat compile time, penyimpanan bisa dioptimalkan dengan mem-packing tag_idx ke 4~5 bit atas dan membiarkan va_for_tag_idx memakai sisanya. Referensi: https://www.cs.cornell.edu/~asampson/blog/flattening.html
    • Penulisan array yang mengubah tipe indeks sepertinya akan sangat mahal

  • Agak disayangkan bahwa pattern matching di Rust tidak bisa diekspresikan lebih sebagai trait dalam type system yang bisa diikuti oleh struct sembarang, alih-alih sebagai tipe objek hardcoded eksplisit kelas satu dengan struktur penyimpanannya sendiri
    Belakangan ini saya juga mengimplementasikan AST seperti di tulisan ini dan interpreter opcode/bytecode, dan merasa enum Rust tidak sepenuhnya ideal untuk keduanya. Pada AST, saya ingin menambahkan atribut nomor baris/kolom ke semua node statement, tetapi jika baris/kolom dimasukkan ke semua case di enum Stmt, boilerplate-nya jadi berantakan; sementara jika enum dibungkus ke struct Stmt baru yang memuat enum asli plus atribut baris/kolom, refaktornya banyak dan tidak elegan. Di sisi opcode juga, enum Rust yang bisa di-pattern match sulit disebut encoding ideal untuk performa interpreter opcode VM, tetapi bahasa ini mendorong ke arah tersebut dan fitur pola destructuring sangat menarik. Tampaknya ada ruang untuk peningkatan type system agar kita bisa memakai implementasi low-level yang diinginkan sambil tetap mendapatkan fitur pattern matching

    • Akan bagus jika ada contoh yang lebih konkret. Yang pertama terpikir adalah semacam structural type system, tetapi saya tidak yakin apakah pemahaman itu tepat
      https://en.wikipedia.org/wiki/Structural_type_system
    • Teknik lama pada interpreter bytecode adalah memakai indirect jump saat berpindah ke implementasi opcode berikutnya. gcc punya ekstensi computed goto untuk ini, dan di Rust sepertinya perlu sesuatu yang memaksa function pointer dan optimisasi tail call
      Jika indirect jump seperti ini diletakkan di bagian awal implementasi tiap opcode, prediktor indirect jump yang dimiliki CPU karena OOP bisa memiliki model terpisah untuk bagian akhir opcode yang berbeda, sehingga tingkat prediksinya meningkat. Instruksi berikutnya sendiri mungkin sulit diprediksi, tetapi misalnya kemungkinan branch muncul setelah test bisa jauh lebih tinggi. Namun teknik lain, seperti menyimpan puncak stack di register pada stack machine, tampaknya lebih penting, dan saya tidak yakin apakah teknik di atas masih relevan sekarang
    • Beberapa bahasa punya fitur yang mirip dengan yang diinginkan. Lihat extractor di Scala atau active view di F#

  • Pernyataan bahwa “AST clang yang sudah diparse secara rutin memakan memori 50 kali lebih besar daripada kode sumber aslinya” memang terdengar cukup besar, tetapi konteks yang hilang adalah seberapa jauh ini bisa diperbaiki. Jika harus mempertahankan posisi sumber tiap token dan mengodekan informasi yang cukup agar bisa dipulihkan dengan benar dari AST, saya penasaran apakah kenaikan ideal dibanding sumber aslinya itu 1,5 kali atau 15 kali

    • Misalnya, jika penghematan memori 30% memungkinkan, itu kabar yang cukup besar. Namun jika itu membuat compiler lebih sulit dipelihara ke depannya dan hanya mengurangi 30%, nilainya mungkin tidak sepadan. Sebaliknya, jika dengan memperlakukan compiler sedikit lebih kasar bisa mendapat penghematan 80%, itu layak dicoba
      Sulit mengatakan berapa rasio pembengkakan source→AST yang ideal untuk bahasa yang ramah pengguna sekaligus ramah bagi pengembang compiler, tetapi 50 kali pun masih berfungsi. Tulisan aslinya memakai pembengkakan 50 kali sebagai motivasi untuk mengotomatiskan optimasi tertentu. Akan menarik jika vector enum di Rust bisa otomatis memecah nilai enum menjadi tag dan nilai buram, lalu menyimpannya dalam bentuk structure of arrays seperti yang dilakukan tulisan asli di Zig. Tampaknya juga tidak banyak tempat untuk menyembunyikan penggunaan unsafe
    • Sebagai pembanding, simdjson tape hanya sekitar 3 kali lebih besar daripada dokumen aslinya. Sebagian besar dari ini bisa dikurangi dengan memasukkan angka hanya ke satu slot tape, atau dengan tidak menyalin string tanpa escape sequence dan cukup merujuk ke posisi di dokumen asli
      Pada dokumen yang sebagian besar terdiri dari karakter [] atau karakter 0,, overhead maksimumnya tampak sekitar 8 kali
    • Kode sumber itu luar biasa padat. Sebagai satu data tentang sejauh mana ini bisa diperbaiki, ada hasil ketika parser Zig sendiri mem-parse parser Zig sendiri
      Byte sumber: 139 KiB, token: 24646 buah (120 KiB), node AST: 10998 buah (140 KiB). Tiap token sangat diminimalkan pada 5 byte (tag 1 byte + offset file 4 byte), dan node AST juga dikodekan secara padat serta tidak seragam, dalam kasus ini sekitar 13 byte per node. Bahkan dengan encoding minimal seperti ini, parse tree menjadi hampir 2 kali ukuran file sumber. Tetap saja, 2 kali jauh lebih baik daripada 50 kali. Sumber: zig ast-check -t lib/std/zig/Parse.zig | head -n7
    • Sebaiknya tonton saja presentasi yang ditautkan. Presentasinya bagus. Seingat saya angka persisnya tidak diberikan, dan mungkin saat itu masih terlalu awal untuk merasa yakin. Bisa saja angkanya keluar kecil karena ada data yang belum disadari perlu dimasukkan

  • Ruang masalah ini terasa seperti varian dari packing problem
    Akan bagus jika kita bisa mulai dari struktur akhir yang mudah ditangani manusia, lalu menghasilkan rekomendasi struktur data yang mengurangi pemborosan memori, mematuhi aturan alignment, dan meningkatkan locality ruang. https://en.wikipedia.org/wiki/Packing_problems

  • Akan bagus jika proc macro berkembang sehingga bisa menanyakan informasi ke compiler. Untuk itu perlu desain yang hati-hati terkait penambahan tahap kompilasi, tetapi hal seperti “apakah struct ini mengimplementasikan trait ini” atau “berikan daftar semua trait yang diimplementasikan secara konkret” sering kali sangat berguna dalam proc macro

    • Jika ingatan saya benar, compiler menjalankan plugin dalam dua tahap. Tahap pertama menerima AST sebelum type checking dan dapat memodifikasi AST; macro dan sebagian lint clippy berjalan di sini. Tahap kedua terjadi setelah type checking, sehingga menerima informasi tipe tetapi tidak bisa memodifikasi, dan lint clippy lainnya berjalan di sini

  • Saya hanya memahami sebagian tulisannya, tetapi dari sudut pandang orang yang ingin menulis spreadsheet engine dengan Rust, ini terlihat sangat relevan. Nilai sel memerlukan bentuk seperti ini
    pub enum Expr { Number(i32), String(String), Reference(Position), Binary(Box, char, Box), Function(String, Vec), }
    Saya akan terus membaca dan mempelajarinya, dan kalau ada referensi yang bisa dipakai, saya akan senang menerimanya

    • Masalah yang ditekankan di sini adalah ukuran variant sangat berbeda, dan jika ada banyak nilai seperti ini dalam array, performa memburuk karena ruang yang terbuang untuk padding
      Teknik umum dari dunia game adalah memecah array of structs (AoS) menjadi structure of arrays (SoA). Misalnya, dengan struct Humans { healths: Vec, ammo: Vec, … }, indeks ke-i dari setiap vector menjadi Human ke-i pada layout AoS. Vector paralel seperti ini hanya contoh dan bukan efisiensi optimal, karena pembukuan panjang dan kapasitas terduplikasi di setiap field sehingga boros. Tulisan ini pada dasarnya mencoba menerapkan ide serupa secara otomatis untuk enum, dan di Rust ini sulit dilakukan begitu saja. Seberapa besar masalah ini dalam praktik mungkin agak dilebih-lebihkan. Untuk spreadsheet, sebaiknya simpan dulu sebagai optimasi yang mungkin, dan tentukan terlebih dahulu apakah Anda membuatnya demi kecepatan atau demi kesederhanaan serta kemudahan dipahami
    • Kelihatannya proyek yang menarik. Jika ditujukan untuk pengguna umum, Anda harus berasumsi bahwa pengguna akan mengisi empat sudut ekstrem sheet dan memeriksa apakah engine tumbang
      Jika mengizinkan 1 juta × 1 juta sel dan menyimpan null di semua sel yang belum terisi, memori akan habis. Jadi Anda bisa mempertimbangkan cara menyimpan isi sel secara sparse. Salah satu caranya adalah memakai implementasi hash map seperti hashbrown. Poin tulisan ini adalah detail level rendah, jadi jika dari awal memakai hash map untuk menghindari batasan memori awal, Anda tidak perlu memikirkannya terlalu dalam untuk saat ini
    • Saya pernah benar-benar membuat spreadsheet engine dengan Rust. Kodenya bukan open source, tetapi saya bisa memberi beberapa saran. Sebelum mendapat keuntungan dari metode dalam tulisan ini, Anda akan lebih dulu menemui banyak masalah performa lain
      Masalah tunggal yang paling sulit adalah strategi evaluasi

  • Bagaimana dengan https://doc.rust-lang.org/reference/type-layout.html#the-alignment-modifiers

  • Sepertinya ada bug di kode contoh
    field_map[idx] = svec.len - 1;
    Itu akan salah jika svec sudah memuat size di posisi yang bukan entri terakhir