6 ms·

Rust Atomics and Locks: Low-Level Concurrency in Practice

292 points by signa11 4y ago

gavinray 4y ago
I'm curious how folks in Rust implement striped-locking? Striped locking is where you chunk sections of data behind the same lock to improve scalability. So, 1 lock might protect 1,000 items in an array, for example.
- lilyball 4y ago
  I've never done this but I imagine you could use something like [Mutex<[T; 1000]>; 10]
- remexre 4y ago
  First thing that'd come to mind for me would be replacing the unstriped Vec<Mutex<T>> with some wrapper like: struct Striped<T, const StripeSize: usize>(Vec<Mutex<[T; StripeSize]>>, Mutex<tinyvec::ArrayVec<[T; StripeSize]>>); I think I'd probably want a wrapper either way to ensure I'm always taking locks in a particular order to avoid deadlocks, anyway.
- tick_tock_tick 4y ago
  Realistically you don't unless you really really need it. If you really need it you drop to unsafe and build a "safe" interface in-front of it. Rust makes writing very high performance multi-threaded code incredibly hard because most of the tricks to get that last bit of performance out are basically asking to generated races and are near impossible to express in a way that is provably safe. You basically thinking of your data-layout from day one if you need that kind of performance your just going to have to deal with a bunch of unsafe in your codebase.
zengid 4y ago
Its very kind of Mara to share the book online, though I still preordered a paper copy for bedtime reading. :)
infamouscow 4y ago
This book is absolutely wonderful and a pleasure to read.* * I say this as a staunch critic of Rust.
estebank 4y ago
The foreword by Paul E. McKenney makes a great case to read this book even if you don't care about Rust at all: > Which brings us to another group of potential readers, the Rust skeptics. While I do believe that most Rust skeptics are doing the community a valuable service by pointing out opportunities for improvement, all but the most Rust-savvy of skeptics would benefit from reading this book. If nothing else, doing so would enable them to provide sharper and better-targeted criticisms. > Then there are those dyed-in-the-wool non-Rust developers who would prefer to implement Rust's concurrency-related safety mechanisms in their own favorite language. This book will give them a deeper understanding of the Rust mechanisms that they would like to replicate, or, better yet, improve upon. https://marabos.nl/atomics/foreword.html https://marabos.nl/atomics/foreword.html
- seanhunter 4y ago
  In case anyone here doesn’t know, Paul McKenney was one of the main contributors to the RCU[1] implementation for the Linux kernel. So the guy knows a thing or two about concurrency. [1] https://en.wikipedia.org/wiki/Read-copy-update https://en.wikipedia.org/wiki/Read-copy-update if you just want to know what it is and http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01... if you want the good stuff
  - cwzwarich 4y ago
    Although, somewhat amusingly, neither C++ nor Rust (which basically just copies the C++ atomics and memory model) can be used to correctly express RCU written within the language. The leading proposal for C++ (at least AFAICT) is to just add RCU primitives to the library and make their correctness the implementation's concern: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2545r1.pdf https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p25... I hope we get a next generation of systems languages with improved memory models that can actually express these things directly.
    - throwaway17_17 4y ago
      Can you provide any extra information about what is unable to be expressed? I’d like to look into what sort of constructs could be useful in this context.
