10 ms·
Lock-Free Rust: Crossbeam in 2019
- jph 8y agoExcellent! Crossbeam is for concurrent programming. Crossbeam provides lock-free data structures (e.g. ArrayQueues), thread synchronization (e.g. ShardedLock), memory sharing (e.g. AtomicCell), and utilties (e.g. Backoff). Thank you to the author and team! Next I am very much looking forward to a Crossbeam implementation of the LMAX Disruptor ring queue: https://lmax-exchange.github.io/disruptor/ https://lmax-exchange.github.io/disruptor/
- strictfp 8y agoLMAX? Really? Did you get LMAX to work well? I never did.
- jph 8y agoMore specifically, I mean a Rust ring buffer data structure, implemented by using Crossbeam tooling, and sized to fit into CPU cache. For readers who are interested: https://dzone.com/articles/ring-buffer-a-data-structure-behind-disruptor https://dzone.com/articles/ring-buffer-a-data-structure-behi...
- presscast 8y agoI've been looking for something like this in Go (yes, yes, I know... lack of generics...). Does such a thing exist?
- majewsky 8y agoI doubt it. Go has good performance for most applications out of the box, but if you're hitting the limits of what `chan` can do, it's either about to get very ugly (which goes against everything that Go stands for) or you should be looking at something like Rust at least for the hot paths.
- bpicolo 8y agoThe one thing I would love to see a good story in chan/go concurrency in general for still is 1-to-n fanout. Right now a lock and a loop seems to be the answer, which is a bit of a blunt tool. Possible I'm missing an option, though!
- Thaxll 8y agoNot really if chan are problem perf wise then you use mutex, it doesn't have to be ugly.
- vardump 8y agoMutexes cause performance problems.
- Thaxll 8y agoWhat I'm saying is if channel are too slow you can re implement something with mutex that will be faster and it doesn't have to be ugly. https://youtu.be/DJ4d_PZ6Gns?t=535 https://youtu.be/DJ4d_PZ6Gns?t=535 ( it's one of the best Go performance video on Youtube )
- jerf 8y agoThere are applications for which even that is not enough. When you get to that point, it's best to not use Go. In fact it's best to have known that you would get to that point and not use Go in the first place. One example is high-performance routing on 10Gbps networks using user-space networking. Pretty much every cycle counts into your throughput numbers, because the rest of the hardware can barely keep up with the network card even before you're trying to do something. Go is a poor fit for this use case. (This from someone who has been accused of being a Go shill. I use it a lot and like it a lot professionally, but it is no more suitable for every task than any other language.)
- jasonwatkinspdx 8y agoThere are some similar lock free data structures in golang up on github such as "onering". One challenge of writing this kind of code in go is that go routines are not pre-emptive, so you can't just port over an implementation that works in c.
- nindalf 8y ago> So these are the things I’d like to see in Crossbeam this year: AtomicReference and ConcurrentHashMap written in Rust. Really looking forward to ConcurrentHashMap.
- pedrocr 8y agoI've hacked around this issue in a contended hashmap by doing a Vec<RwLock<HashMap>> where you index into the Vec with the first bits of the key hash and then use the HashMap within it: https://github.com/pedrocr/syncer/blob/master/src/rwhashes.rs https://github.com/pedrocr/syncer/blob/master/src/rwhashes.r... Worked fine but a full ConcurrentHashMap would be much nicer.
- pas 8y agoAny thoughts on evmap?
- pedrocr 8y agoI had never seen it. The API seems more complex to support consistency/performance tradeoffs. I'm not sure if it would work in my case as I definitely want writes to block if two threads are accessing the same entry. It also doesn't support concurrent writes so that would be a huge penalty. It may very well be that my hack is actually a very reasonable way to go about this. If I need more concurrency I can just increase the number of bits of the hash and get more individual buckets. It does make me slightly uneasy that when two keys hash to the same prefix I end up with a pathological worst case when I should get perfect scaling instead because there's no actual contention.
- pas 8y agoThe Vec<RwLock<HashMap>> seems like a great hack, though you might still benefit from trying to come up with a scheme that avoids that RwLock (which internally uses a Mutex - as far as I know, even on reads), which can be slow if you have a lot of reads. (That's why evmap [and most lock-free structures I've ever heard of] use epochs [which is kind of like double buffering writes to batch up updates].)
- CyberDildonics 8y ago> the blog post titled Lock-freedom without garbage collection, which demonstrates that one doesn’t need a language with a tracing garbage collector to write fast lock-free programs. The secret sauce is a technique called epoch-based garbage collection, which is much different from traditional garbage collectors and is easily implemented as a library. I'm not sure where there is a focus on lock free programming needing any kind of garbage collection. Garbage collection is just for heap allocation and there are already lock free heap allocators. Memory allocation isn't, in my experience, a major difficulty of lock free data structures.
- gpderetta 8y agoThe issue is memory reclamation in node based data structures with multiple concurrent lock free writers. With GC it is a non issue. Otherwise you have resort to reference counting (or GC by another name), hazard pointers, RCU or similar.
- Diggsey 8y agoYep, but even reference counting doesn't really help: the basic building block of many lock free algorithms is the ability to read/write a reference to/from a shared location atomically. With a reference counted pointer, you cannot "read" it without incrementing the count, or else someone else might drop the count to zero and free the memory. You would need hardware support for atomically reading a pointer, dereferencing it, and then incrementing the value at that location. GC (whether tracing or epoch based), hazard pointers or avoiding dynamic memory allocations in the first place (so all memory is pre-allocated, outside of the lock free parts) are the only solutions to this I'm aware of.
- gpderetta 8y agoTrue. IIRC there are ways [1] to implement try lock free updates of reference counted pointers but they are a bit exotic and not cheap. [1] at the very least you can implement a lock free n-CAS operation given a plain CAS.
- 8y ago
- crimsonalucard 8y agoForgive me, I'm not that familiar with rust, but I assumed that borrow checking got rid of the notion of two threads sharing the same data structure and therefore got rid of the need for locks? What's going on with this library? Are locks often used in rust?
- winstonewert 8y agoNo, Rust has locks and shared data structures. What it does is enforce their usage. It will be a compile error if you try to modify the same data structure from multiple threads without a lock.
- steveklabnik 8y agoYou sometimes do not need a lock, depending. Scoped threads can have two different threads modify two different elements of a vector simultaneously without locks, for example.
- pcwalton 8y agoThe borrow checker allows two threads to share the same data structure immutably without locks. If you need to mutate the data structure from multiple threads, you need some kind of synchronization, and the borrow checker enforces that this synchronization is present. Rust doesn't prevent you from using synchronized shared mutable state, though of course if you want to program without any shared mutable state that's a perfectly valid option too.
- geofft 8y agoThe borrow checker tracks two kinds of borrows (in addition to ownership), &T for a constant reference and &mut T for a mutable reference. But it's not really about constant/mutable, it's really about shared/unique or, if you prefer, reader/writer. Essentially the borrow checker is a compile-time reader-writer lock: multiple threads or multiple structures can have a read borrow at once, but only one can have a write borrow and you need to get rid of the read borrows first. But there are common use cases where you need to have concurrent write access to the same structure from multiple threads. The way to implement this is "interior mutability," where you write a method that takes an &self - a shared reference - but can still mutate it. A simple example of this is the std::sync::atomic types (https://doc.rust-lang.org/std/sync/atomic/ https://doc.rust-lang.org/std/sync/atomic/). There's a method AtomicUsize::compare_and_swap that takes an &self, not an &mut self, as well as the values for comparing and swapping. Because it executes in an atomic machine instruction (or otherwise figures out how to make it atomic), it's okay for compare_and_swap to take only a &self. There's no risk of data races/memory corruption from multiple threads calling it at once. You're dynamically enforcing safety: if the compare doesn't work, the compare_and_swap operation returns an error. There's also a method AtomicUsize::get_mut(&mut self) -> &mut usize that takes a unique reference to the AtomicUsize type, and gives you a unique reference to the underlying integer. As long as you hold a unique borrow, you can do normal memory read/write operations to the integer inside it, but at this point the compiler will statically make sure that nobody else can take shared references to the same AtomicUsize. You can always do what you want via message-passing between threads, but sometimes you want higher performance. (I guess that's why you're using threads in the first place; you can always write code in a single-threaded manner if you want.) std::sync::atomic and a few other standard library types help you with this; crossbeam really helps you with this. And they all integrate into the borrow checker pretty smoothly. See also the Rust book's chapter on interior mutability https://doc.rust-lang.org/book/ch15-05-interior-mutability.html https://doc.rust-lang.org/book/ch15-05-interior-mutability.h... and the "Too Many Lists" exercise https://cglab.ca/~abeinges/blah/too-many-lists/book/README.html https://cglab.ca/~abeinges/blah/too-many-lists/book/README.h... for more examples.
- tombert 8y agoLock-free structures have always felt like the "holy grail" of concurrent programming. I remember being blown-away when I read through the paper on CTries (which I'm assuming ConcurrentHashMap would be based on), and even more blown away about how well they performed. I always assumed that Ctries basically necessitated a GC, but I am very happy to be wrong about this!
- pcwalton 8y agoPeople (including me) always talk about how memory safety without GC is the most important feature of Rust, but just as important is how easy Rust makes fine-grained parallelism. In Rust, you can often start off writing sequential code and then bolt parallelism on after the fact and have it all "just work" with improved performance, thanks to libraries like Crossbeam and Rayon and the way the ownership/borrowing rules enforce data race freedom. That's really powerful.
- deepsun 8y agoWait, but Crossbeam does have a GC inside it.
- kinghajj 8y agoYes, but that's only to support its goal of efficient lock-free data structures, not for Rust's goal of memory safety.
- est31 8y agoAnd if it doesn't "just work" then there will be a clear error message pointing to the problem instead of nasal demons haunting you. That way you can debug and fix the problem much more easily.
- 2bitencryption 8y agoAllow me to ask a dumb question: At the end of the day, how can something that is safely concurrent also be lock-free? At the lowest level, what is the primitive that enforces the safety, if it's not a lock or mutex? My brain starts to run in cricles when I think of this scenario: two threads trying to write to one piece of data. To do so safely, they need to take turns. Therefore, one has to wait for the other to complete. Therefore, one must acquire a mutually exclusive... hold on, that's a mutex! Can someone please clear this up for me?
- jaccarmac 8y agoI've read one of these articles and bookmarked the other. They give some introduction to the problem space, with pictures. I'm no expert though and can't rate their accuracy; Just know they helped me feel a little more confident about the basics. https://preshing.com/20120612/an-introduction-to-lock-free-programming/ https://preshing.com/20120612/an-introduction-to-lock-free-p... http://lucteo.ro/2018/11/18/look-ma-no-locks/ http://lucteo.ro/2018/11/18/look-ma-no-locks/
- coder543 8y agoOne word: atomics. A simple example would be concurrently writing into a shared queue. To make it really simple, let's assume that this queue's buffer can only be written once, and then the program has to exit. If we have a buffer in this queue that can hold 20 messages, and an atomic integer that represents the current index, then we could have two (or however many) threads writing into it at the same time by just doing "index = myAtomic.fetch_add(1)", which will atomically add one to the index, then return the previous value. Atomics are supported at a hardware level, so they're generally pretty efficient, and there definitely is no lock like a Mutex involved here. In the end, both threads are able to write into shared memory without conflicting with each other. Using one or two more atomic integers, we could support having one or more readers reading off of the queue at the same time that we're writing to it, and we could get to the point where we're able to start reusing the buffer in a circular fashion.
- pmalynin 8y agoWhile what you said is all true, its not turtles all the way down. Eventually when it comes down to the hardware level the processor will have to assert #LOCK (or whatever mechanism it uses). So arguably even atomics aren't "lock" free, somewhere along the line some piece of hardware will have to block all other hardware to do its thing. DRAM can only read one thing at a time (and has to write it back afterwards).