Introduction to Wait-free Algorithms in C++ Programming - Daniel Anderson - CppCon 2024

---

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.
---

---

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.
---

---

#concurrency #cpp #cplusplus #cppcon #cppprogramming #cplusplusprogramming #softwaredevelopment #softwareengineering #coding #code #technology #technews #programming #programmer

[spacechild]

That's a really great talk! Daniel must be a terrific teacher.

[StefaNoneD]

Pretty mind blowing and really creative solution!

[kontojutubowe]

Great talk. wish I could give it two likes.

[YourCRTube]

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.

[Roibarkan]

27:01 [slide 16] note that the C++ standard (c++23 and prior) doesn’t provide any assurance that the atomic-read-modify-write operations are wait-free, and all one can portably check/verify is if an operation is lock-free (vs. blocking). In fact, many popular C++ compiler implement fetch_add on x86 as a lock-free cas-loop. This means that it might be impossible to implement portable wait-free algorithms in “pure” c++ at the moment.
Daniel addresses some of this in 1:01:09 and 1:03:37

[Roibarkan]

4:23 [slide 4] note that the precondition for decrement seems suspicious in a concurrent world - what if the counter is 1 and 2 threads call decrement. The precondition is violated although neither of the threads could “protect itself” from the violation. In practice it’s fine because the typical behavior is that every thread that calls decrement does so after having earlier called increment_if_not_zero() and received a true result. Daniel discusses it in 44:10
Great talk Daniel - definitely worthy of the big room 😂

[jeffersoncarpenter]

RE legality of calling decrement around 44:00, I think "you know the counter is not 0" is accurate but can be made more specific: the ways you know the counter is not 0 are (1) you constructed the counter and have not decremented it yet, or (2) you incremented the counter successfully and have not decremented it yet. If you're in such a code branch, you can decrement the counter.

The logic here can be perfectly static - or the legality of decrementing can be carried around in a variable - but it's almost automatic to get that right, if you've written a logical program.

[rutabega]

I can't imagine myself using this technique in a million years, but such an interesting talk!

[freax]

Couldn't read() just return 1 if it sees that val is zero? Obviously, we can't return 0 because that would allow situations where the value switches from 1 to 0 to 1, but if we just lie and say that the decrement hasn't finished until it committed the zero flag, read could return 1, I think this would be entirely consistent for outside observers. One advantage of this would be that we don't need the helper flag anymore. Another advantage is that read always just reads and never branches and writes.

[ngideo]

Just want to say that a software engineer named Chip Hogg is epic. Cheers to you, Chip!

[syntaxed]

So young but such a great speaker - How is that even possible?

[FalcoGer]

@41: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.

[IvanYakimov-yq]

Wait-free algorighms were invented to make Lock-free look simple.

[MatthewWalker]

I wonder if the timing is more consistent with the wait-free counter. I would guess it would be, and that can be useful for real-time systems.

[billvon]

Is there any code that we can run e.g. to benchmark and so on? At least, author's own github doesn't have it yet...

[adamrushford]

Interesting I got the same results with my own testing, so I've gone with wait free for a game development environment but it looks like a tested swapping system might be best.

[omartechnologies]

Isn't the problem just pushing the goal-post to the top bit now being the thing that needs to be verified ? I have only reached 33:55 so I'm not sure if this is going to be addressed, but I suspect that there'd be a way to 'elect' or support other threads to all verify or agree that if one says the top bit is 0 .. (hence counter = 0), we all agree, and should end our threads or return that the counter is now zero..

[gracicot]

At 48:46, would it have been possible to just return 1 in the case where the counter is zero but without the flags? Would saying that read linearize before decrement work too? Because if the counter is at zero, then you know that at the beginning of decrement you were at one. If the decrement operation is not done, you could assume it's still one. If another thread increments in the meantime, then that 1 was true. Otherwise, it was as if decrement was called after since it will finish after the load. Am I right to assume this?

[LoneTech]

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.

[olegmytnyk]

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.