Truth is that one of the reasons they're "hard" in rust is because it's actually harder than people think to make a proveably correct linked list (in the absence of a cycle-safe garbage collector). It's really just surfacing a cognitive dissonance common to the programming world.
(Note for clarity: closures are also hard to prove correct in the same environment, but there's a lot more need to write them in normal working code)
I think most people definitely underestimate the amount of caution / design care required to implement even something as simple as a linked list with zero bugs, memory leaks, potential infinite loops in member functions, etc.
The Rust compiler prevents entire classes of bugs at compile time, and just requires that you to write an 'unsafe' block if you really want to go ahead with this sort of code without the compiler complaining. This emphasizes that you really do have to be careful and think through the logic and memory ownership semantics of the code you just wrote. People used to GC'ed languages will find this annoying to have to worry about at all, but that is inherently the price you must pay to eliminate GC pauses/overhead.
I'm not saying you should never use data structures that Rust makes hard to write, but that going into Rust thinking it's just going to be 're-skinned C++', or 'as easy as a GC language' is going to be a recipe for disappointment. If you allow yourself to learn a new way of thinking about low/systems-level coding, you may be pleasantly surprised. But if you're too "set in your ways" (whether it be of C/C++ or JS/Python/etc.), you're not going to see Rust's benefits.
Rust is a deeply different language than C/C++. I think people forget this, primarily because Rust is so powerful and efficient (with no inherent language overhead, allowing it to be used even in embedded environments and other systems programming tasks).
That's all true, if you squint really hard, gloss over the equivalencies, discount the additional complexity, and ignore the basic simplifying elegance of linked-lists (particularly the so-called intrusive data structure implementations). But it's dramatically overstated because of a certain defensiveness.
What is absolutely true is that cyclical referencing is the bane of static analysis, and anathema to a language that leans so heavily on its typing system for modeling language semantics. What you think that implies depends on your faith in how far type-based, lifetime-based static analysis can go toward addressing larger issues in the software ecosystem.
that's true on any CPU with more than 16kb of cache. linked lists were a good idea at the time of 486, not so much at the time of modern CPUs with 8+ megabytes of L3.
See https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vecto...
[1]: https://www.youtube.com/watch?v=aWbGPMxs0AM
[2]:https://twitter.com/bcantrill/status/1035335403186806784
[3]: https://twitter.com/bcantrill/status/1038495464692146176
"So that was a surprise. (...) I've done zero profiling on this. I've made absolutely zero attempt to make this thing faster. None. In fact, you can pretty reasonably argue that I've gone out of my way to make it slower. And we are 40% faster than my C."
Which doesn't mean that rust is faster than C, but that changing your approach can, in fact, lead to results you wouldn't have expected.
« In hindsight and with a deeper understanding, it’s not surprising why a doubly linked list is so problematic. Each variable can only have 1 owner. If prev and next both hold pointers to a middle node, which is the owner? They can’t both be the owner. If one is the owner, another can borrow. But Rust won’t let you mutate while someone else is borrowing, so neither could actually modify the list! In general, if you have loops in your object graph you’re out of luck. »
So the solution for doubly linked lists is to write some "unsafe"-marked Rust once, really bang on it, and ship that in a crate full of generic data structures. This is acceptable to me; it's no worse than C.
With closures, it sounds like the issue is not that it's impossible, but that the lifetime and mutability analysis get tricky in some cases.
That's a very shallow concern. Writing a "doubly linked list" is what you do in Rust with unsafe or will several other ways. It's also not something you usually do, you just use one of the several implementations in the library and third party libraries and get on with your actual program.
And this doesn't show closures to be that hard at all. It's the basic dynamic vs statically typed language thing, plus a couple of caveats to keep in mind. Hardly anything to write home about.
The fact the tons of people use Rust for production code already, and love it, doesn't give these concerns pause?
Which means you either need some sort of garbage collection setup, or reference counting (with cycle collection), or some sort of indirection where you really hold references to a "tree + node" pair and then have to worry about what happens when a node moves from one tree to another. Or something else, other than just having a bunch of objects that all point to each other without any explicit ownership semantics...
https://github.com/servo/servo/blob/master/components/script...
https://manishearth.github.io/blog/2015/09/01/designing-a-gc...
What is difficult is to implement it in the safe Rust. But then try to proof that, say, C++, code doing the same is safe. It is very hard.
Besides, if one really wants cyclic structures in safe Rust, one can always do ancient Fortran trick and just represent pointers with array indexes. It may even be faster due to more cache-friendly memory layout.
[1] Bulletproofs crypto library: https://github.com/dalek-cryptography/bulletproofs/
[2] https://blog.chain.com/faster-bulletproofs-with-ristretto-av...
[3] https://blog.chain.com/bulletproof-multi-party-computation-i...
[1]: https://www.reddit.com/r/programming/comments/7zbi6s/why_wri...
As both a C/C++ developer with more than a decade of experience, and a Rust developer, I'll posit that if you are smart enough to master Rust, you still aren't smart enough to write safer C++. Not even close. Rust might enlighten you in some ways, and avoid you doing some mistakes in C++, but without e.g. a borrow-checker, there are still too many ways to shoot yourself in the foot in C++, that Rust would find at compile time, while the equivalent C++ code would fail at runtime. If you're lucky and happen to hit the error conditions when you test it.
Easy for you to say as a C++ developer! As someone who came to Rust as a JavaScript/PHP/Python developer, I greatly appreciate Rust checking all my work. I'm plenty smart enough to work out the problems that the compiler picks up (once I have an error message I can google for explanations and solutions), I just don't/didn't have the experience to know that my naive code was going to cause problems.
This theory says well written software doesn't (and can't) simply stitch together various data structure implementations through generic interfaces. That in robust, elegant software there's no dividing line between where the fundamental data structure is implemented and where the application specific logic resides.
One classic example is the Thompson NFA. The argument is that the path to devising elegant solutions like the Thompson NFA is to think in terms of simple data structures tailored to particular problems. A toolbox of pre-implemented data structures is of little value because implementation matters and often needs to be tailored to the problem. It's not a matter of performance; it's that if your data structure implementations aren't tailored to the problem your use of them will require overly complex, opaquely layered code and you would (justifiably) architect your solution some other way; a way better suited to gluing together libraries but poorly suited to the actual functional problem.
I don't think this particular theory is right in any absolute sense. But I think it's more right in the domain that Rust targets, which means I believe the cost of implementing things like linked-lists and trees is underestimated; and that how often people will end up resorting to unsafe code (or recapitulating reliance on unchecked memory access, such reinventing pointers as indexes into arrays) is underestimated.
Most of my theoretical computer science knowledge was based on the fact that there are a bunch of basic well known algorithms and data structures and you build everything out of this.
Do you have resources on the approach "invent" such things on your own so they are better suited for the problem?
Rule 5. Data dominates. If you've chosen the right data
structures and organized things well, the algorithms will
almost always be self-evident. Data structures, not
algorithms, are central to programming.
I read about the analysis of Thompson NFA, in the context a simplified version implemented by Rob Pike, in the chapter that Brian Kernighan wrote for "Beautiful Code: Leading Programmers Explain How They Think". Kernighan and Pike also wrote "The Practice of Programming", where the simplified version was originally published. Perhaps I'm making too much of that example, but it's what popped into my head.
Basically I think the idea is that if you farm all the complex data structure and algorithmic code to generic libraries, you're not apt to wrestle with the core functional problems. What functional features are you willing to sacrifice, if any, to create a more elegant solution? You can't begin to approach such a question unless you're also thinking, in very fundamental terms, about how to implement and combine the data structures and algorithms. There's an interplay between how you model a problem and how you implement it that effects every aspect of your design--or should effect every aspect of it. Using an off-the-shelf implementation brings a different cost-benefit profile, including wrt to composition. Sometimes it's better to use off-the-shell code, sometimes not; but you have to be prepared to think holistically about the problem.
A language that makes it more painful to implement or apply certain approaches internally effects your calculus from the outset.
A very simplified example: say you have some problem where a stack data structure (i.e. LIFO) is the obvious solution. If you think in terms of using off-the-shelf code, then in a language like Rust you're going to use something like a Vec or w'ever. But if your language supports recursion atop a dynamically growable stack, then a recursive solution will often be the simpler and more elegant approach. Both are, fundamentally, using stack data structures. But how you implement the stack can make a world of difference; conversely, which approach you choose is highly dependent on the problem and on other aspects of the larger implementation.
Taking that process to its logical end can result in a language like Go, where they've taken one of the primary problems in expressing highly-concurrent tasks, expressing a multitude of serial flows of execution that dynamically branch and collapse (not unlike the Thompson NFA), into the core language. A dynamic, growable call stack is fundamental to their approach.[1] Now step back and realize that Go itself is a solution to the specific problem of writing network services. It's obvious to most people how Go has sacrificed certain use cases for the benefit of others. It's an elegant solution for its problem domain because of how they were willing to apply and layer their abstractions. How you implement generic data structures matters. Among other things, you can combine abstract data structures more creatively and more powerfully when you're implementing them with a particular, shared goal mind.
Another good read along these line is, "Passing a Language through the Eye of a Needle: How the embeddability of Lua impacted its design". (https://queue.acm.org/detail.cfm?id=1983083) It discusses how the semantics of the Lua language were constrained by its problem domain, on the one hand; and how they were made more powerful by novel implementation solutions (e.g. clever approach to compiling closures that resulted in elegant code with efficient runtime behavior), on the other.
[1] Whereas other languages, like Python, JavaScript, and C++ solve concurrency differently (e.g. using Promises or async/await) because they're limited in how far down they can push the implementation of the call stack.
It true that there's an argument that says you often get more dividends for your effort wrestling with larger architecture and design than about, e.g., how easily you can write (or reuse) a binary tree implementation. A library won't help you implement the binary tree implementation for accessing a filesystem's on-disk data structures, for example. The value of some of the most beneficial use cases is often precluded to generic implementations. I think that reality played into why they discounted the value of generics, making them a low priority, but it's subtle and complex.
Generics (and meta programming more generally) cut both ways in terms of cost and benefit, at least when you think more holistically, and especially when you think about the complexity of the language and language implementation. It's a complex topic. There's no right answer, at least no right answer without a careful accounting of the context--the problems you're trying to solve and which aspects are the most critical or the most difficult to solve. That's the point.
Another way to think of it is that Go's structural typing (loosely speaking, duck typing) had much more bang-for-the-buck than generics, both abstractly and concretely. If you came to that conclusion early on, you may design and implement the language in a way that makes generics even more difficult to fit into the language. The original decision could have been perfectly legitimate, but over time it might seem like you simply didn't appreciate generics at all, especially when criticisms take the benefits of the existing design for granted without thinking about path dependency, etc.
FWIW, I've never written a single line of Go code.
Would be nice if there was some theory around this I could follow :)
Lots of other problems are.
The core of it is two things: mindset, and how programmers think about learning languages.
Mindset: there's two things at play here. The first is that C programmers tend to reach for linked lists by default. It's a CS 101 data structure. Not super hard. A Rust programmer, however, would reach for a vector (or a deque) by default. For many use-cases, these structures are better, thanks to amortized allocations + cache reasons. As always, depends on exactly what you're doing. The second mindset issue is write vs use; C programmers tend to write their data structures themselves. Rust programmers tend to use packages. If you've determined that you need a linked list in Rust, you don't start writing one: you "use std::collections::LinkedList;". It's a doubly-linked one, so maybe that's not what you need. In that case, you go on crates.io and see if someone has already written what you need. (225 hits incidentally: https://crates.io/search?q=linked%20list) Only if that fails do you write it yourself. As the ecosystem has filled out, this happens increasingly infrequently. So "a linked list is painful to write" just doesn't apply to the vast, vast majority of Rust programmers who are simply getting work done.
Learning: because linked lists are a CS 101 data structure, they're something people reach for when learning Rust. But different languages are different, and Rust is not C. Writing a good data structure isn't a beginner Rust topic, it's an intermediate to expert one. There's stuff Rust makes easy that C makes hard as well. You can't assume that topics are equally difficult across the languages. Even then, there's http://cglab.ca/~abeinges/blah/too-many-lists/book/.
TL;DR: linked lists being painful to implement is sorta true, but also not really relevant, other than people who try to learn Rust by building them and having a bad time. (Which is unfortunate, but many people don't as well, or have at least heard that they're hard and so have the right expectations going in.)
Now, I've gotta get back to my benchmarks: std::collections::LinkedList is twice as fast as my straightforward C linked list, and I gotta figure out where I messed up. I'll check back later for replies.
(If you're interested in this benchmark I'm working on, https://godbolt.org/z/lF1D85 is the disassembly. They look so close, I have no idea why 100,000 pushes, the Rust impl is taking 7.9038 ms on average, whereas the C impl is taking 15.413 ms. That seems very wrong...)
Not sure why you bring this up, since sooner/later people are going to need to implement their own data-structures(and this ownership problem will surface) and being it harder to implement is not relevant to package management(after all somebody did just implement that and made it available).
These two blog posts have really nothing to do with one another, are describing unrelated problems with unrelated things, sharing only the fact that they both have to do with the Rust language and both describe something as difficult (but meaning pretty different things by the word) and you draw a conclusion that "Rust is not a language to 'get things done.'"
I don't know how to prove that Rust is "a language to 'get things done'" - this seems like an almost meaningless qualifier - but many people (including me) are getting things done using Rust every day.
It is precisely because Rust makes it difficult to implement a lot of bad ideas, that I find myself spending a tiny fraction of my time debugging Rust applications vs C/C++/others (including even high level GC languages).
I love that Rust encourages inherently reliable code, while also not stopping you from writing "unsafe" blocks in the (rare) cases where they're necessary. In fact, in every case so far where I thought 'maybe I should try an unsafe block', I started to realize that implementing this idea or data structure was actually riddled with hard memory management problems, or race conditions, etc. that Rust was preventing from even being possible at all.
P.S. Of course there's a steep learning curve to Rust at first, but it's not fair to count that against Rust -- unless you also weigh against C++ all the years it takes to really master it. IMO, Rust's learning curve is far less steep and painful than C++, it's just that many of us are biased and comfortable having already climbed the C++ learning cliff (so we tend to forget it is there, and how bad it is).
I'm sure there's a package that makes this easy, but this took me about ten minutes to toss together from scratch.
I love Rustdoc, but I really wish it wasn't so obtuse when it came to casually browsing the various iterator traits. Perhaps Steve, for the benefit of myself and thread parent, you could point us to some better-edited literature for the various iterator methods?
P.S: just wanted to add, if I were faced w/ this issue in production code, I likely would've just reached for the excellent byteorder[2] crate. It's so useful for "bit twiddling" like this.
[1]: https://play.rust-lang.org/?gist=4b4ff7263d9744caeb8bacd4c0d...
[2]: https://docs.rs/byteorder/1.2.6/byteorder/trait.ReadBytesExt...
> Perhaps Steve, for the benefit of myself and thread parent, you could point us to some better-edited literature for the various iterator methods?
I used that page to find this. I knew it was "chunks" or "windows" or something, so I just looked at them (I guessed windows, but I was wrong).
It took hours to figure out how to implement this in rust: https://github.com/sctb/lumen/blob/master/bin/lumen
If you want to see an "expert" programmer's attempt at making sense of the language, here you go: https://gist.github.com/shawwn/4d7a89188cac72f3e591f47c84d3c...
Now that it's done though, I see why people fall in love with Rust. It's really satisfying seeing Lumen's startup time drop from 200ms to 100ms.
But yes, like -- dude, at one point I just wanted to write a for loop like this, to grab some environment vars:
let mut lumen_host = "luajit";
let mut lua_path = "";
let mut node_path = "";
for (name, value) in env::vars() {
if name == "LUMEN_HOST" {
lumen_host = &value;
} else if name == "LUA_PATH" {
lua_path = &value;
} else if name == "NODE_PATH" {
node_path = &value;
}
}
println!("{} {} {} {}", bin, lumen_host, lua_path, node_path);
That said, Cargo is amazing. It's truly a wonderful, delightful piece of software. Cargo crates plus a dynamic language seems like a recipe for success.
let lumen_host = env::var("LUMEN_HOST").unwrap_or(String::from("luajit"));
let lua_path = env::var("LUA_PATH").unwrap_or(String::new());
let node_path = env::var("NODE_PATH").unwrap_or(String::new());Out of curiosity, did you spot any other antipatterns? I'm sure there are a bunch: https://gist.github.com/shawwn/4d7a89188cac72f3e591f47c84d3c...
I poo poo the language a lot, but it's satisfying to get the hang of it.
fn realpath(path: &str) -> &str {
unsafe {
return CStr::from_ptr(
libc::realpath(
path.as_ptr() as *const i8,
0 as *mut i8
)).to_str().unwrap();
}
}
That being said.. A lot of this stuff is things that already exist that you don't need to write yourself. dirname, basename, join, even s is .to_string. It's also the same as str. getenv is env().unwrap_or().
> Curious about that block in particular.
I would call https://doc.rust-lang.org/std/fs/fn.canonicalize.html and be done with it, instead of importing libc and going through all of this.
In the end, this should be like 40LOC, 50 tops, if you made use of the standard library rather than trying to re-implement it all :)
The question is why. The relevant examples are everywhere:
https://doc.rust-lang.org/std/env/fn.var.html
https://doc.rust-lang.org/std/env/fn.vars.html
https://doc.rust-lang.org/book/second-edition/ch12-05-workin...
The reason it's difficult is that it simultaneously introduces the concepts of optionals, unwrapping, string processing, variable assignment, and lifetime management. It's not like it's impossible to figure out. I was only saying the workload was similar to "baby's first vi session".
That would be like criticizing vi based on "baby's first vi session", because "couldn't even exit the editor!".
On the other hand, you're absolutely right: the hypothesis is, given two equally-experienced programmers, one of them a Rust aficionado and the other a LuaJIT maniac, the LuaJIT dev will deliver reliable and maintainable software with an order of magnitude less effort. So you're right, that remains to be seen (to put it mildly).
Looking forward to seeing how close I can get to XSV's performance. It's a great benchmark.
You have a couple of helper functions, like `s` and `str` which you might consider using `to_str` and `to_string` in their place, as it's more idiomatic to use them directly rather than save characters.
And obviously you can replace `getenv` with `env::var`.
1: https://doc.rust-lang.org/std/path/struct.Path.html#method.c...
Criticizing a language by how easy it is to write the "first 20 lines" doesn't sound really fare...
But writing a doubly linked list was already shown to be difficult [1], and now closures are too ... It really feels like this is not a language to "get things done". Please let someone prove me wrong.
[1] https://rcoh.me/posts/rust-linked-list-basically-impossible/