capableweb 4y ago
Interesting to check what the various stores prices the book as. Cheapest I found was 34 EUR and most expensive 68 EUR, pretty much double the price.
samsquire 4y ago
Thanks for putting the time and extensive effort into this book. I am deeply interested in concurrency, asynchrony and parallelism I even journal about it everyday on my GitHub journal ideas repository (see my profile) I've been talking on the r/programminglanguages discord about syntax for async/await. I am writing a programming language that has parallelism as a first class citizen. I use this actor2.java lock free algorithm below for sending messages between threads. I want my async/await tasks to be eager and run in their own threads. So if I do this handle1 = async task1(); handle2 = async task2(); handle3 = async task3(); // at this point in time, the token ring thread pool shall be running 3 tasks in parallel return1 = await handle1; return2 = await handle2; return3 = await handle3; I believe other languages do not run CPU bound async/await computations on a thread except for IO. I wrote an unrolled state machine for my async/await in Java. This models a simple async/await program and runs tasks on other threads - without locks. I use a design I call token ring parallelism, where threads take turns and are linked together in a ring structure. A semaphore communicates write status along the ring. The plan is to write a transpiler to generate the switch statements automatically. Then any language with threading can have async await support even if it is not native. https://github.com/samsquire/multiversion-concurrency-control/blob/main/src/main/java/main/TokenRingTimer2AsyncAwait3.java https://github.com/samsquire/multiversion-concurrency-contro... I wrote a own lock free algorithm here that I use to do message passing between actor threads. My goal is high throughput performance and low latency. https://github.com/samsquire/multiversion-concurrency-control/blob/main/src/main/java/main/Actor2.java https://github.com/samsquire/multiversion-concurrency-contro... With 11 threads (on a 12 core processor, deliberately left one core for Windows) I get This code with 100 threads, gets 114657500 total requests 22079241.286347 requests per second Time taken: 5.193000 166512180 total requests 33249237.220447 requests per second Time taken: 5.008000 For a lock based benchmark with 100 threads, I get: 16307090 total requests 3246484.172805 requests per second With 11 threads, the lock benchmark gets 178770160 total requests 35732592.444533 requests per second Time taken: 5.003000 Each request is a synchronization event that sends 10 messages in a loop or adds 10 to a counter to represent the synchronization event. There's probably problems with my measuring methodology, I am doing the simplest possible thing that shall work. I am trying to show that my lock free algorithm scales even with heavy contention.
- 4y ago
elfprince13 4y ago
FWIW, this isn't mentioned in the book, and only extremely cursorily in the official Rust docs, but looks like 128bit atomics have landed (on supported architectures): https://github.com/rust-lang/rust/blob/19bc8fb05ab083a315ee4285b4df7822e8bb1e24/library/core/src/sync/atomic.rs#L2860-L2899 https://github.com/rust-lang/rust/blob/19bc8fb05ab083a315ee4...
oslac 4y ago
One of the things most concurrency material leaves out is the actual definition of concurrency. I read the first chapter, but didn't see it defined, but I see this touches upon Happens-Before so it might include it later (?)
sylware 4y ago
BTW, I am looking for a statically linked rust compiler (the one written in rust ofc) toolchain for ELF64. This is for bootstrap.
deleted 4y ago
[deleted]
63 4y ago
I'm interested in the concept of concurrency, but is there anywhere that it would be useful outside of scientific applications and operating systems? It feels like a powerful paradigm to master but I'm just not sure it's worth the investment for the average developer.
- maxbond 4y ago
  For what it's worth, if I hadn't learned about low-level concurrency primitives in Rust, I wouldn't have had the mental framework to succeed in creating a realtime websocket service in Python. My two cents is that learning is enriching and inspiring. If you learn concepts from one context you can apply them in another in new and surprising ways. Don't put yourself in a box like "I'm just a normal developer, I don't know about that OS stuff"; learn about the things that excite you and worry about applying them later. Specialization is for ants. But if this advice isn't useful to you, feel free to discard it.
- kevinossia 4y ago
  I've used tons of concurrency in Android apps, iOS apps, Unreal Engine games, C++ code running a Raspberry Pi drone, embedded Android telemetry (Java/C++), and C++ AR/VR high-resolution realtime media streaming systems. If you can wield concurrency, you can use it anywhere. It's liberating to be able to drastically improve the performance of your code by leveraging the multi-core processors our software runs on these days. I've never done any OS work nor scientific computing.
- yazaddaruvala 4y ago
  It’s a common misconception but there is a difference between concurrency and parallelism. Concurrency is very useful across all aspects of the stack including OS code, and even web app code. Your comment about “usefulness” is likely about Parallelism. Which I agree with you is typically only useful in abstractions like OS code and even web frameworks.
- oslac 4y ago
  Most web servers / apps. Just think about how you would test a simple register endpoint for example.
