#rustposting

[schrodingers-moth]

jesus christ why is cranelift so badly documented i just wanted to use the fancy new stack maps :(

[nothinsnooty]

The very thought of you...

Pinterest

[snaillesnaille]

[ihaterain22]

Circular black plastic eyes

[merklehellman]

Good news: my remove() seems to be self-balancing now too, just gotta write some more unit tests for difficult cases.

Bad news: my code is absolutely ass right now. I have spaghetti'd all over my IDE. A humongous refactor is approaching and i am NOT looking forward to it, lmao.

[merklehellman]

Came back home after christmas, did not feel like coding at first but riding the satisfaction of last few weeks i somehow managed to do that. That's pretty cool since i used to have to force myself pretty hard before (being off work might also be helping with that).

Anyhow, i decided to attempt some self-balancing for my Rust binary tree project. I was torn between Red-Black and AVL trees, but i felt adding AVL into an existing project might be easier and they also felt easier for me to conceptualize.

This is probably the hardest part of the project for me.

I have implemented BSTs in other languages in the past - python, c, c++ etc. Also, what i have planned in the future (serialization) is also something i have a pretty good knowledge of.

But i haven't done a self-balancing tree yet. And given that it's rust, it felt intimidating.

It proved to be slightly tricky but - another success for me - i managed to defeat my perfectionism and force myself to write something that is far from perfect but works, instead of striking for perfection right away.

Needless to say, i have an insert() method on my BST which keeps balance of the tree!

I had to keep stack of ancestors during insertion, and i did not want to resort to unsafe {} right away (i will leave that for when i'm optimizing performance), so currently the stack takes ownership of the nodes along the way, and restores the tree during unwinding. Since the nodes are all Box'ed, taking ownership means just moving a pointer which would happen even with mut references/pointers anyhow.

The performance penalty i think happens in case when insert() overwrites an existing node instead of adding a new one. If i had a stack of references, unwinding wouldn't be necessary at all since no nodes were added and tree was not modified. When taking ownership i obviously have to unwind the stack in every case to not lose data.

I will work on it after i am done implementing self-balancing remove(). I think it might end up copying code from insert() anyways, but who knows - maybe there are some removal-specific cases. Afterwards, i will probably need to do some refactoring. I feel like more unit tests regarding balancing of the tree would be in order too, to make sure no data is lost during rotations.

Nonetheless, when i insert 15 monotonic values into my tree and see the height as 4 instead of 15, it brings me so much joy :)

[merklehellman]

holyyyyyyyyyyyy i managed to make my iter_mut() 100% safe rust!

I wrote my iter() by just putting a reference to the entire Node struct on the stack, and it worked. When writing iter_mut() i just copied it and changed & to &mut, but that did not work.

I have read many times, that this is a particularly difficult case for rust and the borrow checker does not understand it despite the fact that it's a pretty normal pattern and yadda yadda. Due to all of that i decided to just use unsafe {} and push raw pointers on the stack.

After finding some theoretical UB with miri (which i did not really believe could happen, but i had my doubts) i decided to have a closer look at what's happening in the code.

Recently i learned about struct destructuring and split borrows (basically, borrowing a struct Point { x, y } in such a way that x and y are borrowed separately, with separate lifetimes). I realized that my Node struct has fields that serve different purpose and are used in different parts of code, especially in the iter_mut() (key, value vs. left, right subtrees). This made me think that i could try splitting the borrows, to make it easier for the compiler to track lifetimes.

Effectively, having a Node { left, right, value, key } my stack definition went from:

Vec<&mut Node, VisitedInfo>

to:

Vec<(Option<&mut left>, Option<(&key, &mut value)>, Option<&mut right>)>

(it's a bit of a pseudocode cause left and right are not types ofc, but the type got super complicated even without expanding those. In fact, the type got so complex that clippy started complaining and i had to make type aliases to appease it.).

I also changed the code of my next() function, using struct destructuring on references, and it just clicked! I guess splitting the borrows between three different parts made the compiler understand what i was meaning to do lol.

It also feels nice, since each element of the tuple is only used in one branch of the process (left subtree, current node, right subtree), and instead of using an enum which tracks what was visited i can just use Options for that (two of which will be optimized thanks to null pointer optimization).

Honestly i am super excited ever since the tests passed, i genuinely did not think this could be done. Also i think it might be an experience worth remembering, split borrows sound like a useful tool for cases like those.

[atlas-hyperfixes]

Spotted myself several times in the new music video in the clips for the STL show (not difficult to do when I'm a fucking Glowing Beacon)

Bonus, spotted my brother and I at the Columbus show hehe