Lock freedom without garbage collection in Rust
aturon.github.io
aturon.github.io
This man knows how to get right down to business.
Anyway, this is an excellent way to present an idea to the public.
Also worth noting, and something I missed when I read the draft of this post: this isn't just an implementation of a lock-free structure: it's a whole library, Crossbeam[1] that helps you implement your own lock-free structures.
> In general, it’s possible to take lock-free algorithms “off the shelf” (the
> ones on the shelf generally assume a GC) and code them up directly against
> Crossbeam in this way.
1: https://crates.io/crates/crossbeam[1]: http://www.mpi-sws.org/~turon/turon-thesis.pdf
[2]: https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
Oh, and thank you for including a colophon, I really wish more books did that :)
The typesetting is quite remarkable. If you're going to procrastinate, this is sure a good way to do it.
Maybe I'm just too used to C and see it everywhere, but in this specific case, I don't really see the the "unique powers of Rust". Personally I find that perfectly alright - there's only few people that actuall will (and can) write correct lock free code, and as long as that lock free code can easily and seamlessly be integrated into the rest of the environment.
I'll echo that Rust really does seem to be something new and exciting in the native land of languages.
I feel like it's still got some rough spots(around FFI and just some APIs still being unstable) but there's so many things to like with the current direction.
clib is marked as unstable - https://doc.rust-lang.org/stable/libc/types/os/arch/c95/type...
Most of the intrinsic types are usable but anything involving strings seems to hit unstable/experimental branch pretty quickly.
I'm sure it'll improve I was just a bit surprised to not see it mentioned in the docs.
(Also, the error message when you don't have a `#![feature(libc)]` should say "hey, please use the external crate thanks")
Yeah, that error message sent me down the wrong path :).
Let me add another plus for Rust is the community around it.
> The operation is unsafe because it is asserting that:
> * the Shared pointer is not reachable from the data structure,
> * no other thread will call unlinked on it.
This is only necessary because the library here is concerned with sharing a data structure among multiple owners (the owners being threads in this case) who all wish to mutate the data structure.There are other places like this where one may wish to subvert the borrow checker, and when such a pattern becomes widely observed it can be placed in the standard library behind a safe interface, (ideally) removing the need for unsafety in client code entirely. The `Rc` smart pointer in the stdlib is one such example of a safely-exposed interface to code that internally uses unsafety to subvert ownership in a specific way. And as long as you trust the compiler to be correct, you can also trust that the "unsafe" code in the stdlib is also correct (or at the very least that the Rust developers are guaranteed to fix any incorrectness that is found).
(On the other hand, I'm not sure what guarantees GC-based lock-free data structures can make in the same situation.)
Not entirely sure how a thread is supposed to set its active bit without racing with a guy who just noticed that all active bits are clear. I guess that's why it says "try to increment the epoch" and not "increment it". i.e. it can fail. EDIT: I guess this is why you go two epoch units back and not one. That, combined with the idea that everybody only goes forward in time, would probably do it.
``` Although limbo lists are accessed using lock-free operations, and garbage collection does not interfere with other mutator processes, this reclamation scheme is not strictly lock-free. For example, a process which stalls for any reason during a shared-memory operation will not observe updates to the epoch count. In this situation the limbo lists will never be reclaimed and memory cannot be reused. Other processes can make progress only until the application reaches its memory limit. This drawback may also affect preemptively-scheduled systems, in which a process may be descheduled in the middle of a shared-memory operation with no guarantee when it will be rescheduled. ```
It does mean that a stuck or killed process can cause rather noticeable pain. With a GC you usually have a upper bound of the amount of memory one stuck process can prevent from being reclaimed, not so with a generation based approach.
On the other hand it dies often voids concerns around ABA style problems.
The epoch algorithm strikes me as pretty much strictly better than hazard pointers.
You say "RCU like this", but AIUI RCU and epoch-based collection like in this article are quite different from each other.
RCU involves no-synchronization reads of a data structure and writers that wait for a "quiescent" state to delete old nodes. It is used for data structures that have pure readers (like a frequently read but infrequently-updated list of things).
Epoch-based GC involves lock-free writes but puts garbage in freelists to be collected at a later time. It is used for data structures that are mostly based around writes (for a stack or queue, both push and pop are mutating operations).
This paper (linked from the blog post) was very helpful in comparing them: http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc0...
However, with both RCU and the epoch-based scheme, you can make quiescent states as fine- or coarse-grained as you desire.
A rather common, in my opinion, way to use something like rcu is to delay freeing (or reusing) memory to the next grace period, without blocking until then. E.g. in the kernel you can use kfree_rcu(..); instead of synchronize_rcu(); kfree(..); for that. That's basically what the epoch based approach does with a the lists of to-be-freed allocations.
RCU is an overloaded name; it's both a family of implementations of epochs, and a pattern for using epoch-like systems. The name literally refers to the latter (a read-mostly RWlock setup where we don't bother protecting the read side of a data structure, but _copy_ and atomically update access to the data, using epochs to dispose of the old version safely) but is often used to describe the whole system (tracking quiescence and determining when disposal is safe.) One could easily use the kernel's RCU (our my userspace one) to build a data structure like this.
Not in my experience.
The programs submitted to the benchmark game currently show Rust faster than g++ in some benchmarks, slower in others, but generally in the same ballpark. Of course this changes as the compilers and the programs improve, and the benchmark game isn't representative of anything in particular, but it illustrates some of what's possible.
http://benchmarksgame.alioth.debian.org/u64q/compare.php?lan...
1. Alioth's Regex DNA: this was one of Rust's worst in the benchmark game. The author (burntsushi) of the Regex library being used (written in Rust) hypothesized that it was because of the algorithm the lib used. He worked on it, and now Rust performs excellently on that benchmark.
2. Alioth's n-body: the fast implementations are directly using SIMD. In Rust that is currently on an active path towards stabilization.
3. A networking micro benchmark -- I lost the link here, but the Rust implementation made the simple mistake of allocation a large array by pushing one element at a time to an initially empty dynamic array. Rust compared well after the fix.
4. Rust's buffered reader zeros it's internal buffer, and its default buffer size is [was?] pretty large. This made some IO operations pretty slow without manually tuning the buffer size, and still left some amount of overhead after tuning. In the Reddit thread where this complaint was brought up someone announced a pull (since merged) to significantly reduce the zeroing overhead.
I found these examples encouraging, except for the last. The former are regular growing pains of any language ecosystem and benchmark implementation. Only the last looked like an issue where Rust's design might cause a measurable run time cost. In all cases it was cool seeing people tackle the issues and get a good speedup. Worth mentioning is that although Rust's benchmark game results are still behind C's, they are now in a similar ballpark with C++'s.
[1] http://benchmarksgame.alioth.debian.org/u64q/performance.php... , https://www.reddit.com/r/rust/comments/3b2i0f/psa_regex_is_n...
[2] https://www.reddit.com/r/rust/comments/3i85lg/simd_in_rust/ , http://benchmarksgame.alioth.debian.org/u64q/performance.php...
[4] https://www.reddit.com/r/rust/comments/3cgaui/trying_to_find...
[Rust/C++] http://benchmarksgame.alioth.debian.org/u64q/compare.php?lan...
1. Rust is working on cross compiling support (very hard atm).
2. Rust can (pretty trivially) interface with C.
1. Cross compiling has worked in rust since before 1.0, but it's required some manual configuration (downloading the platform's stdlib and adding command line switches, etc.). A goal for the future is push-button cross compilation [1]. I'd also add that the standard library has most of what you'd want for cross platform compatibility, from higher-level interfaces that work cross-platform (like std::thread [2]) to lower level bindings for each platform like (std::os::unix::fs [3] or the OsStr system [4]).
2. Yep, C interfaces are pretty trivial. However, they do need to be manually defined. There is no built-in way to parse C header files or declarations. [5]
[1]: http://blog.rust-lang.org/2015/08/14/Next-year.html
[2]: https://doc.rust-lang.org/nightly/std/thread/
[3]: https://doc.rust-lang.org/nightly/std/os/unix/fs/
[4]: https://doc.rust-lang.org/nightly/std/ffi/struct.OsStr.html
LLVM for IR highlighting, Rust for Rust highlighting.
I've tried racer in the past but it just doesn't scale with the current compiler architecture. I'm hoping the ongoing refactoring work will get us a great incremental/parallel/continuous compilation system for autocomplete/red-squigglies.
My two biggest pains are: "trivial" errors (syntax, typos, etc) which I ideally would just see as red squigglies as I go (not a compile-fail loop); and the absolute lack of any kind of incremental compilation (which paired with the community's over-use of generics is super painful for codegen time).
In any case, Rust really shines for the Owned and Shared types, where the affine typing & lifetimes allows sharing to be controlled so that most operations are perfectly (memory-)safe, with compile-time guarantees.
That said, Rust is able to eliminate some sources of unsafety here -- in particular, it guarantees that you have pinned to an epoch before you get your hands on any snapshots, and provides statically safe access to the snapshots for as long as you're pinned. This is very similar to the way that Rust deals with locks, which is explained more in an earlier post: http://blog.rust-lang.org/2015/04/10/Fearless-Concurrency.ht...
I like Mozilla and would like to see Rust succeed, but I just see adoption as too risky right now. It's like when Go was the new-and-shiny; many jumped on the hype bandwagon because it was Google backing it and it was fast, then tried it out and realized it was a language for the <5% of teams that have projects that fit well.
Performance is an awesome thing and there is definitely a place for Rust. But, I don't see it taking the place of C, C++, or Java anytime soon for writing high performance or portable apps. All the same, I look forward to using it in a web browser!
I don't see that all with Go. Go is getting a good degree of traction, because it's a really useful language for a lot of people.
> But, I don't see it taking the place of C, C++, or Java anytime soon for writing high performance or portable apps.
Why not, specifically?
I agree that Go has the traction and community to stay around for the long haul as a niche language.
It's not a replacement for C, and never will be. I can't imagine more than 5% of developers ever using it.
Let's take Java which despite C# is still the number one language in the world to use by number of developers and just compare Go to Java. That's more than fair since the number of Java developers in the world is less than the total number of developers in the world.
Given that, here's data to back my wild claims:
Java is in ~2.7% job postings on indeed.com currently: http://www.indeed.com/jobtrends?q=java&l=
Go(lang) is in ~0.0035% and the adoption curve has slowed: http://www.indeed.com/jobtrends?q=golang&l=
Similarly, in GitHut which compares language use across GitHub, you can see how the amount of Java code dwarfs the Go code currently shared: http://githut.info/
I know, I know- Go still have a great growing community, but it just hasn't taken off the way they would like you to believe. I still think it's a great language, but it isn't making the inroads we'd all believe it has based on the hype. That's not to say it isn't useful- it is, or that developers shouldn't learn it or use it- they should. But, it isn't one of the top languages nor will it be at the current rate of adoption.
> Why not, specifically?
That's a much bigger question, but the answer is: Go is not AngularJS.
What?!! You may ask. Here's what I mean:
In today's development world of every decent language and framework getting 15 minutes of fame, you have to have something really trendy and seemingly cost-saving to get you there. Go is a practical language written for speed (similar to Rust). That is not the Toyota Camry or Honda Civic of languages, that is the high speed locomotive. A different use case, and tough to market.
The point of any given programming language is not to be crowned queen of the programming prom, it's to produce useful software and improve the state of software development. As long as your language meets a minimum threshold for notoriety (which both Go and Rust do), the fact that they have less marketshare than Java is irrelevant unless your sole motivation for learning a language is to get a job at an enterprise company (which is a fine reason to learn a language, but I think you might be on the wrong forum if that's your overriding concern :P ).
A year ago Rust was (to first order) an awkward compromise between Go and C++11, in personality. Today it is strictly a better C++ (although arguably Go has been shifting in the same direction). It's not just a better C++, since there are fundamental ways of thinking about things (which this post touches on) that aren't and never will be pervasive in C++. On the flip side, the library ecosystem is much younger, so that definition of "better" is not yet there. But I'd argue that any long-term projects you might want to start in C or C++ could be better done in Rust, and I'm way more confident of that argument for Rust 1.x than for a hypothetical continuation of Rust as it was about 12-18 months ago.