Alexis Beingessner, a Rust contributor, writes about Rust data structures, collections, and language design.
HN commenters praise his "Learning Rust With Entirely Too Many Linked Lists" as one of the best explorations of any language and for learning data structures in Rust.
An article you might find helpful is this one on why imperative algorithms are harder to mathematically verify than functional ones:
https://semantic-domain.blogspot.com/2018/04/are-functional-programs-easier-to.html
You don't need to be a mathematician to follow it with this excerpt summarizing its key point:
"The difficulty of imperative programming arises from the combination of state, aliasing and procedure calls. Any two of these features can be handled without that much difficulty, but the combination of all three effectively makes reasoning (nearly) as difficult as correct concurrent programming. "
The garbage-collected languages let you ignore the aliasing problems with a performance penalty. Rust in safe mode without GC forces you to (a) deal with it and (b) deal with it in a way that works for all inputs (type/memory safety). That usually requires mathematical verification using tools such as separation logic. Rust's method is much easier to use with tradeoff of limitations on expressing code in certain ways.
Folks that get along with the borrow-checker say it helps to design the program around data and easy methods of using it versus starting with control flow forcing it on a data structure. I'll also add that linked lists are inherently hard to get right on all inputs regardless of low-level language. They're actually a popular way to test new, mathematical methods for specifying and proving algorithms correct. Fortunately, Rust folks have a goto write-up on…
I can't tell if this is an April Fool's joke or not. If it is, congratulations, troll successful. But I'm going to go ahead and reply anyway...
There are exactly two valid* points in this post:
- rustc is slow
- "the circlejerk"
* i.e. not completely without merit
I'll just go through these really quick:
1. rustc is slow
Rust just shipped (in beta) incremental compilation, a technique commonly used by compilers to speed up recompiles:
https://internals.rust-lang.org/t/incremental-compilation-beta/4721
This doesn't change the fact rustc is slow, but it certainly makes the developer experience much better. Try it out!
That said, rustc is still slow. A valid complaint.
2. rust needs unions
Rust has two types of unions:
- tagged unions a.k.a. sum types. These are preferred
- #[feature(untagged_unions)]: actual C-style unions, unsafe, useful for C interop
You probably want the first kind. Rust does have them!
3. linked lists are great
Linked lists are great! I use them in one of the main Rust programs I'm working on. The thing about Rust linked lists is how you write one will depend entirely on your memory model.
One of the best tutorials on Rust explains the language's memory model in terms of linked lists. It's a great read, a harrowing tale of "fighting rustc" until you achieve victory:
http://cglab.ca/~abeinges/blah/too-many-lists/book/
I'm using immutable arena-allocated linked lists, which is a great pattern. This is in conjunction with…
> I'd like to hear something like "This is how our team used Rust to do (really hard thing involving heavy concurrency and lots of state)".
Our team uses Rust for moderately complex concurrency.
TL;dr: There are tradeoffs, but Rust can be quite nice when you care about performance.
In my experience, concurrency is actually pleasant in Rust. The borrow checker eliminates 99% of problems before they ever occur. As for libraries, the popular crossbeam library provides scoped thread pools, which make it easy to spin up a bunch of local worker threads. https://docs.rs/crossbeam/0.3.2/crossbeam/struct.Scope.html#method.spawn For "parallel iterators", Rayon is excellent. https://github.com/rayon-rs/rayon For async I/O, the tokio library still demands solid Rust skills (at least until Rust 2018 lands), but once you figure it out, it Just Works. https://tokio.rs/
As for our other experiences using Rust:
- Rust is amazing for fast, cross-platform CLI tools.
- For most kinds of programs, I barely notice the borrow checker any more. But this is partly because I don't write programs with giant webs of objects that all try to mutate each other (like some game engines, for example). Also, I've never needed to implement a non-hierarchical data structure in Rust (the gory details of which are described at http://cglab.ca/~abeinges/blah/too-many-lists/book/), mostly because anything I needed was already on crates.io.
- Library support is much better than I would expect for a young…
> It was a weekend learning project, and all I wanted to do was create a freshman level data structure from scratch.
It's worth mentioning that the implementation difficulty of data structures in Rust is not representative of the general difficulty of programming in Rust. Just because this is hard doesn't make it a bad language. Rust's philosophy is that you deal with the trouble of writing unsafe code each time you need a new low level abstraction, and when done, you don't have to worry about it again.
Also, writing generic datastructures in C++ without falling afoul of UB, and/or getting destruction semantics right can be quite tricky. Rust ... really doesn't have additional issues here; raw pointers in Rust work the same way as in C++, except they're a tad verbose. The only difference is that in Rust you probably want to provide a safe API, whereas in "freshman C++ datastructures" the datastructure does not have the unsafety neatly encapsulated. This is a hard task in both Rust and C++, especially with generic datastructures.
Writing datastructures isn't really a common task. It's a "simple" task because it's simple in C and C++, but here's no real reason it has to be in Rust. You can write inefficient datastructures in 100% safe Rust without too many problems, much like you can implement datastructures in regular-joe Java. Writing efficient, low-level datastructures can be pretty hard, but like I said it's a rare task so not much of an…
Recently experimented a bit with Rust and I found the reverse to be true. You cannot compose types in Rust. You compose behaviors not types. Very important distinction as I found out the hard way.
Take the following example I have found on the net: https://play.rust-lang.org/?version=stable&mode=debug&edition=2015&gist=52feae5c84edb7942d05c8bf112b8237
In that example, both the bicycle and the car have the property `speed`. Imagine you have multiple types now that need to have the `speed` property. You would need to copy-paste the same code for each new type in order for you to be type safe.
Apparently it is called *Monomorphization*: https://cglab.ca/~abeinges/blah/rust-reuse-and-recycle/#monomorphization
From the article:
* But if I want a single queue to be able to handle different tasks, then it's not clear how that could be done with monomorphization alone. That's why it's called "mono"morphization. It's all about taking abstract implementations and creating instances that do one thing. *
Which was exactly what I was experimenting with: A single queue worker that can handle different cases. Honestly, it made Rust almost not worth it for me. Sadly, I was too deep to turn back so I wound up doing the whole thing in Rust. I have tons of copy-paste code. It is ugly and it is bothering me.
> For people like me, if writing trivial data-structures in Rust is a great challenge, it shows that writing other, less trivial things in Rust will be much more challenging than might be preferred.
I understand the source of the sentiment, but also disagree with it. I've been writing Rust code for years and have never had occasion to write my own custom data structure, and (discounting FFI) I've reached for the `unsafe` keyword like twice (which I think I ended up removing anyway, because I was trying to be too clever).
But then again, my background is in higher-level languages (Java, Python) where writing data structures isn't your usual beginner task. I sympathize with C programmers to whom a linked list is the go-to toy learning program, but the urge to resort to unsafe shenanigans to implement self-referential data structures doesn't reflect the typical experience of using the language.
And for those who still wish to persist, may I recommend the book "Learning Rust With Entirely Too Many Linked Lists": http://cglab.ca/~abeinges/blah/too-many-lists/book/