oconnor663 4y ago
Does anyone know how to pronounce the author's name? Is the "s" more like an "sh"?
bfrog 4y ago
What a great looking book! Congrats!
blacklion 4y ago
It is exceptionally good book about very hard topics. I'm programming high-performance tasks in Java for 10+ years, and Java was first commonly-used language with formal memory model, as far as I know. C/C++/Rust memory models are modeled after Java's one. There was no new material for me, but all material is very well organized, explained, and presented. This is very hard material, there are a lot of tutorials about JMM and most of them are worse than this book. Other good property of this book is density of information. Many IT-related books now contains unneeded repetitions and artificial bloat to increase page count. Each page of this book is useful! This book will be exceptionally useful not only for any Rust programmer, but, also for any non-Rust programmer who uses language with same or similar memory models, including C, C++ and Java programmers. 5 stars out of 5, recommended for every programmer who want to understand complex mechanics of memory models and high-performance concurrency of modern languages.
mlindner 4y ago
The book, especially chapter 7 seems to say several things completely opposite to what Herb Sutter did in his famous talk a number of years ago. In the book: > This means that on ARM64, sequentially consistent operations are exactly as cheap as acquire and release operations. Or, rather, that ARM64 Acquire, Release, and AcqRel operations are as expensive as SeqCst. Unlike x86-64, however, Relaxed operations are relatively cheap, as they don’t result in stronger ordering guarantees than necessary. However in Herb Sutter's talk (specifically the second half here: https://www.youtube.com/watch?v=KeLBd2EJLOU https://www.youtube.com/watch?v=KeLBd2EJLOU ) he says that ARMv8 Acquire/Release/AcqRel operations are cheaper than SeqCst. This book seems to claim that x64 is somehow superior to ARMv8, which from my understanding is completely wrong.
- psykotic 4y ago
  Let's go to primary sources: https://developer.arm.com/documentation/ddi0487/latest https://developer.arm.com/documentation/ddi0487/latest The author is right. ARMv8 supports relaxed memory ordering but its memory model does not support acquire-release ordering without sequential consistency. (Update: Support for weaker acquire-release ordering was added in a later revision.) I'll quote a relevant excerpt from B2.3.11: Where a Load-Acquire appears in program order after a Store-Release, the memory access generated by the Store-Release instruction is Observed-by each PE to the extent that PE is required to observe the access coherently, before the memory access generated by the Load-Acquire instruction is Observed-by that PE, to the extent that the PE is required to observe the access coherently. Sequential consistency is needed to avoid store/load reordering in cases like this: // Thread 1 flag1.store(1, SeqCst) if flag2.load(SeqCst) == 0 { // Guarded action } // Thread 2 flag2.store(1, SeqCst) if flag1.load(SeqCst) == 0 { // Guarded action } If these were instead implemented with acquire/release ordering as defined by the C++ or Rust memory model, the resulting happens-before constraints would not prevent both threads from executing their guarded actions. The excerpt from the Architecture Reference Manual says that if you use their load-acquire (ldar) and store-release (stlr) instructions, it is not possible for the store-release to be moved after the load-acquire, as observed by PEs (processing elements, their abstraction of hardware threads). Let's look at how C++ compilers implement acquire-release vs sequential consistency on x86 and ARMv8: https://godbolt.org/z/3fd5jse18 https://godbolt.org/z/3fd5jse18 The machine code on ARMv8 is identical for thread_acq_rel and thread_seq_cst. Whereas on x86 the thread_seq_cst code has to use xchg (an alternative to store + mfence) to achieve sequential consistency. Update: shachaf pointed out that ARMv8 more recently added support for weaker acquire-release semantics in the ARMv8.3 revision. It looks like the first processor to ship with ARMv8.3 support was the A12X from Apple in 2018, which is 5 years after Herb's talk. If we take the code from before and compile for ARMv8 with all architectural features enabled, you will see different machine code for thread_acq_rel which uses the newer ldaprb instruction: https://godbolt.org/z/dnP9sebcz https://godbolt.org/z/dnP9sebcz This illustrates a difficulty with talking about "ARMv8" as a fixed thing. It's much more of a rapidly moving target than x86. That said, the ARMv8.3 addendum should have been mentioned, at least parenthetically; I emailed the author suggesting an info box.

