Hacker News Reader

Comment by varjag | Hacker News Reader

…on the other hand it doesn't take a PhD to write a linked list in C++.

Linked lists are complicated. You can get something that compiles easily with C++, but to be sure it doesn't leak memory might require you to get that PhD after all.

Linked lists are a very simple data structure, and pretty much everyone can get them right. There haven't been any big memory safety CVEs to my knowledge around linked list manipulation. The same for binary trees.

These pointer-based data structures are used a lot when you are manipulating large structs in C and C++, as they let you "move" then between data structures without copying a ton of memory.

It's not exactly rocket science or even PhD worthy, but getting basic exception safety right around manual memory management can get tricky.

Well..implementing them in "safe" Rust is not just tricky - it requires a super-brain.

You can use unsafe in Rust to get basically the same guarantees for your simple linked list as in C++?

If you need a PhD to avoid memory leaks, stop coding immediately, you don’t know what you are doing

Show an example of a lock-free concurrent stack freeing nodes memory.

... on the third hand it's better not to roll your own list in any language ;-)

Joking aside, some stuff are currently really hard in Rust, but the rate of change slowed down, and all I can see now is everyday ergonomic improvements, so there is hope for (slightly) simpler syntax in the future.

Doubly linked lists break one of the fundamental promises you make to the borrow checker: single ownership. I doubt they're going to get much easier.

It's also just generally not a wise structure to be making or using in applications level development at this point. Vectors will outperform them most of the time, are more cache friendly, and easier to write these days. And Rust has already done the work of building collections you can already use, including some that can be used no-std in embedded/baremetal environments.

And if you really need a linked-list type structure, and are competent to make it and use it properly/safely, unsafe {} is waiting for you.

You tend to see linked lists in places like operating systems, storage systems, and stackless asynchronous server systems. These kinds of linked lists actually do perform better than vectors in most cases.

Specifically, linked lists do well when objects are: 1. Large, specifically 100s of bytes 2. Moved frequently between collections 3. Intrusively linked (meaning that the pointers are part of the struct, not a separate library) and 4. Never randomly accessed

One size does not fit all when it comes to performance of list structures, unfortunately. In particular, large items tend to break standard library structures, since they are not the usual case.

Yes, hence why I said "applications level" development specifically. 99% of developers will never need to go this path. Those that do, they're already working down in unsafe land usually in embedded systems and OS development, and they need to think carefully about what they're doing.

I'm personally not entirely sold on Rust's memory safety model, though I did learn to work with it when I was getting paid to work in it.

I don’t think it takes a PhD to write an unsafe linked list in Rust. And an unsafe linked list in Rust would still be safer than the equivalent linked list in C++

How would the equivalent linked list in c++ be unsafe?

The problem with c++ was never writing simple data structures, but was writing complete programs without a single mistake in the informal contracts between functions. Static analysis tools and other crutches help but having a stricter ruleset to enforce is what makes rust a winner.

The list itself would not be unsafe, but the usages of it could be. For example, iterator invalidation, access from another thread, etc that Rust would prevent you from doing even if you used unsafe to implement the linked list.

Reply on news.ycombinator.com