Lab note #038 Prolly Tree Incremental Insert Finally Done

It took a long time, but the incremental insert for a Prolly Tree is finally done. I don't think I've ever spent this long as such a little part of code. The two aspects that had me struggling were the bottom-up breadth-first traversal, and how to replace the swath of nodes. I'm only consoled by rumors that Rich Hickey spent a long time implementing the Relaxed-Radix Balanced Trie when he first started Clojure.

I was eager to put it through its paces when I first completed the incremental Prolly Tree. My stats showed that building a tree incrementally was increasing linearly to building it from scratch. 😱 Oh no. Was it all not worth it?

It ended up being a bug in my stats collection code. Whew. 😮‍💨

I first measured the duration for inserting a single key as I inserted a million keys into a tree. It seems to be about 0.21ms. As we can see, inserting keys into a growing tree didn't significantly grow the duration of inserting a single key. To note, the store is currently still in memory, and this is implemented in Typescript, so I wouldn't take the absolute duration to heart. It'll need to be reimplemented in Zig later anyway.

Next, I looked at the number of nodes that changed between the previous tree and the next tree after every insertion, as I inserted a million keys. Here, we see that early on, the number of nodes changed upon insertion quickly grew, but then tapered off at around 8 to 10 nodes as we approached a million keys.

Looks like it's working, as far as I can tell.

When I finally got it working it was admittedly a little anti-climatic. But I did feel a huge sigh of relief, and there was a lot of fist-pumping. I think I can see another way to approach the difficult parts of the implementation, now that I have more experience. But for now, I'm going to leave it alone, as it's done, and I can finally move on.

What's next? I'm going to implement immutable maps and sets with Prolly Trees. Then using those, I'm going to implement Causal Length Sets. I'll detail more in the next week.