Comment by pornel | Hacker News Reader

Comment by pornel | Hacker News Reader

Oh no, anything but the linked list.

Real-world Rust programs don't implement linked lists. There's LinkedList in libstd if you really wanted one, but in modern architectures cache locality is so important that almost always some other data structure is a better choice. Rust's standard library and crates.io have plenty of containers to choose from.

Linked list is popular because it's a CS101 topic, and because C is so barren. When you don't have any containers in stdlib, dependency management is hell, and due to lack of generics any 3rd party implementation will be either inefficient or full of macros, only then low-effort hand-rolled linked list seems like a sensible choice.

Linked lists have a really important property: each node can be owned by a different allocator. You can have a node which is stack memory, linking to a node which is heap allocated with libc malloc, linking to a node which is arena-allocated per frame of a game engine, linking to a node which is global static memory. And you can set this up in a maintainable, sensible way.

Linked lists are incredibly useful when an object can exist in a predetermined set of lists, and allocation failure must not be possible when adding the object to a list.

Your comment kind of reminds me of this implementation http://www.rosettacode.org/wiki/Power_set#C for generating a power set in C. The code recursively calls a function that permutes through the members of the power set and creatively constructs linked lists pointing up the call stack.

Yes, and in C++, linked lists can retain this property and be implemented in a memory safe way using non-owning reference-counting smart pointers[1].

Many defend the use of unsafe Rust in cases like these, in part by asserting that C++ would have the same (un)safety issue. I don't think that's right. A C++ implementation would not have to use (unsafe) raw pointers, or (expensive, intrusive) owning pointers from the standard library.

I think C++ has the advantage in cases like these because of the aforementioned non-owning reference-counting smart pointers. I don't think the same type of pointer/reference can be implemented in Rust (as it would need a constructor), but it's not immediately obvious to me that such a reference type couldn't be added to the language as an intrinsic element (like Rc). I think such an element is dearly missing from the Rust language. I suspect that adding it would make the language safer and easier to use.

[1] shameless plug: https://github.com/duneroadrunner/SaferCPlusPlus#norad-point...

I'm not a Rust expert, but aren't you describing https://doc.rust-lang.org/std/rc/struct.Rc.html?

Linked lists get shit on a lot, but they're great for a lot of use cases that Rust is ideal for. Hell, doubly linked lists are pretty much the data structure of the Linux kernel, and it seems to run pretty fast.

I recently had to write a bunch of custom linked list like structures in C++. Seeing how Rust adds that big heap of complicated boiler plate on top of the actual algorithms doesn't exactly make me a fan of that language.

no double delete and no dangling pointers is the tradeoff.

i once spent two 12h long days hunting a dangling pointer. it was fun finding it, that one time.

If all you want is the C++ experience there is no complicated boilerplate.

There is so many ways you can write good C++ code. It depends on the use case. I have code that is nice, modern and concise and I have code where I recently threw all of that out and even introduced custom containers and custom memory management to get an important 2x to 3x speedup.

It's not 'boilerplate', and rust is remarkably good at removing boilerplate. It's that in this case, what you've described as "the actual algorithms" is only a small part of the semantics that are provided by a safe, generic data structure under Rust. If you want to ignore all of that and only want the C++ level of semantics, writing the code in unsafe blocks is all you need to do.

If I have to write in unsafe blocks, then what is the point? I get the intent to prove memory accesses to be correct during compilation. But if a simple linked list turns into a nightmare project then I get the feeling that this language has missed the mark on usability as a systems language.

The thing is, that proving that the interface for "a simple linked list" is safe is actually nontrivial. It's not something that translates into day to day Rust. It's just a different language, different parts are hard (most parts are easier IMO). Picking off a linked list just happens to be one of the hardest pieces.

Brian Cantrell has some really interesting blog posts on this http://dtrace.org/blogs/bmc/2018/09/28/the-relative-performa...

Sometimes, choices aren't entirely about the structure itself, but about the affordances that a language offers you.

Reply on news.ycombinator.com