Hacker News Reader

Comment by madez | Hacker News Reader

That Rusts compiler fights against intuitive doubly linked lists is reasonable, because they wouldn't work when working in parallel on the list, while Rust by default also ensures safety doing that.

Having that in mind makes it easier for me to come up with ways how to appease the compiler. What measures would you take to write a thread-safe doubly linked list in C? Would you make it entirely exclusive and blocking? Well, then you might want let one "list" structure own all nodes. Would you want to allow parallel execution of operations on the list? Well, then break the ownership of the nodes up into smaller parts that you can hand out in parallel when they don't affect each other. What granularity of allowed and prepared-for parallelism gives the best performance depends on the use-case.

View on HN

I think this is the point that's often overlooked. Everything in safe rust is supposed to be both memory safe and thread safe. The textbook implementation of linked lists and trees are not thread safe, and easily not memory safe.

I’ll be the pedantic one. It doesn’t guarantee thread safety, it guarantees that its data race free.

In practice this often reduces to the same thing, but you can still create deadlocks, etc.

Yes, you are correct. Rusts safety does not rule out deadlocks. Guaranteeing data-race-freeness is however already enough to reject intuitive doubly-linked lists. Thanks for bringing that up, which I don't think is pedantic.

Lots of (most?) rust libraries are "not thread safe" in the sense that those data structures aren't though. The reason this is ok is that to actually share a piece of data across threads it needs to implement Sync (which requires unsafe).

Also, as a sibling comment points out, the "thread safety" guarantee is relatively narrow -- it won't guarantee a general lack of concurrency bugs any more than a gc will guarentee reasonable memory usage.

I haven't thought through the details, but I suspect it's possible to adjust the semantics of rust in a way that allows multiple mutable references without sacrificing memory safety.

What you would hit is that the compiler would be hindered when doing optimizations in the same way that c and c++ compilers are, because of pointer aliasing.

There's a trade off there, and I think you can make the argument either way.

Sync is implemented automatically for most types; if you want to tell the compiler something is Sync when it thinks it isn’t, that’s when you need unsafe.

Same with Send, which is more primitive than Sync.

Ah, point. That would probably need to change to relax the one mutable reference constraint, if you wanted to.

> I haven't thought through the details, but I suspect it's possible to adjust the semantics of rust in a way that allows multiple mutable references without sacrificing memory safety.

Please do think about the details deeply, because if you find a way to do this, you'll probably bring a revolution to Rust.

I'm kind of skeptical of course, but I'd be really happy to be wrong.

I'm not sure how to build a lock-less doubly-linked list in C, honestly, and it may not be possible. I've authored several lock-less data structures in C, but I've not thought about this one... A singly-linked list is easy-peasy for addition at the head or tail (just atomic reads and atomic compare-and-swap), though deletion is tricky (because the obvious CAS thing to do is racy if you'd free the deleted element, and you do want to free it eventually...).

A good pattern for thread-safety is to use immutable data structures. jq's jv API [0] is a great example of how to make it easy to deal with immutable data structures. Of course, you don't get to have cycles this way and so you don't get to have doubly-linked lists. Also, for root state you kinda need something like a thread-safe variable (of which there are a number of flavors in Clojure, Haskell, and others) where when you read it you're guaranteed to have a stable reference to the value, but also guaranteed that garbage will be collected -- this is great when the values are immutable data structures.

You could have cycles in immutable data structures if you install the cycle before ever sharing with other threads and can make sure you don't fall into a loop when releasing the immutable value. But this is the sort of thing that requires "unsafe mode" unless the compiler/runtime can figure out that a) you haven't shared the thing yet, b) it won't be mutated once shared. I don't know how to figure that out statically, but that might be a good avenue for research.

[0] https://github.com/stedolan/jq/wiki/C-API:-jv

Some CPUs have a 128-bit compare-and-swap (lock cmpxchg16b on x64). You can build a lockless doubly-linked list with that. See for example https://gist.github.com/glampert/c40f2584d2fbc72316e1c8a6ef1...

As to the doubly-linked list in Rust: I think one could add the notions of “allocated block that must have n references to it” and accompanying “one of n references to an allocated block”. That could lead, for example, to code

   let p1, p2 = heap::allocate2(elem_size, align);

to allocate such a block with two references. The borrow tracker could then ensure that both p1 and p2 get stored once somewhere before the function allocating the memory returns or get returned from the function, or that both get passed to a function freeing the memory, and never used afterwards.

I respect your expertise here, but pulling up 20,000 feet...shouldn't Rust feel some urgency to provide something like simple-to-use common data structures without pain? Or a reasonable alternative? Current state feels a little science projecty.

There are simple-to-use data structures available in Rust. In fact, they are particularly easy access due to the excellent package manager. What is not so easy is to write some of these data structures yourself. Which is a publicity problem for Rust, as these tens to be exercises that people from a C/C++ background want to try in Rust.

Ahh, okay. So maybe a "c++ common approach" vs "rust best practices" FAQ? Like "maybe you don't need a c++ like doubly linked list, and here's why" write-up?

