https://cppcon.org --- Introduction to Wait-free Algorithms in C++ Programming - Daniel Anderson - CppCon 2024 --- If you've attended any talks about concurrency, you've no doubt heard the term "lock-free programming" or "lock-free algorithms". Usually these talks will give you a slide that explains vaguely what this means, but you accept that is is approximately (but not quite exactly) equal to "just don't use locks". More formally, lock-freedom is about guaranteeing how much progress your algorithm will make in a given time. Specifically, a lock-free algorithm will always make some progress on at least one operation/thread. It does not guarantee however that all threads make progress. In a lock-free algorithm, a particular operation can still be blocked for an arbitrary long time because of the actions of other contending threads. What can we do in situations where this is unacceptable, such as when we want to guarantee low latency for every operation on our data structure rather than just low average latency? In these situations, there is a stronger progress guarantee that we can aim for called wait-freedom. An algorithm is wait free if *every* operation is guaranteed to make progress in a bounded amount of time, i.e., no thread can ever be blocked for an arbitrarily long time. This helps to guarantee low tail latency for all operations, rather than low average latency in which some operations are left behind. In this talk, we will give an introduction to designing and implementing wait-free algorithms. Without assuming too much background of the audience, we will review the core ideas of lock-free programming and understand the classic techniques for transforming a blocking algorithm into a lock-free one. The main bread-and-butter technique for lock-free algorithms is the compare-exchange loop or "CAS loop", in which an operation reads the current state of the data structure, creates some sort of updated version, and then attempts to install the update via a compare-exchange, looping until it succeeds. compare-exchange loops suffer under high contention since the success of one operation will often cause another to have to repeat work until they succeed. The bread-and-butter technique of wait-free programming that overcomes this issue is helping. When operations contend, instead of racing to see who wins, an operation that encounters another already-in-progress operation attempts to help it complete first, then proceeds with its own operation. This results in the initial operation succeeding instead of being clobbered and forced to try again. --- Slides: https://github.com/CppCon/CppCon2024/blob/main/Presentations/When_Lock-Free_Still_Isn't_Enough.pdf Work at Hudson River Trading (HRT): https://tinyurl.com/safxfctf --- Daniel Anderson Daniel Anderson is an assistant teaching professor at Carnegie Mellon University, where he recently graduated with a PhD in computer science focusing on parallel computing and parallel algorithms. Daniel teaches algorithms classes to hundreds of undergraduate students and spends his remaining time writing C++ libraries that aim to make parallel computing easier and more accessible to non-experts. He is the recipient of a Best Paper Award from the ACM Symposium on Parallelism in Algorithms and Architecture (SPAA) conference. --- CppCon is the annual, week-long face-to-face gathering for the entire C++ community. The conference is organized by the C++ community for the community. You will enjoy inspirational talks and a friendly atmosphere designed to help attendees learn from each other, meet interesting people, and generally have a stimulating experience. Taking place this year in Aurora, Colorado, near the Denver airport, and including multiple diverse tracks, the conference will appeal to anyone from C++ novices to experts. Annual CppCon Conference - https://www.cppcon.org https://www.linkedin.com/company/cppcon https://x.com/cppcon https://www.facebook.com/CppConference https://www.reddit.com/r/cppcon/ https://mastodon.social/@CppCon --- Videos Filmed & Edited by Bash Films: http://www.BashFilms.com YouTube Channel Managed by Digital Medium Ltd: https://events.digital-medium.co.uk --- #concurrency #cpp #cplusplus #cppcon #cppprogramming #cplusplusprogramming #softwaredevelopment #softwareengineering #coding #code #technology #technews #programming #programmer
ADVERTISEMENT
My favorite cppcon speaker, very well presented as always
Great talk, clever trick, dont want such code in production ever xD
This morning I was talking to a friend about a Ventrilo server we rented about 15-16 years ago to play games with our friends. I started watching this talk and I thought I recognised the voice and the name. Turns out I was correct because Daniel was a member of that vent server and we used to play obscene amounts of League of Legends together. The fact that I've independently thought of him in 2 completely unrelated contexts on the same day is driving me slightly insane.
Excellent Daniel… That shows your presentation skills on the complex topics..
Damn bro looping same point at least 5 times per each slide.
Great speaker with excellent delivery skills.
I think Daniel has to revise his lock-free definition. As per his current definition "System wide progress, at any given time at least one thread is making progress on its operation.", funnily this means that a lock-based program can trivially satisfy the lock-free property. A lock guarantees progress of at least one thread: When threads compete for a lock, one of them gets the lock without blocking and makes progress. When it's done, it releases the lock and then another thread gets it without blocking and makes progress. At any given time, at least one thread is not being blocked, and therefore it is making progress.
Dude is so talented and charming
isn't his explanation of lock free how the locking mechanisms work?
I'm curious why no one asks what happens if you call decrement when the counter is at 0? It seems like a bug in both the lock free and wait free versions, but maybe he added a caveat about how once decrement returns true, there's a guarantee it will never be called again.
Great speaker, one of the best one I've seen for the clarity it explain complex topics
Thanks!
Surely locks eliminate parallelism ;)
Great, great talk. About the "weird" decrement. I think it is simpler to explain that all bits being 0 at some point in time does not matter. All it matters is to have 0x10 in the bits portion of the counter. Until this happens the counter is not zero. The semantics of decremante-to-zero are separated from the physical representation.
36:20 and if you have 2ˆ63+1 fetch_adds happen, they can overwrite that is_zero flag. Maybe don't design in overflows in your logic. On the other hand, if you used the least significant bit and just count by 1<<num_flags, the flags are left intact.
very good talk!
Lock-free but all the functions we use to do that have lock in them (interlocked) 🤔
:42 what if 1. Thread1: decrement the counter to literally 0. 2. Thread1: gets descheduled 3. Thread2: decrements the counter and finds the old value was 0, the if statement doesn't get executed 4. The counter is now all bits set to 1, including the zero bit 5. Thread1: gets rescheduled 6. Thread1: tries to set the zero flag, but the value doesn't match 7. Thread3: increments the counter, it sees the old value had the zero flag set and reports a failue, the counter is now 0 again with the zero flag bit not set 8. Thread4: increments the counter. it sees the old value is literally zero, and reports the success. the counter value is now 1, with the zero flag bit not set - this is not allowed by design, but the logic allows it because the counter bits are all 0, incuding the zero flag not being set.
Thanks but hell no! This is a sympathetic talk but it took 44 minutes to state that decrement() can overshoot and ruin the day. Also I strongly reject the second flag and read() “helping.” Decrement now has three atomic operations which are *exactly* locks as they put a LOCK on the memory bus and are also costly full barriers, plus new branches and what not. This is horrible. Zero is an absorbing state (can’t get out of if once entered) and that can indeed be expressed using the high bit. That’s the key idea and it’s great! But Read() should simply return zero if the high bit is set *or* the value was zero. What happens in the talk is that Read sometimes becomes a horribly slow write. No, no, no… Decrement() should simply OR the high bit with release semantics when reaching zero, etc. This can probably be greatly simplified.
It is so easy to make a bug in such code. Just imagine that you have some bug inside your wait-free code similar to this one. Fixing it is a nightmare for a developer other than the author, and even for the author it is challenging.