Skip to content

24. Concurrency

[Source: include/ADS/concurrent/SPSCQueue.h, MPSCQueue.h, MPSCInbox.h, MPMCQueue.h, WorkStealingDeque.h, ConcurrentUnionFind.h, ConcurrentCuckooTable.h, ConcurrentFlatTable.h, MultiQueue.h, EventCount.h, Backoff.h, StealablePriorityQueue.h, LockFreePriorityQueue.h, and their impl/*.tpp]

We are concerned in this chapter with the structures that several threads of one process read and change at the same time, without a lock or with as few locks as possible. They are the queues between producers and consumers, the deque of the scheduling by work stealing, the union-find and the hash tables that the threads share, the relaxed priority queue, the event count on which a thread sleeps until a condition holds, the priority queues of the workers of a parallel search, from which the idle workers steal, and an exact priority queue without locks. These structures are the bricks of the parallel algorithms and of the runtime of the workers of chapter 25, and of the parallel searches of the library. Each of them gives, in a precise sense, the result of a sequential structure of the earlier chapters; its cost, however, depends on how the threads meet in memory more than on the number of its operations. In the sets of §1.9, the headers of this chapter are all advanced.

We organize the chapter as follows. In §24.1 we fix the model of the threads and of the memory, and the meaning of correct and of nonblocking, on which every later claim rests; §24.2 summarizes the structures and their costs. Then §24.3 and §24.4 treat the queues, §24.5 the deque of work stealing, §24.6 the union-find, and §24.7 and §24.8 the two hash tables. We treat the MultiQueue in §24.9, the ways in which a thread waits in §24.10, the priority queues that are stolen in §24.11, and the exact priority queue without locks in §24.12. The file impl/Spin.tpp holds only two helpers that the other headers share (the pause of the processor in a loop that spins, and the prefetch of a line of cache), and we describe them where they are used.

24.1 The model of the threads and of the memory

We call shared object a structure whose operations are called by several threads, each thread being a sequence of calls. An operation takes time, from its invocation to its response, and two operations of two threads may overlap. A sequential specification (e.g., the axioms of the QUEUE of chapter 4) does not specify overlapping operations, and one needs a condition that relates the runs of the shared object to those of the sequential one. Throughout the chapter we use the condition of Herlihy and Wing 1990. We say that a run is linearizable if each operation seems to take effect at one instant between its invocation and its response, its linearization point, and the responses are those of the sequential object on the operations taken in the order of their points; an object is linearizable if all its runs are. A thread may then reason on a linearizable object as on the sequential structure, and the headers name the point of each operation (e.g., the compare-and-swap that claims a place, or the store that publishes an item). Figure 24.1 shows a run of three operations on a queue. The push of b ends before the pop starts, while the push of a overlaps both; the answer b of the pop is explained by the order of the points push(b), push(a), pop.

Figure 24.1. Three operations of three threads on a FIFO queue, each an interval from its invocation to its response, with its linearization point (the dot); the order of the points, push(b), push(a), pop, explains the answer b of the pop.

We call an implementation blocking if a thread stopped in the middle of an operation (descheduled by the system, or simply "slow") may keep the other threads from completing theirs, as a thread that holds a lock does. We call it lock-free if, whatever the threads that stop, some thread that keeps running completes an operation in a finite number of its steps. Thus the system as a whole makes progress, though a single thread may starve. It is wait-free if each thread that keeps running completes each of its operations in a finite number of its steps (Herlihy 1991). A loop that retries a compare-and-swap is lock-free, since the compare-and-swap of a thread fails only because that of another thread succeeded; it is not wait-free, however, since the same thread may lose every round. We write \(\mathrm{CAS}( x , e , d )\) for the compare-and-swap, one atomic read-modify-write that sets \(x \gets d\) and answers true if \(x = e\), and answers false otherwise (in the code it also writes the value found into \(e\)).

The memory is that of C++, which the headers use through std::atomic (Boehm and Adve 2008). We call data race a pair of accesses of two threads to one location, one of them a write, neither of them atomic and neither ordered before the other. A program with a data race has no defined meaning, and a word that two threads may access at once is therefore always an atomic. Each atomic access carries an order. A relaxed access is atomic and nothing more. A store with release and a load with acquire that reads its value synchronize: the writes that the storing thread made before the store happen before the reads that the loading thread makes after the load. This is how an item written by plain stores is handed to another thread, by publishing afterwards an index or a pointer with release. A sequentially consistent access is acquire and release and, furthermore, takes a place in a single total order \(S\) of all such accesses (and of the sequentially consistent fences), consistent with the order of each thread.

Between threads, the orders come only from these. A relaxed access orders no other access, and two threads that each write one word and then read the word of the other, with release and acquire, may both miss the write of the other; only \(S\) excludes it. Several lemmas below (the last item of a deque, the growth of a hash table, the sleep of a waiter) rest on this pattern, and we prove them by placing four accesses in \(S\).

We now recall two facts of the hardware that decide the costs. Indeed, a write to a line of cache takes the line away from the caches of the other cores, which then miss on it. Two words written by two threads on one line (false sharing) make the line travel at each write; the headers therefore put each such word on a separate line, often on a pair of lines, since many processors of the x86 family fetch the lines two at a time. Also, a read-modify-write (e.g., a compare-and-swap or an exchange) costs several times a plain access, and it orders the memory around it. A structure is "fast" when its common case has none, and Table 24.1 states, for each operation, how many it pays. Finally, we recall the ABA problem of a compare-and-swap on a pointer. A thread reads the top \(A\) of a stack and its successor \(B\); another thread pops \(A\) and \(B\) and pushes \(A\) again; then the compare-and-swap of the first thread from \(A\) to \(B\) succeeds, and puts back on the stack a cell that is no longer there. In ADS the headers avoid it by construction rather than by counters of versions (cf. Lemma 24.3).

Throughout the chapter \(p\) is the number of the threads that use an object and \(c\) the capacity of a bounded queue, a power of 2, so that the index \(i\) lies at the place \(i \bmod c\), computed by a mask. The head \(h\) and the tail \(t\) of a queue are integers that only grow, and the items are those of the indices in \([ h , t )\).

24.2 The structures and their costs

In Table 24.1 we list the structures of the area, the threads that each admits, the progress it guarantees and the cost of its operations, which the following sections prove one by one.

Table 24.1. The structures of ADS/concurrent, the threads they admit, their progress and the cost of their operations; \(m\) is the number of the pairs of a queue or of a heap, \(n\) that of the elements of the union-find or of the queues of the MultiQueue, and \(k\) that of the messages taken at once.

Structure Threads Progress Cost of an operation
SPSCQueue one producer, one consumer wait-free \(O( 1 )\), no read-modify-write
MPSCQueue many producers, one consumer wait-free push but for the allocation of a block \(O( 1 )\) amortized, no read-modify-write but per block
MPSCInbox many producers, one consumer lock-free push, wait-free take one CAS per push, one exchange per take, plus \(O( k )\)
MPMCQueue many producers, many consumers lock-free but for a thread stopped between claim and publication one CAS per operation without contention
WorkStealingDeque one owner, many thieves wait-free calls, a steal may fail (abort); retried steals lock-free \(O( 1 )\) amortized for the owner, a CAS only on the last item; one per steal
ConcurrentUnionFind any lock-free \(O( \log_{2 + m / n} n )\) amortized on one thread
ConcurrentCuckooTable any blocking (a lock per region), lookups without locks for atomic keys and values \(O( 1 )\) expected, \(O( 1 )\) amortized for the doublings
ConcurrentFlatTable any wait-free lookups but across a growth, insertions blocking only during a growth (and the renewal of a group, with epochs) \(O( 1 )\) expected, \(O( 1 )\) amortized for the growths; no removals; clear() \(O( 1 )\) amortized with epochs
MultiQueue any, by a handle each blocking (a lock per queue, taken at the first try) \(O( \log m )\) amortized, \(q / ( q - 1 )\) draws expected; relaxed
StealablePriorityQueue one owner, many thieves wait-free for the owner, lock-free steal \(O( \log m )\) for the owner, no read-modify-write; one exchange per steal
LockFreePriorityQueue any, by a handle each lock-free but for the allocation of a node; reclamation blocking \(O( \log m )\) expected insertion, two CAS on average; one FAO per DeleteMin, plus the prefix walked; exact
EventCount any a waiter sleeps, a notifier never waits a fence and a read when nobody waits
SingleWriterFlatTable one writer, many readers wait-free for the writer but for the allocation of a growth, wait-free lookups but across a growth \(O( 1 )\) expected, no read-modify-write; \(O( 1 )\) amortized for the growths
MinBoard one writer per slot, many readers wait-free a load and at most a store per publish, \(p\) loads per min(); coherence only

We remark that the queues of one producer or of one consumer are cheaper than the general one because each of their indices has a single writer. Such an index is written by plain stores with release and read by loads with acquire, and no read-modify-write is needed; many writers of one index, instead, must agree by a compare-and-swap, and contend on its line. This remark runs through the whole chapter. Indeed, the structures are designed so that the "common" case of an operation writes only words that no other thread writes, and they pay a read-modify-write only where two threads may really want the same thing (e.g., the last item of a deque, a free place of a table, or an offer of a queue that is stolen, cf. §24.11).

Each structure exposes its template parameters as member types, Item for the items of the queues and of the deque, Key and Item for the pairs of the priority queues (and, in StealablePriorityQueue, Entry for the pair kept and Bound for its bound, see §24.11), and Key and Value for the tables; we name them in the following sections only where they matter.

24.3 Queues of one producer

SPSCQueue is the circular vector of the queue of chapter 4 shared by two threads. Only the producer writes the tail \(t\), and only the consumer writes the head \(h\); each index is thus an atomic written with release and read with acquire, and no lock is needed (the queue of Lamport 1983). The queue is full when \(t - h = c\) and empty when \(h = t\). Since the indices only grow and are reduced by the mask at each access, the two tests hold also when the integers wrap around. Each thread keeps besides a copy of the index of the other one, \(\mathit{seen}_P \le h\) for the producer and \(\mathit{seen}_C \le t\) for the consumer, and reads the index again only when the queue looks full or empty by the copy (Lee, Bu and Chandranmenon 2010). A stale copy is never ahead of the index it copies; hence it can only make the queue look fuller or emptier than it is. Figure 24.2 shows the vector before and after a push, with both copies stale and neither of them read.

Figure 24.2. An SPSCQueue of capacity 8 with the items b, c, d, before and after push(e); the producer writes the place \(t \bmod 8\) and then the tail, and the copies \(\mathit{seen}_P\) of the head and \(\mathit{seen}_C\) of the tail, both stale, are not read, since the queue looks neither full to the producer nor empty to the consumer.

The class gives the producer push() and emplace(), the consumer pop() and tryPop(), and both of them the batch operations and the wait of §24.10; its public members are

// declarations of <ADS/concurrent/SPSCQueue.h>
template< class T >
class SPSCQueue
{
 public:
 explicit SPSCQueue( std::size_t capacity );
 bool push( const T & v );
 bool push( T && v );
 template< class... Args >
 bool emplace( Args &&... args );
 std::optional< T > pop( void );
 bool tryPop( T & x );
 template< class It >
 std::size_t pushMany( It first , std::size_t n );
 template< class F >
 std::size_t consume( F && f , std::size_t n = std::size_t( -1 ) );
 void notify( void ) noexcept;
 void waitPop( T & x );
 std::size_t size( void ) const;
 std::size_t capacity( void ) const;
 };

and two threads use it as follows, the producer with push(), which answers false on a full queue, and the consumer with waitPop():

ADS::SPSCQueue< int > Q( 1024 );  // c = 1024
std::thread producer( [ & ]() {
 for( int i = 0 ; i < 100 ; ++i ) {
  while( ! Q.push( i ) ) {
   }  // full: try again
  Q.notify();
  }
 } );
long sum = 0;
for( int i = 0 ; i < 100 ; ++i ) {
 int x;
 Q.waitPop( x );  // the items 0, 1, ..., 99
 sum += x;
 }
producer.join();  // sum is 4950

Algorithm 24.1. The push and the pop of SPSCQueue (Lamport 1983, with the copies of Lee et al. 2010 and the wait for a batch of Wang et al. 2013); \(A[ 0 .. c - 1 ]\) is the vector.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{emplace}( x ) \cr 2 & \quad t' \gets t\quad \triangleright\ \text{relaxed, only this} \text{ thread writes it} \cr 3 & \quad \textbf{if}\ t' - \mathit{seen} = c\ \textbf{then} \cr 4 & \qquad \mathit{seen} \gets h\quad \triangleright\ \text{acquire:} \text{ the places freed are seen free} \cr 5 & \qquad \textbf{if}\ t' - \mathit{seen} = c\ \textbf{then} \ \textbf{return false} \cr 6 & \quad A[ t' \bmod c ] \gets x \cr 7 & \quad t \gets t' + 1\quad \triangleright\ \text{release: the item} \text{ is written before the tail} \cr 8 & \quad \textbf{return true} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{tryPop}( x ) \cr 2 & \quad h' \gets h\quad \triangleright\ \text{relaxed, only this} \text{ thread writes it} \cr 3 & \quad \textbf{if}\ h' = \mathit{seen}\ \textbf{then} \cr 4 & \qquad \mathrm{prefetch}( A[ h' \bmod c ] );\ \mathit{seen} \gets t\quad \triangleright\ \text{acquire} \cr 5 & \qquad \textbf{if}\ \mathit{streaming}\ \textbf{and}\ 0 < \mathit{seen} - h' < \min( 64 , c / 2 )\ \textbf{then} \cr 6 & \qquad\quad \text{wait 64 pauses};\ \mathit{seen} \gets t \cr 7 & \qquad \textbf{if}\ h' = \mathit{seen}\ \textbf{then} \ \mathit{streaming} \gets \textbf{false};\ \textbf{return false} \cr 8 & \quad x \gets A[ h' \bmod c ] \cr 9 & \quad h \gets h' + 1\quad \triangleright\ \text{release: the place} \text{ is read before it is freed} \cr 10 & \quad \mathit{streaming} \gets \textbf{true}; \ \textbf{return true} \end{array} \]

We view the correctness of the queue as the transfer of each item, and of each place, between the two threads in the order of happening before. Two pairs of a release and an acquire give it.

Lemma 24.1. Let the producer write the item of the index \(t\) and then store \(t + 1\) in the tail with release, and let the consumer load the tail with acquire, read the items of the indices below it, and then store the new head with release, which the producer loads with acquire before it reuses a place. Then the consumer reads each item whole, after it was written, and the producer never overwrites an item not yet read:

\[ \mathrm{write}( A[ i ] ) \to \mathrm{read}( A[ i ] ) \to \mathrm{write}( A[ i + c ] ) \quad \forall i , \tag{24.1} \]

where \(\to\) is the order of happening before. The queue is wait-free, and it is linearizable with the point of a push at its store of the tail and that of a pop at its store of the head (at its load of the tail if it finds the queue empty).

Proof. We follow the item of the index \(i\). Its write precedes in the producer the release store of a tail larger than \(i\), which the consumer reads by an acquire load before it reads \(A[ i ]\). These two accesses synchronize, whence the first arrow of (24.1). Similarly, the second arrow follows from the argument on the head, since the producer writes \(A[ i + c ]\) only after it has read a head larger than \(i\), i.e., after it has found \(t - h < c\). A stale copy can only make the test of full (of empty) succeed where the index would make it fail, and the copy is read again before the queue is declared full (empty); thus no push and no pop fails wrongly. Each operation runs a constant number of steps, whatever the other thread does. At its store of the tail a push makes its item visible at the end of the queue, and at its store of the head a pop removes the first item, which it has read; the order of these points is the order of the operations of the sequential queue. \(\square\)

The implementation follows Algorithm 24.1 line by line; it builds the item in place, and it compares the index with the copy before it reads the index of the other thread (lines 3 to 5 of emplace()), so that the common case reads no line that the other thread writes.

Two "details" of engineering change the time of a queue between two cores several times over, without changing its argument. First, the two indices and the two copies lie on four separate lines of cache, grouped in pairs of lines. A thread that spins on a full or empty queue rewrites its copy, and this layout keeps it from invalidating the line that the other thread writes, also through the prefetch of the adjacent line. Also, the places are raw memory with a line of padding at each end, and the first and the last items share no line with other data. Second, a consumer that is right behind a "streaming" producer, and looks again at once, would take from it at each item the lines of the tail and of the item it is writing. When the last pop took an item and the consumer finds some new ones, but fewer than \(\min( 64 , c / 2 )\), it therefore waits 64 pauses of the processor for a batch before it takes them (the backtracking of B-Queue, Wang et al. 2013). Then the lines travel once per batch. After a pop that found no item, instead, the consumer takes at once what comes, and a single item after a "silence" costs no wait. Furthermore, a consumer that finds the queue empty prefetches the line of its next place before it reads the tail again. When the item has come, the two lines travel together, and a round trip between two threads usually costs one miss a side instead of two in a row.

Two batch operations publish several items by one store of the tail and free several places by one store of the head, which is the "cheapest" way in which one can move many items between two threads. Note that consume( f , n ) calls \(f\) on each item in place, and dequeues the items called also when a call throws.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{pushMany}( x_0 , \ldots , x_{n - 1} ) \cr 2 & \quad t' \gets t;\ \textbf{if}\ t' - \mathit{seen} < n \ \textbf{then}\ \mathit{seen} \gets h\quad \triangleright \ \text{acquire} \cr 3 & \quad k \gets \min\{ n , c - ( t' - \mathit{seen} ) \} \cr 4 & \quad \textbf{for}\ j \gets 0\ \textbf{to}\ k - 1\ \textbf{do} \ A[ ( t' + j ) \bmod c ] \gets x_j \cr 5 & \quad t \gets t' + k\quad \triangleright\ \text{release}; \ \textbf{return}\ k \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{consume}( f , n ) \cr 2 & \quad h' \gets h;\ \textbf{if}\ h' = \mathit{seen}\ \textbf{then} \ \mathit{seen} \gets t\quad \triangleright\ \text{acquire} \cr 3 & \quad k \gets \min\{ n , \mathit{seen} - h' \} \cr 4 & \quad \textbf{for}\ j \gets 0\ \textbf{to}\ k - 1\ \textbf{do} \ f( A[ ( h' + j ) \bmod c ] ) \cr 5 & \quad h \gets h' + k\quad \triangleright\ \text{release}; \ \textbf{return}\ k \end{array} \]

MPSCQueue serves many producers and one consumer, and is unbounded. Each producer has a lane, i.e., a queue of one producer and one consumer, and the producers never compete with one another. Its consumer takes the lanes in turn, and drains the one it is on before it moves to the next. We build a lane as a list of blocks of \(B\) places (1024 by default, a power of 2), after the list of bounded buffers of Aldinucci et al. 2012. Each producer writes the places of its last block in order and publishes, after each item, their count \(f\) in the block, by a store with release and no read-modify-write. When the block is full it links a new one after it, by a store with release of the link. In turn, the consumer reads the count of its block once for all the items that it shows, and takes them. When it has taken the \(B\) items of a block and finds the next one linked, it gives the block back to its lane, on a stack that the producer empties at once, by an exchange, when it needs a block and before it allocates one (Figure 24.3). A producer is a handle of class Producer that producer() returns, used by one thread at a time. All the lanes form a list built by the push of Treiber of §24.4, and they live as long as the queue, also when their producer is gone and its items are still to be taken.

Figure 24.3. An MPSCQueue with two lanes of blocks of 4 places; \(f\) is the count of the items written in a block, the consumer reads from the place below its arrow and the producer writes at the place under its own; the first lane has a block that the consumer gave back, on the stack from which the producer takes its next block.

Its public members are those below; a producer pushes through its handle,

// declarations of <ADS/concurrent/MPSCQueue.h>
template< class T , std::size_t B = 1024 >
class MPSCQueue
{
 public:
 class Producer
 {
  public:
  template< class... Args >
  void emplace( Args &&... args );
  void push( const T & v );
  void push( T && v );
  void notify( void );
  };
 Producer producer( void );
 bool tryPop( T & x );
 std::size_t popInto( T * out , std::size_t n );
 void waitPop( T & x );
 std::size_t waitPopInto( T * out , std::size_t n );
 bool empty( void );
 };

e.g., four threads that each send 1000 items to one consumer:

ADS::MPSCQueue< int > Q;
std::vector< std::thread > T;
for( int k = 0 ; k < 4 ; ++k )
 T.emplace_back( [ & , k ]() {
  auto P = Q.producer();  // one lane per handle
  for( int i = 0 ; i < 1000 ; ++i )
   P.push( 1000 * k + i );
  P.notify();
  } );
int x , got = 0;
while( got < 4000 ) {
 Q.waitPop( x );  // in order within each lane
 ++got;
 }
for( auto & t : T )
 t.join();

Algorithm 24.2. The operations of MPSCQueue (the list of bounded buffers of Aldinucci et al. 2012, the wait for a batch of Wang et al. 2013, and the stack of Treiber 1986 for the lanes).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{emplace}( x ) \cr 2 & \quad p \gets b.f\quad \triangleright\ \text{relaxed, only this} \text{ thread writes it} \cr 3 & \quad \textbf{if}\ p = B\ \textbf{then} \cr 4 & \qquad n \gets \text{a spare block, else one of the blocks} \text{ given back (all taken by an exchange), else a new one} \cr 5 & \qquad n.f \gets 0;\ b.\mathit{next} \gets n\quad \triangleright \ \text{release};\ b \gets n;\ p \gets 0 \cr 6 & \quad b[ p ] \gets x \cr 7 & \quad b.f \gets p + 1\quad \triangleright\ \text{release: the item} \text{ before its count} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{popInto}( \mathit{out} , n ) \cr 2 & \quad \textbf{foreach}\ \text{lane } \ell \text{ in turn, from the} \text{ last one drained}\ \textbf{do} \cr 3 & \qquad k \gets 0 \cr 4 & \qquad \textbf{while}\ k < n\ \textbf{do} \cr 5 & \qquad\quad \textbf{if}\ h = B\ \textbf{then} \cr 6 & \qquad\qquad \textbf{if}\ b.\mathit{next} = \textbf{nil} \ \textbf{then break}\quad \triangleright\ \text{acquire} \cr 7 & \qquad\qquad \text{push } b \text{ on the stack given back of } \ell \text{ by a CAS};\ b \gets b.\mathit{next};\ h \gets 0 \cr 8 & \qquad\quad f \gets b.f\quad \triangleright\ \text{acquire} \cr 9 & \qquad\quad \textbf{if}\ f - h < \min( B , 64 )\ \textbf{and}\ f < B\ \textbf{and}\ \ell.\mathit{streaming}\ \textbf{then} \cr 10 & \qquad\qquad \text{wait 64 pauses};\ f \gets b.f \cr 11 & \qquad\quad \textbf{if}\ h = \min( f , h + n - k ) \ \textbf{then break} \cr 12 & \qquad\quad \textbf{while}\ h < \min( f , h + n - k ) \ \textbf{do} \cr 13 & \qquad\qquad \mathit{out}[ k ] \gets b[ h ];\ h \gets h + 1;\ k \gets k + 1 \cr 14 & \qquad \ell.\mathit{streaming} \gets k > 0 \cr 15 & \qquad \textbf{if}\ k > 0\ \textbf{then return}\ k \cr 16 & \quad \textbf{return}\ 0 \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{producer}() \cr 2 & \quad \ell \gets \text{a new lane with one empty block} \cr 3 & \quad \textbf{repeat}\ \ell.\mathit{next} \gets L\ \textbf{until} \ \mathrm{CAS}( L , \ell.\mathit{next} , \ell )\quad \triangleright \ \text{release} \cr 4 & \quad \textbf{return}\ \ell \end{array} \]

We may thus see each lane as a queue of Lamport whose block holds the count of its items in place of the tail, and Lemma 24.1 applies (cf. (24.1)) to it place by place: the item is written before its count is published, and the consumer reads the count with acquire before the items. A block is reused by its producer only after the consumer has read all its \(B\) items and has pushed it, with release, on the stack of the blocks given back. Its producer takes that stack by an exchange with acquire, and therefore (24.1) holds for each place of a block across its reuses. We observe that this stack has one pusher, the consumer, and one taker, which takes it all at once; it has thus no ABA problem (cf. Lemma 24.3).

Lemma 24.2. A lane of MPSCQueue that has held at most \(m\) items at once keeps at most \(\lceil m / B \rceil + 1\) blocks. A push costs \(O( 1 )\) time and no read-modify-write, but for the push that finds its block full, which costs at most an exchange (none when its spare stack has a block), or an allocation when the lane has fewer blocks than it needs.

Proof. At any moment the blocks of a lane in use are those from the block of the consumer to that of the producer, which hold the items present; they are at most \(\lceil m / B \rceil + 1\), since the first and the last may be partly empty. A block out of them lies in one of the two stacks of blocks to reuse, and a producer allocates a block only when both stacks are empty, i.e., when all the blocks of the lane are in use. Hence the lane never holds more blocks than the largest number in use at once. A push writes its item and a count, two stores with no read-modify-write, unless it finds its block full; then it takes a block from its spare stack, or all the stack given back by an exchange, or a new block. \(\square\)

We conclude that in a steady state a lane cycles over the same blocks, which stay in the caches. Here the count and the link of a block share a line that only the producer writes, and the consumer touches the lines of the producer once per batch, with the same wait for a batch as SPSCQueue (when a call took some items and the next one finds fewer than \(\min( B , 64 )\) in the block). Furthermore, the consumer of either queue may sleep until an item comes, by waitPop(), on the event count of §24.10 (and the consumer of MPSCQueue by waitPopInto( out , n ), the popInto() that sleeps until at least one item comes); the producers then call notify() after their pushes.

24.4 Queues of many producers or of many consumers

MPSCInbox is the "simplest" of the queues of many producers, e.g., the inbox of a worker of a parallel search, into which the other workers send their messages. A producer pushes a cell on a stack by a loop of \(\mathrm{CAS}( \mathit{top} , \mathit{next} , \mathit{cell} )\) (the stack of Treiber 1986). Its consumer takes all the stack at once, by \(\mathrm{exchange}( \mathit{top} , \mathbf{nil} )\), and reverses it; the messages of each producer thus come out in the order in which it sent them (Figure 24.4). Hence take() costs one atomic operation however many messages there are, plus \(O( k )\) time for the \(k\) messages taken, and the consumer never competes with the producers on single items. This inbox suits the messages that usually come in bursts, at the price of an allocation per message.

Figure 24.4. The stack of an MPSCInbox before and after push(d), whose compare-and-swap links the new cell above the top it read, and after take(), which exchanges the top with nil and returns the messages reversed, in the order of sending.

Its public members are

// declarations of <ADS/concurrent/MPSCInbox.h>
template< class T >
class MPSCInbox
{
 public:
 void push( T v );
 std::vector< T > take( void );
 std::vector< T > waitTake( void );
 bool empty( void ) const;
 };

where waitTake() is the take() that sleeps until a message comes, on the event count of §24.10.

Algorithm 24.3. The push and the take of MPSCInbox (Treiber 1986).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{push}( v ) \cr 2 & \quad c \gets \text{a new cell of } v \cr 3 & \quad \textbf{repeat}\ c.\mathit{next} \gets \mathit{top} \ \textbf{until}\ \mathrm{CAS}( \mathit{top} , c.\mathit{next} , c )\quad \triangleright\ \text{release} \cr 4 & \quad \mathrm{notify}() \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{take}() \cr 2 & \quad c \gets \mathrm{exchange}( \mathit{top} , \textbf{nil} )\quad \triangleright\ \text{acquire} \cr 3 & \quad L \gets \text{the values of the cells from } c \text{, newest} \text{ first} \cr 4 & \quad \textbf{return}\ L \text{ reversed} \end{array} \]

Lemma 24.3. Let the cells of a stack of Treiber be pushed one at a time, by a compare-and-swap whose new value is a cell of the pushing thread, and be taken only all at once, by an exchange. Then the ABA problem does not occur: each successful push links its cell above the true top, and each take returns all the cells pushed before it that are not yet taken. Moreover, the push is lock-free, and the take is wait-free and costs one exchange and \(O( k )\) time for the \(k\) cells it returns.

Proof. We recall that the ABA problem needs a compare-and-swap whose expected value was read before the cell it names was removed and put back. Here we have only one compare-and-swap, that of a push, whose expected value is the top read by the pusher. If it succeeds, the top is that value at that instant, whatever happened in between (e.g., a take, then pushes that brought the top back to the same address after a reuse of the memory); the cell becomes the new top above the cell that is really there, since a push never reads the successor of the top. No cell is ever popped singly. An exchange is one atomic step, and the cells it returns are those of the pushes that precede it in the order of the modifications of \(\mathit{top}\). Finally, a push publishes its cell with release and the take reads the top with acquire, and therefore the contents of the cells are seen. The compare-and-swap of a push fails only if the top changed after the pusher read it, i.e., only if another push or a take succeeded in between, and some thread thus completes an operation at each failure; a take runs one exchange and then reverses the \(k\) cells it got, which no other thread can reach any more. \(\square\)

The same argument holds for the list of the lanes of MPSCQueue and for its stacks of blocks given back. A push is not wait-free, however, since a pusher may lose every round to other pushers.

MPMCQueue is the bounded queue of many producers and many consumers of Vyukov 2010, on a circular vector of \(c\) places. Each place carries a sequence number besides the room of an item: the place of the index \(i\) holds the sequence \(i\) when it waits for the push of \(i\), \(i + 1\) when it holds the item of \(i\), and \(i + c\) when that item has been taken and the place waits for the push of \(i + c\). We let a producer read the tail \(p\) and the sequence \(s\) of its place. If \(s = p\) it claims the index by \(\mathrm{CAS}( t , p , p + 1 )\), builds the item and publishes it by storing the sequence \(p + 1\) with release; if \(s < p\) the queue is full; and if \(s > p\) another producer took \(p\), and it reads the tail again. A consumer does the same on the head \(q\) with the sequence \(q + 1\), and frees the place by storing \(q + c\) (Figure 24.5). Its tail and its head lie on separate lines, and producers and consumers meet only at the places they share, with one read-modify-write per operation.

Figure 24.5. An MPMCQueue of capacity 4 with the items of the indices 5 and 6, before and after a push that claims the index 7: the place 3 held the sequence 7 (free for the index 7), and the push writes the item and then the sequence 8; the place 0 holds the sequence 8, i.e., it waits for the push of the index 8.

Its public members are

// declarations of <ADS/concurrent/MPMCQueue.h>
template< class T >
class MPMCQueue
{
 public:
 explicit MPMCQueue( std::size_t capacity );
 template< class... Args >
 bool emplace( Args &&... args );
 bool push( const T & v );
 bool push( T && v );
 bool tryPop( T & x );
 std::size_t size( void ) const;
 bool empty( void ) const;
 std::size_t capacity( void ) const;
 };

where push() answers false on a full queue and tryPop() on an empty one, and size() is exact only when no operation runs.

Algorithm 24.4. The push and the pop of MPMCQueue (Vyukov 2010); \(C[ i ]\) is the place \(i \bmod c\) and \(C[ i ].s\) its sequence.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{emplace}( x ) \cr 2 & \quad p \gets t \cr 3 & \quad \textbf{loop} \cr 4 & \qquad s \gets C[ p ].s\quad \triangleright\ \text{acquire} \cr 5 & \qquad \textbf{if}\ s = p\ \textbf{then}\quad \triangleright \ \text{the place is free for } p \cr 6 & \qquad\quad \textbf{if}\ \mathrm{CAS}( t , p , p + 1 ) \ \textbf{then} \cr 7 & \qquad\qquad C[ p ].x \gets x;\ C[ p ].s \gets p + 1\quad \triangleright\ \text{release} \cr 8 & \qquad\qquad \textbf{return true} \cr 9 & \qquad\quad \textbf{else}\ p \gets t\quad \triangleright \ \text{the CAS failed and read it} \cr 10 & \qquad \textbf{else if}\ s < p\ \textbf{then return false}\quad \triangleright\ \text{full} \cr 11 & \qquad \textbf{else}\ p \gets t\quad \triangleright\ \text{another} \text{ producer took } p \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{tryPop}( x ) \cr 2 & \quad q \gets h \cr 3 & \quad \textbf{loop} \cr 4 & \qquad s \gets C[ q ].s\quad \triangleright\ \text{acquire} \cr 5 & \qquad \textbf{if}\ s = q + 1\ \textbf{then}\quad \triangleright \ \text{the item of } q \text{ is there} \cr 6 & \qquad\quad \textbf{if}\ \mathrm{CAS}( h , q , q + 1 ) \ \textbf{then} \cr 7 & \qquad\qquad x \gets C[ q ].x;\ C[ q ].s \gets q + c\quad \triangleright\ \text{release} \cr 8 & \qquad\qquad \textbf{return true} \cr 9 & \qquad\quad \textbf{else}\ q \gets h \cr 10 & \qquad \textbf{else if}\ s < q + 1\ \textbf{then return false}\quad \triangleright\ \text{empty} \cr 11 & \qquad \textbf{else}\ q \gets h \end{array} \]

We remark that the implementation compares the sequence with the index on their difference, taken as a signed integer; the test thus holds across the wrap-around of the integers, as the tests of SPSCQueue do.

Lemma 24.4. In MPMCQueue, each index is claimed by one producer and by one consumer. The consumer of the index \(i\) reads the item that the producer of \(i\) wrote, and the producer of \(i + c\) writes the place only after the consumer of \(i\) has read it; a failed compare-and-swap means that another thread claimed the index.

Proof. We note first that a compare-and-swap of the tail from \(p\) to \(p + 1\) succeeds for one thread only, since the tail never goes back, and the same holds for the head. In fact, the producer of \(i\) publishes by storing \(i + 1\) with release after it has written the item, and the consumer claims \(i\) only after an acquire load that read \(i + 1\), whence the first arrow of (24.1). In turn, the consumer stores \(i + c\) with release after it has read the item, and the producer of \(i + c\) claims its index only after it has read the sequence \(i + c\) with acquire, whence the second one. A producer that reads a sequence below \(p\) finds the item of \(p - c\) not yet taken, i.e., the queue full, and one that reads a sequence above \(p\) was overtaken, and reads the tail again. Also, the failure of its compare-and-swap means that another producer claimed \(p\), which is progress of the queue. Consumers are symmetric. \(\square\)

The queue is lock-free in the common case, but not in the strict sense of §24.1. In fact, a thread stopped between its compare-and-swap and its publication holds up the threads that come round to its place, which find a sequence that means neither "free" nor "full". For the same reason a pop may answer that the queue is empty while a push that has claimed its index has not yet published it, which is consistent with a linearization point of the push at its publication. We remark that the rings of Nikolaev 2019, with a cycle per place, are lock-free in the strict sense, at the price of a somewhat more complex protocol. In chapter 25 the farm takes its tasks from an MPMCQueue; there such a stop happens only when the system deschedules a thread, and it then delays the other threads only until that thread runs again.

24.5 The deque of work stealing

In the scheduling by work stealing each worker pushes and takes its tasks at the bottom of its deque, as on a stack, which keeps the tasks it made last, and their data, in its cache. An idle worker steals the oldest task, at the top of the deque of another worker; in a computation by fork and join this task is often the root of a "large" subtree of work (Blumofe and Leiserson 1999; the bound on the time of this schedule is in chapter 25). WorkStealingDeque is the deque of Chase and Lev 2005. Its owner thread pushes and takes at the bottom, and any other thread steals from the top, without locks, on a circular vector of \(2^k\) places that the owner doubles when it is full. In it, the bottom \(b\) is written by the owner only, and the top \(t\), which only grows, only by a compare-and-swap; the items are those of \([ t , b )\), at the places of their indices modulo the size of the vector (Figure 24.6). Its items are kept in atomics of relaxed order, and their type must therefore be trivially copyable (e.g., an index or a pointer to a task).

Figure 24.6. A WorkStealingDeque of 8 places with the items a, b, c in \(\lbrack t , b ) = \lbrack 2 , 5 )\), after take() of the owner, which takes c at the bottom, and after steal() of a thief, which takes a at the top; the violet cell is the place that the operation empties.

Its public members are

// declarations of <ADS/concurrent/WorkStealingDeque.h>
template< class T >
class WorkStealingDeque
{
 public:
 explicit WorkStealingDeque( std::size_t capacity = 1024 );
 void push( T x );                 // the owner
 std::optional< T > take( void );  // the owner
 bool steal( T & x );              // any thief
 std::size_t size( void ) const;
 bool empty( void ) const;
 std::size_t capacity( void ) const;
 };

in which push() doubles the vector when it is full, so that only take() and steal() may fail, the latter also when it loses a race.

Algorithm 24.5. The operations of WorkStealingDeque (Chase and Lev 2005, with the orders of memory of Lê et al. 2013); \(A\) is the vector of \(|A|\) places, the index \(i\) at its place \(i \bmod |A|\).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{push}( x ) \cr 2 & \quad b' \gets b;\ t' \gets t\quad \triangleright\ \text{relaxed} \text{ and acquire} \cr 3 & \quad \textbf{if}\ b' - t' = |A|\ \textbf{then} \cr 4 & \qquad A' \gets \text{a vector of } 2 |A| \text{ places}; \ \textbf{for}\ i \gets t'\ \textbf{to}\ b' - 1\ \textbf{do}\ A'[ i ] \gets A[ i ] \cr 5 & \qquad A \gets A'\quad \triangleright\ \text{release, the old} \text{ vector kept for the thieves} \cr 6 & \quad A[ b' ] \gets x \cr 7 & \quad b \gets b' + 1\quad \triangleright\ \text{release} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{take}() \cr 2 & \quad b' \gets b - 1;\ b \gets b'\quad \triangleright \ \text{sequentially consistent, before the read of } t \cr 3 & \quad t' \gets t\quad \triangleright\ \text{sequentially} \text{ consistent} \cr 4 & \quad \textbf{if}\ t' > b'\ \textbf{then}\ b \gets b' + 1; \ \textbf{return nil}\quad \triangleright\ \text{empty} \cr 5 & \quad x \gets A[ b' ] \cr 6 & \quad \textbf{if}\ t' < b'\ \textbf{then return}\ x\quad \triangleright\ \text{no thief reaches } b' \cr 7 & \quad \mathit{won} \gets \mathrm{CAS}( t , t' , t' + 1 )\quad \triangleright\ \text{the last item, raced for} \cr 8 & \quad b \gets b' + 1 \cr 9 & \quad \textbf{if}\ \mathit{won}\ \textbf{then return}\ x \ \textbf{else return nil} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{steal}( x ) \cr 2 & \quad t' \gets t;\ b' \gets b\quad \triangleright\ \text{both} \text{ sequentially consistent, in this order} \cr 3 & \quad \textbf{if}\ t' \ge b'\ \textbf{then return false} \cr 4 & \quad y \gets A[ t' ]\quad \triangleright\ A \text{ read with} \text{ acquire} \cr 5 & \quad \textbf{if not}\ \mathrm{CAS}( t , t' , t' + 1 ) \ \textbf{then return false} \cr 6 & \quad x \gets y;\ \textbf{return true} \end{array} \]

We first remark that, when more than one item is left, the owner and the thieves take different items (the owner \(b - 1\) and a thief \(t\)), and only the thieves race among themselves, on the compare-and-swap of \(t\). The somewhat "delicate" case is the last item, which the owner and a thief must not both take, nor both leave. Here the orders of memory matter, and Lê et al. 2013 placed two fences that make the deque correct in the model of C11. In ADS, the header writes those fences as sequentially consistent accesses to the bottom and to the top, since the sanitizer of threads models these accesses but not the fences themselves.

Lemma 24.5. Let take() store \(b - 1\) in the bottom and then load the top, and steal() load the top and then the bottom, all four accesses sequentially consistent. Then, when one item is left, the owner and a thief do not both take it, and they do not both leave it while it is there.

Proof. We place the four accesses in the total order \(S\) of §24.1. If the load of the bottom of the thief follows in \(S\) the store of the owner, the thief either sees \(t \ge b\) and gives up, or it sees the item; in the second case both threads race for the item by a compare-and-swap of \(t\) from the same value, which only one of them wins. Otherwise the load of the bottom of the thief precedes the store of the owner, and hence the load of the top of the thief precedes the load of the top of the owner. If the thief has already taken the item, the owner sees the top raised and finds the deque empty; if not, the owner sees \(t = b - 1\) and races for the item by the compare-and-swap, as the thief does. In each case at most one compare-and-swap of \(t\) from the same value succeeds, and when both threads race one of them wins. \(\square\)

We remark that with release and acquire only both threads could read the old value of the word written by the other, and both take the item. The two sequentially consistent pairs are the store of the bottom and the load of the top of take() (lines 2 and 3 of its pseudocode in Algorithm 24.5) and the loads of the top and of the bottom of steal() (its line 2); the other accesses are relaxed, or acquire for the vector.

We note that a thief reads the item before the compare-and-swap that claims it, from the vector that it reads after the bottom; the owner publishes a new vector with release before it publishes a bottom that needs it. A doubling copies the items of \([ t , b )\) to the same indices of the new vector, and a thief that read the old vector thus reads from it an item that the copy did not change; its compare-and-swap then decides whether the item is its. All the old vectors are kept until the deque is destroyed, and no read is ever of freed memory.

Lemma 24.6. The doublings of a WorkStealingDeque of initial capacity \(c_0\) cost \(O( 1 )\) amortized time per push, and the vectors kept occupy less than twice the vector in use.

Proof. We charge each doubling to the pushes before it. A doubling from \(2^k\) places copies \(b - t = 2^k\) items. It happens only after at least \(2^{k - 1}\) pushes since the previous doubling (or \(c_0\) pushes for the first), since a push adds one item and the vector was at most half full after the previous doubling. Hence the copies are at most twice the pushes, as for the vector of Lemma 3.3. The sizes of the vectors form the geometric series \(c_0 , 2 c_0 , \ldots , 2^j c_0\), whose sum is less than \(2^{j + 1} c_0\). \(\square\)

Thus push() and take() cost \(O( 1 )\) time and no read-modify-write but when take() reaches the last item, and steal() costs one compare-and-swap. The sequential specification against which the deque is correct lets a steal fail (an abort, as in Chase and Lev 2005): a thief fails when another thread took the item it wanted, also while other items remain, and steal() then returns false, so that the caller may try another victim.

Lemma 24.7. WorkStealingDeque is linearizable with respect to a deque whose steal may abort, with the point of a push at its store of the bottom, that of a take at its store of \(b - 1\) (at its compare-and-swap on the last item, at its load of the top when it finds the deque empty), and that of a steal at its compare-and-swap (at its load of the bottom when it finds the deque empty). Each call runs a constant number of steps, but for the copy of a doubling; a thief that retries until it gets an item is lock-free.

Proof. We observe first that the items present at any instant are those of \([ t , b )\) by the values of \(t\) and \(b\) in the order of their modifications, and the points above are the instants at which these values change, or are read. A push writes its item before its store of \(b + 1\) and becomes the new bottom item there. A take with more than one item left takes \(b - 1\), which no thief can reach, since a thief claims only \(t < b - 1\) by its compare-and-swap of \(t\) after it read the new bottom (it read \(b\) after \(t\), cf. Lemma 24.5); on the last item, take and steal race by a compare-and-swap of \(t\), and Lemma 24.5 gives that exactly the winner takes it, if anyone reads it there. A successful steal takes the item \(t\) at the instant at which \(t\) grows, which is the top item of the sequential deque then; a failed one changes nothing, and is an abort. Each operation is a fixed sequence of loads, stores and at most one compare-and-swap, with no loop but the copy of a doubling. A compare-and-swap of \(t\) fails only because another one on \(t\) succeeded, i.e., another operation completed; hence a thief that retries completes, or some other thread does, at each of its failures. \(\square\)

This deque is that of the pool of threads of chapter 25. Its argument returns in §24.11, where the queues of a search are stolen without making their owner race for each item.

24.6 A union-find shared by threads

ConcurrentUnionFind realizes the MFSET of chapter 11 on the elements \(0 , \ldots , n - 1\), for threads that unite and find at once (Jayanti and Tarjan 2021). It keeps a forest of parents \(p[ 0 .. n - 1 ]\), a root being its own parent, each parent an atomic word changed only by a compare-and-swap (with no lock). Thus find( x ) climbs to the root by splitting: each element on the way is given the parent of its parent, by a compare-and-swap whose failure is "harmless", and the paths halve their lengths as they are walked. This is the concurrent form of the path splitting of Tarjan and van Leeuwen 1984. Then unite( x , y ) finds the two roots and hooks the larger one under the smaller, by a compare-and-swap of the parent of the larger (Figure 24.7). The compare-and-swap fails only if another thread hooked that root first, and it is then tried again from the roots found anew.

Figure 24.7. A ConcurrentUnionFind before and after unite(6, 5): the splitting of find(6) gives 6 its grandparent 3, find(5) finds the root 0, and the larger root 3 is hooked under the smaller root 0; the violet elements are those whose parent changed.

Its public members are

// declarations of <ADS/concurrent/ConcurrentUnionFind.h>
class ConcurrentUnionFind
{
 public:
 explicit ConcurrentUnionFind( std::size_t n );
 std::size_t size( void ) const;
 std::int32_t find( std::int32_t x );
 std::int32_t parent( std::int32_t x ) const;
 void compress( std::int32_t x );
 bool unite( std::int32_t x , std::int32_t y );
 bool sameSet( std::int32_t x , std::int32_t y );
 };

where unite() answers whether it joined two sets, and parent() reads \(p[ x ]\) without changing it.

Algorithm 24.6. The operations of ConcurrentUnionFind: the splitting and the linking by index of Jayanti and Tarjan 2021.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{find}( x ) \cr 2 & \quad \textbf{loop} \cr 3 & \qquad u \gets p[ x ];\ g \gets p[ u ]\quad \triangleright \ \text{acquire} \cr 4 & \qquad \textbf{if}\ u = g\ \textbf{then return}\ u \cr 5 & \qquad \mathrm{CAS}( p[ x ] , u , g )\quad \triangleright \ \text{release, its failure harmless} \cr 6 & \qquad x \gets u \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{unite}( x , y ) \cr 2 & \quad \textbf{loop} \cr 3 & \qquad x \gets \mathrm{find}( x );\ y \gets \mathrm{find}( y ) \cr 4 & \qquad \textbf{if}\ x = y\ \textbf{then return false} \cr 5 & \qquad \textbf{if}\ x < y\ \textbf{then}\ \text{swap } x \text{ and } y \cr 6 & \qquad \textbf{if}\ \mathrm{CAS}( p[ x ] , x , y ) \ \textbf{then return true}\quad \triangleright\ \text{the larger} \text{ root hooked} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{sameSet}( x , y ) \cr 2 & \quad \textbf{loop} \cr 3 & \qquad x \gets \mathrm{find}( x );\ y \gets \mathrm{find}( y ) \cr 4 & \qquad \textbf{if}\ x = y\ \textbf{then return true} \cr 5 & \qquad \textbf{if}\ p[ x ] = x\ \textbf{then return false}\quad \triangleright\ x \text{ still a root after } y \text{ was found} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{compress}( x ) \cr 2 & \quad u \gets p[ x ] \cr 3 & \quad \textbf{if}\ u \ne x\ \textbf{then} \cr 4 & \qquad r \gets \mathrm{find}( u ) \cr 5 & \qquad \textbf{if}\ r \ne u\ \textbf{then}\ \mathrm{CAS}( p[ x ] , u , r ) \end{array} \]

We now show that the correctness rests on an invariant of the order of the elements, which no interleaving of the operations can break.

Lemma 24.8. If a root \(x\) is hooked only under a root \(y < x\), by \(\mathrm{CAS}( p[ x ] , x , y )\), and a parent \(p[ x ]\) is otherwise only replaced by an ancestor of \(x\), then at every moment

\[ p[ x ] \le x \quad \forall x , \tag{24.2} \]

the forest has no cycle, and the root of each tree is its least element; hence the label \(\mathrm{find}( x )\) of a set does not depend on the order of the operations, once they have ended.

Proof. We argue by induction on the successful compare-and-swaps. A hook succeeds only if \(x\) is still a root, and sets \(p[ x ] = y < x\). The splitting of find() replaces \(p[ x ] = u\) by \(g = p[ u ] \le u\), by a compare-and-swap that fails if \(p[ x ]\) changed in the meantime; the parent of \(u\) only moves up the tree of \(u\), so \(g\) is an ancestor of \(x\), and \(g \le u \le x\) keeps (24.2). Along a path the elements decrease strictly (but at the root), which excludes a cycle and makes the root the least element of its tree. compress() sets \(p[ x ]\) from \(u\) to the root found from \(u\), an ancestor of \(x\), and the same argument applies. \(\square\)

Lemma 24.9. ConcurrentUnionFind is lock-free and linearizable: a find() takes effect at the read that finds a root, a unite() at its successful hook (or, when it answers false, at the read of its second find() that found the same root), and a sameSet() at the read by which its second find() found the root of \(y\), whether it answers true or false.

Proof. A failed compare-and-swap of a splitting only leaves a longer path, and it fails because another thread changed \(p[ x ]\), by a hook or by a splitting, both successful steps; a failed hook means that another thread hooked \(x\) first. Each loop of the operations thus repeats only after a successful step of another thread, and since by Lemma 24.8 every path decreases strictly, a thread that runs alone ends after a finite number of steps; this is lock-freedom. A root, once hooked, is never a root again, and the parents only move up the trees, so that the sets only merge. At the read that finds a root \(r\) from \(x\), \(r\) is the root of the tree of \(x\), hence the answer of the sequential find() then. A successful hook of \(x\) under \(y\) merges the two sets at that instant, which is the effect of the sequential unite(); a unite() that answers false read at that instant the same root from both elements. A sameSet() that answers true read the root of \(y\) equal to a root of \(x\) found before; since sets only merge, \(x\) and \(y\) are in one set at the second read. One that answers false found the root \(r_y \ne r_x\) of \(y\) and then saw the root \(r_x\) of \(x\) still a root (line 5 of its pseudocode); since a root that is hooked never becomes a root again, \(r_x\) was a root at the read that found \(r_y\), and two distinct roots then headed the trees of \(x\) and of \(y\), i.e., two distinct sets. If \(r_x\) is no longer a root, the loop starts again, after a successful hook of another thread. Each hook uses the orders acquire and release, and a thread that follows a parent thus sees the writes that preceded the hook. \(\square\)

After the compression of all the elements, with no union running, parent( x ) is the label of the set of \(x\), the least element; the parallel connected components of chapter 25 use it in this way.

Lemma 24.10. On one thread, ConcurrentUnionFind performs \(m \ge n\) operations on \(n\) elements in \(O( m \log_{2 + m / n} n )\) steps.

Proof. On one thread every compare-and-swap succeeds, since no other thread changes a parent between the read and the swap. Then find() is the find with path splitting, and unite() is two finds followed by a link of one root under the other, chosen by the indices only, i.e., the linking that Tarjan and van Leeuwen 1984 call naive (it ignores the sizes and the ranks); sameSet() is two finds, and each operation thus makes at most two finds and one link. For path splitting with naive linking, Tarjan and van Leeuwen prove that \(m'\) finds and at most \(n - 1\) links on \(n\) elements, \(m' \ge n\), take \(O( m' \log_{1 + m' / n} n )\) steps. Here \(m' \le 2 m\), and for \(m \ge n\) we have \(1 + m / n \ge 2\), whence \(\log( 2 + m / n ) \le \log_2 3 \cdot \log( 1 + m / n )\) and \(\log_{1 + 2m / n} n \le \log_{1 + m / n} n \le \log_2 3 \cdot \log_{2 + m / n} n\); the bound follows. \(\square\)

The linking by index has the advantage of canonical labels, at the price of a somewhat weaker bound, logarithmic rather than nearly constant. We remark that the randomized linking of Jayanti and Tarjan 2021 hooks by a random order of the elements instead of their indices. It bounds the expected work on \(p\) threads by \(O( m ( \alpha( n , m / ( n p ) ) + \log( n p / m + 1 ) ) )\), but its labels are not the least elements. Note also that the constructor is not concurrent with the other operations (size() gives the constant \(n\)), and \(n < 2^{31}\), since the parents are words of 32 bits.

24.7 A cuckoo table under locks per region

ConcurrentCuckooTable is the cuckoo hashing with buckets of 4 places and tags of 8 bits of BucketCuckooTable (chapter 7), made concurrent with one lock per region of buckets and, for keys and values that the processor reads atomically, lookups that take no lock at all. A key of hash \(h\) has two buckets: \(b_1\), given by the top bits of \(h\), and

\[ b_2 = b_1 \oplus \left( \left\lfloor g( \tau ) / 2^{64 - r} \right\rfloor \vee 1 \right) , \tag{24.3} \]

where \(\tau\) is the tag of \(h\), \(g\) a mixing of the tag (the partial-key cuckoo hashing of Fan, Andersen and Kaminsky 2013), and \(R = 2^r\) the buckets of a region. Thus one can compute the other bucket of a key from its bucket and its tag, and both lie in the same region. The \(B\) buckets form \(P = \min( 2048 , \max( 1 , B / 256 ) )\) regions of \(R = B / P\) buckets each. We give a region one lock, i.e., a counter of versions (on a separate line), odd while the lock is held (the lock striping of Herlihy and Shavit 2008, chapter 13, with a stripe per region instead of a stripe of scattered buckets). A lock is taken by a compare-and-swap from an even value after a spin on plain loads, with the pause of the processor and, after 64 rounds, a yield to the system (Figure 24.8).

Figure 24.8. A ConcurrentCuckooTable of 16 buckets in 4 regions of 4 buckets, each with the version \(v\) of its lock (odd, as that of the region 1, while a writer holds it); the two buckets \(b_1\) and \(b_2\) of a key lie in its region, so that an operation on the key takes one lock.

An operation on a key takes one lock, that of its region. The cuckoo path of an insertion never leaves the region; it is searched in breadth, and its keys are moved, under that lock only, with no state to check again. By contrast, Li et al. 2014 search without locks and lock two buckets per move. Only the doubling, reserve(), clear(), forEach() and consistent() take more locks.

Its public members are

// declarations of <ADS/concurrent/ConcurrentCuckooTable.h>
template< class K , class V , class H = DefaultHash< K > ,
          class Eq = std::equal_to< K > >
class ConcurrentCuckooTable
{
 public:
 explicit ConcurrentCuckooTable( std::size_t n = 0 , H h = H() ,
                                 Eq eq = Eq() );
 std::optional< V > find( const K & k ) const;
 bool contains( const K & k ) const;
 bool insert( const K & k , const V & v );
 bool insertOrAssign( const K & k , const V & v );
 template< class F >
 bool update( const K & k , F && f );
 bool erase( const K & k );
 std::size_t size( void ) const;
 bool empty( void ) const;
 std::size_t capacity( void ) const;
 std::size_t rehashes( void ) const;
 void reserve( std::size_t n );
 void clear( void );
 template< class F >
 void forEach( F && f );
 bool consistent( void ) const;
 static constexpr bool optimistic = refLockFree< K >() && refLockFree< V >();
 };

and several threads count words in it as follows, update() applying its function to the value under the lock of the region:

ADS::ConcurrentCuckooTable< std::uint64_t , int > C( 1 << 16 );
auto count = [ & ]( std::uint64_t w ) {
 if( ! C.update( w , []( int & c ) { ++c; } ) )
  if( ! C.insert( w , 1 ) )  // inserted meanwhile
   C.update( w , []( int & c ) { ++c; } );
 };
auto work = [ & ]() {
 for( int i = 0 ; i < 1000 ; ++i )
  count( i % 7 );
 };
std::thread a( work ) , b( work );
a.join();
b.join();  // C.find( 0 ) holds 286

Algorithm 24.7. The lookup and the insertion of ConcurrentCuckooTable: the seqlock of Boehm 2012 on the partial-key cuckoo hashing of Fan et al. 2013, with the search in breadth of Li et al. 2014; \(v_R\) is the version of the region \(R\) and \(n_R\) the number of its pairs.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{find}( k ) \cr 2 & \quad h \gets \mathrm{hash}( k );\ t \gets \mathrm{tag}( h ) \cr 3 & \quad \textbf{if}\ \mathit{optimistic}\ \textbf{then} \cr 4 & \qquad \textbf{for}\ a \gets 1\ \textbf{to}\ 4\ \textbf{do} \cr 5 & \qquad\quad T \gets \text{the table in use};\ b_1 , b_2 \gets \text{the buckets of } h \text{ in } T;\ \text{fetch their lines} \cr 6 & \qquad\quad v \gets v_R\quad \triangleright\ \text{acquire, } R \text{ the region of } b_1 \cr 7 & \qquad\quad \textbf{if}\ v \text{ is odd}\ \textbf{or}\ T \text{ is no longer in use}\ \textbf{then}\ \text{a pause}; \ \textbf{continue} \cr 8 & \qquad\quad x \gets \text{the value of the place of } b_1 , b_2 \text{ with the tag } t \text{ and the key } k \text{, or} \textbf{ nil}\quad \triangleright\ \text{acquire} \cr 9 & \qquad\quad \textbf{if}\ v_R = v\ \textbf{then return}\ x \cr 10 & \quad \text{lock the region of } h \text{ in the table in use} \cr 11 & \quad \textbf{return}\ \text{the value of } k \text{ in } b_1 , b_2 \text{, or}\ \textbf{nil}\quad \triangleright\ \text{and unlock} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{insert}( k , v ) \cr 2 & \quad h \gets \mathrm{hash}( k );\ t \gets \mathrm{tag}( h ) \cr 3 & \quad \textbf{loop} \cr 4 & \qquad T \gets \text{the table in use, with the lock of the region} \text{ } R \text{ of } h \cr 5 & \qquad b_1 \gets \text{the top bits of } h;\ b_2 \gets b_1 \oplus ( g( t ) \text{ in } R ) \cr 6 & \qquad \textbf{if}\ k \text{ is in } b_1 \text{ or } b_2 \ \textbf{then}\ \text{unlock};\ \textbf{return false} \cr 7 & \qquad p \gets \text{a free place of } b_1 \text{, else of } b_2 \cr 8 & \qquad \textbf{if}\ p = \textbf{nil}\ \textbf{and}\ n_R + 1 \le 0.98 \cdot 4 |R|\ \textbf{then}\ p \gets \mathrm{makeRoom}( T , h ) \cr 9 & \qquad \textbf{if}\ p \ne \textbf{nil}\ \textbf{then} \cr 10 & \qquad\quad \text{put } ( k , v ) \text{ in } p \text{ with the} \text{ tag } t;\ n_R \gets n_R + 1;\ \text{unlock}; \textbf{return true} \cr 11 & \qquad \text{unlock};\ \mathrm{grow}( T ) \cr 12 & \textbf{function}\ \mathrm{makeRoom}( T , h ) \cr 13 & \quad Q \gets \text{a queue of the buckets } b_1 , b_2 \text{ of } h \text{ at the depth } 0 \cr 14 & \quad \textbf{while}\ Q \ne \emptyset\ \textbf{do} \cr 15 & \qquad b \gets \mathrm{dequeue}( Q ) \cr 16 & \qquad \textbf{if}\ b \text{ has a free place}\ \textbf{then} \cr 17 & \qquad\quad \textbf{foreach}\ \text{bucket } c \ne b_1 , b_2 \text{ on the path to } b \text{, from } b\ \textbf{do} \cr 18 & \qquad\qquad \text{move into } c \text{ the key of its parent that} \text{ led to it} \cr 19 & \qquad\quad \textbf{return}\ \text{the place freed in } b_1 \text{ or } b_2 \cr 20 & \qquad \textbf{if}\ \text{the depth of } b < 5\ \textbf{then} \cr 21 & \qquad\quad \textbf{foreach}\ \text{tag } u \text{ of the 4 keys} \text{ of } b\ \textbf{do} \cr 22 & \qquad\qquad c \gets \text{the other bucket of } u \text{ from } b \cr 23 & \qquad\qquad \textbf{if}\ c \text{ is not on the path to } b \ \textbf{and}\ |Q| \text{ in all} < 1024\ \textbf{then} \ \mathrm{enqueue}( Q , c ) \cr 24 & \quad \textbf{return nil} \cr 25 & \textbf{procedure}\ \mathrm{grow}( T ) \cr 26 & \quad \text{lock all the stripes in use, in increasing order} \cr 27 & \quad \textbf{if}\ T \text{ is still in use}\ \textbf{then} \cr 28 & \qquad \textbf{if}\ 4 B \ge 256\ \textbf{and}\ 16 n < 4 B \ \textbf{then}\ \text{throw}\quad \triangleright\ \text{too many} \text{ equal hashes} \cr 29 & \qquad T' \gets \text{a table of } 2 B \text{ buckets; place each} \text{ pair of } T \text{ in } T' \text{, doubling } T' \cr 30 & \qquad \text{again if one finds no place};\ \text{lock the new} \text{ stripes too} \cr 31 & \qquad \text{count the pairs of each region};\ \text{make } T' \text{ the table in use}\quad \triangleright\ \text{release} \cr 32 & \quad \text{unlock all} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{update}( k , f ) \cr 2 & \quad \text{lock the region of } h = \mathrm{hash}( k ) \text{ in } \text{the table in use} \cr 3 & \quad \textbf{if}\ k \text{ is not in its buckets}\ \textbf{then} \ \text{unlock};\ \textbf{return false} \cr 4 & \quad x \gets \text{the value of } k;\ f( x );\ \text{store } x \text{ as the value of } k\quad \triangleright\ \text{atomically if} \text{ optimistic} \cr 5 & \quad \text{unlock};\ \textbf{return true} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{erase}( k ) \cr 2 & \quad \text{lock the region } R \text{ of } h = \mathrm{hash}( k ) \text{ in the table in use} \cr 3 & \quad \textbf{if}\ k \text{ is not in its buckets}\ \textbf{then} \ \text{unlock};\ \textbf{return false} \cr 4 & \quad \text{set the tag of its place to } 0;\ n_R \gets n_R - 1 \cr 5 & \quad \text{unlock};\ \textbf{return true} \end{array} \]

We prove the table correct by an argument on the locks, one on the lookups without locks and one on the doubling.

Lemma 24.11. The locks of ConcurrentCuckooTable cannot deadlock.

Proof. An operation on a key holds one lock and waits for no other while it holds it. The operations that take more than one lock take all those in use in increasing order, from the stripe 0, and the doubling takes the locks of the new regions in the same order, before the new table is seen. Hence a thread that holds the lock \(i\) and waits for the lock \(j\) has \(i < j\), and a cycle of waits would give \(i_1 < i_2 < \cdots < i_k < i_1\), which is impossible. \(\square\)

Let the keys and the values be trivially copyable, and let std::atomic_ref read and write them without locks (e.g., integers and pointers; the constant optimistic of the class is then true). A lookup is then a read under the version of the region, i.e., a seqlock. It reads the even version \(v\), then the table in use, the tags and the places of the key with atomic loads that acquire, and then the version again. If the version is still \(v\) it returns what it read; otherwise it tries again, and it takes the lock after 4 tries. A writer makes the version odd by its compare-and-swap, stores with release, and makes the version even again by a store with release.

Lemma 24.12. A lookup without locks that reads the same even version \(v\) before and after its reads returns a state of the region of its key, i.e., what a lookup under the lock would have returned at the moment of its first read of the version.

Proof. We suppose that the lookup read a value stored by a writer \(w\) that held the lock after the version \(v\) was written. This writer stored it with release, after its compare-and-swap of the version from an even value \(v' \ge v\) to \(v' + 1\), and the lookup read it with acquire, before its second load of the version. The store synchronizes with the load, so that the compare-and-swap happens before the second load of the version, which therefore reads \(v' + 1\) or a later value, i.e., not \(v\). Boehm 2012 writes the same order by a release fence after the compare-and-swap and an acquire fence before the second load, with relaxed accesses between them; we order the accesses themselves (the sanitizer of threads does not model the fences, and on x86-64 the accesses remain plain loads and stores). Hence, when the second load reads \(v\), every value read was stored before the release that made the version \(v\), by writers that had all released the lock, and no writer held it in between; the reads see one state of the region. No access is a data race, since all of them are atomic. \(\square\)

A lookup without locks thus costs no read-modify-write and no store to a shared line. Furthermore, the tables replaced by a doubling are kept until the table is destroyed, since a reader may still be on one; with \(B_0 < \cdots < B_k\) buckets they total \(\sum_{j < k} B_j < B_k\), less than the table in use. Other keys and values (e.g., std::string) are read under the lock, and the tables replaced are freed at once.

We now turn to the insertion, which puts the new key in a free place of its two buckets if there is one. Otherwise it searches in breadth, from the two buckets, a path of at most \(L = 5\) moves that ends in a bucket with a free place, and moves the keys of the path from its end, each into its other bucket, which (24.3) computes from its tag only.

Lemma 24.13. A search in breadth over buckets of \(b\) places that looks at \(M\) places finds a path of at most

\[ L = \left\lceil \log_b \left( \frac{M}{2} - \frac{M}{2 b} + 1 \right) \right\rceil \tag{24.4} \]

moves when one exists among them, against the \(M / 2\) moves of a search in depth; for \(M = 2000\) and \(b = 4\), \(L = 5\).

Proof. We count the places of the two trees of the search, rooted at the two buckets of the key: they have \(2 b^l\) places at the depth \(l\), since each place of a bucket names one other bucket. Hence the places within \(L\) moves are \(\sum_{l = 1}^{L} 2 b^l = 2 b ( b^L - 1 ) / ( b - 1 )\), which is at least \(M\) exactly when \(b^L \ge M / 2 - M / ( 2 b ) + 1\), whence (24.4). For \(M = 2000\) and \(b = 4\) the argument of the logarithm is 751, and \(\log_4 751 \approx 4.78\). A search in depth follows one path, which may be as long as half the places it looks at (Li et al. 2014). \(\square\)

The search stops at \(L = 5\), or at 1024 buckets, all in the region, whose tags form a block of \(8 R\) bytes. We double the table when a region would pass the load 0.98, or when no path is found. The thread that doubles it takes all the locks in use, and those of the new regions too before the new table is seen; then it checks that no other thread has doubled the table in the meantime, and places each pair again in the new table ("stop-the-world"). With 2 buckets per key and 4 places per bucket, the cuckoo hashing of \(n\) random keys succeeds with high probability while \(n / ( 4 B ) < 0.9803\), the threshold of the 4-orientability of the random graphs (Cain, Sanders and Wormald 2007), here in each region. Now, a region of \(4 R\) places holds a binomial number of the \(n\) keys, of mean \(\mu = n / P\) and standard deviation \(\sqrt{ \mu ( 1 - 1 / P ) }\). This is a relative deviation of about \(1 / \sqrt{ 4 R \alpha }\) at the load \(\alpha\) (3.3% for \(R = 256\) and \(\alpha = 0.9\)), and therefore the fullest region of a large table reaches 0.98 at a mean load of about 0.88 to 0.92. A restriction of the choices to a part of the table (there, a page) is also studied by Dietzfelbinger, Mitzenmacher and Rink 2011. The cost of the doublings is in Lemma 24.14 below. A doubling that would leave a table of at least 256 places less than 1/16 full throws std::length_error, which happens only when more than 8 keys share both buckets at every size (e.g., by equal hashes), and leaves the table unchanged.

A lookup touches two buckets. It fetches ahead, at once, the tags of both and the line of the places of the first, and the misses overlap (the 4 places of a bucket share a line of cache when their size is a power of 2 up to 64 bytes). Those of the second bucket, where fewer keys usually are, are read only when a tag matches there. Also, the tags and the places of a table of 2 MB or more lie on transparent huge pages, and the random accesses then miss the TLB once per 2 MB instead of once per 4 KB (Navarro et al. 2002). With uniform keys two operations contend for a lock with probability \(1 / P\). Each region counts its pairs under its lock, and size() is the sum of \(P\) counters read without locks, exact when no operation runs and otherwise an estimate.

Lemma 24.14. The operations of ConcurrentCuckooTable on a single key are linearizable, at an instant at which they hold the lock of the region of the key in the table in use, or at the second read of the version for a lookup without locks; forEach() visits the pairs of one instant; and if each doubling to \(2 B\) buckets follows at least \(\epsilon B\) insertions since the previous doubling, for a constant \(\epsilon > 0\), the doublings cost \(O( 1 / \epsilon )\) amortized time per insertion.

Proof. An operation that holds the lock of the region of its key in the table in use is alone on the two buckets of the key, which lie in that region by (24.3), and a doubling, which takes all the locks, cannot run meanwhile; its effect is therefore that of the sequential operation at any instant within its critical section. An operation that finds, after taking the lock, that the table was replaced releases it and starts again on the new table, and it has had no effect. A lookup without locks returns, by Lemma 24.12, the state of the region at its first read of the version, which no writer changed before the second read; any instant between the two reads is thus a point. forEach() holds all the locks while it visits, so that no operation takes effect meanwhile. A doubling to \(2 B\) buckets places again the at most \(4 B\) pairs present, in \(O( B )\) time, which we charge to the at least \(\epsilon B\) insertions since the previous doubling, \(O( 1 / \epsilon )\) each; every insertion is charged by one doubling only. \(\square\)

The hypothesis of the last claim is not a property of the code but of the keys: a doubling halves the load, to at most \(0.49\), and with random hashes the fullest region of a large table reaches \(0.98\) only at a mean load of about \(0.88\) (see above), i.e., after about \(0.39 \cdot 4 B\) insertions, while keys that share both buckets make the doublings come with no insertion, until the table throws std::length_error.

Also, besides these operations, contains( k ) is the lookup that returns only whether \(k\) is there, insertOrAssign( k , v ) is the insertion that, for a key found, assigns \(v\) to its value before the unlock, and rehashes() counts the doublings of the table.

24.8 Linear probing that grows

ConcurrentFlatTable gives up what ConcurrentCuckooTable needs its versions for: a word of its vector, once written, never changes nor moves within its vector, since there are no removals and the keys are never displaced. It is open addressing with linear probing on a vector of \(2^l\) atomic words of 64 bits, i.e., the folklore table that Maier, Sanders and Dementiev 2019 found the "fastest" to read among the hash tables shared by threads, made to grow while the threads work and to keep its pairs where they are. It is meant as the CLOSED set of a parallel search. Indeed, findOrInsert( k , h , v ) takes a key with its hash of 64 bits, computed once by the caller, and either finds the key or inserts it with the value \(v\); in both cases it returns the pair that the table holds. The threads that reach the same state at once thus agree on one pair, and only one of them is told that it inserted it.

We let a word be 0 when its place is free; it is written once, by a compare-and-swap from 0, and it is never changed afterwards but by update(). We distinguish the forms in which the pairs are kept, chosen by their types and by the processor when compiling. (i) When the key and the value are trivially copyable and fit in 8 bytes together (e.g., a key of 32 bits with a value of 32 bits, or a key of 64 bits with no value, i.e., a set), the word is the pair itself (the constant packed of the class). Pairs whose key is made of zero bytes, whose word could be 0, are kept apart in one atomic word. (ii) When they do not fit together but each fits in 8 bytes, and the compare-and-swap of 16 bytes of Boost.Atomic is free of locks (cmpxchg16b on x86-64, the pairs of registers of AArch64, as Boost finds them under the flags of the compiler), a place is two words, the key and the value, written together by that instruction (inlined); without Boost, the pairs are in the form (iii). (iii) Otherwise the word holds the index of a node, where the pair lies with its hash, and 24 bits of the hash; a lookup follows the index only when those bits match, which happens once in \(2^{24}\) times for another key. Nodes never move, and the pair returned is a reference to the node, valid as long as the table; the member type Ref is what an operation returns of a pair, i.e., a copy of the value in the forms (i) and (ii) and a reference to the node (of the type Entry) in the form (iii). The nodes are cut from segments of \(2^{12} , 2^{13} , \ldots\) nodes, of which each thread reserves 64 at a time; an insertion thus takes no lock, and calls the allocator once per 64 nodes at most.

Here the place of a key of hash \(h\) is \(\lfloor h / 2^{64 - l} \rfloor\), and the key is looked for from there on, cyclically, up to its word or to a word 0. When the pairs lie in the words, each place has besides a tag of a byte, 0 or 7 bits of the hash of its key with the high bit set, as the metadata of the tables of Swiss and F14 kind. Tags are kept apart from the words, 8 to an atomic word. A lookup reads the tags from the place on, 8 at a time, compares them all with the tag of the key in one step, reads only the words of the places whose tag matches, and stops at the first tag 0. An absent key thus costs one line of the tags, (\(1/8\) of the words or less), which the cache usually keeps. A tag is written, with release, after the word it tags, and always with the same value, by the insertion that wrote the word or by any insertion that passes the place while it looks for a place; the insertion takes effect when the tag of its word is written (Figure 24.9). We give the pairs in nodes no tags, since a tag would add a third miss to the two of a key found in its node.

Figure 24.9. The tags (upper row, 0 for a place free or not yet tagged) and the words (lower row) of a ConcurrentFlatTable of 12 places, before and after the insertion of a key \(k\) whose place is 5: the insertion passes the places 5 to 7, which hold other keys, writes \(k\) into the free place 8 by a compare-and-swap, and then its tag.

Its public members, but for the variants that take the hash already computed (each operation on a key \(k\) has one, with the hash \(h\) as a second argument), are

// declarations of <ADS/concurrent/ConcurrentFlatTable.h>
template< class K , class V , class H = DefaultHash< K > ,
          class Eq = std::equal_to< K > , class C = ZeroingClear >
class ConcurrentFlatTable
{
 public:
 static constexpr bool packed =
   std::is_trivially_copyable_v< K > && std::is_trivially_copyable_v< V > &&
   plainKey() && ( sizeof( K ) + valueBytes() <= 8 );
 static constexpr bool inlined =
   ( ADS_FLAT_CAS16 != 0 ) && ! packed && std::is_trivially_copyable_v< K > &&
   std::is_trivially_copyable_v< V > && plainKey() && ( sizeof( K ) <= 8 ) &&
   ( sizeof( V ) <= 8 );
 struct Entry
 {
  const K key;
  V value;
  };
 using Ref = std::conditional_t< packed || inlined , V , Entry & >;
 explicit ConcurrentFlatTable( std::size_t n = 0 , H h = H() , Eq eq = Eq() );
 std::uint64_t hash( const K & k ) const;
 std::pair< Ref , bool > findOrInsert( const K & k , const V & v );
 bool insert( const K & k , const V & v );
 std::optional< V > find( const K & k ) const;
 std::optional< K > findKey( const K & k ) const;
 bool contains( const K & k ) const;
 void prefetch( std::uint64_t h ) const;
 template< class F >
 bool update( const K & k , F && f )
  requires( packed || inlined );
 std::size_t size( void ) const;
 bool empty( void ) const;
 std::size_t capacity( void ) const;
 std::size_t rehashes( void ) const;
 void reserve( std::size_t n );
 void clear( void );
 std::uint64_t epoch( void ) const;
 template< class F >
 void forEach( F && f ) const;
 bool consistent( void ) const;
 };

besides findOrInsertKey( k , h ) of a packed set and entry( k , h ), the node of a key of a table that is neither packed nor inlined. The lookup findKey( k ) returns a copy of the key that the table holds equal to \(k\) by Eq, or nothing, and inserts nothing; in a set of pointers to nodes compared by the states they hold, a thread thus reads the pointer stored for a state equal to that of its own node, while the owner inserts, with no second copy of the pointer in the value. It is the lookup of find(), with its progress and its point of linearization, and it reads the key of a node as find() reads its value.

Algorithm 24.8. The insertion and the lookup of ConcurrentFlatTable (the folklore table of Maier et al. 2019, with the growth below); \(W\) is the vector in use, \(c_t\) the counter of the thread and \(g\) the flag of the growth.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{findOrInsert}( k , h , v ) \cr 2 & \quad \textbf{loop} \cr 3 & \qquad c_t \gets c_t + 1\quad \triangleright\ \text{sequentially} \text{ consistent} \cr 4 & \qquad \textbf{if}\ g\ \textbf{then}\ c_t \gets c_t - 1; \ \mathrm{help}();\ \textbf{continue} \cr 5 & \qquad w \gets \text{the word of } ( k , v ) \text{, or of a new} \text{ node of } ( h , k , v ) \cr 6 & \qquad i \gets \lfloor h / 2^{64 - l} \rfloor;\ r \gets 0 \cr 7 & \qquad \textbf{loop} \cr 8 & \qquad\quad x \gets W[ i ] \cr 9 & \qquad\quad \textbf{if}\ x = 0\ \textbf{and}\ \mathrm{CAS}( W[ i ] , 0 , w )\ \textbf{then}\ c_t \gets c_t - 1 + 2^{16}; \ \textbf{return}\ ( w , \textbf{true} ) \cr 10 & \qquad\quad \textbf{if}\ x = 0\ \textbf{then}\ x \gets W[ i ] \quad \triangleright\ \text{written by another thread} \cr 11 & \qquad\quad \textbf{if}\ x \text{ holds } k\ \textbf{then} \ c_t \gets c_t - 1;\ \textbf{return}\ ( x , \textbf{false} ) \cr 12 & \qquad\quad i \gets ( i + 1 ) \bmod 2^l;\ r \gets r + 1 \cr 13 & \qquad\quad \textbf{if}\ r > 128\ \textbf{and}\ \text{the table} \text{ is } 1/8 \text{ full}\ \textbf{then break} \cr 14 & \qquad c_t \gets c_t - 1;\ \mathrm{grow}( l + 1 ) \cr 15 & \textbf{procedure}\ \mathrm{grow}( l' ) \cr 16 & \quad \textbf{if}\ \mathrm{CAS}( g , \textbf{false} , \textbf{true} )\ \textbf{then} \cr 17 & \qquad \textbf{while}\ \text{some } c_t > 0\ \textbf{do} \ \text{a pause} \cr 18 & \qquad W' \gets 2^{l'} \text{ words } 0;\ \text{publish } W' \text{ for the helpers} \cr 19 & \qquad \mathrm{help}();\ \textbf{wait until}\ \text{all the} \text{ blocks are copied} \cr 20 & \qquad W \gets W';\ g \gets \textbf{false}\quad \triangleright \ \text{release} \cr 21 & \quad \textbf{else}\ \mathrm{help}() \cr 22 & \textbf{procedure}\ \mathrm{help}() \cr 23 & \quad \textbf{while}\ g\ \textbf{do} \cr 24 & \qquad \textbf{foreach}\ \text{block of } 4096 \text{ words of } W \text{ claimed by a counter}\ \textbf{do} \cr 25 & \qquad\quad \textbf{foreach}\ x \ne 0 \text{ in the block} \ \textbf{do}\ \text{put } x \text{ at the first free place of its} \text{ key in } W' \text{, by a CAS} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{find}( k , h ) \cr 2 & \quad \textbf{loop} \cr 3 & \qquad T \gets \text{the vector in use } W\quad \triangleright \ \text{acquire} \cr 4 & \qquad i \gets \lfloor h / 2^{64 - l} \rfloor \cr 5 & \qquad \textbf{while}\ T[ i ] \ne 0\ \textbf{do}\quad \triangleright\ \text{acquire} \cr 6 & \qquad\quad \textbf{if}\ T[ i ] \text{ holds } k\ \textbf{then} \ \textbf{return}\ \text{its value} \cr 7 & \qquad\quad i \gets ( i + 1 ) \bmod 2^l \cr 8 & \qquad \textbf{if}\ T \text{ is still the vector in use} \ \textbf{then return nil} \end{array} \]

The lookups take no lock, write no word, and check no version, since a word or a tag, once written, stays. We now show why they are correct while insertions run.

Lemma 24.15. Let the words and the tags of a vector be written only from 0, once each, and only while the vector is in use, and let an insertion write the tags of the places it passes before it writes its own. Let a lookup of \(k\) in the vector \(T\) read the tag 0 at the place \(j\), after tags at the places from that of \(k\) to \(j - 1\) whose words hold other keys, and then find \(T\) still in use. Then no insertion of \(k\) had taken effect when the lookup read the tag of \(j\).

Proof. We follow an insertion of \(k\), which writes the first word 0 of the sequence of places of \(k\), and before its own tag the tags of all the places it passed. We suppose that it had taken effect, i.e., written its tag, before the lookup read the tag of \(j\). The place \(j\) comes before its word, or is its word, and it would have had its tag then, since a tag is written once and stays; but the lookup read 0 there. \(\square\)

A lookup that finds \(k\) returns a pair that stays, and it is linearized at the read of its word (of its tag, when the places have tags). One that finds the vector replaced starts over on the new one, which happens once per growth. Also, the lookups read with acquire. Hence the word of a tag read is read whole, and so is the pair of a node, built before the compare-and-swap with release that published its index; \(p\) threads that only read therefore scale as \(p\) independent sequential tables (cf. Table 24.1). Note that an insertion that finds \(k\) in a word whose tag is still 0 writes the tag before it answers, and its answer thus comes after the insertion of \(k\) has taken effect. For the pairs in nodes, which have no tags, the lemma holds with the words in place of the tags, an insertion taking effect at its compare-and-swap.

We let the table grow when its pairs pass half of its places. Insertions (and update()) exclude a growth, and the growth excludes them, by a protocol of Dekker over 64 counters on separate lines, as in the growth of Maier et al. 2019 that synchronizes the threads. A thread adds 1 to its counter and then reads the flag \(g\) of the growth, while the thread that grows the table raises \(g\) and then reads the counters (lines 3 and 4, and 16 and 17, of findOrInsert() in Algorithm 24.8).

Lemma 24.16. Let a writer raise its counter and then read the flag \(g\), and the thread that grows the table raise \(g\) and then read the counters, all these accesses sequentially consistent; and let a writer that reads \(g\) raised lower its counter and retry after the growth. Then no word of a vector is written once its copy has begun.

Proof. We place the four accesses in the single order \(S\). If the read of \(g\) by the writer follows the raise of \(g\), the writer backs off. Otherwise the read of \(g\) precedes the raise, and hence the raise of the counter of the writer precedes the read of the counters by the grower. Then the grower sees the counter and waits for it to drop, i.e., for the writer to leave the vector (the mutual exclusion of Dekker, which Dijkstra 1965 published). Thus the copy starts only when no writer is inside the old vector, and no writer enters it until the growth ends. \(\square\)

The grower allocates a vector twice as large. Meanwhile, the threads that come to insert copy blocks of 4096 words of the old vector, claimed by a counter, instead of waiting. Each word is placed at the first free place of its sequence in the new vector, which no other thread reads yet, and the new vector is published, with release, once all the blocks are copied. Meanwhile the lookups never wait: they read the old vector, which no longer changes, until the new one is in use. We let the counters of the threads also count the pairs, in their upper 48 bits, and an insertion counts its pair in the same read-modify-write by which it leaves. Their sum, which reads 64 lines, is taken once per 1024 insertions of a counter (more often in a vector of less than \(2^{20}\) places). An insertion that reads more than 128 words also grows the table, if it is at least one eighth full. A table less full than that, which typically only keys of equal hash make so "crowded", is read on to its first free place instead.

Lemma 24.17. With the load \(\alpha\) of the table at most \(1/2\) and random hashes, a lookup reads on average

\[ \frac{1}{2} \left( 1 + \frac{1}{1 - \alpha} \right) \le 1.5 \quad \text{and} \quad \frac{1}{2} \left( 1 + \frac{1}{( 1 - \alpha )^2} \right) \le 2.5 \tag{24.5} \]

places when it succeeds and when it fails, respectively. The growths that the load triggers cost \(O( 1 )\) amortized time per insertion, at most \(18 / 7\) copies of a word each, provided that the load stays below \(9/16\).

Proof. We recall that the two averages are those of linear probing with random hashes (Knuth 1998, §6.4), increasing in \(\alpha\), taken at \(\alpha = 1/2\). A growth from \(2^l\) places copies the at most \(( 9/16 ) 2^l\) words in use, each once. The previous growth left a load of at most \(( 9/16 ) / 2 = 9/32\) in the vector of \(2^l\) places, and a growth triggered by the load happens only when the pairs pass \(2^l / 2\); hence at least \(( 1/2 - 9/32 ) 2^l = ( 7/32 ) 2^l\) insertions lie between the two, and the copies are at most \(( 9/16 ) / ( 7/32 ) = 18/7\) per insertion. \(\square\)

We remark that the load may pass \(1/2\) before a growth, since each of the 64 counters triggers the sum only once per period of \(2^{\min( \max( l - 10 , 0 ) , 10 )}\) of its insertions: between two sums the pairs grow by less than \(64 \cdot 2^{l - 10} = 2^l / 16\), and hence \(\alpha < 9/16\), which is the proviso of Lemma 24.17, and where the two averages of (24.5) are below 1.65 and 3.12. A growth for a crowded insertion (more than 128 words read at a load of at least \(1/8\)) is outside the lemma: with random hashes it is rare, and with keys of equal hash it may follow the previous growth with few insertions. Most of the places of (24.5) lie on one line of 8 words, which the lookup fetches while it reads the tags, and a key that is there typically costs about one miss. The progress of the operations is that of Lemma 24.18 below. Where the pairs are inlined, the copy of a growth moves the two words of a place at once, and a lookup reads the key with acquire and then the value from the same line. Lemma 24.15 then holds unchanged for the key, since update() changes the value by the same instruction and never the key; the lookup reads a value written with that key, or a later one of update(). We remark that clear(), forEach() and consistent() may not run with the other operations. Also, contains( k ) (or contains( k , h ) with the hash given) is the lookup that returns only whether \(k\) is there, and rehashes() counts the growths of the table. Vectors replaced are kept until the table is destroyed, and with sizes that double they occupy less than the vector in use. For a packed set (with no value), findOrInsertKey() returns the key that the table holds, which is equal to \(k\) by Eq, though not necessarily by its bytes. In a set of pointers to objects compared as the objects, the threads that insert at once pointers to equal objects therefore all get the pointer of the one that inserted it; this is the intrusive set of the nodes of a parallel search.

Lemma 24.18. A lookup of ConcurrentFlatTable never waits, and it ends after a number of its steps bounded by the places of the vector times one plus the growths that complete while it runs; an insertion waits only for a growth that runs, or for the renewal of a group by another insertion.

Proof. A lookup reads the vector in use and its words, never a lock or a counter, and in one vector it reads at most all its places before it finds the key or a free place (the vector is never full, since it grows at half of its places). It starts over only when it finds the vector replaced, i.e., after a growth completed; each start reads at most the places of the vector then in use. An insertion that finds the flag \(g\) raised helps the copy, whose blocks it claims by a counter, and waits only for the blocks claimed by the other threads and for the publication of the new vector; outside a growth it runs the probe of a lookup and one compare-and-swap per free place it tries, which fails only when another insertion wrote that place, and it then reads on. With the policy EpochClear described next, it may also wait for the store of the epoch of a group that another insertion renews. \(\square\)

clear() writes 0 to every place, in time linear in the capacity, which a table cleared often and filled little in between (the restarts of an incremental search) pays at each clear. With the policy EpochClear< S >, the fifth template parameter (ZeroingClear, the default, leaves the table as above; the concept FlatClear admits these two policies only), clear() takes \(O( 1 )\) amortized time instead. Each group of 8 places has a stamp of the unsigned type \(S\) (32 bits by default, i.e., half a byte per place), and the group is in use only if its stamp is the epoch of the table, which clear() raises, so that all the groups fall out of use at once. A lookup reads the tags of a group, or a word of a table without tags, only if the stamp of its group is the epoch, and a group out of use is free, where the lookup stops. An insertion that reaches a group out of use renews it first: it takes the group by a compare-and-swap of its stamp to a mark, writes 0 to its words and tags, and stores the epoch with release:

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{renew}( T , g ) \cr 2 & \quad \textbf{loop} \cr 3 & \qquad e \gets E_g\quad \triangleright\ \text{acquire} \cr 4 & \qquad \textbf{if}\ e = \epsilon\ \textbf{then return} \cr 5 & \qquad \textbf{if}\ e \ne \beta\ \textbf{and}\ \mathrm{CAS}( E_g , e , \beta )\ \textbf{then} \cr 6 & \qquad\quad \text{write 0 to the words and to the tags of } g \cr 7 & \qquad\quad E_g \gets \epsilon\quad \triangleright\ \text{release}; \ \textbf{return} \cr 8 & \qquad \text{a pause, or a yield after 64 of them}\quad \triangleright\ \text{renewed by another thread} \end{array} \]

The other insertions that reach the group meanwhile wait for that store, a few words long, while the lookups see the group free until then, which is right, since no insertion of the new epoch has taken effect in it; once the stamp is the epoch, the group is a group of a new vector, and Lemma 24.15 holds for it unchanged. A renewal runs within the critical section of its insertion, so that by Lemma 24.16 no growth runs with it; the copy of a growth takes only the groups in use, into a vector whose groups all have the epoch. The stamps of the old epochs are less than the epoch, and when the epoch would reach the mark, the largest value of \(S\), clear() writes 0 to the whole vector and starts again from the epoch 1: once per \(2^{|S|} - 2\) clears, so that no stamp left from an old epoch can equal a new one. Of course, the pairs of a table in nodes are then dropped with no destructor, their nodes reused by the next epoch, and the policy therefore requires keys and values trivially destructible; epoch() gives the epoch (test engineered.concurrent-flat-table-epochs).

24.9 Relaxed priority queues

We observe that a priority queue shared by \(p\) threads under one lock serializes them. A relaxed priority queue returns instead a pair that need not be the least: the rank of a popped pair is 1 plus the number of the pairs present with a smaller key, and its rank error the rank less 1, which is 0 for an exact queue. A search that takes its states from a relaxed OPEN expands a few states that an exact one would not, and in exchange its threads do not wait for one another. MultiQueue is the MultiQueue of Rihani, Sanders and Dementiev 2015, with the stickiness and the buffers of Williams, Sanders and Dementiev 2021, on pairs \(( k , x )\) of a key (an integer or a real, the least first by less) and an item.

In it, the \(n\) queues are sequential priority queues, each with a separate lock and with the key of its minimum, \(\mathit{top}_j\), kept apart in an atomic word that the other threads read without the lock. A push puts the pair in a random queue whose lock it takes at the first try, and draws another one when the lock is held. A pop reads the minima of two distinct random queues, locks the queue with the smaller one if it is free (draws two other queues otherwise), and takes its minimum (Figure 24.10). With \(n = 1\) the queue is exact, a priority queue under one lock, which is typically used for testing and for comparison.

Lemma 24.19. Let there be \(n = q p\) queues, \(q > 1\), used by \(p\) threads, and let each draw of a queue be uniform and independent of the locks held. Then a push takes a lock after fewer than \(q / ( q - 1 )\) draws in expectation (2 for \(q = 2\), i.e., the \(n = 2 p\) queues that the header suggests), and no thread waits for a lock.

Proof. A thread that draws holds no lock, and each of the other \(p - 1\) threads holds at most one; hence at most \(p - 1\) of the \(n\) queues are held at each draw, and a draw finds a held lock with probability at most \(( p - 1 ) / ( q p ) < 1 / q\). The number of draws up to the first free lock is thus dominated by a geometric variable of success probability \(1 - 1 / q\), whose mean is \(q / ( q - 1 )\). A held lock is never waited for: the thread draws again instead. \(\square\)

The independence of the draws from the locks is that of the generator of each handle, which no other thread reads; a pop draws two queues per round and takes a lock with at least the same probability, since it fails only if the better queue is held.

Figure 24.10. A MultiQueue of four queues, each with its minimum \(\mathit{top}\), read without locks, and its deletion buffer \(D\) (the least pair on the right); a pop that draws the queues 1 and 3 takes the key 4 from the better one, while the keys 2 and 3 are in the other queues: its rank error is 2.

Its public members, and those of the handle of a thread, are

// declarations of <ADS/concurrent/MultiQueue.h>
template< class K , class T , class Less = std::less< K > ,
          template< class , class > class H = MultiQueueHeap >
class MultiQueue
{
 public:
 struct Entry
 {
  K key;
  T item;
  };
 class Handle
 {
  public:
  void push( K k , T x );
  template< class It >
  void pushAll( It first , It last );
  std::optional< Entry > tryPop( void );
  };
 explicit MultiQueue( std::size_t n , unsigned s = 16 ,
                      std::uint64_t seed = 1 ,
                      Less less = Less() );
 Handle handle( void );
 std::size_t queues( void ) const;
 unsigned stickiness( void ) const;
 std::size_t size( void ) const;
 bool empty( void ) const;
 bool consistent( void ) const;
 };

where \(s\) is the stickiness and tryPop() answers nothing only when the queues it looked at were empty; the constant decrease_key of the class declares, in the vocabulary of §1.14, that a key is lowered lazily, by a new pair. Each thread takes its own handle:

ADS::MultiQueue< int , int > M( 8 );  // n = 8 queues
std::vector< std::thread > T;
for( int k = 0 ; k < 4 ; ++k )
 T.emplace_back( [ & , k ]() {
  auto h = M.handle();
  for( int i = 0 ; i < 100 ; ++i )
   h.push( 4 * i + k , i );
  while( auto e = h.tryPop() ) {
   }  // small keys first, roughly
  } );
for( auto & t : T )
 t.join();

Algorithm 24.9. The push and the pop of MultiQueue::Handle (Rihani et al. 2015, with the stickiness and the buffers of Williams et al. 2021); \(D_j\) and \(I_j\) are the buffers of the queue \(j\), \(H_j\) its heap, and \(b = 16\).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{push}( k , x ) \cr 2 & \quad \textbf{loop} \cr 3 & \qquad \textbf{if}\ \text{the two queues kept were used } s \text{ times}\ \textbf{then}\ \mathrm{draw}() \cr 4 & \qquad j \gets \text{one of the two at random} \cr 5 & \qquad \textbf{if}\ \mathrm{tryLock}( j )\ \textbf{then break} \cr 6 & \qquad \mathrm{draw}()\quad \triangleright\ \text{two random} \text{ queues, used } 0 \text{ times} \cr 7 & \quad \textbf{if}\ D_j \ne \emptyset\ \textbf{and}\ k \le \max D_j \ \textbf{then} \cr 8 & \qquad \textbf{if}\ |D_j| = b\ \textbf{then}\ \mathrm{add}( j , \max D_j )\text{, removed from } D_j \cr 9 & \qquad \text{insert } ( k , x ) \text{ into } D_j \text{, sorted} \cr 10 & \quad \textbf{else if}\ |D_j| < b\ \textbf{and}\ I_j = \emptyset \ \textbf{and}\ H_j = \emptyset\ \textbf{then}\ \text{insert } ( k , x ) \text{ as the greatest of } D_j \cr 11 & \quad \textbf{else}\ \mathrm{add}( j , ( k , x ) ) \cr 12 & \quad \mathit{top}_j \gets \text{the key of } \min D_j; \ \mathrm{unlock}( j )\quad \triangleright\ \text{release} \cr 13 & \textbf{procedure}\ \mathrm{add}( j , e ) \cr 14 & \quad \textbf{if}\ |I_j| < b\ \textbf{then}\ \text{add } e \text{ to } I_j \cr 15 & \quad \textbf{else}\ \text{push the pairs of } I_j \text{ and } e \text{ into } H_j;\ I_j \gets \emptyset \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{tryPop}() \cr 2 & \quad \textbf{loop} \cr 3 & \qquad \textbf{if}\ \text{the two queues kept were used } s \text{ times}\ \textbf{then}\ \mathrm{draw}() \cr 4 & \qquad j \gets \text{the one of the two with the least } \mathit{top}\quad \triangleright\ \text{read without locks} \cr 5 & \qquad \textbf{if}\ \mathit{top}_j = \infty\ \textbf{then return} \ \mathrm{scan}() \cr 6 & \qquad \textbf{if}\ \mathrm{tryLock}( j )\ \textbf{then break} \cr 7 & \qquad \mathrm{draw}() \cr 8 & \quad \textbf{if}\ D_j = \emptyset\ \textbf{then}\ \mathrm{unlock}( j );\ \textbf{return}\ \mathrm{scan}() \cr 9 & \quad e \gets \text{the least pair of } D_j \text{, removed} \cr 10 & \quad \textbf{if}\ D_j = \emptyset\ \textbf{then} \cr 11 & \qquad \text{push the pairs of } I_j \text{ into } H_j; \ I_j \gets \emptyset \cr 12 & \qquad \text{move the } \min( b , |H_j| ) \text{ least pairs of } H_j \text{ into } D_j \cr 13 & \quad \mathit{top}_j \gets \text{the key of } \min D_j \text{, or } \infty;\ \mathrm{unlock}( j );\ \textbf{return}\ e \cr 14 & \textbf{function}\ \mathrm{scan}() \cr 15 & \quad \textbf{foreach}\ \text{queue } j \text{, from a random one} \ \textbf{do} \cr 16 & \qquad \mathrm{lock}( j ) \cr 17 & \qquad \textbf{if}\ D_j \ne \emptyset\ \textbf{then}\ \text{take} \text{ its least pair as above};\ \textbf{return}\ \text{it} \cr 18 & \qquad \mathrm{unlock}( j ) \cr 19 & \quad \textbf{return nil} \end{array} \]

We measure the quality of the pops by the expected rank error, for which the sequential model of the MultiQueue has an exact analysis. In this model the pairs are spread over the \(n\) queues uniformly at random, and then popped one at a time, each from the queue whose least key is the \(j\)-th of the \(n\) with a probability \(\sigma_j\); we write \(\sigma_{\le i} = \sigma_1 + \cdots + \sigma_i\).

Theorem 24.1. (Walzer and Williams 2025.) If \(\sigma_{\le i} > i / n\) for \(i < n\), the rank error of a pop converges in distribution as the pops go on, and the mean of its limit is

\[ E[ R ] = \sum_{i = 1}^{n - 1} \frac{\sigma_{\le i} ( 1 - \sigma_{\le i} )} {\sigma_{\le i} - i / n} ; \tag{24.6} \]

for the better of two queues drawn with replacement, \(\sigma_{\le i} = 1 - ( 1 - i / n )^2\) and

\[ E[ R ] = \sum_{i = 1}^{n - 1} \left( 2 - \frac{i}{n} \right) \left( 1 - \frac{i}{n} \right) = \frac{5}{6} n - 1 + \frac{1}{6 n} , \tag{24.7} \]

and the maximum over \(\mathrm{poly}( n )\) pops is \(O( n \log n )\) with high probability.

We do not reproduce the proof, whose idea is about the queues ordered by their least keys. Here the \(i\) best queues hold a share \(i / n\) of the pairs that come next in the order of the keys, since the pairs were spread at random, and a pop takes from them with the probability \(\sigma_{\le i}\). When \(\sigma_{\le i} > i / n\) they are emptied faster than their share, and the number of pairs that separate the \(i\)-th least key from the \(( i + 1 )\)-th is a geometric variable whose mean depends only on \(\sigma_{\le i}\) and \(i / n\). Walzer and Williams prove that the ranks of the least keys of the queues converge to sums of such independent variables, whence (24.6). With one draw, \(\sigma_{\le i} = i / n\), the best queues are emptied only as fast as they are filled, and the rank error grows without bound. Two draws that fall on the same queue are such a draw. Hence MultiQueue draws two distinct queues, for which \(\sigma_{\le i} = 1 - ( n - i ) ( n - i - 1 ) / ( n ( n - 1 ) )\) and \(\sigma_{\le i} - i / n = i ( n - i ) / ( n ( n - 1 ) )\), so that (24.6) becomes

\[ E[ R ] = \sum_{i = 1}^{n - 1} \sigma_{\le i} \, \frac{n - i - 1}{i} , \tag{24.8} \]

somewhat less than (24.7) (Table 24.2).

Table 24.2. The expected rank error of the limit of the sequential model, for two queues drawn with replacement, by (24.7), and for two distinct queues, by (24.8).

\(n\) with replacement (24.7) distinct (24.8)
8 5.69 4.63
32 25.67 24.53

The earlier bounds of Alistarh et al. 2017, \(O( n )\) for the mean and \(O( n \log n )\) for the maximum, hold for pushes and pops mixed as well, but for a comparison and a pop done atomically. As Williams et al. 2021 do, MultiQueue reads the least keys of the two queues without their locks, possibly stale. In a run of many threads its rank errors are therefore measured rather than bounded, and the test engineered_queues.multi-queue-rank compares the measured mean with (24.8) on one thread.

We adopt two devices of Williams et al. 2021, which save most of the misses of the cache. A thread keeps the two queues it drew for \(s\) operations (the stickiness), and their lines stay in its cache; it draws two others after \(s\) operations or when a lock is held. A push goes to one of the two at random, a pop to the better one. Also, each queue is an 8-ary heap behind two buffers of 16 pairs. We keep the deletion buffer \(D\) sorted by decreasing keys; it holds the least pairs of the queue, and a pop takes its pair from its end without moving the others. The insertion buffer \(I\) is unsorted; a push fills it, and it goes into the heap only when it is full or when \(D\) runs out.

Lemma 24.20. In each queue, let \(D\) be empty only if the queue is, and let no pair of \(I\) or of the heap \(H\) be less than a pair of \(D\). Then the least pair of \(D\) is the least of the queue, and the push and the pop of Algorithm 24.9 keep both properties, at a cost of \(O( \log m )\) amortized time per operation on a queue of \(m\) pairs.

Proof. We note that the first statement is the second property. A push of a pair not greater than the greatest of \(D\) puts it into \(D\). Then the greatest of a full \(D\) moves into \(I\) (with \(I\) into \(H\) when \(I\) is full), and it is not less than the rest of \(D\). A greater pair goes into \(I\), or into \(D\) when \(I\) and \(H\) are empty, and the pairs of a full \(I\) go into \(H\); neither move changes the two properties. A pop takes the least of \(D\) and, if \(D\) becomes empty, moves \(I\) into \(H\) and the least \(\min( 16 , |H| )\) pairs of \(H\) into \(D\), which are not greater than the rest of \(H\); \(D\) is then empty only if \(H\) is. As to the cost, a push or a pop changes \(D\) or \(I\) in \(O( b )\) time, \(b = 16\); a full \(I\) goes into \(H\) by \(b\) pushes, in \(O( b \log m )\) time, at most once per \(b\) pairs put into \(I\), and \(D\) is refilled by at most \(b\) pops of \(H\), in \(O( b \log m )\) time, at most once per \(b\) pairs taken from \(D\), but for the refills of fewer than \(b\) pairs, which happen only when \(H\) empties and cost \(O( |H| \log m )\), charged to the pairs that entered \(H\). \(\square\)

Each queue is therefore exact, the relaxation is only in the choice of the queue, and Theorem 24.1 applies unchanged. Its heap is touched by batches of 16 pairs, and the lines of \(D\) and \(I\) usually stay in the cache of the thread. The lemma asks of \(H\) only an exact queue, and MultiQueue takes it as its template parameter H, given the type of the pairs and their order, by default MultiQueueHeap, the 8-ary heap: with the keys of packFG(), the pairs \(( f , g )\) of a best-first search with integer costs, \(H\) can be the bucket queue of BucketHeap (§9.9), whose pushes and pops take \(O( 1 )\) amortized time with bounded keys, so that the cost of an operation no longer grows with \(m\) (test engineered_queues.multi-queue-buckets). The Multi Bucket Queue of Zhang, Posluns and Jeffrey 2024 shares the buckets among the threads, each bucket a MultiQueue of its own; here each queue keeps its buckets under its lock, and the choice of the queue is the one of Theorem 24.1. We know of no theory of the stickiness yet: the measures of Williams et al. 2021 show rank errors that grow about linearly in \(s\), which is why \(s\) is a parameter of the constructor (16 by default, given by stickiness()); the bounds above are those of \(s = 1\). Furthermore, pushAll() puts a range of pairs into one queue under one lock. A thread that makes several pairs at once (e.g., the successors of a node) thus takes one lock instead of one per pair, at the price of a relaxation like that of a stickiness of the number of the pairs. A pop that finds both queues empty scans all the queues, each under its lock. When no push runs at the same time, a scan that finds no pair proves the structure empty, which a parallel search needs in order to stop. Its locks are test-and-test-and-set on a byte, taken by an exchange after a plain read; a pop holds one lock, a push one, and the scan one at a time, so that no deadlock is possible. Each operation of a single queue is linearizable at its lock, while the structure as a whole is relaxed, i.e., it is not a linearizable priority queue but for \(n = 1\). The greatest key under less (the infinity of a real) stands for an empty queue in the atomic minima, and a pair with that key is popped only by the scan.

24.10 Waiting until a condition holds

A thread that waits for an item could look at the structure again and again, which wastes a core, or sleep for fixed lengths, which delays the item. The event count of Reed and Kanodia 1979 lets it sleep until another thread signals that the condition may have become true, with no lock and with nearly no cost for the signal when nobody sleeps. EventCount holds an epoch \(e\) and the number \(w\) of the waiters, the two halves of one word of 64 bits (on a separate line). It also holds a copy \(E\) of the epoch of 32 bits, the size of a futex, on which the waiters sleep. A waiter announces itself and reads the epoch in one read-modify-write (prepareWait(), which adds 1 to \(w\) and returns \(e\), of the member type Key), and looks at the condition once more. If the condition is still false, it sleeps while \(E = e\) (commitWait( e ), by std::atomic::wait); otherwise it withdraws (cancelWait( e )). A notifier makes the condition true, and then notify() reads the word after a fence. Only if there are waiters does it advance the epoch and set \(w\) to 0, in one compare-and-swap, and wake them (Figure 24.11). Later notifications, while the woken threads are still on their way, find no thread to wake and cost no system call.

Figure 24.11. The word of the epoch \(e\) and of the waiters \(w\) of an EventCount, and the copy \(E\) of the epoch, after prepareWait() of a waiter, which then sleeps while \(E = 5\), and after notify(), which advances the epoch, withdraws the waiter and wakes it.

Its public members are

// declarations of <ADS/concurrent/EventCount.h>
class EventCount
{
 public:
 using Key = std::uint32_t;
 Key prepareWait( void ) noexcept;
 void cancelWait( Key k ) noexcept;
 void commitWait( Key k ) noexcept;
 void notify( void ) noexcept;
 template< class P >
 void await( P && p , std::int64_t spin = 20000 );
 std::uint32_t waiters( void ) const noexcept;
 };

and a thread waits for a flag that another one raises as follows:

ADS::EventCount E;
std::atomic< bool > ready{ false };
std::thread w( [ & ]() {
 E.await( [ & ]() { return( ready.load() ); } );  // spins, then sleeps
 } );
ready.store( true );  // the condition first,
E.notify();           // then the notification
w.join();

Algorithm 24.10. The operations of EventCount (after Reed and Kanodia 1979); \(( e , w )\) is the word of the epoch and of the waiters, and \(E\) the copy of the epoch.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{prepareWait}() \cr 2 & \quad ( e' , w' ) \gets \mathrm{fetchAdd}( ( e , w ) , 1 )\quad \triangleright\ \text{sequentially consistent} \cr 3 & \quad \text{a full fence (none with a read-modify-write in} \text{ the notifier)} \cr 4 & \quad \textbf{return}\ e' \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{cancelWait}( k ) \cr 2 & \quad \textbf{repeat}\ ( e' , w' ) \gets ( e , w ) \ \textbf{until}\ e' \ne k\ \textbf{or}\ \mathrm{CAS}( ( e , w ) , ( e' , w' ) , ( e' , w' - 1 ) ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{commitWait}( k ) \cr 2 & \quad \textbf{while}\ E = k\ \textbf{do}\ \text{sleep until } E \text{ changes}\quad \triangleright\ \text{acquire} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{notify}() \cr 2 & \quad \text{a full fence};\ ( e' , w' ) \gets ( e , w )\quad \triangleright\ \text{or a read-modify-write that adds 0} \cr 3 & \quad \textbf{while}\ w' > 0\ \textbf{do} \cr 4 & \qquad \textbf{if}\ \mathrm{CAS}( ( e , w ) , ( e' , w' ) , ( e' + 1 , 0 ) )\ \textbf{then}\quad \triangleright\ \text{acquire and} \text{ release} \cr 5 & \qquad\quad \text{raise } E \text{ to } e' + 1 \text{ if it is} \text{ behind}\quad \triangleright\ \text{release}; \ \text{wake all the threads asleep on } E \cr 6 & \qquad\quad \textbf{return} \cr 7 & \qquad ( e' , w' ) \gets ( e , w )\quad \triangleright\ \text{read} \text{ by the failed CAS} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{await}( p , \mathit{spin} ) \cr 2 & \quad \textbf{repeat}\ \textbf{if}\ p()\ \textbf{then return}; \ \text{a pause}\ \textbf{until}\ \mathit{spin} \text{ ns have} \text{ passed} \cr 3 & \quad \textbf{while not}\ p()\ \textbf{do} \cr 4 & \qquad k \gets \mathrm{prepareWait}() \cr 5 & \qquad \textbf{if}\ p()\ \textbf{then}\ \mathrm{cancelWait}( k ); \ \textbf{return} \cr 6 & \qquad \mathrm{commitWait}( k ) \end{array} \]

The notifier and the waiter each run a full fence of the standard. When no thread waits, a notification thus costs the fence and the read of a line that stays shared. With ADS_EVENTCOUNT_RMW defined, the notifier reads the waiters by a read-modify-write that adds 0 instead, and neither side runs a fence: the read-modify-write reads the last value in the order of the modifications of the word, so that it either sees the waiter or is seen by it through the release sequence; this is also the form that the sanitizer of threads checks, since it does not model the fences, and the one that the header takes when the build defines ADS_SANITIZE_THREAD, as CMake and the makefile do when the options of the compiler turn the sanitizer on. Which of the two costs less depends on the processor (a full fence against a line taken exclusive at each notification), and we leave the choice of the default to the campaign of Appendix B. It is worth noting that the asymmetric fences of the system (membarrier( 2 ) on Linux, Ladan-Mozes, Lee and Vyukov 2011), which would let the notifier run only a fence of the compiler, have no portable form.

Lemma 24.21. Let the read-modify-write of the waiter be followed by a full fence, and the write that makes the condition true be followed by a full fence before the notifier reads the waiters. Then a waiter does not sleep through a notification of a condition that is true.

Proof. We place the two fences in \(S\). If that of the notifier comes first, the waiter, which looks at the condition after its fence, sees it true and does not sleep. If that of the waiter comes first, the notifier reads its announcement, \(w \ge 1\), and advances the epoch by a release on the same word; then either the waiter has not yet compared \(E\) with \(e\), and finds it changed, or it sleeps on \(E = e\) and is woken by the notification that follows the change. A "spurious" wake-up only makes the waiter look again. \(\square\)

We need one more detail to keep the lemma true with several notifiers. Two notifiers that advanced the epoch of the word to \(e - 1\) and to \(e\) may reach \(E\) in the other order. A store of \(e - 1\) after \(e\) would then put back the epoch of a waiter that the second notifier withdrew, and that waiter would sleep with the condition true and no thread to wake it. Hence the copy is only raised, by a compare-and-swap with release that compares the epochs modulo \(2^{32}\): the epoch \(e\) is ahead of the copy \(E\) when \(0 < ( e - E ) \bmod 2^{32} < 2^{31}\). Under the sanitizer of threads, which does not model the fences, the notifier reads the word by a read-modify-write instead, which reads the last value in the order of its modifications.

Finally, await( p ) packs the loop of Algorithm 24.10. It returns when p() is true, \(p\) being called by the waiting thread only (which may thus take the item in \(p\)). It first looks again and again for 20 \(\mu\)s (the parameter spin, in nanoseconds), with a pause of the processor between the looks and a read of the clock every 64 looks; then it waits by prepareWait(), cancelWait() and commitWait() as above. Also, waiters() gives the number \(w\) of the waiters announced, a relaxed read. An item that comes within that time costs no sleep and no wake-up, each of which takes about the time of a system call and of a switch of threads. We use it in the queues of §24.3 and §24.4 for their operations that sleep (waitPop(), waitTake()).

Spinning is not "free" either, since the loads and the failed compare-and-swaps of the threads that spin on one line keep moving it between their caches. Backoff is the exponential backoff of Anderson 1990 (see also Mellor-Crummey and Scott 1991). Its call \(k\) from the last reset() runs \(2^k\) pauses of the processor (pause on x86, yield on AArch64) while \(k \le S\), and from then on it yields the processor to the system. Note that spinning() is true when the next call still spins; a waiter can then move on to sleep, e.g., on an EventCount, once it yields. With \(S = 6\) (the default; the constructor requires \(0 \le S \le 16\)) the spinning lasts \(2^7 - 1 = 127\) pauses, a few microseconds, and step() gives the number \(k\) of the calls since the last reset() (up to \(S + 1\)).

Its public members are

// declarations of <ADS/concurrent/Backoff.h>
class Backoff
{
 public:
 explicit Backoff( int S = 6 );
 void pause( void ) noexcept;
 void reset( void ) noexcept;
 bool spinning( void ) const noexcept;
 int step( void ) const noexcept;
 };
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{pause}() \cr 2 & \quad \textbf{if}\ k \le S\ \textbf{then} \cr 3 & \qquad \textbf{for}\ i \gets 1\ \textbf{to}\ 2^k\ \textbf{do} \ \text{a pause of the processor} \cr 4 & \qquad k \gets k + 1 \cr 5 & \quad \textbf{else}\ \text{yield the processor} \end{array} \]

Lemma 24.22. A thread that looks at a condition before each call of pause() and once after the last one, from a reset(), makes its look \(j \ge 1\) after \(2^{j - 1} - 1\) pauses, for \(j \le S + 2\); hence a condition that becomes true after \(0 < t \le 2^{S + 1} - 1\) pauses is seen after fewer than \(2 t + 1\) pauses, with \(O( \log t )\) looks.

Proof. The look \(j\) follows the calls \(0 , \ldots , j - 2\), which run \(1 + 2 + \cdots + 2^{j - 2} = 2^{j - 1} - 1\) pauses while \(j - 2 \le S\). If the condition becomes true after \(t > 0\) pauses, the look 1, after no pause, sees it false; let the last look that sees it false be the look \(j\), after \(T = 2^{j - 1} - 1 < t\) pauses. Since \(t \le 2^{S + 1} - 1\), we have \(j \le S + 1\), and the next look comes after \(2^j - 1 = 2 T + 1 < 2 t + 1\) pauses; the looks are \(j + 1 \le \log_2 ( t + 1 ) + 2\), i.e., \(O( \log t )\). \(\square\)

The looks of \(p\) threads at one line thus thin out geometrically, while the delay added to a wait is less than the wait itself (plus one pause), and a wait longer than \(2^{S + 1}\) pauses gives the processor back to the system. The test engineered_search.backoff-threads checks the steps and four threads that wait with it for a flag.

24.11 Priority queues that are stolen

A best-first search on \(p\) workers (e.g., a branch-and-bound by bounds, or an A* search) may keep its OPEN in one queue shared by all, exact under a lock or relaxed as the MultiQueue of §24.9. Alternatively, it may keep a queue per worker, from which the idle workers steal. We adopt the second choice, which keeps the order of each worker exact. A search needs this when it counts the nodes of each worker against a limit, or when it wants the same run from the same steals. It loses the global order, however, and a worker may expand a node worse than the best of another worker; the steals (hopefully) keep this loss "small" when they move "good" nodes. StealablePriorityQueue is such a queue, and StealingFrontier holds \(p\) of them with the detection of the end of the search. Its design has to settle how many pairs a thief takes, which ones, and at what price for the owner.

As to how many, a thief takes half of the pairs, as in the queues of Hendler and Shavit 2002 and in the priority queues stolen by Wimmer et al. 2014. A steal of one pair usually sends the thief back at once, while a steal of half spreads the pairs made by one worker over \(p\) workers in about \(\log_2 p\) rounds of steals. The Stealing Multi-Queue of Postnikova et al. 2022 steals instead a batch of a few of the best tasks. Its owner sets them apart in a buffer and skips them in the meantime, and its order is thus relaxed by that buffer.

As to which ones, the "better" half sends the victim, which made those pairs, to "worse" ones, and the next steal brings the good pairs back the other way. In turn, the worse half gives the thief the pairs that a best-first search expands last, and that a bound improved in the meantime is likely to prune. An "interleaved" half, instead, gives each worker a share of the best pairs as of the others. This is the reason behind several balancing rules of the parallel branch-and-bound. That of Tschöke, Lüling and Monien 1995 is best when each of the \(p\) processors holds one of the \(p\) subproblems of least bound, and it balances the least bounds of the heaps besides their sizes. Also, Karp and Zhang 1993 send each child to a random processor, and the randomized priority queue of Sanders 1998 spreads its items at random over the processors.

We therefore let the queue deal its pairs to two 4-ary heaps \(H_0\) and \(H_1\) of its owner, which no other thread reads. A push goes into the smaller heap, and into each in turn when they are as large. Hence the pairs pushed one after the other (e.g., the children of a node) go to both heaps, and either heap holds, for each range of keys, about half of the pairs in it. A pop takes the better of the two least pairs. A thief takes the heap whose least pair is not the least of the queue, and the owner thus keeps its best pair and its next pop (Figure 24.12).

Figure 24.12. A StealablePriorityQueue whose owner pushed the keys 1 to 8, dealt to its two heaps (in the order of a 4-ary heap); serve() moves into the offer the heap whose least key 2 is not the least of the queue, and a thief claims it by an exchange and deals its pairs to two heaps of its own.

As to the price, a queue whose pairs a thief may take at any time makes its owner race the thieves at each pop. By the laws of order of Attiya et al. 2011, a linearizable pop of such an object needs a read-modify-write or a fence, as take() of the deque of §24.5 does. Here, instead, a thief raises the flag hungry of the queue, which the owner reads with no order at its next push or pop (or at serve()). Its owner answers by moving a heap into the offer, an atomic pointer published with release, which a thief claims by an exchange with null; these are the receiver-initiated steals of the private deques of Acar, Charguéraud and Rainey 2013. Thus the common case of the owner costs no read-modify-write and no fence. A thief, in exchange, waits (hopefully briefly) for the next operation of the owner, as long as a Backoff spins, before it tries another victim.

Its public members are

// declarations of <ADS/concurrent/StealablePriorityQueue.h>
template< class K , class T , class Less = std::less< K > , class Bd = void ,
          class BdLess = std::less<> >
class StealablePriorityQueue
{
 public:
 static constexpr bool bounded = ! std::is_void_v< Bd >;
 using Bound = std::conditional_t< bounded , Bd , detail::SpqNoBound >;
 using Entry = detail::SpqEntry< K , T , Bd >;  // key, (bound,) item
 explicit StealablePriorityQueue( Less less = Less() , BdLess bl = BdLess() );
 void push( K k , T x )
  requires( ! bounded );
 void push( K k , Bound b , T x )
  requires bounded;
 std::optional< Bound > minBound( void ) const
  requires bounded;
 std::optional< Entry > pop( void );               // the owner
 const Entry & top( void );                        // the owner
 void serve( void );                               // the owner
 std::size_t steal( StealablePriorityQueue & v );  // a thief, into v
 template< class F >
 std::size_t drain( F && f );
 std::size_t size( void ) const;
 bool empty( void ) const;
 bool stealable( void ) const;
 bool offering( void ) const;
 std::pair< std::size_t , std::size_t > halves( void ) const;
 bool consistent( void ) const;
 };

Algorithm 24.11. The operations of StealablePriorityQueue; \(O\) is the offer, \(k_O\) its least key and \(\mathit{offered}\) the knowledge of the owner that it made it.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{push}( k , x ) \cr 2 & \quad \textbf{if}\ |H_0| \ne |H_1|\ \textbf{then}\ j \gets \text{the smaller}\ \textbf{else}\ \tau \gets 1 - \tau;\ j \gets \tau \cr 3 & \quad \mathrm{push}( H_j , ( k , x ) );\ \mathrm{serve}() \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{pop}() \cr 2 & \quad \mathrm{serve}();\ \mathrm{settle}() \cr 3 & \quad \textbf{if}\ H_0 = H_1 = \emptyset\ \textbf{then return nil} \cr 4 & \quad \textbf{return}\ \mathrm{pop}( H_j ) \text{ for the } j \text{ of the least top, } 0 \text{ on a tie} \cr 5 & \textbf{procedure}\ \mathrm{settle}() \cr 6 & \quad \textbf{if}\ \mathit{offered}\ \textbf{and}\ ( H_0 = H_1 = \emptyset\ \textbf{or}\ k_O < \text{the least local key} ) \ \textbf{then} \cr 7 & \qquad G \gets \mathrm{exchange}( O , \textbf{nil} ); \ \mathit{offered} \gets \textbf{false}\quad \triangleright \ \text{acquire and release} \cr 8 & \qquad \textbf{if}\ G \ne \textbf{nil}\ \textbf{then}\ \text{the} \text{ pairs of } G \text{ and of the smaller heap into one heap} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{serve}() \cr 2 & \quad \textbf{if not}\ \mathit{hungry}\ \textbf{then return} \quad \triangleright\ \text{relaxed} \cr 3 & \quad \textbf{if}\ \mathit{offered}\ \textbf{and}\ O \ne \textbf{nil}\ \textbf{then return}\quad \triangleright\ \text{one} \text{ offer at a time} \cr 4 & \quad \mathit{offered} \gets \textbf{false};\ \mathit{hungry} \gets \textbf{false} \cr 5 & \quad \textbf{if}\ |H_0| + |H_1| < 2\ \textbf{then return} \cr 6 & \quad j \gets \text{the heap whose top is not the least}; \ m \gets |H_0| + |H_1| \cr 7 & \quad \textbf{if}\ 5 |H_j| < m\ \textbf{or}\ 5 |H_j| > 4 m \ \textbf{then} \cr 8 & \qquad \text{deal the pairs of } H_0 \text{ and } H_1 \text{ in turn to two new heaps};\ j \gets \text{as at line } 6 \cr 9 & \quad k_O \gets \text{the key of } \mathrm{top}( H_j );\ O \gets H_j;\ H_j \gets \emptyset;\ \mathit{offered} \gets \textbf{true} \quad \triangleright\ \text{release} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{steal}( v ) \cr 2 & \quad \textbf{if}\ O_v = \textbf{nil}\ \textbf{then} \cr 3 & \qquad \textbf{if}\ v \text{ holds less than two pairs} \ \textbf{then return}\ 0\quad \triangleright\ \text{a hint of } v \cr 4 & \qquad \mathit{hungry}_v \gets \textbf{true};\ \text{wait a little} \text{ while } O_v = \textbf{nil} \cr 5 & \qquad \textbf{if}\ O_v = \textbf{nil}\ \textbf{then return}\ 0 \cr 6 & \quad G \gets \mathrm{exchange}( O_v , \textbf{nil} )\quad \triangleright\ \text{acquire and release} \cr 7 & \quad \textbf{if}\ G = \textbf{nil}\ \textbf{then return}\ 0 \quad \triangleright\ \text{another thread was first} \cr 8 & \quad \text{deal the pairs of } G \text{ in turn to } H_0 \text{ and } H_1;\ \textbf{return}\ |G| \end{array} \]

Until a thief claims the offer, its pairs still belong to the owner. A pop whose least local key is greater than \(k_O\) (or whose heaps are empty) takes the offer back by the same exchange, and whoever of the two threads exchanges first gets all of it.

Lemma 24.23. Let the owner take the offer back, by an exchange with null, before a pop whose two heaps are empty or whose least key is greater than \(k_O\). Then each pop of the owner returns a pair of least key among those that the owner holds at the moment of the pop, the pairs of an offer not yet claimed included.

Proof. We first note that the heaps of the owner change only by its operations. Now, the offer, once published, does not change until one exchange takes it, by a thief or by the owner and never by both, since the exchanges on one word are totally ordered and only the first one finds the pointer. If the least local key is not greater than \(k_O\), the local pair is a least pair of all, whether a thief claims the offer before the pop or not. Otherwise the owner exchanges; either it gets the offer back and pops from the pairs joined, or a thief had claimed it before, and the pairs were no longer of the owner when it popped. \(\square\)

Each pop is thus exact at the moment of its exchange, or of its last change of the heaps. Otherwise, the only pairs that leave the owner are those of an offer, a choice of the owner that keeps its least pair.

Lemma 24.24. For an owner that holds \(m\) pairs, a push and a pop cost \(O( \log m )\) time and a load of the flag hungry, besides the answer to a thief that they may give; the answer costs \(O( 1 )\) time, or \(O( m )\) when the heap \(j\) to offer is unbalanced (\(5 | H_j | < m\) or \(5 | H_j | > 4 m\)) and the owner first deals the \(m\) pairs again; and a steal of \(s\) pairs costs the thief one exchange, a store of the flag hungry, and \(O( s )\) time.

Proof. Each heap holds at most \(m\) pairs, and a push or a pop sifts one pair along a path of a 4-ary heap, of length \(O( \log_4 m )\); the choice of the heap and the reading of the flag are \(O( 1 )\). A deal puts the \(m\) pairs in turn into two vectors and makes each a heap by the construction of Floyd, which costs time linear in its size. Answering a thief is the store of a pointer to a heap with release, and the heap moves with its pointer, with no copy of a pair. A thief raises the flag by a relaxed store, claims the offer by one exchange and, if it got it, moves the heap into its own, with no copy, and deals its \(s\) pairs to its two heaps, again by Floyd's construction. \(\square\)

StealingFrontier holds the queues of \(p\) workers, one per call \(f( i )\) of the run( p , f ) of an executor (see chapter 25). Its pop( i ) returns the least pair of the queue of the worker \(i\). When that queue is empty, it returns the least pair of what it steals from victims drawn at random; it returns no pair only when no worker holds one, or after stop() (terminated() tells whether no worker holds a pair, i.e., \(C = 0\), and stopped() whether stop() was called). The owner of a StealablePriorityQueue learns from offering() whether one of its offers waits for a thief.

Its public members are

// declarations of <ADS/concurrent/StealablePriorityQueue.h>
template< class K , class T , class Less = std::less< K > , class Bd = void ,
          class BdLess = std::less<> >
class StealingFrontier
{
 public:
 using Queue = StealablePriorityQueue< K , T , Less , Bd , BdLess >;
 using Entry = typename Queue::Entry;
 using Bound = typename Queue::Bound;
 explicit StealingFrontier( std::size_t p , std::uint64_t seed = 1 ,
                            Less less = Less() , BdLess bl = BdLess() );
 std::size_t workers( void ) const;
 Queue & queue( std::size_t i );
 void push( std::size_t i , K k , T x )
  requires( ! Queue::bounded );
 void push( std::size_t i , K k , Bound b , T x )
  requires Queue::bounded;
 std::optional< Bound > minBound( std::size_t i ) const
  requires Queue::bounded;
 template< class F >
 std::size_t drain( std::size_t i , F && f );
 void serve( std::size_t i );
 std::optional< Entry > pop( std::size_t i );
 void stop( void );
 bool stopped( void ) const;
 bool terminated( void ) const;
 std::size_t steals( void ) const;
 template< class E , class F >
 void run( E & ex , F && f );
 template< class F >
 std::size_t leftovers( F && f );
 };

and \(p\) workers of the pool of §25.3 run a search on it as follows, each worker \(i\) popping from its queue (or stealing, inside pop( i )) until the frontier is empty everywhere:

#include "ADS/parallel/ThreadPool.h"

ADS::ThreadPool pool( 4 );
ADS::StealingFrontier< int , int > F( 4 );
F.push( 0 , 0 , 1 );  // the root, key 0, at worker 0
std::atomic< long > nodes{ 0 };
F.run( pool , [ & ]( std::size_t i ) {
 while( auto e = F.pop( i ) ) {  // nothing once terminated
  ++nodes;
  if( e->item < 1000 )  // two children
   for( int c : { 2 * e->item , 2 * e->item + 1 } )
    F.push( i , e->key + 1 , c );
  }
 } );  // nodes is 1999

Algorithm 24.12. The pop of a worker of StealingFrontier; \(C\) is the counter of the workers at work and of the thieves trying, \(p\) at the start.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{pop}( i ) \cr 2 & \quad e \gets \mathrm{pop}( Q_i );\ \textbf{if}\ e \ne \textbf{nil}\ \textbf{then return}\ e \cr 3 & \quad C \gets C - 1\quad \triangleright\ i \text{ holds nothing} \cr 4 & \quad \textbf{loop} \cr 5 & \qquad \textbf{if}\ \text{stopped}\ \textbf{or}\ C = 0 \ \textbf{then return nil} \cr 6 & \qquad v \gets \text{a worker} \ne i \text{ at random} \cr 7 & \qquad \textbf{if}\ v \text{ offers, or holds two pairs at least} \ \textbf{then} \cr 8 & \qquad\quad C \gets C + 1 \cr 9 & \qquad\quad \textbf{if}\ \mathrm{steal}( Q_i , Q_v ) > 0 \ \textbf{then return}\ \mathrm{pop}( Q_i ) \cr 10 & \qquad\quad C \gets C - 1 \cr 11 & \qquad \text{back off} \end{array} \]

Lemma 24.25. In StealingFrontier, let the counter \(C\) start at \(p\), and let a worker subtract 1 when its pop finds its heaps and its offer empty. Let a thief add 1 before the exchange that claims an offer and subtract 1 if the exchange fails, and let only a worker that holds a pair (or the program before the run) push. Then no pair exists when \(C = 0\), and none exists afterwards.

Proof. We observe that a pair lies in the heaps or in the offer of a worker that has not left \(C\), since a worker leaves only when it holds no pair; or it lies in the offer claimed by a thief, which entered \(C\) before its exchange. The victim that finds its offer claimed has read the null of the exchange of the thief, and the two exchanges synchronize (a release read by an acquire). Hence the entry of the thief happens before the exit of the victim, and \(C\), whose modifications are totally ordered, cannot reach 0 in between; hence, a pair in transit is always counted. When \(C = 0\) no pair exists, and no pair can be created, since only a worker that holds one pushes. Thieves that still try enter and leave \(C\) with no pair to find, and see \(C = 0\) again. \(\square\)

When we give a type of bounds, each pair carries a bound besides its key, e.g., the key of selection of a branch-and-bound by depth first or by best estimate, and the bound by which it prunes. Then minBound() gives the least bound \(\beta\) of the pairs of the owner, and when \(\beta\) cannot improve the incumbent beyond the tolerance, drain() drops the entire queue. Each heap keeps its least bound as long as no pop takes a pair of that bound (a push lowers it, if its bound is less), and finds it again by a scan of its pairs when one does. With bounds independent of the keys, a pop takes the least of \(m\) bounds with probability about \(1 / m\), and the scans cost \(O( 1 )\) expected per pop. With bounds that go with the keys, as in a search by best first, each pop takes it, and each scan costs \(\Theta( m )\). Hence, when the pairs scanned exceed 16 times the pops and the pairs held, plus \(2^{16}\) for the start, on a heap of 64 pairs at least, the heap keeps instead, in a vector apart, the least bound \(\mu( i )\) of the pairs of the subtree of each node \(i\):

\[ \mu( i ) = \min\{ b( i ) , \mu( 4 i + 1 ) , \ldots , \mu( 4 i + 4 ) \} , \tag{24.9} \]

where \(b( i )\) is the bound of the pair of \(i\), and the children that do not exist are left out; the least bound of the heap is then \(\mu( 0 )\). A push moves the hole of a new leaf up to the place \(i\) of the new pair. The nodes passed by the hole took the pair of their parent, and get (24.9) again from their children, from the leaf up. The subtree of \(i\), and of each node above it, gained the new bound \(b\) only, and \(\mu\) is lowered to \(b\) from \(i\) up as long as \(b\) is less, since \(\mu\) does not increase towards the root. A pop moves the last pair \(z\) down from the root along a path \(P\). A node off \(P\) on the path of the old last leaf lost \(z\) only; it keeps its \(\mu\) if \(\mu\) is less than the bound of \(z\), and so do all those above it off \(P\). The rest of that path, and then \(P\) from its end up, get (24.9) again.

Lemma 24.26. A heap of \(m\) pairs that keeps its least bound by scans spends \(O( c )\) expected time on the scans per pop when the pair popped carries the least bound with probability at most \(c / m\). A heap that keeps \(\mu\) satisfies (24.9) at every node after each push and each pop, which cost \(O( \log m )\) time, and \(\mu( 0 )\) is its least bound.

Proof. A scan reads the \(m\) pairs, and it runs only when the pop takes a pair of the least bound, whence \(O( m \cdot c / m )\) expected per pop. By induction on the depth, (24.9) at every node makes \(\mu( i )\) the least bound of the subtree of \(i\), and \(\mu( 0 )\) that of the heap. A push changes the pairs only on the path from the new leaf to the place \(i\) of the new pair: the nodes below \(i\) on that path hold the pairs of their parents, and recomputing (24.9) from the leaf up restores it there, since their children are already right; above \(i\), each subtree gained the bound \(b\) only, and \(\mu\) becomes \(\min\{ \mu , b \}\), which stops changing at the first node where \(\mu \le b\), since \(\mu\) does not increase towards the root. A pop removes the last leaf, whose pair \(z\) moves down from the root along a path \(P\); off \(P\), only the nodes on the path of the old last leaf lost a pair, \(z\), and their \(\mu\) changes only if it was the bound of \(z\), in which case recomputing (24.9) from below restores it; the nodes of \(P\) are recomputed from the end of \(P\) up. Each recomputation reads at most 5 values, along \(O( 1 )\) paths of length \(O( \log_4 m )\). \(\square\)

A read of \(\mu( 0 )\) thus costs \(O( 1 )\).

We remark that two alternatives cost more on both kinds of bounds. We discard both. The first keeps the bounds of the pushes and those of the pops in two multisets, the least bound being the least of the first once their equal tops are taken out; it adds a push into one of them per operation, on heaps that grow with the pops until they are made again. The second keeps a heap by the bounds, indexed by the places of the pairs, and it adds a second sift per operation and an update of the index at each move of a pair.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{minBound}() \cr 2 & \quad b \gets \min\{ \beta( H_j ) : H_j \ne \emptyset \} \cr 3 & \quad \textbf{if}\ \mathit{offered}\ \textbf{and}\ O \ne \textbf{nil}\ \textbf{then}\ b \gets \min\{ b , b_O \}\quad \triangleright\ \text{acquire} \cr 4 & \quad \textbf{return}\ b\quad \triangleright\ \textbf{nil} \text{ if there is no pair} \cr 5 & \textbf{function}\ \beta( H )\quad \triangleright\ \ell \text{ the least bound known, } \mu \text{ those of the} \text{ subtrees} \cr 6 & \quad \textbf{if}\ \mu \text{ is kept}\ \textbf{then return} \ \mu( 0 ) \cr 7 & \quad \textbf{if}\ \ell \text{ is known}\ \textbf{then return} \ \ell\quad \triangleright\ \text{no pop took a pair of bound } \ell \cr 8 & \quad \ell \gets \text{the least bound of the pairs of } H \text{, by a scan} \cr 9 & \quad \textbf{if}\ |H| \ge 64\ \textbf{and}\ \text{the pairs} \text{ scanned} > 16 ( \text{pops} + |H| ) + 2^{16}\ \textbf{then} \ \text{build } \mu \cr 10 & \quad \textbf{return}\ \ell \end{array} \]

Lemma 24.27. Let the owner keep, when it makes an offer, the least bound \(b_O\) of the heap that it moves into the offer. Let minBound() return the least of the least bounds of its heaps that are not empty and, if the offer that it made is still there at an acquire load of the pointer, of \(b_O\). Then the value returned is the least bound of the pairs that the owner holds at the moment of that load.

Proof. The heaps of the owner change only by its operations, and the least bound of each is exact. In fact, the one known stays the least while no pop takes a pair of that bound, a push lowers it when its bound is less, a scan computes it, and \(\mu( 0 )\) is it by (24.9). The pairs of an offer are fixed from its publication until an exchange takes it, and \(b_O\) is their least bound. At the load, the offer is either still there, and then its pairs are of the owner (cf. Lemma 24.23: a thief that claims it later takes pairs that the owner held at the load), or claimed, and then its pairs belong to the thief from its exchange on. \(\square\)

The pairs stolen keep their keys and their bounds: the thief adopts the heap as it is, deals its pairs to two heaps, and rebuilds (24.9) on them. Note that drain() takes the offer back first, if no thief has claimed it, and empties both heaps; a queue pruned by its \(\beta\) holds no pair afterwards. StealingFrontier::run() calls the \(p\) workers by ex.run( p , f ). An exception of a worker stops the others, through stop(), and the first one is thrown again once all the workers have returned; afterwards, leftovers() hands to a function the pairs left in the queues, which bound the optimum of what was not explored.

24.12 An exact priority queue without locks

The MultiQueue of §24.9 relaxes the order of the pops, and the queues of §24.11 keep it exact only within each worker. Some parallel searches, however, want one OPEN shared by all the threads in the exact order of the keys (e.g., the SPA* of Burns et al. 2010, whose threads take the best open node of the search). A heap under one lock serializes them, and its root is a line that they all write. LockFreePriorityQueue is the skiplist of Lindén and Jonsson 2013, which is linearizable and lock-free, and whose DeleteMin pays one read-modify-write in the common case. The earlier queues on skiplists (Lotan and Shavit 2000; Sundell and Tsigas 2005) unlink each node that they delete. A DeleteMin then writes the pointers of the first nodes of the list (one CAS to mark the node and one per level to unlink it), and the other DeleteMin, which read those pointers, usually miss on them; Sundell and Tsigas, moreover, keep at most one deleted node in the list, and make the threads that meet it help to unlink it. Lindén and Jonsson leave instead the deleted nodes in the list, and cut them off in batches.

The pairs are the nodes of a skiplist (Pugh 1990) of \(L = 32\) levels between a head and a tail, a node of height \(h\) (drawn with probability \(2^{-h}\)) being in the lists of the levels \(0 , \ldots , h - 1\). The keys are made distinct by a stamp of the insertion, \(\kappa = ( k , s )\), where \(s\) is the count of the insertions of the handle and its number, so that two pairs of equal keys come out in the order of their stamps (the device of Sundell and Tsigas 2005); we compare the nodes by \(\kappa\), the tail having the greatest. The pointer of level 0 of a node \(p\) carries in its lowest bit, as in the lists of Harris 2001, a mark, which we write \(d( p )\); note that the mark tells that the node after \(p\) is deleted, and a node is deleted when the word that reaches it at level 0 is marked. An insertion swings that word by a CAS from its value unmarked, and therefore never links a node in front of a deleted one. A DeleteMin walks the list of level 0 from the head over the marked words and marks the first word not marked by a fetch-and-or (FAO), which deletes the node that the word reaches. A DeleteMin that walked more than \(b\) nodes (the parameter offset of the constructor, \(b \ge 1\)) moves the word of level 0 of the head past the deleted nodes by one CAS (a cut), the upper words of the head after them (the restructure), and hands the nodes cut off to the reclamation by epochs described below. We write \(x \prec y\) when the node \(x\) comes before \(y\) in the list of level 0.

Lemma 24.28. The words of level 0 change only by the CAS of an insertion, which links a new node between two adjacent ones, by the FAO of a DeleteMin, which sets a mark, and by the cut, which moves the word of the head forward with its mark set. Hence \(\prec\) is a fixed order of the nodes ever linked, and at each moment (i) the marked words form a prefix of the list, i.e., the deleted nodes are a prefix of it, (ii) after the first deletion the word of the head is marked, and (iii) the nodes not deleted have increasing \(\kappa\) along the list.

Proof. No other statement writes a word of level 0 once its node is linked, and none of the three moves a node or unlinks one but the cut, which unlinks only from the head. As to (i), a FAO marks \(x.\mathit{next}[ 0 ]\) where \(x\) is the head or a node reached by a marked word, and hence extends the prefix, while the CAS of an insertion succeeds only on an unmarked word, and writes an unmarked word to the new node, whose own word, \(\langle S_0 , 0 \rangle\), is unmarked as well. Property (ii) holds since the first FAO marks the word of the head and the cut writes it with its mark set. As to (iii), the walk of \(\mathrm{locate}( \kappa )\) stops at level 0 at a node \(S_0\) that is the tail or has a greater key. Its predecessor \(P_0\) is the head, a node of key less than \(\kappa\), or a deleted node, since the walk passes a node only for its key, for a mark on the word that reaches it, or for a mark on its own word, i.e., when its successor is deleted (the start \(P_1\) of the walk of level 0 falls in the same cases, by induction on the levels). The CAS succeeds only if \(P_0.\mathit{next}[ 0 ]\) is still \(\langle S_0 , 0 \rangle\); hence \(S_0\) is not deleted at that moment, and the new node lies after the deleted nodes and between two nodes not deleted of smaller and greater keys. \(\square\)

We now turn to the upper lists. They are only shortcuts, and need not hold all the nodes (an insertion links its node there from the bottom up, after the CAS of level 0, and stops at the first level where its test fails); we need, however, that the pointers of all the levels lead forward in \(\prec\), since the walks and the safety of the reclamation rest on it. Lindén and Jonsson try to ensure it by stopping the insertion when the successor \(S_i\) found at the level \(i\) is deleted, which they detect by \(d( S_i )\), or, for the last deleted node, whose \(d\) is not set, by comparing \(S_i\) with the last deleted node met by the walk of level 0. This walk, however, starts from \(P_1\), and it misses \(S_i\) when \(P_1\) lies past it. This may happen when the list of level 1 has a branch: a node linked at level 1 after a node that the head has already passed is reachable at level 1 only from that node, and yet it may be linked at level 2 after the head. The insertion would then link its node \(n\) before \(S_i \prec n\), i.e., backwards, and a later walk may reach through it the nodes freed. Hence we use instead the test \(\mathrm{behind}( S_i , n )\) of Algorithm 24.13, which reads the successor of \(S_i\).

Lemma 24.29. Let \(n\) be linked at level 0, and let \(c\) be the successor found at an upper level by a walk for \(\kappa( n )\) made after the CAS that linked \(n\) (or by the walk before it, when \(c\) is compared after that CAS). If \(\mathrm{behind}( c , n )\) is false, then \(n \prec c\).

Proof. Let \(c \prec n\), and let us see that the test is true. The tail comes after all the nodes, and therefore \(c\) is not the tail, and \(\kappa( c ) > \kappa( n )\), since the walk did not pass \(c\) at its level. Let \(P_0\) be the predecessor of \(n\) found by the walk of level 0; then \(c \preceq P_0\). If \(c\) were not deleted when \(n\) was linked, then neither would \(P_0\) be, by Lemma 24.28 (i), and \(P_0\) would have a key less than \(\kappa( n )\), as in its proof; by (iii) \(\kappa( c ) \le \kappa( P_0 ) < \kappa( n )\), which is false. Hence \(c\) is deleted, and so is it at the read of \(c.\mathit{next}[ 0 ]\) in \(\mathrm{behind}\). If the word read is marked, the test is true. Otherwise \(c\) is the last deleted node and its successor \(f\) is the first node not deleted; \(n\) is not deleted, since \(c \prec n\) and the deleted nodes are a prefix, whose last is \(c\), and therefore \(f \preceq n\). Either \(f = n\), or \(f \prec n\), and then \(\kappa( f ) < \kappa( n )\) by (iii), and \(f\) is not the tail; in both cases the test is true. \(\square\)

The test may be true when \(n \prec c\) as well, but only if \(n\) is deleted by then (cf. the last case of the proof), and the insertion then just stops its tower, as it does anyway when \(d( n )\) is set.

Lemma 24.30. A pointer of any level of a node, when not null, reaches a node after it in \(\prec\), and each walk of Algorithm 24.13 moves forward.

Proof. The words of the head and of level 0 do so by Lemma 24.28. An upper pointer of a node is written only by an insertion, either \(n.\mathit{next}[ i ] \gets S_i\) after the test of line 7, which gives \(n \prec S_i\) by Lemma 24.29, or by the CAS that sets \(P_i.\mathit{next}[ i ]\) to \(n\). In the latter case, by induction on the steps, the walk of \(\mathrm{locate}\) moves forward, and \(P_i \preceq P_{i - 1} \preceq \cdots \preceq P_0\), while \(P_0\) is the predecessor of \(n\): in the first round by the CAS of level 0, and after a new \(\mathrm{locate}\) by the test \(S_0 = n\) of line 10. Hence \(P_i \prec n\). \(\square\)

Lemma 24.31. Let the abstract queue be the sequence of the pairs of the nodes not deleted, in the order of the list of level 0. Then insert() and tryDeleteMin() are linearizable as the operations of a priority queue at the points of the header: insert() at the CAS that links its node at level 0, tryDeleteMin() at the FAO that marks the word that reaches the node it returns, or, when it returns nothing, at the read of a pointer to the tail; tryMinKey() at the read of the first unmarked word.

Proof. By Lemma 24.28 (iii) the abstract queue is ordered by \(\kappa\), and each point lies between the invocation and the response of its operation. At the CAS of insert() the new node joins the nodes not deleted at the place of its \(\kappa\), and nothing else changes. A DeleteMin applies its FAO to the word of a node \(x\) that is the head or a deleted node, since it reached \(x\) by marked words. If the word was not marked, the node \(y\) that it reaches is the first not deleted, by (i), i.e., the pair of least key; the FAO removes it from the abstract queue, and no other DeleteMin returns it, since only one FAO finds the word unmarked. If it was marked, another DeleteMin deleted \(y\) in the meantime, nothing changes, and the walk goes on. A DeleteMin that reads a pointer to the tail from the head or from a deleted node \(x\) finds no node after \(x\), and hence an empty abstract queue. Note that no FAO marks a pointer to the tail: the FAO follows a read of the same word that did not reach the tail, and such a word never comes to reach it (an insertion links a node before its old successor). The same argument gives the point of tryMinKey(). The responses are therefore those of the sequential queue on the operations in the order of their points. \(\square\)

Lemma 24.32. Let a cut move the word of level 0 of the head from the node \(o\) to the node \(\nu\). Then (i) the cuts and their restructures run one at a time; (ii) no node being inserted lies before \(\nu\); (iii) once the restructure of the cut is over, each word of the head reaches \(\nu\) or a node after it, and does so ever after; (iv) a thread whose reads of the list follow the end of that restructure reaches no node before \(\nu\).

Proof. (i) The CAS of a cut expects a word without the bit of a cut and writes it with the bit, which only the thread of the cut clears, after its restructure, and no other statement writes the word of the head once it is marked. (ii) The values of the word of the head never repeat, since they move forward; hence the walk of the DeleteMin that cut read the word as \(o\), and visited as its node \(x\) each node from \(o\) to \(\nu\), the last excluded. Then \(\nu\) is the first of them whose flag \(\mathit{inserting}\) it read set, or the node that it deleted; a node before \(\nu\) was read with its flag clear, which an insertion clears once and at its end. (iii) Each node before \(\nu\) has \(d\) set at the cut: those visited were passed by marked words, and those before \(o\) were cut before by induction. The restructure, alone by (i), reads each upper word \(h\) of the head after the cut, leaves it if \(d( h )\) is clear, and then \(\nu \preceq h\), or writes it by a CAS from \(h\) to the first node \(c\) with \(d( c )\) clear that it finds, and then \(\nu \preceq c\). The only other writes of an upper word of the head are those of the restructures of the later cuts, which by the same argument write nodes after their own \(\nu' \succeq \nu\), and the CAS of the insertions with \(P_i\) the head, which write a node being inserted, after \(\nu\) by (ii). (iv) Follows from (iii) and from Lemma 24.30, since the pointers lead forward. \(\square\)

The memory of the nodes cut off is reclaimed by epochs (Fraser 2004; Hart et al. 2007), which the queue owns, since the area has no other reclamation that fits a structure of nodes (the epochs of ConcurrentFlatTable clear a table, they do not free memory). The queue keeps an epoch \(E\), and each handle a record with the epoch announced, \(2 e + 1\) inside an operation of the epoch \(e\) and 0 outside. An operation reads \(E\) and makes the announce by a sequentially consistent exchange before it reads the list, whose words it then reads with sequential consistency too. The thread of a cut stamps the nodes cut off with \(E\), read with sequential consistency after the cut and the restructure, keeps them in its record, and then raises \(E\) by a CAS if all the records inside an operation announce \(E\); a node stamped \(r\) is freed once its thread reads \(E \ge r + 2\). Let a thread \(t\) reach a node stamped \(r\) inside an operation. If the announce of \(t\) followed in the total order \(S\) of §24.1 the last CAS of the cut and of its restructure, so would the reads of \(t\), sequenced after it. A sequentially consistent read that precedes a write in the order of the modifications of its word precedes that write in \(S\) (it is coherence-ordered before it), so that these reads would see the words written by the CAS, and \(t\) would reach no node cut, by Lemma 24.32 (iv). Hence the announce of \(t\) precedes that CAS in \(S\), which precedes the read of \(E = r\). The read of \(E\) by which \(t\) made its announce \(a\) precedes the announce, and therefore \(a \le r\); the read of \(E = r\) precedes the CAS from \(r\) to \(r + 1\). The scan that would raise \(E\) from \(r + 1\) to \(r + 2\) follows that CAS, and hence the announce of \(t\), in \(S\); it sees the announce \(a \ne r + 1\), or a later value of the record, and cannot raise \(E\) while \(t\) stays inside its operation. Of course, a relaxed store of the announce followed by a sequentially consistent fence, with reads that acquire, gives the same order through the rules of the fences. We prefer the exchange, since the sanitizer of threads does not model the fences, and on x86-64 it is one instruction where the store and the fence are two (a sequentially consistent load is there the same plain load as one that acquires). No node is leaked: the destructor frees those that wait for their epoch and those still in the list. The reclamation is blocking, as in the paper: a thread stopped inside an operation keeps \(E\) from growing, and the nodes cut off afterwards from being freed, while the operations of the other threads go on.

Lemma 24.33. The operations are lock-free but for the allocation of the nodes: in an infinite run of \(p\) threads, some operation completes infinitely often.

Proof. Each operation completes after a bounded number of its own successful read-modify-writes: an insertion after at most \(L\), a DeleteMin after one FAO and, if it cuts, one CAS, at most \(L - 1\) in its restructure and the clear of the bit. Let no operation complete after some moment of an infinite run; then each of the \(p\) operations running performs finitely many successful read-modify-writes, and after a later moment none at all. From then on no word of the list changes, and therefore no CAS fails, no FAO finds a mark set by another, and no walk passes more than the finitely many nodes of the list. Some operation, however, takes infinitely many steps, since the run is infinite and the threads are \(p\), and it then performs a successful read-modify-write or completes, a contradiction. We remark that no step waits for another thread (the flag \(\mathit{inserting}\) and the bit of a cut only keep a cut from moving past a node, or from starting), and that a restructure retries a level only after a CAS of an insertion on the same word, since no other restructure runs at the same time, by Lemma 24.32 (i). \(\square\)

A thread stopped inside an insertion (with its flag set), or inside a cut (with the bit set), keeps the head where it is, and the prefix then grows with the deletions, which all the later DeleteMin walk; Lindén and Jonsson remark the first case. Without such a thread, the prefix is bounded as follows.

Lemma 24.34. In a run of one thread, a DeleteMin walks at most \(b + 1\) nodes (the head included), the list holds at most \(b\) deleted nodes between two operations, and the deleted nodes are cut off once per \(b\) DeleteMin that delete a node, from the \(( b + 1 )\)-th on.

Proof. Let \(j\) be the number of the deleted nodes in the list before a DeleteMin that deletes a node. Its walk visits the head and the \(j\) deleted nodes, \(o = j + 1\) nodes, and deletes one more; if \(o > b\), its cut leaves only the node just deleted, the new first node of the head, and \(j = 1\) afterwards, and otherwise \(j + 1\). From \(j = 0\) the values after each DeleteMin are \(1 , 2 , \ldots , b\), then the cut gives 1, and the cycle repeats with \(b\) DeleteMin per cut. An insertion does not change \(j\), and a DeleteMin that finds the queue empty walks the same \(j + 1 \le b + 1\) nodes and changes nothing. \(\square\)

With \(p\) threads the walk is (possibly) longer by the deletions of the others that take place during it. Also, a cut may fail because another one started since its DeleteMin read the head, and then the next DeleteMin that walks more than \(b\) nodes cuts. The test engineered_queues.lockfree-pq checks the bound of the lemma. Furthermore, each handle counts in counts() its read-modify-writes, those that failed, the nodes walked and the cuts, by which two queues can be compared on a busy machine without timing them. The public members of the queue are

// declarations of <ADS/concurrent/LockFreePriorityQueue.h>
template< class K , class T , class Less = std::less< K > >
class LockFreePriorityQueue
{
 public:
 struct Entry
 {
  K key;
  T item;
  };
 struct Counts
 {
  std::uint64_t rmw = 0;
  std::uint64_t failed = 0;
  std::uint64_t walked = 0;
  std::uint64_t cuts = 0;
  };
 class Handle
 {
  public:
  void insert( K k , T x );
  std::optional< Entry > tryDeleteMin( void );
  std::optional< K > tryMinKey( void );
  bool empty( void );
  const Counts & counts( void ) const;
  };
 explicit LockFreePriorityQueue( unsigned offset = 32 ,
                                 std::uint64_t seed = 1 ,
                                 Less less = Less() );
 Handle handle( void );
 unsigned offset( void ) const;
 std::size_t size( void ) const;
 bool empty( void ) const;
 std::size_t prefix( void ) const;
 bool consistent( void ) const;
 };

where size(), empty(), prefix() and consistent() of the queue are called with no operation running, while empty() of a handle is linearizable, as tryMinKey(); as in the MultiQueue, the constant decrease_key declares that a key is lowered by a new pair. Each thread takes its own handle, which holds its record of the epochs:

ADS::LockFreePriorityQueue< int , int > Q;  // b = 32
std::vector< std::thread > T;
for( int k = 0 ; k < 4 ; ++k )
 T.emplace_back( [ & , k ]() {
  auto h = Q.handle();
  for( int i = 0 ; i < 100 ; ++i )
   h.insert( 4 * i + k , i );
  } );
for( auto & t : T )
 t.join();
auto h = Q.handle();
while( auto e = h.tryDeleteMin() ) {
 }  // the keys 0, 1, 2, ...

Algorithm 24.13. The insertion and the DeleteMin of LockFreePriorityQueue::Handle (Lindén and Jonsson 2013, with the test \(\mathrm{behind}\) and the bit of a cut of ours); \(P\) and \(S\) are the predecessors and the successors at each level, \(d( p )\) the mark of \(p.\mathit{next}[ 0 ]\), and \(b\) = offset().

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{insert}( k , x ) \cr 2 & \quad n \gets \text{a node } ( \kappa , x ) \text{ of height } h \text{, drawn with probability } 2^{-h};\ n.\mathit{inserting} \gets \mathit{true} \cr 3 & \quad \textbf{repeat}\ ( P , S ) \gets \mathrm{locate}( \kappa ); \ n.\mathit{next}[ 0 ] \gets S_0 \cr 4 & \quad \textbf{until}\ \mathrm{CAS}( P_0.\mathit{next}[ 0 ] , \langle S_0 , 0 \rangle , \langle n , 0 \rangle )\quad \triangleright\ \text{the linearization point} \cr 5 & \quad i \gets 1 \cr 6 & \quad \textbf{while}\ i < h\ \textbf{do} \cr 7 & \qquad \textbf{if}\ d( n )\ \textbf{or}\ \mathrm{behind}( S_i , n ) \ \textbf{then break}\quad \triangleright\ n \text{ deleted, or } S_i \text{ maybe before } n \cr 8 & \qquad n.\mathit{next}[ i ] \gets S_i \cr 9 & \qquad \textbf{if}\ \mathrm{CAS}( P_i.\mathit{next}[ i ] , S_i , n )\ \textbf{then}\ i \gets i + 1 \cr 10 & \qquad \textbf{else}\ ( P , S ) \gets \mathrm{locate}( \kappa ); \ \textbf{if}\ S_0 \ne n\ \textbf{then break} \cr 11 & \quad n.\mathit{inserting} \gets \mathit{false} \cr 12 & \textbf{function}\ \mathrm{locate}( \kappa ) \cr 13 & \quad p \gets \mathit{head} \cr 14 & \quad \textbf{for}\ i \gets L - 1\ \textbf{downto}\ 0\ \textbf{do} \cr 15 & \qquad c \gets p.\mathit{next}[ i ] \cr 16 & \qquad \textbf{while}\ c.\kappa < \kappa\ \textbf{or}\ d( c ) \ \textbf{or}\ ( i = 0\ \textbf{and}\ d( p ) )\ \textbf{do} \ p \gets c;\ c \gets p.\mathit{next}[ i ] \cr 17 & \qquad P_i \gets p;\ S_i \gets c \cr 18 & \quad \textbf{return}\ ( P , S ) \cr 19 & \textbf{function}\ \mathrm{behind}( c , n ) \cr 20 & \quad \textbf{if}\ c = \mathit{tail}\ \textbf{then return} \ \mathit{false} \cr 21 & \quad \langle f , m \rangle \gets c.\mathit{next}[ 0 ] \cr 22 & \quad \textbf{return}\ m\ \textbf{or}\ f = n\ \textbf{or}\ ( f \ne \mathit{tail}\ \textbf{and}\ f.\kappa < n.\kappa ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{tryDeleteMin}() \cr 2 & \quad x \gets \mathit{head};\ o \gets 0;\ \mathit{nh} \gets \mathrm{nil};\ \mathit{obs} \gets \mathit{head}.\mathit{next}[ 0 ] \cr 3 & \quad \textbf{loop} \cr 4 & \qquad o \gets o + 1;\ \langle y , m \rangle \gets x.\mathit{next}[ 0 ] \cr 5 & \qquad \textbf{if}\ y = \mathit{tail}\ \textbf{then return nil} \quad \triangleright\ \text{empty: linearized at this read} \cr 6 & \qquad \textbf{if}\ \mathit{nh} = \mathrm{nil}\ \textbf{and} \ x.\mathit{inserting}\ \textbf{then}\ \mathit{nh} \gets x \cr 7 & \qquad \textbf{if not}\ m\ \textbf{then}\ \langle y , m \rangle \gets \mathrm{FAO}( x.\mathit{next}[ 0 ] , 1 )\quad \triangleright \ \text{the linearization point if } m = 0 \cr 8 & \qquad x \gets y;\ \textbf{if not}\ m\ \textbf{then break} \cr 9 & \quad e \gets ( x.k , x.x )\text{, the item moved out}; \ \textbf{if}\ \mathit{nh} = \mathrm{nil}\ \textbf{then}\ \mathit{nh} \gets x \cr 10 & \quad \textbf{if}\ o > b\ \textbf{and}\ \mathit{obs} \text{ has no cut bit}\ \textbf{and}\ \mathit{nh} \ne \mathit{obs}\ \textbf{and} \ \mathrm{CAS}( \mathit{head}.\mathit{next}[ 0 ] , \mathit{obs} , \langle \mathit{nh} , 1 , \mathit{cut} \rangle )\ \textbf{then} \cr 11 & \qquad \mathrm{restructure}();\ \text{clear the cut bit} \cr 12 & \qquad \text{retire the nodes from } \mathit{obs} \text{ to } \mathit{nh} \text{, the latter excluded} \cr 13 & \quad \textbf{return}\ e \cr 14 & \textbf{procedure}\ \mathrm{restructure}() \cr 15 & \quad i \gets L - 1;\ p \gets \mathit{head} \cr 16 & \quad \textbf{while}\ i > 0\ \textbf{do} \cr 17 & \qquad h \gets \mathit{head}.\mathit{next}[ i ];\ c \gets p.\mathit{next}[ i ]\quad \triangleright\ \text{in this order} \cr 18 & \qquad \textbf{if not}\ d( h )\ \textbf{then}\ i \gets i - 1; \ \textbf{continue} \cr 19 & \qquad \textbf{while}\ d( c )\ \textbf{do}\ p \gets c;\ c \gets p.\mathit{next}[ i ] \cr 20 & \qquad \textbf{if}\ \mathrm{CAS}( \mathit{head}.\mathit{next}[ i ] , h , c )\ \textbf{then}\ i \gets i - 1 \end{array} \]

As to the cost, an insertion is the search of a skiplist, \(O( \log m )\) expected on \(m\) nodes, plus the deleted prefix that its walk of level 0 may pass, and one CAS per level of its tower, two on average. A DeleteMin walks the prefix, \(O( b )\) nodes on one thread by Lemma 24.34, and pays one FAO, plus one cut per \(b\) deletions, whose restructure walks, at each level, the nodes of that level among the \(O( b )\) cut off. We remark that the nodes of the prefix are read by all the DeleteMin and written by none but for the word that each DeleteMin marks. Indeed, this is the reason of the design: the reads of lines that nobody writes are "cheap", while a write to the first nodes (as in the queues that unlink each node) makes the other DeleteMin miss on them. The FAO on the first unmarked word, however, is still one word that all the DeleteMin contend for, and at most one of them succeeds per deletion. With many threads the queue therefore (typically) serves the DeleteMin one at a time at that word, which the relaxed queue of §24.9 avoids at the price of the order.

24.13 Structures of one writer

A worker of a parallel search keeps state that only it changes and that the others read: its CLOSED set, which the others look up to prune the states they reach, and the least \(f\) of its OPEN list, which bounds the work of all. A structure of one writer needs no read-modify-write, since no two threads may want to write the same word (cf. §24.2), and the two of this section are built on that remark.

One writer and many readers. SingleWriterFlatTable is the linear probing of §24.8 with the pairs in the words (one word for a set, two for a key and a value, each trivially copyable and of at most 8 bytes), filled by one thread. An insertion reads the words from the place of its key and, at the first free one, stores the value and then the key, the key by a store with release. A growth fills a vector twice as large while no reader can see it, and then stores it as the vector in use with release; the old one is kept for the readers still on it. A lookup is that of ConcurrentFlatTable: it reads the vector in use and the words with acquire, and, when it ends at a free place, reads the vector in use again and starts over if the table grew meanwhile. The counters of the threads and the protocol of Dekker of Lemma 6 of the theory, i.e., two sequentially consistent read-modify-writes per insertion, are thus gone, and an insertion is made of plain loads and stores on x86-64. With EpochClear the writer renews a group out of use when an insertion first reaches it, writing 0 to its words and then its stamp with release, so that clear() takes \(O( 1 )\) as in §24.8. Its public members, but for the variants that take the hash already computed, are

// declarations of <ADS/concurrent/SingleWriterFlatTable.h>
template< class K , class V , class H = DefaultHash< K > ,
          class Eq = std::equal_to< K > , class C = ZeroingClear >
class SingleWriterFlatTable
{
 public:
 explicit SingleWriterFlatTable( std::size_t n = 0 , H h = H() ,
                                 Eq eq = Eq() );
 std::uint64_t hash( const K & k ) const;
 std::pair< V , bool > findOrInsert( const K & k , const V & v );
 bool insert( const K & k , const V & v );
 template< class F >
 bool update( const K & k , F && f )
  requires( valueBytes() > 0 );
 std::optional< V > find( const K & k ) const;
 std::optional< K > findKey( const K & k ) const;
 bool contains( const K & k ) const;
 std::size_t size( void ) const;
 bool empty( void ) const;
 std::size_t capacity( void ) const;
 std::size_t rehashes( void ) const;
 void reserve( std::size_t n );
 void clear( void );
 std::uint64_t epoch( void ) const;
 template< class F >
 void forEach( F && f ) const;
 bool consistent( void ) const;
 };

besides findOrInsertKey( k , h ) of a set, which returns the key held equal to \(k\). One thread at a time, the writer, calls findOrInsert(), findOrInsertKey(), insert(), update(), reserve() and clear(), and the role may pass to another thread by any synchronization. Any thread calls the lookups; size() gives the writer its exact count, and the others a count that the table had since the last clear().

Algorithm 24.14. The insertion, with the growth, and the lookup of SingleWriterFlatTable; \(W\) is the vector in use, of \(2^l\) places, and \(n\) the number of the pairs.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{findOrInsert}( k , h , v ) \cr 2 & \quad \textbf{if}\ 2 ( n + 1 ) > 2^l\ \textbf{then} \ \mathrm{grow}() \cr 3 & \quad i \gets \lfloor h / 2^{64 - l} \rfloor \cr 4 & \quad \textbf{loop} \cr 5 & \qquad \textbf{if}\ \text{the group of } i \text{ is out of use} \ \textbf{then}\ \text{write 0 to its words; store the epoch as} \text{ its stamp}\quad \triangleright\ \text{release} \cr 6 & \qquad \textbf{if}\ W[ i ].\mathit{key} = 0\ \textbf{then} \cr 7 & \qquad\quad W[ i ].\mathit{value} \gets v;\ W[ i ].\mathit{key} \gets k\quad \triangleright\ \text{the key with release} \cr 8 & \qquad\quad n \gets n + 1;\ \textbf{return}\ ( v , \textbf{true} ) \cr 9 & \qquad \textbf{if}\ W[ i ].\mathit{key} = k\ \textbf{then} \ \textbf{return}\ ( W[ i ].\mathit{value} , \textbf{false} ) \cr 10 & \qquad i \gets ( i + 1 ) \bmod 2^l \cr 11 & \textbf{procedure}\ \mathrm{grow}() \cr 12 & \quad W' \gets \text{a vector of } 2^{l + 1} \text{ free places} \cr 13 & \quad \textbf{foreach}\ \text{pair } ( k , v ) \text{ of } W \ \textbf{do}\ \text{put it at the first free place of } k \text{ in } W' \cr 14 & \quad \text{keep } W \text{ for the readers};\ W \gets W'\quad \triangleright\ \text{release} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{find}( k , h ) \cr 2 & \quad \textbf{loop} \cr 3 & \qquad T \gets \text{the vector in use } W\quad \triangleright \ \text{acquire} \cr 4 & \qquad i \gets \lfloor h / 2^{64 - l} \rfloor \cr 5 & \qquad \textbf{while}\ \text{the group of } i \text{ is in use} \ \textbf{and}\ T[ i ].\mathit{key} \ne 0\ \textbf{do}\quad \triangleright\ \text{acquire} \cr 6 & \qquad\quad \textbf{if}\ T[ i ].\mathit{key} = k\ \textbf{then} \ \textbf{return}\ T[ i ].\mathit{value} \cr 7 & \qquad\quad i \gets ( i + 1 ) \bmod 2^l \cr 8 & \qquad \textbf{if}\ T \text{ is still the vector in use} \ \textbf{then return nil} \end{array} \]

Lemma 24.35. Let one thread make all the insertions, the updates and the growths of a SingleWriterFlatTable, and let any thread make lookups. Then (i) a lookup that reads a key word \(w \ne 0\) reads with it the value stored at its insertion or by a later update, and everything that the writer wrote before the insertion; (ii) a lookup of \(k\) that reads a free place of the vector \(T\) (or a group out of use) and then \(T\) again as the vector in use is linearized at that read, which no insertion of \(k\) happens before; (iii) a vector replaced by a growth is no longer written, and holds every pair inserted before the growth. Hence the lookups are wait-free between two growths and start over at most once per growth.

Proof. For (i), the store of the value and every earlier write of the writer are sequenced before the store of the key with release, which the load of the key with acquire synchronizes with; an update stores one atomic word with release, so that the value read is whole. For (ii), let the insertion of \(k\) into \(T\) write the place \(j\). The writer found full the places from that of \(k\) to \(j - 1\), renewing with EpochClear each group out of use among them (its words, then its stamp with release), and these writes are sequenced before the store of \(k\). If that store happened before the read of a place \(i < j\) of the sequence, the write of \(i\) (or of the stamp of its group) would happen before the read as well, and the coherence of the reads would forbid reading the free place. If \(k\) was inserted into a later vector, its store follows the store of that vector as the one in use, and if it happened before the read of \(i\), it would happen before the second read of the vector in use, which then could not read \(T\). For (iii), the writer writes only the vector in use, and the new one before it is published, after the copy has read every pair of the old one; the vectors replaced are freed only by clear() or by the destruction, which run with no reader. A lookup restarts only when it reads a vector other than the one it searched, i.e., once per growth. \(\square\)

The insertions of one writer thus cost the loads of their probe and one or two stores, against the two sequentially consistent read-modify-writes on the counter of a thread of ConcurrentFlatTable, which several writers need (Lemma 6 of the theory). The price is that the table has one writer: the threads of a search keep one table each, and a thread that looks for a state reads the table of the worker that may hold it.

A board of least keys. MinBoard< K > keeps \(p\) keys, one per thread, each in an atomic word on a line of cache of its own. publish( i , k ), called by the owner of the slot \(i\) only, reads the slot and stores \(k\) only if it differs, both relaxed; a worker whose key stays thus leaves its line shared in the caches of the readers. min() reads the \(p\) slots, relaxed, and returns the least key read. Its public members are

// declarations of <ADS/concurrent/MinBoard.h>
template< class K >
 requires( std::totally_ordered< K > && std::is_trivially_copyable_v< K > )
class MinBoard
{
 public:
 explicit MinBoard( std::size_t p , K k = std::numeric_limits< K >::max() );
 std::size_t size( void ) const;
 void publish( std::size_t i , K k );
 K at( std::size_t i ) const;
 K min( void ) const;
 void reset( K k = std::numeric_limits< K >::max() );
 };

Lemma 24.36. Let each slot of a MinBoard be written by its owner only. Then (i) a read of the slot \(i\) reads a key published there (or the initial one), not older in the order of the publishes of \(i\) than any publish of \(i\) that happens before the read, and two reads of \(i\) by one thread never read the second older than the first; (ii) min() returns \(\min_i x_i\) of keys \(x_i\) so read, one per slot, which need not be the least key of the board at any instant; (iii) if the keys published in each slot never increase, the value returned lies between the least key of the board at the end of the call and the least of the keys published before the call (those whose publish happens before it), and the values returned to one thread never increase.

Proof. (i) is the coherence of the atomic objects of C++, which holds for relaxed accesses, with the publishes of a slot made in the program order of its owner; a publish that skips its store finds the key already there, and leaves the slot as if it had stored it. (ii) holds since min() reads each slot once, at different times. For (iii), with the keys of each slot never increasing, a key read is at most the last one published before the call, by (i), and at least the key that the slot holds at the end of the call; the minimum over the slots keeps both bounds, and two calls by one thread read each slot in the order of its publishes. \(\square\)

The board orders nothing else: a thread that reads \(k\) in a slot learns nothing of the writes that the owner made before publishing \(k\), which need their own synchronization, and it uses the board as a bound only, e.g., the least \(f\) of the workers below which a search may prune. A publish costs a load of a line that the owner holds, and a store only when the key changes; min() costs \(p\) loads of lines that only their owners write.

24.14 Discussion and references

We follow the model of Herlihy and Shavit 2008, whose book covers linearizability (Herlihy and Wing 1990), the hierarchy of the progress conditions (Herlihy 1991), the locks that spin (Anderson 1990; Mellor-Crummey and Scott 1991) and the striping of locks. For the memory of C++ we follow Boehm and Adve 2008, and Williams 2019 explains it for the programmer, with the total order of the sequentially consistent operations and the fences.

We take the queue of one producer and one consumer from Lamport 1983, and its engineering for the caches from Lee et al. 2010 and from B-Queue (Wang et al. 2013). Our lanes of blocks recycled are those of the unbounded queues of FastFlow (Aldinucci et al. 2012), and the stack of the inbox is that of Treiber 1986. The bounded queue of many producers and consumers is that of Vyukov 2010, which Nikolaev 2019 made lock-free in the strict sense. Work stealing uses the deque of Chase and Lev 2005, with the orders of memory proved correct by Lê et al. 2013; the schedule of Blumofe and Leiserson 1999 rests on it. We take the union-find from Jayanti and Tarjan 2021, with the analysis of the sequential splitting of Tarjan and van Leeuwen 1984.

Among the hash tables, we built the cuckoo table after MemC3 (Fan et al. 2013) and the search in breadth of Li et al. 2014, with the seqlock analyzed by Boehm 2012. Our table of linear probing that grows follows the folklore table and the growth of Maier et al. 2019, who also compare the concurrent hash tables, among them those that grow without locks. The tables of open addressing without locks of Purcell and Harris 2005 also remove keys, at the price of a protocol of states per place. The phase-concurrent tables of Shun and Blelloch 2014 give deterministic contents by separating the phases of insertion and of lookup; the table of §24.8 does not need them, since its insertions of one key agree on the pair kept.

The MultiQueue is that of Rihani et al. 2015, with the engineering of Williams et al. 2021 (and the later account of Williams and Sanders 2025). Its rank errors are bounded by Alistarh et al. 2017 and, exactly in the sequential model, by Walzer and Williams 2025. For the event count we follow Reed and Kanodia 1979; the asymmetric fences are those of Ladan-Mozes et al. 2011. The priority queues that are stolen combine the steal of half of Hendler and Shavit 2002 with the receiver-initiated steals of Acar et al. 2013, which the laws of order of Attiya et al. 2011 motivate, and with the balancing of the best subproblems of the parallel branch-and-bound (Tschöke et al. 1995; Karp and Zhang 1993; Sanders 1998). Wimmer et al. 2014 and Postnikova et al. 2022 study other ways of stealing priority work. The exact queue without locks is that of Lindén and Jonsson 2013, on the skiplists of Pugh 1990 and the marked pointers of Harris 2001, after the queues of Lotan and Shavit 2000 and of Sundell and Tsigas 2005; its reclamation by epochs is that of Fraser 2004, compared with the hazard pointers and the other schemes by Hart et al. 2007. A comparison of these structures with those of other libraries (e.g., oneTBB, Folly, the queues of FastFlow) belongs to the benchmarks of appendix B, made on an idle machine, and it is not reported here.

24.15 Exercises

Each exercise names the test of the library that solves it (run it with ctest -R <name>).

  1. Realize a bounded queue between one producer thread and one consumer thread with no lock and no read-modify-write, and show that the copies of the indices kept by each thread never make an operation fail wrongly. Tests: engineered.spsc-queue, engineered_queues.spsc-queue-items.
  2. Realize an unbounded queue of many producers and one consumer in which the producers never write a common word, and bound the blocks that a lane keeps. Test: engineered_queues.mpsc-queue.
  3. Realize an inbox of many producers whose consumer takes all the messages by one atomic operation, in the order of sending of each producer, and explain why the ABA problem cannot occur. Test: engineered.mpsc-inbox.
  4. Realize a bounded queue of many producers and many consumers with one compare-and-swap per operation, and find the step at which a stopped thread holds up the others. Test: engineered_queues.mpmc-queue.
  5. Realize the deque of Chase and Lev, and show that with release and acquire only the owner and a thief may both take the last item. Test: engineered_queues.work-stealing-deque.
  6. Realize a union-find without locks whose labels are the least elements of the sets, whatever the order of the operations. Test: engineered_parallel.concurrent-union-find.
  7. Make a cuckoo table concurrent with one lock per region and lookups without locks under the versions of the regions, and prove that it cannot deadlock. Tests: engineered.concurrent-cuckoo, engineered.concurrent-cuckoo-threads.
  8. Realize a table of linear probing shared by threads that grows while they insert, with lookups that never wait, and with the pairs in the words, in places of two words, or in nodes. Tests: engineered.concurrent-flat-table, engineered.concurrent-flat-table-threads, engineered.concurrent-flat-table-words.
  9. Realize the MultiQueue with buffers, check that it is exact with one queue, and compare its mean rank error with (24.8). Tests: engineered_queues.multi-queue, engineered_queues.multi-queue-rank, engineered_queues.multi-queue-threads.
  10. Realize an event count with which no wake-up is lost, also with several notifiers at once. Tests: engineered_queues.event-count, engineered_queues.event-count-notifiers.
  11. Realize the exponential backoff of a waiting thread, and let four threads wait with it for a flag. Test: engineered_search.backoff-threads.
  12. Realize a priority queue whose owner pops in the exact order of its keys with no read-modify-write while thieves take half of its pairs, and keep the least bound of its pairs exact. Tests: engineered_queues.stealable-pq, engineered_queues.stealable-pq-threads, engineered_queues.stealable-pq-bound, engineered_queues.stealable-pq-bound-threads.
  13. Detect the end of a best-first search of \(p\) workers that steal from one another, also when it is stopped or a worker throws. Tests: engineered_runtime.stealing-frontier, engineered_runtime.stealing-frontier-stop, engineered_runtime.stealing-frontier-bound.
  14. Realize the skiplist of Lindén and Jonsson with its memory reclaimed by epochs, check that every pair comes out once with \(p\) threads, and find a linearization of short histories of the operations by the search of Wing and Gong. Tests: engineered_queues.lockfree-pq, engineered_queues.lockfree-pq-threads, engineered_queues.lockfree-pq-linearizable.