tf::NonblockingNotifier class

class to create a non-blocking notifier

A non-blocking notifier enables threads to wait for user-defined predicates without blocking locks or protecting the predicate with a mutex. Conceptually, it is similar to a condition variable, but the wait predicate is evaluated optimistically and does not require mutual exclusion.

A waiting thread follows this pattern:

wid = this_waiter_id();
if (predicate) {
  return act();
}
notifier.prepare_wait(wid);    // enter the two-phase wait protocol
if (predicate) {
  notifier.cancel_wait(wid);
  return act();
}
notifier.commit_wait(&w);      // park (e.g., preempted by OS until notified)

A notifying thread performs:

wid = this_notifier_id;
predicate = true;
notifier.notify_one(wid);

The notify operation is inexpensive when no threads are waiting. The prepare_wait and commit_wait operations are more costly, but they are only executed when the initial predicate check fails. The flow diagram for notifier and waiter is shown below:

The synchronization algorithm relies on two shared variables: a user-defined predicate and an internal state variable. To avoid lost wake-ups, the protocol follows a two-phase update-then-check pattern. A waiting thread publishes its intent to wait by updating the state before rechecking the predicate. Conversely, a notifying thread updates the predicate before inspecting the state. This interaction is governed by a memory barrier of sequential consistency that guarantees at least one thread will observe the other's progress. Consequently, the waiter either detects the work and stays active, or the notifier detects the waiter and issues a wakeup. It is impossible for both threads to miss each other's updates.

The state has the following layout, which consists of the following three parts:

STACK_BITS is a stack of committed waiters
PREWAITER_BITS is the count of waiters in the pre-waiting stage
EPOCH_BITS is the modification counter

Reference: https://gitlab.com/libeigen/eigen/-/blob/master/Eigen/src/ThreadPool/EventCount.h

Public static variables

static const uint64_t STACK_BITS: Number of bits used to encode the waiter stack index.
static const uint64_t STACK_MASK: Bit mask for extracting the waiter stack index.
static const uint64_t PREWAITER_BITS: Number of bits used to encode the pre-waiter ticket.
static const uint64_t PREWAITER_SHIFT: Bit shift of the pre-waiter ticket field.
static const uint64_t PREWAITER_MASK: Bit mask for extracting the pre-waiter ticket field.
static const uint64_t PREWAITER_INC: Increment value for advancing the pre-waiter ticket.
static const uint64_t EPOCH_BITS: Number of bits used to encode the epoch counter.
static const uint64_t EPOCH_SHIFT: Bit shift of the epoch field.
static const uint64_t EPOCH_MASK: Bit mask for extracting the epoch field.
static const uint64_t EPOCH_INC: Increment value for advancing the epoch counter.

Constructors, destructors, conversion operators

NonblockingNotifier(size_t N) explicit: constructs a notifier with N waiters
~NonblockingNotifier(): destructs the notifier

Public functions

auto num_waiters() const -> size_t: returns the number of committed waiters
auto capacity() const -> size_t: returns the maximum number of waiters supported by this notifier
void prepare_wait(size_t wid): prepares the calling thread to enter the waiting set
void commit_wait(size_t wid): commits a previously prepared wait operation
void cancel_wait(size_t wid): cancels a previously prepared wait operation
void notify_one(): notifies one waiter from the waiting set
void notify_all(): notifies all waiter from the waiting set
void notify_n(size_t n): notifies up to n waiters from the waiting set
auto size() const -> size_t: returns the number of waiters supported by this notifier

Function documentation

tf::NonblockingNotifier::NonblockingNotifier(size_t N) explicit

constructs a notifier with N waiters

Parameters
N	number of waiters

Constructs a notifier that supports up to N waiters. The maximum allowable number of waiters can be acquired by calling capacity(), which is equal to 2^STACK_BITS.

size_t tf::NonblockingNotifier::num_waiters() const

returns the number of committed waiters

Returns	the number of committed waiters at the time of the call.

A committed waiter is a thread that has completed the pre-waiting stage and is fully registered in the waiting set via commit_wait().

size_t tf::NonblockingNotifier::capacity() const

returns the maximum number of waiters supported by this notifier

The maximum number of waiters supported by this non-blocking notifier is equal to 2^STACK_BITS.

void tf::NonblockingNotifier::prepare_wait(size_t wid)

prepares the calling thread to enter the waiting set

Parameters
wid	identifier of the calling thread in the range of `[0, N)`, where `N` represents the number of waiters used to construct this notifier

This function places the thread into the pre-waiting stage. After calling prepare_wait(), the thread must re-check the wait predicate and then complete the protocol by calling either commit_wait() or cancel_wait() with the same waiter identifier.

A thread in the pre-waiting stage is not yet considered a committed waiter, and its waiting status is considered incomplete. Failing to follow prepare_wait() with exactly one call to commit_wait() or cancel_wait() results in undefined behavior.

void tf::NonblockingNotifier::commit_wait(size_t wid)

commits a previously prepared wait operation

Parameters
wid	identifier of the calling thread in the range of `[0, N)`, where `N` represents the number of waiters used to construct this notifier

This function completes the waiting protocol for a thread that has previously called prepare_wait(). Upon successful completion, the thread becomes a committed waiter and will park until being notified.

The thread must have re-checked the wait predicate before calling commit_wait(). Once committed, the thread may be awakened by notify_one(), notify_n(), or notify_all().

Each call to prepare_wait() must be followed by exactly one call to either commit_wait() or cancel_wait() using the same thread identifier.

void tf::NonblockingNotifier::cancel_wait(size_t wid)

cancels a previously prepared wait operation

Parameters
wid	identifier of the calling thread in the range of `[0, N)`, where `N` represents the number of waiters used to construct this notifier

This function aborts the waiting protocol for a thread that has previously called prepare_wait(). After cancellation, the thread does not become a committed waiter and will return to user-side control.

cancel_wait() must be called after the wait predicate has been re-checked and found to be false. This allows a thread to safely abandon waiting without blocking or being notified.

Each call to prepare_wait() must be followed by exactly one call to either commit_wait() or cancel_wait() using the same thread identifier.

void tf::NonblockingNotifier::notify_one()

notifies one waiter from the waiting set

Wakes up one waiter from the waiting set, including those in the pre-waiting stage.

The function is cheap when no threads are waiting.

void tf::NonblockingNotifier::notify_all()

notifies all waiter from the waiting set

Wakes up all waiters from the waiting set, including those in the pre-waiting stage.

The function is cheap when no threads are waiting.

void tf::NonblockingNotifier::notify_n(size_t n)

notifies up to n waiters from the waiting set

Parameters
n	maximum number of waiters to notify

Wakes up at most n waiters from the waiting set. If n is greater than or equal to the maximum number of waiters in this notifier, this function behaves identically to notify_all().

The function is cheap when no threads are waiting.

size_t tf::NonblockingNotifier::size() const

returns the number of waiters supported by this notifier

Returns	the number of waiters supported by this notifier

The size of a notifier is equal to the number used to construct that notifier.