Patrick DubroyMar 13

Looking forward to a couple of @ohmjs- and @wasmgroundup- related things next week:

1️⃣ Talking about the PEG-to-#Wasm compilation in Ohm v18 at MoreVMs: https://2026.programming-conference.org/home/MoreVMs-2026

2️⃣ Live-streaming with @jlengstorf on Thursday at 17:30 CET, teaching him about WebAssembly.

MoreVMs 2026 - MoreVMs'26 - ‹Programming› 2026

The 10th MoreVMs workshop aims to bring together industrial and academic programmers to discuss the design, implementation, and usage of modern languages and runtimes. This includes aspects such as reuse of language runtimes, modular implementation, language design, compilation strategies, as well as the interaction of modern languages and runtimes with operating systems and modern hardware architectures. By bringing together both researchers and practitioners, the workshop aims to enable a diverse discussion on how languages and runtimes are currently being utilized, and where they need t ...

Show threadPatrick DubroyMar 17

Had a great time hanging out at MoreVMs today, thanks to @smarr and @sbrunthaler for the invitation and for organizing!

I believe my talk was recorded, so hopefully I can share soon.

Show threadPatrick DubroyMar 17

Interesting theme that came up in a few talks (incl. mine) & conversations was flat/packed tree representations.

https://types.pl/@vollmerm (Univ. of Kent) has done tons of interesting work in this area: https://recurial.com

mike vollmer 🎃 (@[email protected])

501 Toots, 178 Following, 360 Followers · Lecturer in Computing, University of Kent. FP and compilers.

types.pl
Show threadChris EidhofMar 18
@dubroy is this where you model an AST as an array? (I'm simplifying, of course). I'd love to learn more about that.
Show threadPatrick DubroyMar 18

@chris Yes, it varies but the general idea is —

For ASTs, CSTs, and intermediate representations (e.g. CFGs)…

They are many small objects, that all have the same lifetime, and that lifetime corresponds to a clearly-defined phase, so:

- avoid per-node memory management space overhead
- do bump allocation into some kind of arena/region, free them en masse at the end of the phase.
- use integer offsets rather than first-class pointers. (Memory savings, better cache locality, and — in GC'd environments — avoids GC overhead scanning a large object graph.

In many languages, you can do this effectively with a large array, but there are other approaches too.

See also what @adrian wrote about it: https://www.cs.cornell.edu/~asampson/blog/flattening.html

Happy to chat about this sometime!

Flattening ASTs (and Other Compiler Data Structures)

This is an introduction to data structure flattening, a special case of arena allocation that is a good fit for programming language implementations. We build a simple interpreter twice, the normal way and the flat way, and show that some fairly mechanical code changes can give you a 2.4× speedup.

Show threadPatrick Dubroy

@chris I've also found that, in V8 at least, if you can avoid allocation when walking large trees, you can see a ~10x speedup for operations that visit all/most of the nodes in the tree.

(I have one type of walker that lazily materializes CST nodes from the packed representation into first-class objects, and another one that does little/no allocation at all during the walk.)

Mar 18 at 10:44amWeb
Show threadChris Eidhof6d ago
@dubroy I'm only getting to process this now, thank you so much. This is really useful. I'm building something (for now) on top of SwiftSyntax, at which point a tree has already been constructed. Not sure yet if it's better to then do all my analyses on the flattened tree or if we should build up a database of facts about the code first...