AST dan perataan struktur data kompiler

 (cs.cornell.edu)
3 poin oleh GN⁺ 2023-07-04 | 1 komentar | Bagikan ke WhatsApp
  • Jika AST tidak disimpan sebagai graf objek yang terhubung dengan pointer, melainkan direpresentasikan dengan satu array dan indeks, tata letak memori dan cara pengelolaan struktur data ala kompiler menjadi lebih sederhana
  • Contoh Rust mengimplementasikan AST yang diratakan hanya dengan perubahan kecil: mengganti Box<Expr> menjadi ExprRef dan menambahkan add/get ke ExprPool
  • Dalam microbenchmark yang membuat sekitar 100 juta node AST lalu langsung menginterpretasikannya, implementasi biasa memakan 3,1 detik, sedangkan implementasi yang diratakan 1,3 detik, sehingga 2,4× lebih cepat
  • Perbedaan performa berasal dari lokalitas karena tata letak memori yang berurutan, referensi yang lebih kecil karena memakai indeks 32-bit alih-alih pointer 64-bit, alokasi yang murah, dan dealokasi per pool
  • Jika memanfaatkan sifat bahwa dalam array anak berada lebih dulu daripada induk, traversal pohon rekursif dapat berubah menjadi eksekusi linear, yang bentuknya mendekati interpreter bytecode

Ide dasar perataan

  • Arena atau region digunakan luas dalam implementasi bahasa modern, dan pendekatan yang dibahas di sini adalah perataan struktur data yang memakai arena berisi satu tipe saja seperti array sederhana
  • Ini adalah teknik mengganti pointer dalam struktur data yang penuh pointer menjadi indeks array; contoh utamanya AST, tetapi bisa diterapkan juga ke struktur data kompiler lain
  • Kode contohnya ada di repositori flatcalc, dan perbedaan antara implementasi biasa dan implementasi yang diratakan bisa dilihat pada perbandingan branch
  • Perubahan kodenya kecil, tetapi pada microbenchmark terlihat peningkatan kecepatan 2,4×, dan selain performa juga ada kelebihan dari sisi kemudahan penggunaan kode

Representasi AST yang umum

  • Bahasa contoh adalah bahasa ekspresi aritmetika yang sangat sederhana dan hanya mendukung literal bilangan bulat serta empat operator aritmetika biner
    • Contoh program yang mungkin adalah 42, 0 + 14 * 3, (100 - 16) / 2
  • Representasi Rust terdiri dari enum BinOp dan Expr
    • Expr::Binary(BinOp, Box<Expr>, Box<Expr>)
    • Expr::Literal(i64)
  • Box<Expr> di Rust setara dengan pointer yang menunjuk ke Expr, dan berperan mirip dengan Expr* di C
  • Parser, formatter output, dan interpreter memiliki struktur yang khas, dan interpreter ditulis sebagai metode rekursif pada Expr
  • Semantik aritmetikanya disusun agar semua ekspresi pada akhirnya dievaluasi menjadi i64
    • Penjumlahan, pengurangan, dan perkalian memakai operasi wrapping
    • Pembagian dengan 0 diproses dengan checked_div agar mengembalikan 0
  • Generator program acak dengan seed PRNG tetap dipakai untuk mengukur performa manipulasi AST tanpa biaya parsing dan formatting output

Mengubah AST menjadi array dan indeks

  • Perataan terdiri dari dua perubahan
    • Objek Expr tidak lagi dialokasikan satu per satu di heap, melainkan disimpan dalam satu array berurutan
    • Node anak direferensikan dengan indeks di dalam array, bukan pointer
  • Dalam contoh Rust, ExprPool didefinisikan sebagai newtype dari Vec<Expr>
struct ExprPool(Vec<Expr>);
  • Peran pointer sebelumnya digantikan oleh ExprRef berbasis bilangan bulat 32-bit
struct ExprRef(u32);
  • Perubahan tipe inti adalah mengganti field anak pada Binary dari Box<Expr> menjadi ExprRef
enum Expr {
    Binary(BinOp, ExprRef, ExprRef),
    Literal(i64),
}
  • ExprPool diberi utilitas add untuk memasukkan Expr baru dan get untuk mencari Expr dari ExprRef
  • Parser tidak lagi mengembalikan Expr secara langsung, melainkan menambahkan node ke ExprPool lalu mengembalikan ExprRef
  • Interpreter juga menjadi metode pada ExprPool, bukan metode Expr, dan sebelum pattern matching ia melakukan dereferensi referensi dengan self.get(expr)
  • Secara keseluruhan, perubahan yang dibutuhkan kecil: cukup mengganti Box<Expr> dengan ExprRef dan menambahkan add serta get di titik yang perlu

