10 ms·
Lock freedom without garbage collection in Rust
- sbahra 11y agoStand-alone EBR also available at http://concurrencykit.org http://concurrencykit.org
- sbahra 11y agoNote that epoch reclamation is only competitive with amortization, otherwise you may as well use hazard pointers for simple structures to benefit from stronger progress guarantees. Of course, QSBR is best if you have quiescent points.
- steveklabnik 11y agoI'm extremely excited about posts/libraries like these. They really show off the unique powers of Rust in a way that's a bit more compelling than "Rust is just C++14 with a bit stronger guarantees and more clean semantics." 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 https://crates.io/crates/crossbeam
- eternalban 11y agoIs this based on his thesis?
- steveklabnik 11y agoI haven't read it. On IRC he said he was gonna post this and then go to lunch, but given that he submitted it here, I'm sure he'll be back to elaborate at some point :)
- brson 11y agoNo, this isn't an implementation of Aaron's thesis (reagents [1]). It's an implementation of Keir Fraser's thesis :) [2] [1]: http://www.mpi-sws.org/~turon/turon-thesis.pdf http://www.mpi-sws.org/~turon/turon-thesis.pdf [2]: https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf https://www.cl.cam.ac.uk/techreports/UCAM-CL-TR-579.pdf
- doomrobo 11y agoWow, I am very impressed with the typesetting on [1]. Jealous, even...
- bsder 11y agoSomeone procrastinated a lot. :)
- aturon 11y agoNot toooo much, but I will say that feeling inspired by the typesetting helped keep my motivation up for all 299 pages...
- kevin_thibedeau 11y agoPage 9 has a TL;DR footnote. Degree granted.
- doomrobo 11y agoI totally get that. Even though I spent 50% of my time on a take-home math final writing it in XeTeX from scratch (or "article"), it was still worth it, even if only for the motivation. I love the choice of Minion in your paper, but I needed something more math-friendly so I went with my other favorite: Arno Pro. Oh, and thank you for including a colophon, I really wish more books did that :)
- bsder 11y agoI was mostly joking ... but procrastination is sometimes valuable in and unto itself. The typesetting is quite remarkable. If you're going to procrastinate, this is sure a good way to do it.
- sanderjd 11y agoI agree with you, and this post and the library are awesome, but honestly "it has all the great stuff C++14 has, but without the decades of compromise" is not a bad start for a pitch either. Playing in the same league as C++14 is already a major achievement for a language.
- steveklabnik 11y agoI think so too, but it depends on who you're talking to.
- anarazel 11y ago> I'm extremely excited about posts/libraries like these. They really show off the unique powers of Rust in a way that's a bit more compelling than "Rust is just C++14 with a bit stronger guarantees and more clean semantics." 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.
- kibwen 11y agoUsing the borrow checker to help enforce correct usage of the API is indisputably unique, given that C doesn't have anything approximating a borrow checker.
- vvanders 11y agoAwesome stuff. 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.
- rhelmer 11y agoWhat do you feel is rough around FFI? Safer, zero-cost bindings to C libraries - what's not to like? :)
- vvanders 11y agoCString::from_ptr is unstable - https://doc.rust-lang.org/stable/std/ffi/struct.CString.html https://doc.rust-lang.org/stable/std/ffi/struct.CString.html clib is marked as unstable - https://doc.rust-lang.org/stable/libc/types/os/arch/c95/type.c_char.html 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.
- steveklabnik 11y agoYou should use libc from crates.io, which is stable. Not the compiler-internal one you linked to.
- vvanders 11y agoAh, the docs around FFI say that libc is a part of the standard library so it wasn't clear that I'd have to pull that from crates.io.
- steveklabnik 11y agoHmm, can you point me to where they say that so I can fix it? Seems bad. (Also, the error message when you don't have a `#![feature(libc)]` should say "hey, please use the external crate thanks")
- kbenson 11y agoLet's see, a TL;DR, then a table of contents list, then straight to benchmarks... This man knows how to get right down to business.
- yokohummer7 11y agoActually, as I'm so used to the articles that place benchmarks at the end, I immediately scrolled down to the bottom after reading the preface. Then I realized the pretty graphs are at the beginning. Anyway, this is an excellent way to present an idea to the public.
- sitkack 11y agoLooks like the OP took https://xkcd.com/773/ https://xkcd.com/773/ to heart.
- srean 11y agoThis is gold. Just had to say it.
- medecau 11y agoI suggest experimenting with horizontal bar graphs.
- ahh 11y agoVery nice. RCU like this can be very effective (we have a custom per-cpu version based on https://lwn.net/Articles/650333/ https://lwn.net/Articles/650333/ here, which scales better than per-thread versions for obvious reasons.) I'm glad to see more wide use of the techniques.
- haberman 11y agoCool! Who is "we" and where can this code be found? 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).
- arielby 11y agoCould someone explain the big difference between RCU and epoch-based reclamation? It seems that the only difference is that RCU has quiescent periods between reschedules and epoch-based has them when you don't have a Guard struct active. Seems like six of one, half a dozen of the other.
- aturon 11y agoThey are very similar; I think of the epoch scheme as a particular way of doing RCU that does not impose the need to find quiescent states yourself (RCU can be employed in userspace as well if your application can provide quiescent states in some way). This paper (linked from the blog post) was very helpful in comparing them: http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc07.pdf http://csng.cs.toronto.edu/publication_files/0000/0159/jpdc0...
- arielby 11y ago
- klickverbot 11y agoGiven that about every other line in the example stack implementation is marked as "unsafe", I fail to see how Rust is any more safe or well-suited for this than other low-level programming languages (C++, D, etc.).
- dbaupp 11y agoI see 3 lines/expressions marked `unsafe` in http://aturon.github.io/blog/2015/08/27/epoch/#treiber%27s-stack-on-epochs http://aturon.github.io/blog/2015/08/27/epoch/#treiber%27s-s... and a tweaked `unlinked` API could cut that down to 2, and removing the unsafety from `cas_shared` (which doesn't strictly need it, but is a major contributor to any issues that could occur) would cut it to 1. Those lines are exactly the danger-points of the data structure, i.e. where misuse can cause use-after-free. 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.
- SamReidHughes 11y agoThe number of individual lines marked "unsafe" isn't what's important. The safety of those lines relies on invariants put in play by by the rest of the code. All the code behind an asserted-to-be-safe API has to be correct, or incorrect but lucky, in order for the data structure to be safe.
- kibwen 11y agoAnd yet Rust still provides tremendously more type safety in this application thanks to the lifetime system statically verifying the accessibility of the guarded data. It's true that unsafety is a stateful property than a local one, but unsafety still has to involve the unsafe block somehow and that's enormously useful for auditing, debugging, and providing general assurance towards code correctness.
- bjz_ 11y agoThe important thing is that the unsafe implementation satisfies the invariants of type system. So the unsafety is contained within a much smaller surface area than those other systems programming languages.
- imh 11y agoI've been something wondering something for a while now. Rust is supposed to be a kind of C/C++ replacement, right? But the last I heard it's still much slower. So what's the roadmap to speeding it up? Googling for it failed me.
- dbaupp 11y agoThere may be cases where the compiler doesn't optimise as well as older C/C++ compilers (e.g. in my SIMD work, C/C++ code compiled with GCC occasionally comprehensively beats both the same code compiled with Clang and equivalent Rust with rustc (both built on LLVM) due to better optimisations and instruction selection: not a language issue), or where the pure-Rust libraries aren't as optimised as C/C++ equivalents. However, my experience is that it is rarely a lot slower.
- pcwalton 11y ago> But the last I heard it's still much slower. Not in my experience.
- mbrubeck 11y agoIn general it's possible to write Rust code that is competitive in speed with C and C++. Some safety features like bounds checking do have a small performance cost, though in typical performance-sensitive code it is on the order of 1–2%. You can write unsafe code to avoid the penalty when really necessary. 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?lang=rust&lang2=gpp http://benchmarksgame.alioth.debian.org/u64q/compare.php?lan...
- Veedrac 11y agoRust has also yet to finalize SIMD, which will help a ton on some where Rust is behind. http://huonw.github.io/blog/2015/08/simd-in-rust/ http://huonw.github.io/blog/2015/08/simd-in-rust/
- merb 11y agoas browsing the api docs I kinda like lots of things from rust however, how is the portability ie. target windows/linux/mac at once? is it easy to cross compile? is it easy to include c/c++ header files and use them? kinda like to link with nuance c sdk
- kansface 11y agoTo the best of my knowledge: 1. Rust is working on cross compiling support (very hard atm). 2. Rust can (pretty trivially) interface with C.
- mastax 11y agoSome things I'd add: 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 http://blog.rust-lang.org/2015/08/14/Next-year.html [2]: https://doc.rust-lang.org/nightly/std/thread/ https://doc.rust-lang.org/nightly/std/thread/ [3]: https://doc.rust-lang.org/nightly/std/os/unix/fs/ https://doc.rust-lang.org/nightly/std/os/unix/fs/ [4]: https://doc.rust-lang.org/nightly/std/ffi/struct.OsStr.html https://doc.rust-lang.org/nightly/std/ffi/struct.OsStr.html [5]: https://doc.rust-lang.org/nightly/book/ffi.html https://doc.rust-lang.org/nightly/book/ffi.html
- steveklabnik 11y agoThere is https://crates.io/crates/bindgen https://crates.io/crates/bindgen but it's not perfect.
- merb 11y agowhat editor do you guys use? or what editor has the best rust support, yet? In golang code was easily written via st2/st3
- rcthompson 11y agoIsn't there theoretically a risk that one thread could hang indefinitely while accessing (or holding a reference to) the data structure, which would prevent the epoch from ever advancing and prevent all memory from being reclaimed? (On the other hand, I'm not sure what guarantees GC-based lock-free data structures can make in the same situation.)
- aturon 11y agoYes. In practice this is extremely unlikely for correct lock-free structures. But you can also protect against it by releasing the epoch on every iteration of the retry loop, rather than just at the outset. (This may be a good idea for other reasons.)
- asveikau 11y agoIf I read correctly, you only increment the epoch when the active bits for the current epoch are clear. As long as your stalled thread doesn't clear its active bit at an unsafe time, the epoch will stall with it and you'll be ok. 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.
- sanjoy_das 11y agoFrom the thesis the post linked to: ``` 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. ```
- anarazel 11y agoThe epoch based approach basically is on of the many variants of RCU (as e.g. used by the Linux kernel - thoroughly documented on lwn.net BTW). 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.
- anarazel 11y agoOh, one more thing: often an approach based on hazard pointers allows to reduce the impact of a stick or slowed down process, without using a GC. And while stool protecting against ABA. Another good thing is that luckily the patent application around it was rejected.
- pcwalton 11y agoHazard pointers aren't any better when it comes to stuck processes, right? If you aren't removing your nodes from the hazard pointer list, you're stopping reclamation just as with this algorithm. The epoch algorithm strikes me as pretty much strictly better than hazard pointers.
- sbahra 11y agoHP is much more granular and a stuck thread does not inhibit system wide progress (yes, the slots won't be reclaimed but other entries will continue to be reclaimed).
- pieguy 11y agoA couple years ago I saw a 3.5x improvement migrating a lockfree skiplist from hazard pointers to epochs. The problem with hazard pointers is that they require memory barriers after every assignment, whereas epochs only require one at the start.
- littlewing 11y agoI tried Rust about a year ago, and it was pretty horrible. Not intuitive and broken back then. Maybe it's better now, and benchmarks are great, but also show me its community and how practical and easy it would be to use. 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!
- pcwalton 11y ago> 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. 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?
- deleted 11y ago[deleted]
- littlewing 11y ago> 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. 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= 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= 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/ 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.
- unfamiliar 11y agoFor each use of unsafe in Rust code, presumably the developer sees some safety guarantee that the compiler does not understand but that he thinks will guarantee that the code is indeed safe. Can anyone shed light on what form these guarantees (that are not seen by the borrow checker) take, and whether it will be possible in future Rust versions to write such code without unsafe (either by improvements to the borrow checker or implementation of an additional safety checker)?
- kibwen 11y agoUsage of `unsafe` generally has to do with subverting the Rust compiler's notion of ownership. Take a look at this snippet from the OP discussing the usage of unsafe code in the client example: > 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).
- unfamiliar 11y agoI understant those concepts. My question was more along the lines of, could the code you mention from the article one day be written without unsafe? Somehow the programmer is very confident that neither of the two restrictions you mention will be broken. Is there any way that it can be proven from the code that they will not be broken, and therefore remove the need for unsafe? Or, if safety can not be proven from the code, how is the programmer so certain of it?