Perataan AST dan Struktur Data Kompiler Lainnya

• Arena atau region adalah teknik yang sederhana dan efektif untuk kompiler dan hal-hal serupa kompiler.
• Meratakan abstract syntax tree (AST) dengan menggunakan arena dapat meningkatkan performa dan memberikan kemudahan.
• Perataan berarti mengemas node AST ke dalam satu array dan menggunakan indeks array alih-alih pointer.
• AST yang diratakan menawarkan keuntungan seperti locality yang lebih baik, referensi yang lebih kecil, serta alokasi dan dealokasi yang lebih murah.
• AST yang diratakan dapat menyederhanakan pengelolaan memori dan memungkinkan deduplikasi yang praktis.
• Hasil performa menunjukkan bahwa versi interpreter yang diratakan bisa 2,4 kali lebih cepat daripada versi biasa.
• Dengan memanfaatkan representasi AST yang datar, rekursi dapat dihilangkan dan penelusuran linear dimanfaatkan untuk lebih meningkatkan performa.
• Artikel ini membahas peningkatan performa yang dicapai melalui perataan struktur data dalam interpreter bahasa pemrograman.
• Selain itu, interpreter yang diratakan menunjukkan peningkatan performa 8,2% dibanding interpreter rekursif, yaitu 1,2 detik vs 1,3 detik.
• Teknik ini pada dasarnya menemukan kembali ide interpreter bytecode, dengan struktur Expr digunakan sebagai instruksi bytecode.
• Disebutkan juga tulisan dan proyek lain terkait perataan struktur data, seperti LuaJIT, Sorbet type checker, dan Oil shell.
• Konsep serupa terkait perataan dan optimasi locality juga muncul di domain seperti video game, pemrosesan data terserialisasi, desain berorientasi data, dan entity-component system.
• Artikel ini merekomendasikan untuk melihat tulisan Inanna Malick yang menerapkan teknik yang sama pada bahasa "kalkulator" mainan yang diimplementasikan dalam Rust.
• Keterbatasan penggunaan teknik ini di Rust juga dibahas, termasuk bahwa struktur Expr tidak bisa menyertakan Expr lain secara inline di dalamnya.
• Perbandingan performa dilakukan pada MacBook Pro dengan prosesor M1 Max dan memori 32GB, menjalankan macOS 13.3.1 dan Rust 1.69.0.

[GN⁺]

Komentar Hacker News

• Blender menggunakan representasi yang sama di disk dan di memori untuk pemuatan dan penyimpanan berkas yang cepat serta tanpa kehilangan data.
• AST yang diratakan digunakan di pulldown-cmark untuk parsing markup inline yang efisien.
• Representasi AST yang diratakan memungkinkan transformasi pohon O(1) tanpa bergantung pada jumlah node atau kedalaman stack.
• Kinerja pulldown-cmark sangat unggul dibandingkan parser CommonMark lainnya.
• Warren Abstract Machine (WAM) menggunakan representasi yang diratakan di heap untuk Prolog.
• Perataan AST adalah konsep yang sudah digunakan sebelumnya dalam bahasa seperti Lisp.
• Menyimpan node dalam array yang dapat diubah ukurannya dapat menimbulkan masalah alokasi memori, tetapi hal ini bisa dikurangi dengan melakukan pooling dalam blok berukuran halaman.
• Perlu perhatian pada bagaimana node AST direpresentasikan dalam kode, dan padding yang tidak perlu harus dihindari.
• Menggunakan indeks alih-alih pointer dapat menghasilkan kode yang lebih kecil dan lebih cepat.
• Memori yang diratakan dapat diimplementasikan dengan menggunakan allocator memori kustom yang berguna dalam skenario tertentu.
• Struktur AST yang ringkas digunakan untuk mengimplementasikan parser dan interpreter JavaScript di lingkungan dengan keterbatasan memori.