292 points by signa11 4y ago

I'm curious how folks in Rust implement striped-locking? Striped locking is where you chunk sections of data behind the same lock to improve scalability. So, 1 lock might protect 1,000 items in an array, for example.

lilyball 4y ago
I've never done this but I imagine you could use something like [Mutex<[T; 1000]>; 10]
remexre 4y ago
First thing that'd come to mind for me would be replacing the unstriped Vec<Mutex<T>> with some wrapper like: struct Striped<T, const StripeSize: usize>(Vec<Mutex<[T; StripeSize]>>, Mutex<tinyvec::ArrayVec<[T; StripeSize]>>); I think I'd probably want a wrapper either way to ensure I'm always taking locks in a particular order to avoid deadlocks, anyway.
tick_tock_tick 4y ago
Realistically you don't unless you really really need it. If you really need it you drop to unsafe and build a "safe" interface in-front of it. Rust makes writing very high performance multi-threaded code incredibly hard because most of the tricks to get that last bit of performance out are basically asking to generated races and are near impossible to express in a way that is provably safe. You basically thinking of your data-layout from day one if you need that kind of performance your just going to have to deal with a bunch of unsafe in your codebase.

zengid 4y ago

Its very kind of Mara to share the book online, though I still preordered a paper copy for bedtime reading. :)

infamouscow 4y ago

This book is absolutely wonderful and a pleasure to read.* * I say this as a staunch critic of Rust.

estebank 4y ago

The foreword by Paul E. McKenney makes a great case to read this book even if you don't care about Rust at all: > Which brings us to another group of potential readers, the Rust skeptics. While I do believe that most Rust skeptics are doing the community a valuable service by pointing out opportunities for improvement, all but the most Rust-savvy of skeptics would benefit from reading this book. If nothing else, doing so would enable them to provide sharper and better-targeted criticisms. > Then there are those dyed-in-the-wool non-Rust developers who would prefer to implement Rust's concurrency-related safety mechanisms in their own favorite language. This book will give them a deeper understanding of the Rust mechanisms that they would like to replicate, or, better yet, improve upon. https://marabos.nl/atomics/foreword.html https://marabos.nl/atomics/foreword.html

seanhunter 4y ago
In case anyone here doesn’t know, Paul McKenney was one of the main contributors to the RCU[1] implementation for the Linux kernel. So the guy knows a thing or two about concurrency. [1] https://en.wikipedia.org/wiki/Read-copy-update https://en.wikipedia.org/wiki/Read-copy-update if you just want to know what it is and http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01c.pdf http://www.rdrop.com/users/paulmck/RCU/rclock_OLS.2001.05.01... if you want the good stuff
- cwzwarich 4y ago
  Although, somewhat amusingly, neither C++ nor Rust (which basically just copies the C++ atomics and memory model) can be used to correctly express RCU written within the language. The leading proposal for C++ (at least AFAICT) is to just add RCU primitives to the library and make their correctness the implementation's concern: https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p2545r1.pdf https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2022/p25... I hope we get a next generation of systems languages with improved memory models that can actually express these things directly.
  - throwaway17_17 4y ago
    Can you provide any extra information about what is unable to be expressed? I’d like to look into what sort of constructs could be useful in this context.

capableweb 4y ago

Interesting to check what the various stores prices the book as. Cheapest I found was 34 EUR and most expensive 68 EUR, pretty much double the price.

samsquire 4y ago

