Compact AST Representation

Compact AST Representation

• Reddit Thread: Representing ASTs as byte strings with with small integers rather than pointers
• sajson: Last week, I described a JSON parse tree data structure that, worst case, requires N words for N characters of JSON text. Single allocation JSON?
• Compiling tree transforms to operate on packed representations at ECOOPLDI 2017
  • Conference Presentation on YouTube
  • This is much more ambitious, but also more limited. Not only are there no pointers, but the tree traversal is equivalent to a linear scan through memory. It compiles a custom programming language and rearranges the operations so this is true.
  • See limitations at the end of the paper.
  • Gibbon compiler
• Good references in that paper:
  • The Lattner/Adve paper below
  • Cache-Conscious Data Structure Layout
  • Compact Normal Form in Glasgow Haskell Compiler -- reduces both space and garbage collection pressure.
• Ken Thompson's postfix encoding for regexes (no pointers) is mentioned here: https://swtch.com/~rsc/regexp/regexp1.html

Array of Homogeneous Nodes / "Inverted" Struct-of-Arrays

As opposed to array of pointers to heterogeneous structs

• Vertical object layout and compression for fixed heaps

  • Implemented in the Virgil Language by Ben Titzer
  • Vertical Object Layout basically means transposing objects and fields. Analogous to arrays of structs -> struct of arrays. Except the "array" is every instance of a given type on the heap.

• Co-dfns APL Compiler Thesis -- Uses an array-based representation of an AST. Section 3.2 is The AST and Its Representation. What's novel is that this is a parallel compiler hosted on the CPU. So it's not just compact, but laid out in a way amenable to parallel computation.

• Zig PR to use Struct-of-Arrays and Indices in AST. Proof of concept for other IRs: https://github.com/ziglang/zig/pull/7920

  • Video Explanation: Practical Data-Oriented Design - Handmade Seattle 2021
  • Downside: you lose type info since you have integers rather than pointers

• Modernizing Compiler Design for Carbon's Toolchain - CppNow 2023

  • Primary Homogeneous Dense Array packed with most ubiquitous data
  • Indexed access allows most connections to use adjacency (implicit pointer, no storage required)
  • Side arrays for secondary data, referred to with compressed index
  • Flyweight Handle wrappers

Compressed Pointers

This is related: more general, but more complex.

• Compressed Ordinary Object Pointers (Oops) in 64-bit JVMs mean that 32-bit integers can address 4 GiB * 8 = 32 GiB of memory (since objects are at least 8-byte aligned)
  • StackOverflow: Trick behind JVM's compressed Oops
  • Apparently this is the default since Java 7 circa 2011, when the max heap size is < 32 GiB
  • https://shipilev.net/jvm/anatomy-quarks/23-compressed-references/
• Relative Pointers. Good survey of 4 kinds of relative pointers, including two that have the memcpy() property:
  1. Virtual Memory Pointers. What we all use on modern OSes.
  2. Global-based pointers (relative to global variable). There are compiler extensions I didn't know about.
  3. Offset pointers -- relative to an explicitly defined base, such as the beginning of a file
     • Offset pointers can also be replicated in C++ through the use of templates. Similar to the previous user-defined based pointers above, the size of the underlying integer can be any size.
  4. Self-Relative/Auto-Relative pointers—relative to its own memory address
     • TODO: explore this for Oil. Might be easier to put multiple interpreters in the same address space. Will complicated debugging a lot!
• Reddit: Transparent Pointer Compression for Linked Data Structures by Lattner, Adve -- divide address in to 4 GiB pools so that internal pointers are 32-bit.
• Jai Demo: Relative Pointers
• Object-Relative Addressing: Compressed Pointers in 64-bit Java Virtual Machines
• Reddit: Idea for Tiny Relative Pointers. Using the LSB for external vs. internal might be a good idea. I also wanted a bit for const vs. non-const.
• CppCon 2019: Steven Pigeon “Small is beautiful: Techniques to minimise memory footprint” -- a lot of C++ metaprogramming tricks with constexpr, etc. Goes to the extreme on size but says little about speed. No benchmarks and no concrete applications, just small pieces of C++.
• Why Sorbet Is Fast -- Fast static type checker for Ruby written in nice C++. 32-bit IDs for interned strings for fast comparison. GlobalState and Ref.
• Flat Buffers don't need to be deserialized before using them. Also there is possible precursor here with flat_file_memory_management (no code)
• Pointer Compression in V8 (March 2020). Chrome switched to being a 64-bit process in 2014, so they got this problem. Each v8 instance is limited to around 4 GB, although they still want to have multiple instances in a single address space (I guess for web workers, where all the workers have the same privileges).
  • In order to simplify integration of Pointer Compression into existing code, we decided to decompress values on every load and compress them on every store. Thus changing only the storage format of tagged values while keeping the execution format unchanged.
  • we observed that Pointer Compression reduces V8 heap size up to 43%! In turn, it reduces Chrome’s renderer process memory up to 20% on Desktop.
  • More comments on Hacker News
• [smol_world: Compact garbage-collected heap and JSON-like object model] comments on lobste.rs. Library in C++ 20 using relative 32-bit "pointers".

Layout Should be Orthogonal to Logic

• You Can Have It All: Abstraction and Good Cache Performance. (2017) Divide objects into pools and can do SoA/AoS on individual sets of fields. It seems like this is done manually, which might be too onerous for big apps? The work hasn't been integrated into a compiler yet. Good related work section, citing a lot of the work above.

Tree Pass Fusion

• https://news.ycombinator.com/item?id=24740889
• Miniphases: compilation using modular and efficient tree transformations, Odersky et al. (2017)
  • https://scholar.google.com/scholar?cluster=7946863864036706551&hl=en&as_sdt=2005&sciodt=0,5
• TreeFuser: a framework for analyzing and fusing general recursive tree traversals. (2017)
  • https://dl.acm.org/doi/abs/10.1145/3133900
  • This one said they prototyped it in Clang.
• Deforestation: Transforming programs to eliminate trees, Wadler (1988)
  • https://scholar.google.com/scholar?cluster=13826873296507613488&hl=en&as_sdt=0,5&sciodt=0,5

I think the key point is that some of the frameworks introduce restrictions that make it hard to write a big program like a compiler. There is a hard tradeoff between the amount of fusing that can be done and how expressive the metalanguage is.

Serialization, GC Pressure, Code Reuse

• Efficient Communication and Collection with Compact Normal Forms - Glasgow Haskell Compiler
  • Paper: http://ezyang.com/papers/ezyang15-cnf.pdf
  • Slides: http://ezyang.com/slides/ezyang15-cnf-slides.pdf
  • Reduces GC pressure
  • No outgoing pointers
  • doesn't seem to have identity/sharing? Duplication is the default

Reducing Garbage Collection Pressure

• Span, Slices, string_view, StringPiece, etc.

Old Oil Stuff

• Oil Blog Post: What is oheap?
  • Oheap V1 was a read-only format for transporting an ASDL tree across the Python/C++ boundary. Though it turned out there wasn't a single clean boundary in the shell's architecture.
• OHeap2 was a read-write format, for OVM2.
  • At first I used it to represent .pyc files (Python's CodeObject)
  • Meant to replace marshal, pickle, and zipimport.
  • 4-16-N model: 4 byte refs, 16 byte cells, and N byte slabs.
  • See ovm2/oheap2.py
  • OHeap2 might still be a good idea, but I judged OVM2 not to be a good idea

Related

• Lossless Syntax Tree Pattern