TreeFlat: Building a (possible) faster tree for Rust, inspired by APL

https://www.elmalabarista.com/blog/2022-flat-tree/

by mamcx • 4 years ago

21 6 4 years ago

elmalabarista.com

jjgreen• 4 years ago

URL should be https://www.elmalabarista.com/blog/2022-flat-tree/ I think

dang• 4 years ago

Thanks! Our software had replaced it with the canonical URL, which is listed as https://www.elmalabarista.com.

jpf0• 4 years ago

The claim here is +80% reduction in time, +5x throughput relative the current standard.

Nice to see illumination of the benefit of high-level algorithmic design associated with the first-principals aspect of APL.

This is also an interesting claim presently, given there's an active conversation in the Jsoftware community currently on how to handle tree structures.

mamcx2• 4 years ago

What is more interesting: Implement it was pretty simple and I don't resort to anything fancy.

P.D: You have the link to the Jsoftware community? Or wanna link back from here?

mnurzia• 4 years ago

The arena design pattern is something I'm using a lot for a project in C. Like Rust, the primary reason it's attractive to use is because of how it plays well with memory safety. Although I'm no Rust expert, I suspect that its ownership model makes designing tree data structures difficult and unwieldy. In C, it is similarly unwieldy to design traditional tree structures because of how hard it is to manage pointers everywhere. If each Tree is a pointer to a dynamically-allocated block of data, it's really hard to remember when to call free(), especially if you have a function that modifies a Node in place by rearranging (or possibly deleting) its children, which is often the case for ASTs. In contrast, the arena pattern uses one flat memory allocation, and allows a couple optimizations:

- References between nodes can be whatever type you want. In most cases, I don't need a full size_t or the width of a pointer to represent a reference to another node, and a uint32_t or the likes will do. (This is faster on some platforms.)

- The whole arena is a single memory allocation (usually a vector.) Rather than allocating on every node, you can allocate memory for a few nodes and then use it until it runs out, at which point you can allocate memory for a few more.

- Since it's a single allocation, destroying the entire tree is trivial: just free the block of memory. Importantly, this doesn't require the recursive algorithm that a pointer-based tree might use to free itself, so you run no risk of blowing out your stack if some user creates a really deep tree.

- You can do repeated node removal/insertion in a really efficient way using a neat trick. It's possible to maintain an "empty list" by using the memory reclaimed from removed nodes in the arena to represent a linked list of empty positions. Then, if you want to add a new node later, you can use the last element of the empty list as the position for your next node, without resizing the arena. For an AST, this can be crucial because some algorithms will thrash the tree by doing lots of insertions and removals. (This technique is not type-safe in C, however, and can be UB if you do it wrong, so you have to be really careful, and it's a bit of a code smell.)

- Since the tree is stored in contiguous memory, it's a little more cache-friendly than a bunch of pointers that are potentially scattered throughout the heap. This is a nice bonus.

- The structure generalizes to any type of graph, like a linked list. If you need a structure that can represent any kind of link between objects without pointers, the arena will do.

There are a few cons, however:

- Like a pointer-based structure, you still have to remember to update edges in the tree when you update its nodes. Instead of updating a Node*, however, you're updating a NodeID, and sometimes less obvious when to do this.

- Since the array is a large contiguous allocation, its effect on your heap is very different than the pointer strategy that uses tons of small allocations. This gives different heap fragmentation characteristics, which might be better or worse depending on what allocator you use.

- Because a NodeID is just a position in an array, you likely won't get segfaults when you access a node that was freed, or a NULL Node*. This is actually a bad thing because you don't catch certain bugs until way later, when the corrupted tree is used. In C, I've found that a healthy amount of assert()s helps a lot but it requires a lot of abstraction and makes the code significantly more verbose.

All in all it's just another example of balancing performance, complexity, and ease of development. Like any programming tool, it's worth considering, but not really necessary unless you really need the speed (C) or unless it actually makes your code easier to use (Rust).*

mamcx2• 4 years ago

Yeah, that is why I say upfront that is "nice one-trick pony" and tied to a specific (if very useful) data pattern.

How update after the fact is something I haven't implemented and one of the reasons I deviate from the way is explained in the APL talk (where it materialize the full path per node) and just keep parent/level is with the hopes it later make updates easier...

TreeFlat: Building a (possible) faster tree for Rust, inspired by APL

Related Stories