Thanks for putting the time and extensive effort into this book. I am deeply interested in concurrency, asynchrony and parallelism I even journal about it everyday on my GitHub journal ideas repository (see my profile) I've been talking on the r/programminglanguages discord about syntax for async/await. I am writing a programming language that has parallelism as a first class citizen. I use this actor2.java lock free algorithm below for sending messages between threads. I want my async/await tasks to be eager and run in their own threads. So if I do this handle1 = async task1(); handle2 = async task2(); handle3 = async task3(); // at this point in time, the token ring thread pool shall be running 3 tasks in parallel return1 = await handle1; return2 = await handle2; return3 = await handle3; I believe other languages do not run CPU bound async/await computations on a thread except for IO. I wrote an unrolled state machine for my async/await in Java. This models a simple async/await program and runs tasks on other threads - without locks. I use a design I call token ring parallelism, where threads take turns and are linked together in a ring structure. A semaphore communicates write status along the ring. The plan is to write a transpiler to generate the switch statements automatically. Then any language with threading can have async await support even if it is not native. https://github.com/samsquire/multiversion-concurrency-control/blob/main/src/main/java/main/TokenRingTimer2AsyncAwait3.java https://github.com/samsquire/multiversion-concurrency-contro... I wrote a own lock free algorithm here that I use to do message passing between actor threads. My goal is high throughput performance and low latency. https://github.com/samsquire/multiversion-concurrency-control/blob/main/src/main/java/main/Actor2.java https://github.com/samsquire/multiversion-concurrency-contro... With 11 threads (on a 12 core processor, deliberately left one core for Windows) I get This code with 100 threads, gets 114657500 total requests 22079241.286347 requests per second Time taken: 5.193000 166512180 total requests 33249237.220447 requests per second Time taken: 5.008000 For a lock based benchmark with 100 threads, I get: 16307090 total requests 3246484.172805 requests per second With 11 threads, the lock benchmark gets 178770160 total requests 35732592.444533 requests per second Time taken: 5.003000 Each request is a synchronization event that sends 10 messages in a loop or adds 10 to a counter to represent the synchronization event. There's probably problems with my measuring methodology, I am doing the simplest possible thing that shall work. I am trying to show that my lock free algorithm scales even with heavy contention.

4y ago

elfprince13 4y ago

FWIW, this isn't mentioned in the book, and only extremely cursorily in the official Rust docs, but looks like 128bit atomics have landed (on supported architectures): https://github.com/rust-lang/rust/blob/19bc8fb05ab083a315ee4285b4df7822e8bb1e24/library/core/src/sync/atomic.rs#L2860-L2899 https://github.com/rust-lang/rust/blob/19bc8fb05ab083a315ee4...

oslac 4y ago

One of the things most concurrency material leaves out is the actual definition of concurrency. I read the first chapter, but didn't see it defined, but I see this touches upon Happens-Before so it might include it later (?)

sylware 4y ago

BTW, I am looking for a statically linked rust compiler (the one written in rust ofc) toolchain for ELF64. This is for bootstrap.

deleted 4y ago

[deleted]

63 4y ago

I'm interested in the concept of concurrency, but is there anywhere that it would be useful outside of scientific applications and operating systems? It feels like a powerful paradigm to master but I'm just not sure it's worth the investment for the average developer.

maxbond 4y ago
For what it's worth, if I hadn't learned about low-level concurrency primitives in Rust, I wouldn't have had the mental framework to succeed in creating a realtime websocket service in Python. My two cents is that learning is enriching and inspiring. If you learn concepts from one context you can apply them in another in new and surprising ways. Don't put yourself in a box like "I'm just a normal developer, I don't know about that OS stuff"; learn about the things that excite you and worry about applying them later. Specialization is for ants. But if this advice isn't useful to you, feel free to discard it.
kevinossia 4y ago
I've used tons of concurrency in Android apps, iOS apps, Unreal Engine games, C++ code running a Raspberry Pi drone, embedded Android telemetry (Java/C++), and C++ AR/VR high-resolution realtime media streaming systems. If you can wield concurrency, you can use it anywhere. It's liberating to be able to drastically improve the performance of your code by leveraging the multi-core processors our software runs on these days. I've never done any OS work nor scientific computing.
yazaddaruvala 4y ago
It’s a common misconception but there is a difference between concurrency and parallelism. Concurrency is very useful across all aspects of the stack including OS code, and even web app code. Your comment about “usefulness” is likely about Parallelism. Which I agree with you is typically only useful in abstractions like OS code and even web frameworks.
oslac 4y ago
Most web servers / apps. Just think about how you would test a simple register endpoint for example.

oconnor663 4y ago

Does anyone know how to pronounce the author's name? Is the "s" more like an "sh"?

bfrog 4y ago

What a great looking book! Congrats!

