The Usual Arithmetic Confusions

by Shafik Yaghmour

There are a lot of aspects of C++ that are not well understood and lead to all sorts of confusion. The usual arithmetic conversions and the integral promotions are two such aspects. Certain binary operators (arithmetic, relational and spaceship) require their operands to have a common type. The usual arithmetic conversions are the set of steps that gets operands to a common type. While the integral promotions brings integral types smaller than int and unsigned int to either int or unsigned int depending on which one can represent all the values of the source type. This is one of the areas in C++ that comes directly from C, so pretty much all of these examples applies to C as well as C++.

We will see some examples with results that many may find surprising. After seeing some of these cases we will discuss the rules and how they explain each case. While covering each rule we will present examples to clarify the rule. We will referring to ILP32 and LP64 data models and it may help to familiarize yourself with the size of types in these models.

It would also help to understand integer literals and the rules around what the type of an integer literal will be in various cases e.g.

// https://cppinsights.io/s/0ffee264 
void f() { 
    auto x1 = 1; // Integer literal 1 will have type int 
    auto x2 = 1U; // Integer literal 1L will have type unsigned int 
    auto x3 = 1L; // Integer literal 1L will have type long int 
    auto x4 = 1UL; // Integer literal 1UL will have type unsigned long int 
} 

I will be including C++ Insights links for many examples.

Introduction to Wait-free Algorithms in C++ Programming

by Daniel Anderson

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.