Unboxing Virgil ADTs For Fun and Profit
summary
Adds two annotations to Virgil: #unboxed removes heap allocation by lowering non-nullary ADT cases into multiple machine scalars/words, and #packed lets the programmer specify exact bit layouts for fields so network or kernel formats map directly. Compiler implements a greedy solution for the scalar assignment problem to minimize words and reuse tag-pointer encodings; packing layout solving is NP-complete so the compiler either falls back, errors, or requires a SAT/solver step. Implementation exists in Virgil and unboxing works but recursion/closure-captured ADTs and packing remain work in progress.
AI-written summary · about
chapters (10)
- 0:00Virgil ADTs intro
- 4:24Unboxing ADTs in Virgil
- 6:54What unboxing ADTs means
- 9:02ADT types to machine scalers
- 12:32Packing ADTs for memory
- 15:41Runtime discrimination of ADTs
- 18:31NP-complete packing problems
- 20:19Compiler feedback on layouts
- 22:28Unboxing in production
- 23:17Q&A on integers and WebAssembly
related talks
01h 04mVirgil as a Systems Programming Language
17mUnboxed types for OCaml
32mBit-Stealing Made Legal: Compilation for Custom Memory Representations of Algebr...
30mA pred-LL(*) Parsable Typed Higher-Order Macro System for Architecture Descriptio...
55mNew Bytecodes, New Objects
01h 27mGeneric Arity: Definition-Checked Variadics in Carbon
19mDecoupling Data Layouts from Bounding Volume Hierarchies
01h 21mNon-local compiler transformations in the presence of dynamic dispatch