Closing a three-year-old issue using Rust arenas
93 points by giacomo_cavalieri
93 points by giacomo_cavalieri
also cutting its peak memory usage by a good 10%!
If this is a point you are looking to improve further, you can look into using a different arena which gives you opaque handles instead of references. The handles can be 16 or 32 bits long instead of 64, which can be significant when you have many small allocs (as it seems to be the case from your 10%).
According to https://donsz.nl/blog/arenas/ , the only crate to do that is compact_arena but it's easy to write your own if it doesn't fit your needs.
(author of that blog post), do note that I did my research 2 years ago, things certainly changed a little since then, and I'm aware my research wasn't perfect for every crate. I accept PRs if you find mistakes or new libraries I've missed!
Other than that: I'm a big fan of arenas, we need more of them :3 Note that there is one big advantage to an arena that gives out references as opposed to handles or smart pointers: it's super nice to match on. In Rust, it's hard to pattern match on recursive enums, since there has to be indirection. So, you can't for example say if let MyAst::Add(MyAst::Multiply(a, b), c) = expr {}, because there's a box or other pointer inbetween. That is, unless you use references, since you can transparently match on them without any nightly features (I'm aware there's work, like DerefPure and DerefOwned, and deref patterns, etc). And if all your references point into one arena you get a consistent lifetime to connect to your entire tree.
ere's a box or other pointer inbetween. That is, unless you use references, since you can transparently match on them without any nightly features (I'm
Totally! Matching on those values directly feels soo nice
And, opaque handles can be cool for a different reason: they let you store the data more compactly. E.g. columnar (personal project) stores a list of Option<T> with one (+eps) bit for each entry, and the T for the present entries. You get back an Option<&T> as the reference type, rather than a &Option<T>, is the trade-off. More generally, structural recursion over references, rather than references over structural recursion. YMMV!
Ooh that’s really interesting thank you! Given the nice outcome, we were thinking we would like to switch to using arenas in other parts of the compiler, so I’ll keep an eye on this!
For my job I work on rustc, and one there we have a very deliberate point where we intern everything. (i.e. arena allocate and deduplicate). The AST uses Boxes, since its expected to change a lot, and we want to deallocate what we don't need anymore. Then during "ast lowering" (we generate the HIR here) we hash and arena allocate everything, generating HirIds, which are essentially handles into the arena (so we don't use references as handles). We do the same extensively in the type system, where we intern types, which helps both directly for performance, and also makes it easy to cache things since we know types are always unique. Here we do even fancier: we use pointer tagging to store the kind of type we're dealing with.
The paper referenced in the article is written by somebody working at a generic IT shop in Brunswick? That's wild.
Thats braunschweig tho, which is in germany, or am i missing something?
The english name for Braunschweig DE is "Brunswick". We tend to not use anglicised names for foreign cities anymore, though.
My understanding is Braunschweig is heavily into various types of applied research.
Nice work! This actually seems quite similar to the approach supported by pretty (another Wadler-style pretty printing library) - alas the fact that it supports multiple methods of allocation can make the API somewhat intimidating.
This feels a bit nitpicky, but I’m impressed that this sentence seemingly contradicts both itself and its footnote (emphasis mine):
I find it actually quite fun to tackle those boring and repetitive jobs where I can turn my brain off and just punch at a keyboard. ^llms
I have always assumed that “turning your brain off” referred to not having to think, so this part of the footnote seem out of place:
I like typing and thinking for myself, thanks!