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

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.

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).*

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