Linked lists are in the standard library[1]. The source code is linked to from that page (`src`, on the top-right corner), although the implementation is optimized so it's probably not a great learning resource.

If, for some reason, you actually need a linked list there are tons of implementations available on crates.io[2].

It's not that there aren't linked lists, and it's not that they can't be implemented as efficiently as in C, it's that implementing them is an inherently tricky problem where the obvious implementation can't be proved by Rust's type system so they're an extremely unpleasant way to learn Rust.

1: https://doc.rust-lang.org/std/collections/struct.LinkedList.... 2: https://crates.io/search?q=linked%20list

I'm not sure that really addresses my question. You seem to be saying C++ folks need to bear the burden of figuring it out. That's fine, but it explains the conflict. If the Rust's team position is that C++ diehards need to fully understand Rust first, then the conflict seems expected. On the other hand, if the Rust team is interested in serious evangelism, something seems missing.

A write-up for the latter: https://isocpp.org/blog/2014/06/stroustrup-lists

High level summary: linked lists are usually not the best data structure.

I think it's more that there's one in the standard library, so you don't actually need to write one in Rust, but if you look at how they did it you'll find that it was written in unsafe Rust because that's how you do things that rely on pointers for their semantics.

>"maybe you don't need a c++ like doubly linked list, and here's why" write-up?

Done and done, you're welcome:

http://cglab.ca/~abeinges/blah/too-many-lists/book/

To be fair, sometimes you have to write a trie or DFA or some other linked data structure.

However, if one is willing to deal with the possibility that the _next_ pointer can be null, then isn't reference counting and with weak references perfectly fine?

> In fact, they are particularly easy access due to the excellent package manager.

People keep screaming this like it's a huge advantage, but having built applications for years, knowing that one of the most difficult parts of modern applications is maintenance, especially of open source dependencies - making sure they're up to date, making sure you are on the same page with the rest of your company, making sure that they're available when you need to build for reproduciblity, making sure you can trust the library, making sure it has a sane interface and maintainer that listens and understands your use cases, etc... I've honestly come to see package managers more as a liability than an advantage. They're tremendous for this Wild Wild West github-pull-requests-are-life style that's become popularized by Javascript programmers, living their life to build one application quickly and move right on to the next... but that's not something I'd aspire to.

Every one of these new languages goes "Woo package manager", everyone codes against them, and then dependencies start stacking up, they start going out of date, APIs change, people move on to other projects, etc, and before you know it you've got 150 copies of "leftpad" and someone deletes the leftpad repository and breaks every build in your company... And this isn't a new story - it's happened to every language I've dealt with that has one of these package managers, from Perl's CPAN to Go.

I want a language to have "Batteries Included", not "Batteries Available by Easy Download from the Internet From Strangers' Githubs". It's the one good thing C++ had going for it - the STL contained the data structures you needed to get going quickly and then it got out of your way - you could bring your own as soon as you needed. You didn't need to track the STL as a dependency and wonder if someone changed the return value of a function - it basically never happened, which meant you didn't feel the need to abstract it or insulate yourself from its API in case it broke.

I want to know my dependencies, and to know that I can trust them, and that my application can be maintained indefinitely, that I won't get stuck on some old library because I assumed this random crate everyone recommended was the best way to do something, then everyone changed their minds and I end up having the dreadful choice of rewriting all my code or taking on maintainership of someone else's abandoned heap.

But I also get that Rust is young and maybe as it matures they'll move some of this stuff downstack so you won't have to just say "Oh I'll just download XYZ package from the internet, what could go wrong..." Or maybe I'm just wrong and this chaos and questionable maintainability is desirable in some insane way, and I just belong to a different generation of developers who want to build lasting applications and not weekend projects...

I think perhaps this is one of those times you should have looked into the package manager and package management system prior to going full rant. I'm with you on the state of package management in general, and most if not all the problems you outlined were very specifically addressed by rust's package manager and system.

There are solutions for these problems, they aren't perfect, but it's getting better.

Not Invented Here

This disease is extremely common among programming language developers and enthusiasts. A rust developer or a rust enthusiast just cannot fathom using a generic tool and instead everything has to be rewritten in rust. This applies to pretty much everything that a programmer might use but is especially bad with package managers.

C and C++ do not have a cross-platform, uniform package manager and build system used by most projects. It’s more of a “not invented” than a “not invented here” situation.

I share both the views of the grandparent and that we should consider rewriting things in Rust. They are not mutually exclusive.

We need ways to package and distribute software written in a variety of languages. Rust should play nice and cooperate with these. That does not exclude that doing things in Rust may give advantages.

I'm not sure that doubly linked lists are common. They are pretty obscure highly specialised datastructures that are only useful when you really know you need them.

I mentioned this in another comment, but it does provide a doubly-linked list in the standard library: https://doc.rust-lang.org/std/collections/struct.LinkedList....

> shouldn't Rust feel some urgency to provide something like simple-to-use common data structures without pain

You can already find most useful data structures in the standard library, including a doubly linked list. (Which probably doesn't even count as a useful one).

Reply on news.ycombinator.com