Keunggulan performa

  • Kelebihan utama AST yang diratakan adalah lokalitas memori
    • Expr biasa yang berbasis pointer berisiko mengalami fragmentasi memori
    • Expr yang diratakan tersusun rapat dalam area memori berurutan sehingga cache data dan prefetcher dapat bekerja lebih baik
    • Allocator memori yang cukup pintar mungkin bisa memberi efek serupa, tetapi memakai array padat mengurangi ketidakpastian
  • Ukuran referensi juga mengecil
    • Pointer biasa pada arsitektur modern berukuran 64-bit
    • Jika node AST yang dibutuhkan tidak lebih dari 4.294.967.295, referensi 32-bit sudah cukup
    • Ada penghematan ruang 50% per referensi, dan pada AST yang kaya pointer ini bisa menurunkan penggunaan memori total
    • Jika struktur datanya lebih kecil, referensi 16-bit atau 8-bit juga memungkinkan
  • Biaya alokasi menjadi lebih rendah
    • Tidak perlu memanggil malloc untuk setiap node
    • Jika memori yang cukup sudah dicadangkan sebelumnya, ruang untuk Expr baru bisa dibuat dengan bump allocation yang hanya menaikkan tail pointer
  • Dealokasi bisa diproses per pool
    • Ini berasumsi bahwa Expr individual tidak dibebaskan satu per satu
    • Dalam banyak implementasi bahasa, AST cenderung dibuat bersama dan hilang bersama
    • AST biasa harus membebaskan setiap node dengan mengikuti pointer, sedangkan AST yang diratakan cukup membebaskan seluruh ExprPool sekaligus
  • Dalam pengantar arena allocation, dealokasi murah sering ditekankan sebagai alasan utama, tetapi dalam konteks kompiler AST bisa hidup sampai kompilasi selesai sehingga dealokasi justru mungkin alasan yang paling tidak penting

Keunggulan dari sisi kemudahan penggunaan kode

  • Perataan menyederhanakan pengelolaan lifetime
    • AST dengan n node bisa dipandang memiliki satu lifetime AST, bukan n lifetime yang berbeda
    • Di Rust, penyederhanaan ini juga langsung memengaruhi cara lifetime diekspresikan dalam kode
    • Alih-alih mengelola lifetime dari &Expr, kita bisa meneruskan ExprRef yang berupa u32 dan bergantung pada lifetime ExprPool
  • Kesederhanaan yang sama juga bisa diterapkan di bahasa dengan pengelolaan memori manual seperti C++
  • Array yang diratakan memudahkan implementasi deduplikasi
    • Kita bisa memakai hash consing atau cara yang lebih sederhana untuk menghindari pembuatan ekspresi yang identik
    • Misalnya, ekspresi Literal yang sering dipakai dari 0 sampai 127 bisa dipesan pada 128 slot pertama ExprPool
    • Saat membutuhkan literal bilangan bulat 42, kita tidak perlu membuat Expr baru dan cukup mengembalikan ExprRef(42)
  • Pada representasi berbasis pointer, hal serupa juga mungkin dilakukan, tetapi kemungkinan memerlukan struktur data tambahan

Hasil microbenchmark

  • Benchmark membuat program acak dengan sekitar 100 juta node AST lalu langsung memasukkannya ke interpreter
    • Parser dan formatter output tidak disertakan
    • Karena satu program dibuat lalu langsung dijalankan, ini bukan benchmark yang realistis
  • Ada beberapa keterbatasan dalam kondisi eksperimen
    • Ruang yang cukup untuk seluruh program dipesan lebih dulu pada Vec<Expr>
    • Di lingkungan nyata, perkiraan ukuran arena akan lebih dibutuhkan
    • Hampir tidak ada pekerjaan selain pembuatan dan eksekusi, sehingga keunggulan alokasi/dealokasi murah bisa terlihat berlebihan
    • Programnya sangat besar sehingga proporsi yang muat di cache CPU kecil, sehingga efek lokalitas bisa jadi justru terukur lebih rendah dari seharusnya
  • Rata-rata 10 kali eksekusi di laptop dibandingkan dengan Hyperfine
    • Lingkungannya adalah M1 Max 10-core 3.2GHz, memori 32GB, macOS 13.3.1, Rust 1.69.0
  • Implementasi biasa memakan 3,1 detik, sedangkan implementasi yang diratakan 1,3 detik, menunjukkan peningkatan kecepatan 2,4×
  • Untuk melihat biaya dealokasi secara terpisah, dibuat versi yang melewati deallocation pada kedua implementasi
    • Pada implementasi yang diratakan, waktu antara versi no-free dan versi standar hampir sama, sehingga waktu dealokasi tidak besar
    • Pada implementasi biasa, waktunya turun dari 3,1 detik menjadi 1,9 detik, artinya sekitar 38% waktu dipakai untuk membebaskan memori
    • Bahkan saat membandingkan sesama versi no-free, implementasi yang diratakan tetap 1,5× lebih cepat daripada implementasi biasa

