CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part II"
Why Stack Overflow recommends it
Stack Overflow users link it when answering questions about lock-free structures, compare-exchange loops, atomic shared_ptr and thread safety in C++.
Recommended by 6 people across 5 different months, 2015 to 2023.
What it is
Herb Sutter's CppCon 2014 talk on designing and writing lock-free algorithms and data structures with C++ std::atomic, worked through examples such as a lock-free linked list. It is the practical follow-up to his separate 'atomic Weapons' talk on the memory model.
What people said
Recommends engf-010 · 2015-02 · Stack Overflow · on “Is there a way of making atomic shared_ptr in libstd++?”
There is an interesting part about atomic shared pointers somewhere in this video series (note there are 2 videos) by Her Sutter ! [LINK] en [this video]
Recommends Maarten Bamelis · 2015-05 · Stack Overflow · on “Non blocking way of adding a work item to array or list”
I have seen Herb's talks recently and I believe his lock-free linked list [this video] should do fine. The only problem is that atomic< shared_ptr<T> > is not yet implemented. I've used the atomic_* function calls as also explained by Herb in his talk. In the example, I've simplified a task to an int, but it could be anything you want. The function atomic_compare_exchange_weak takes three arguments: the item to compare, the expected value and the desired value. It returns true or false to indicate success or failure. On failure, the expected value will be changed to the value that was found instead. #include <memory> #include <atomic> // Untested code. struct WorkItem { // Simple linked list impl
Recommends laurisvr · 2015-05 · Stack Overflow · on “How to implement CAS in c++11”
This is how I would do it: //untested code template<typename T> T compare_and_swap(atomic<T>& reg,T newVal ) { oldVal = atomic_load(reg); while(!atomic_compare_exchange_weak(®, &oldVal, newVal)); return oldVal; } The compare exchange function will update the oldval value if it fails. Therefore there is no need repeating this. As you can see I prefer to use the explicit atomic operations. This is because the full one's aren't always implemented. As is explained by Herb Sutter here [this video] (the rest of the video might also interest you:) ). As a posibbly unnecessary afterthought I would like to warn against using this function with non trivially copyable [this video] types. Or 'normal' pointers.
Recommends anorm · 2015-09 · Stack Overflow · on “Could optimization break thread safety?”
Compiler optimization can not break thread safety! You might however experience issues with optimizations in code that appeared to be thread safe but really only worked because of pure luck. If you access data from multiple threads, you must either Protect the appropriate sections using std::mutex or the like. or, use std::atomic . If not, the compiler might do optimizations that is next to impossible to expect. I recommend watching CppCon 2014: Herb Sutter "Lock-Free Programming (or, Juggling Razor Blades), Part I" [LINK] and Part II [this video]
Recommends Balthazar · 2021-07 · Stack Overflow · on “Lock-free C++11 example using Load-link/store-conditional to prevent ABA?”
If you have the ABA problem with pointers, then you also have a lifetime management issue. At least I don't know of any way of having the ABA problem with pointers, without at some point holding a dangling pointer. Herb Sutter has a talk on this, and the solution he proposes is implemented in MSVC for C++20, hopefully it will be implemented everywhere some day: [this video]
Recommends Marek R · 2023-08 · Stack Overflow · on “C++ perform if-not-equal-then-increment atomically using acquire-release semantics?”
When using atomic there is an option to do "lock free programing". This may look easy, but has lots of subtle traps. For example it is bad idea to use int8_t with std::atomic it since it can be slower for multiple reasons ( int8_t is sow by itself and also this greatly increases danger of "false sharing"). In your case this may look like this: struct Lock { void take_lock() { auto original = m_counter.load(); int newValue; do { while(original == -1) { m_counter.wait(original); original = m_counter.load(); } newValue = original + 1; } while (!m_counter.compare_exchange_strong(original, newValue)); } std::atomic<int> m_counter{0}; }; [LINK] For more details see cppcon talk from Herb Sutter "Lo
Cites 5gon12eder · 2015-02 · Stack Overflow · on “save variable argument list for fprintf calls”
I don't see how this would be done easily using the legacy C vprintf with va_list s. As you want to pass things around between threads, sooner or later you will need to use the heap in some way. Below is a solution that uses Boost.Format [LINK] for the formatting and Boost.Variant [LINK] for parameter passing. The example is complete and working if you concatenate the following code blocks in order. If you compile with GCC, you need to pass the -pthread linker flag. And of course, you'll also need the two Boost libraries which are header-only, however. Here are the headers we will use. #include <condition_variable> #include <iostream> #include <list> #include <locale> #include <mutex> #inclu
Cites MikeMB · 2015-07 · Stack Overflow · on “Atomic shared_ptr for lock-free singly linked list”
I'm wondering if it is possible to create a lock-free, thread-safe shared pointer for any of the "common" architectures, like x64 or ARMv7 / ARMv8. In a talk about lock-free programming at cppcon2014 [this video] , Herb Sutter presented a (partial) implementation of a lock-free singly linked list. The implementation looks quite simple, but it relies on an atomic shared_ptr implementation that doesn't exist in the standard library yet or on using the specialized std::atomic... functions. This is especially important as single push/pop calls potentially invoke multiple atomic loads/stores and compare_exchange operations. The problem I see (and I think some of the questions in the talk went into the
Cites Jonathan S. · 2023-02 · Stack Overflow · on “Does the context switch retain (keep state of variables) the value of the variables when it resumes the task?”
To actually answer your question... The following can (and will!) indeed happen: Thread 1: Load "count" into CPU register "A". Result: A = 0 Thread 1: Increment CPU register A. Result: A = 1 (Context switch) Thread 2: Load "count" -> 0 Thread 2: Increment -> 1 Thread 2: Store 1 in "count" (Context switch) Thread 1: Store 1 from register A in "count" Afterwards, count is still 1, and one increment has been "lost". In practice, pretty much anything can happen, including the counter suddenly going backwards or reading totally nonsensical values. What's preserved across a context switch is the CPU's registers . In order to operate on a variable, the CPU first has to load the variable from memory