News for hackers. Stuff that matters.
Re:Static search trees: 40x faster than binary search by thayne on Wednesday January 01, 2025 @05:54PM (#42569988)
It doesn't though.

Those are fairly straightforward to implement if you are ok using a reference counted type (along with weak references), although that will hurt performance. That would be similar to using a shared_pointer in c++.

And you can implement code similar to what you would in c or c++ if you use raw pointers and unsafe code.

Where you run into difficulties is if you want something that is fast and safe. And then you need a more complicated design that probably involves using indices into a Vec instead of pointers.

Re:Static search trees: 40x faster than binary search by amelius on Wednesday January 01, 2025 @06:25PM (#42570163)
Using a Vec for doubly linked lists sounds like overkill. There's got to be more efficient and more elegant way.
Re:Static search trees: 40x faster than binary search by unrealhoang on Wednesday January 01, 2025 @07:08PM (#42570384)
Yes, there is, just use plain old pointers. Who cares about UB anyway.
Re:Static search trees: 40x faster than binary search by thayne on Thursday January 02, 2025 @04:02AM (#42572862)
Using a Vec actually has some benefits beyond the safety guarantees from rust. There are fewer allocations, and you probably are more likely to get nearby nodes on the same cache line.