Interpreter yang langsung memanfaatkan representasi rata

  • Pada awalnya, perataan dipakai seperti perubahan implementasi internal untuk menggantikan alokasi biasa dan pointer, tetapi sifat representasi array ini juga bisa dimanfaatkan secara langsung
  • Jika Expr bersifat immutable, node anak harus dibuat lebih dulu dan node induk dibuat belakangan
    • Saat membuat a * b, a dan b berada lebih dulu di ExprPool daripada * yang merujuk ke keduanya
    • Panah referensi dalam array selalu mengarah dari belakang ke depan, dan aliran data bergerak maju
  • Dengan memanfaatkan invariant ini, kita bisa membuat interpreter yang memindai ExprPool dari awal sampai akhir alih-alih turun secara rekursif dari root
    • Traversal selalu mengunjungi anak lebih dulu daripada induk
    • Hasil setiap ekspresi disimpan di vektor state
    • Untuk ekspresi biner, nilai diambil dengan melihat state memakai indeks ExprRef anak
    • Pada akhirnya, hasil yang sesuai dengan root yang diminta dikembalikan
  • Interpreter “extra-flat” ini tidak memiliki overhead pengelolaan stack dari pemanggilan rekursif dan dapat menelusuri ExprPool secara linear
  • Sebaliknya, ia harus melakukan akses acak ke vektor state yang besar sehingga bisa kurang baik untuk lokalitas
  • Hasilnya, interpreter extra-flat mencatat 1,2 detik, sedangkan interpreter rekursif berbasis perataan 1,3 detik, atau peningkatan 8,2%

Keterkaitan dengan interpreter bytecode

  • Komentar Bob Nystrom di Reddit melihat bahwa pendekatan ini pada dasarnya menciptakan ulang gagasan interpreter bytecode
  • Struktur Expr bertindak seperti instruksi bytecode, dan referensi variabel dimasukkan seperti referensi yang dikodekan dalam u32
  • Jika tabel state yang sederhana diubah menjadi struktur seperti stack, hasilnya nyaris tidak berbeda dari interpreter bytecode yang memang dirancang sejak awal
  • Hanya dengan mengubah struktur data AST, pendekatan ini berpindah secara alami dari traversal pohon ke gaya bytecode

Materi terkait

Bacaan terkait

