News for hackers. Stuff that matters.
Re:Static search trees: 40x faster than binary search by fpoling on Wednesday January 01, 2025 @01:27PM (#42567964)
Well, one can always emulate that in Rust with array indexes. And it will be closer how the actual CPU works where a pointer is just an offset into a memory chunk.

Perhaps this is the reason performance oriented articles prefer Rust. In allows to skip a lot of memory allocation while still catching memory-safety bugs, which is a hard problem with C++.

Re:Static search trees: 40x faster than binary search by szundi on Wednesday January 01, 2025 @03:35PM (#42569078)
How could something to implement a pointer be more straightforward than a pointer? People seem to like Rust in excessive, sometimes botheringly excessive proportions.
Re:Static search trees: 40x faster than binary search by oconnor663 on Thursday January 02, 2025 @11:57PM (#42582591)
I don't think the indexing strategy is more straightforward in general. It's a thing you have to learn, and the fact that you have to learn it is part of Rust's famously steep learning curve. That said, there are some common cases where you might wish you'd used indexes instead of pointers in other languages too:

- Working with resizeable collections like std::vector in any non-GC language, where resizing invalidates pointers.

- Serialization. If your objects contain indexes to each other, it's easy to turn them into e.g. JSON. But if they contain pointers to each other, it's tricky.

Re:Static search trees: 40x faster than binary search by amelius on Wednesday January 01, 2025 @06:42PM (#42570248)
How are you going to garbage collect inside your array? Sounds like you are just evading the problem and reinventing the heap.
Re:Static search trees: 40x faster than binary search by burntsushi on Wednesday January 01, 2025 @10:26PM (#42571330)
Not easily. But not all use cases require it. The regex crate makes heavy use of this pattern for finite machine states, for example. But this fits nicely with an arena allocation pattern, so everything can just be dropped at once.

Despite this, it's one of the fastest regex engines around: https://github.com/BurntSushi/rebar#summary-of-search-time-b...

Here's a related but more isolated analysis: https://github.com/burntsushi/rsc-regexp

Re:Static search trees: 40x faster than binary search by amelius on Thursday January 02, 2025 @10:27AM (#42575241)
You could probably make an even faster regex by JIT-compiling the resulting automaton.
Re:Static search trees: 40x faster than binary search by burntsushi on Thursday January 02, 2025 @11:23AM (#42575806)
The benchmarks I linked include multiple regex engines with JITs.
Re:Static search trees: 40x faster than binary search by oconnor663 on Friday January 03, 2025 @12:47AM (#42582896)
I'm not sure whether this is exactly what you mean, but when you need to support deletions you can switch to a "generational" collection like Slab or SlotMap. Your indexes are still integers, but under the covers some of the bits get repurposed to disambiguate new elements that reuse old slots.