blacklion 4y ago

It is exceptionally good book about very hard topics. I'm programming high-performance tasks in Java for 10+ years, and Java was first commonly-used language with formal memory model, as far as I know. C/C++/Rust memory models are modeled after Java's one. There was no new material for me, but all material is very well organized, explained, and presented. This is very hard material, there are a lot of tutorials about JMM and most of them are worse than this book. Other good property of this book is density of information. Many IT-related books now contains unneeded repetitions and artificial bloat to increase page count. Each page of this book is useful! This book will be exceptionally useful not only for any Rust programmer, but, also for any non-Rust programmer who uses language with same or similar memory models, including C, C++ and Java programmers. 5 stars out of 5, recommended for every programmer who want to understand complex mechanics of memory models and high-performance concurrency of modern languages.

mlindner 4y ago

The book, especially chapter 7 seems to say several things completely opposite to what Herb Sutter did in his famous talk a number of years ago. In the book: > This means that on ARM64, sequentially consistent operations are exactly as cheap as acquire and release operations. Or, rather, that ARM64 Acquire, Release, and AcqRel operations are as expensive as SeqCst. Unlike x86-64, however, Relaxed operations are relatively cheap, as they don’t result in stronger ordering guarantees than necessary. However in Herb Sutter's talk (specifically the second half here: https://www.youtube.com/watch?v=KeLBd2EJLOU https://www.youtube.com/watch?v=KeLBd2EJLOU ) he says that ARMv8 Acquire/Release/AcqRel operations are cheaper than SeqCst. This book seems to claim that x64 is somehow superior to ARMv8, which from my understanding is completely wrong.

psykotic 4y ago
Let's go to primary sources: https://developer.arm.com/documentation/ddi0487/latest https://developer.arm.com/documentation/ddi0487/latest The author is right. ARMv8 supports relaxed memory ordering but its memory model does not support acquire-release ordering without sequential consistency. (Update: Support for weaker acquire-release ordering was added in a later revision.) I'll quote a relevant excerpt from B2.3.11: Where a Load-Acquire appears in program order after a Store-Release, the memory access generated by the Store-Release instruction is Observed-by each PE to the extent that PE is required to observe the access coherently, before the memory access generated by the Load-Acquire instruction is Observed-by that PE, to the extent that the PE is required to observe the access coherently. Sequential consistency is needed to avoid store/load reordering in cases like this: // Thread 1 flag1.store(1, SeqCst) if flag2.load(SeqCst) == 0 { // Guarded action } // Thread 2 flag2.store(1, SeqCst) if flag1.load(SeqCst) == 0 { // Guarded action } If these were instead implemented with acquire/release ordering as defined by the C++ or Rust memory model, the resulting happens-before constraints would not prevent both threads from executing their guarded actions. The excerpt from the Architecture Reference Manual says that if you use their load-acquire (ldar) and store-release (stlr) instructions, it is not possible for the store-release to be moved after the load-acquire, as observed by PEs (processing elements, their abstraction of hardware threads). Let's look at how C++ compilers implement acquire-release vs sequential consistency on x86 and ARMv8: https://godbolt.org/z/3fd5jse18 https://godbolt.org/z/3fd5jse18 The machine code on ARMv8 is identical for thread_acq_rel and thread_seq_cst. Whereas on x86 the thread_seq_cst code has to use xchg (an alternative to store + mfence) to achieve sequential consistency. Update: shachaf pointed out that ARMv8 more recently added support for weaker acquire-release semantics in the ARMv8.3 revision. It looks like the first processor to ship with ARMv8.3 support was the A12X from Apple in 2018, which is 5 years after Herb's talk. If we take the code from before and compile for ARMv8 with all architectural features enabled, you will see different machine code for thread_acq_rel which uses the newer ldaprb instruction: https://godbolt.org/z/dnP9sebcz https://godbolt.org/z/dnP9sebcz This illustrates a difficulty with talking about "ARMv8" as a fixed thing. It's much more of a rapidly moving target than x86. That said, the ARMv8.3 addendum should have been mentioned, at least parenthetically; I emailed the author suggesting an info box.