1 komentar

 
GN⁺ 2023-07-04
Komentar Hacker News

  • Blender (perangkat lunak pemodelan 3D) adalah contoh menarik dari pendekatan ini. Untuk membuat pemuatan/penyimpanan file cepat dan lossless, Blender menggunakan representasi di disk dan representasi di memori yang sama
    Artinya, semua hal berada di dalam arena, dan simpan/muat kurang lebih setara dengan melakukan memcpy pada seluruh arena. Jika mempertimbangkan potensi kompleksitas proyek Blender serta masalah serialisasi/deserialisasi, ini terlihat seperti desain yang sangat bagus
    Kekurangannya adalah karena file versi lama juga harus bisa dibuka, desain struktur data jadi mudah membeku

    • Bagian yang hilang dari “desain struktur data membeku karena file versi lama harus bisa dibuka” adalah cara membiarkan struktur data berevolusi seiring waktu, seperti migrasi database
      Transformasi semacam ini hanya dijalankan saat memuat data dari versi aplikasi lama, lalu setelah itu langsung disimpan ke disk dalam versi yang sudah diperbarui sehingga biaya yang sama tidak perlu dibayar lagi
      https://www.inkandswitch.com/cambria/ yang dibuat dalam konteks CRDT adalah contoh implementasi konsep ini, dan meskipun tidak bisa diterapkan langsung, tetap bisa menjadi inspirasi yang bagus
    • Saya pernah bekerja pada aplikasi komersial besar berbasis framework I/O buatan sendiri yang bekerja dengan prinsip serupa, dan itu benar-benar menyakitkan
      Suka atau tidak suka pada framework I/O tersebut, karena struktur langsung diserialisasi apa adanya, kami selalu harus menyiapkan struktur data untuk masa depan sambil tahu bahwa kami akan terikat pada struktur itu selamanya. Itu masa yang suram
    • Seingat saya, Microsoft Word pada era “doc” lama juga menggunakan pendekatan membuang struktur langsung ke disk
      Karena itu, menulis konverter menjadi masalah besar, dan saya ingat orang harus menguraikan struktur data internal Word yang tidak terdokumentasi
    • Game PlayStation yang pernah saya kerjakan juga persis seperti ini, dan semuanya ditandatangani sehingga kami sama sekali tidak mengkhawatirkan penyerang
      Jika seseorang bisa mengubah file di disk, itu berarti mereka sudah menguasai perangkatnya. Hasilnya, loading menjadi sangat cepat, dan setelah semuanya dibaca ke memori, kami hanya menambal lokasi pointer ke alamat muat yang sebenarnya
    • Setahu saya, Microsoft Word juga awalnya memakai cara ini, dan ketika format file berevolusi, itu menjadi sumber penderitaan besar

  • Saya menyukai abstract syntax tree yang diratakan. Saya terutama menyukai pendekatan yang dipakai dalam pemrosesan markup inline di pulldown-cmark. Penjelasan sederhananya ada di https://fullyfaithful.eu/pulldown-cmark/
    Input mentah dipecah menjadi urutan node, dan hal seperti * bisa menjadi emphasis atau tetap menjadi teks jika tidak punya pasangan, sehingga dibuat sebagai node MaybeEmphasis
    Pada tahap berikutnya, sebuah stack digunakan untuk menelusuri node secara berurutan sambil mencari pasangan yang mungkin. Jika pasangan ditemukan, node MaybeEmphasis diubah menjadi node emphasis yang sesuai, dan seluruh urutan node di antara node pembuka dan penutup dipotong menjadi subtree dari node baru
    Transformasi tree ini cukup tidak biasa sehingga implementasi naif bisa dengan mudah menjadi O(n), tetapi dalam representasi AST yang diratakan, ini bisa diproses dalam O(1) terlepas dari jumlah node atau kedalaman stack
    Representasi tree yang lebih rinci ada di https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6..., yang pada dasarnya menyimpan indeks child dan next bersama isi node. Kode operasi tree saat pencocokan emphasis ada di https://github.com/raphlinus/pulldown-cmark/blob/b7e709c0bd6...
    Performanya sangat bagus. pulldown-cmark mungkin bukan parser CommonMark tunggal tercepat, tetapi cukup kompetitif, dan misalnya jauh lebih cepat daripada pendekatan yang melakukan alokasi per node

  • Jadi teringat presentasi GDC yang memuji Rust. Isinya bahwa Rust, karena borrow checker-nya, bisa membuat orang frustrasi, atau justru mendorong mereka menata kode dengan sistem entity-component
    Menariknya, dalam kasus nyata dengan masalah lifetime yang rumit, nilai borrow checker pada akhirnya terletak pada bagaimana ia membuat orang mencari cara untuk memasukkan semuanya ke dalam array dan mereferensikannya dengan indeks agar sebisa mungkin menghindari borrow checker

    • Dari sedikit pengalaman memakai engine game Bevy di Rust, entity-component system terasa seperti menulis spaghetti code yang sangat canggih
      Karena objek-objek tidak lagi saling mereferensikan secara langsung, kegunaan sistem tipe berkurang drastis, dan kode menjadi sangat sulit ditelusuri. Saya percaya ini bisa berguna pada sistem yang sangat besar, tetapi pada program kecil yang saya tulis, rasanya lebih seperti penghalang
    • Betul. Lifetime di Rust menjadi kurang kuat di ranah pemrograman performa tinggi tertentu yang menghindari heap atau bahkan tidak memiliki heap sama sekali
      Ini mencakup game, basis data, embedded, pekerjaan batch bergaya komputasi performa tinggi, bahkan compiler
      Tentu saja pembatasan aliasing tetap ada, jadi race condition data tidak akan muncul, tetapi bug yang pada dasarnya sama dengan bug dari pointer mentah tetap bisa terjadi
    • Dengan kata lain, ini memaksa entitas yang berumur panjang untuk memiliki memori, lalu meminjamkannya kepada objek yang berumur pendek
      Dalam proses itu, pihak yang meminjam selalu hidup lebih singkat daripada pemiliknya, dan selama masa kepemilikan hanya bisa mengakses memori yang memang dialokasikan. Saat pemilik mati, memorinya dibebaskan, dan setelah itu tidak seorang pun bisa memakainya atau membebaskannya lagi, sehingga use-after-free, double free, dan akses ke memori yang tidak dialokasikan bisa dihindari
    • Betul. Saya terus melihat orang menyebut arena atau struktur tree/graph yang di-flatten tanpa membahas keamanan memori
      Bahkan ada klaim aneh di C bahwa arena menyelesaikan masalah keamanan memori, padahal tergantung programnya justru tetap sama-sama bisa memicu dangling pointer atau use-after-free dan semacamnya
      Masalah yang sama muncul di C/C++ dan Rust dengan cara yang sedikit berbeda
      Komentar saya pada tulisan ini dua bulan lalu: https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
      Singkatnya, kelebihannya sangat nyata, tetapi kekurangannya juga harus dibicarakan. Arena menunda keamanan memori dan kepemilikannya bisa rumit, perubahan serta penambahan list/vector juga menjadi lebih kompleks, dan representasi pointer lebih ramah untuk debugger
      Di bagian bawah tulisan ini ada tautan ke halaman wiki saya, dan saya senang melihat ada kode nyata dan hasil pengukuran: https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
    • Pointer hanyalah indeks ke ruang memori. Jika Rust ingin menyelesaikan masalah pemrograman secara umum, borrow checker tampaknya harus bisa menangani semua indeks, bukan hanya indeks yang dikhususkan untuk ruang memori

  • Term Prolog juga direpresentasikan di heap dengan cara seperti ini dalam Warren Abstract Machine (WAM). Jika term Prolog +(*(a,b), c) ditulis dalam notasi operator seperti pada contoh di tulisan, hasilnya menjadi
    expr(E) :- E = a*b + c.
    Lalu representasi yang di-flatten dibuat di stack global mesin virtual. Di Scryer Prolog, instruksi WAM dapat dilihat dengan ?- wam_instructions(expr/1, Is), maplist(portray_clause, Is).
    Hasilnya akan terlihat seperti 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).
    Kedua term majemuk dilinearkan, sehingga di heap setiap functor diikuti argumennya, dan masing-masing tepat menempati satu sel memori WAM. Argumen-argumennya bisa menunjuk ke sel memori lain
    Heap adalah array dari sel-sel seperti ini, dan semua sel memiliki tipe konkret yang sama. Misalnya, Scryer Prolog memakai 8 byte per sel sehingga akses dan modifikasi sel sangat efisien di arsitektur 64-bit

  • “Daripada mengalokasikan objek Expr secara berlebihan di heap, simpan semuanya dalam satu array kontigu, lalu biarkan anak mereferensikan indeks array itu alih-alih pointer” lebih dekat ke representasi heap alternatif daripada flattening. Bentuk AST-nya sendiri tidak berubah
    Ini sudah lama dilakukan di banyak bahasa, misalnya seperti keluarga Lisp yang menaruh cons cell dan objek lain di dalam array, lalu memakai bump allocation dan pointer berbasis indeks
    Ketika objek berada di dalam array, garbage collector lebih mudah menelusurinya pada tahap sweep setelah marking selesai. Tahap marking berjalan di atas graf untuk menemukan objek yang masih dapat dijangkau, dan tahap sweep melewati array datar untuk membersihkan bit GC serta menandai objek yang tak terjangkau untuk didaur ulang
    Akan sulit menemukan implementasi Lisp yang cukup serius yang memanggil malloc terpisah untuk setiap cons cell. Jika begitu, akan dibutuhkan linked list global untuk tahap sweep GC, atau array global yang hanya menyimpan pointer
    Saya setidaknya sudah dua kali melihat proyek Lisp mainan buatan akhir pekan yang melakukan malloc untuk cons cell, membiarkan kebocoran memori, dan meninggalkan GC sebagai TODO raksasa
    Bahkan jika sel berasal dari heap array terkompresi, array global pada akhirnya tetap bisa muncul. Misalnya, saat mengimplementasikan garbage collection generasional pada allocator non-copying, objek muda bisa dikumpulkan ke array bantu agar bisa disapu pada siklus GC cepat, dan array itu merepresentasikan nursery

  • Tulisan yang bagus, tetapi ada dua jebakan

    1. Jika node disimpan dalam array yang ukurannya bisa diubah, compiler akan membutuhkan blok memori kontigu yang lebih besar seiring membesarnya program input. Blok itu mungkin ada, mungkin juga tidak. Ini bisa diakali dengan mengalokasikan blok seukuran halaman dan menggunakannya sebagai pool
    2. Perlu berhati-hati dengan cara merepresentasikan node AST di dalam kode. Misalnya, jika node disimpan sebagai union type, ukuran union akan mengikuti anggota terbesar, dan karena ukuran semua node AST tidak sama, node kecil akan mendapat padding yang tidak perlu agar sesuai dengan ukuran node terbesar
    • Fakta bahwa node AST kecil mendapat padding yang tidak perlu karena ukuran node AST terbesar itu poin yang sangat bagus, dan juga saya singgung dalam tulisan blog saya tentang tipe integer bit-width kustom: https://alic.dev/blog/custom-bitwidth
      Tagged union juga bisa dipakai, tetapi penggunaan memorinya harus ditangani dengan cerdas
    • Kadang saya berharap kita tidak berakhir dengan ruang alamat datar
      Teknik “virtual memory” memungkinkan wilayah memori fisik yang terfragmentasi disambung menjadi wilayah memori virtual yang kontigu. Jika ruang alamat virtual tersegmentasi, dari awal ia tidak akan terfragmentasi, dan setiap wilayah memori bisa selalu membesar di tempat tanpa bertabrakan dengan wilayah lain
      Kalau begitu, implementasi realloc() bisa menghilangkan jalur memcpy(), sayang sekali
    • Ini bisa diatasi dengan struktur mirip rope yang membagi vektor menjadi chunk berukuran tetap dan pointer nyata. Re-alokasi jadi tidak diperlukan
      Bagian dalamnya mungkin tidak aman, tetapi antarmuka aman yang hanya-baca tampaknya memungkinkan. Pembebasan memori akan O(n), tetapi tetap jauh lebih cepat daripada tree

  • Saya terkejut masih ada dua pointer (“referensi”) yang tersisa di node, padahal sekarang kita tahu pointer pertama selalu menunjuk tepat ke node berikutnya
    Saya pernah melihat https://github.com/rswier/c4 memakai pendekatan seperti itu. Tentu saja keterbacaan kodenya tidak bagus, tetapi lebih kecil dan lebih cepat

  • Dalam manajemen memori, ketika mendengar arena, yang terbayang bagi saya biasanya allocator arena biasa, bukan “flattening”
    Saat harus mengalokasikan banyak item dengan masa hidup yang sama, pendekatan ini mengalokasikannya dengan lebih efisien dari satu atau beberapa blok memori besar, lalu ketika masa hidup bersama itu berakhir, yang dibebaskan adalah blok besarnya, bukan item satu per satu
    Karena kita hanya perlu memakai ruang dalam blok induk secara berurutan, tidak perlu free list seperti pada heap allocator serbaguna, sehingga alokasinya juga bisa lebih efisien
    Dalam konteks ini, “flattening” yang memakai indeks alih-alih pointer juga bisa dilihat sebagai penggunaan pointer relatif terhadap blok induk, yaitu offset

  • Saat mengimplementasikan V7(https://github.com/cesanta/v7), parser dan interpreter JavaScript untuk lingkungan embedded dengan memori yang sangat terbatas, saya memakai struktur AST ringkas seperti ini
    Belakangan saya mengubahnya menjadi tahap kompilasi dari AST ke bytecode, tetapi untuk sementara waktu saya langsung menelusuri AST implisit saat interpretasi berlangsung

  • Saya juga melakukan sesuatu yang mirip di compiler Yaml to Sql saya di https://yaml2sql.netlify.app
    Proses flattening-nya agak aneh, tetapi menyenangkan, dan pada akhirnya sepadan dengan usaha yang dikeluarkan
    Misalnya, flattening ekspresi boolean adalah latihan yang bagus bagi siapa pun yang ingin mencobanya: https://github.com/revskill10/yaml2sql/blob/main/app/query.r...