C++ slim condition notifier

Question

When writing multi-threading code, one often need the thread to wait for some condition being met. A naive approach would look like this:

std::atomic_bool is_lifted;

...

//waiting for it being lifted
while (false == is_lifted.load())
    std::this_thread::yield();

This code is suboptimal, as the busy waiting loop wastes CPU power. Nonetheless, it has several benefits:

• It is simple and easy to comprehend.
• The writer side does not need to do any extra job to notify the reader.
• It has very small memory footprint.

Edit1[[----------------

Since C++20, the code can be easily improved using the std::atomic::wait/notify_* functions:

std::atomic_bool is_lifted;

...

//writer
is_lifted.store(true);
is_lifted.notify_all();

...

//reader
//waiting for it being lifted
is_lifted.wait(false);

Usually std::atomic::notify_* implementations are smart to avoid syscall'ing to the kernel if there are no waiters, however the cost is not negligible. In Windows10+VS2022, one notify function call (no waiter) costs ~50 instructions. If you use Windows7, since there is no WaitOnAddress/WakeByAddressXxx, it costs even more.

A common solution to cut this cost off is to store waiting status alongside the condition var, like this one: https://github.com/microsoft/STL/blob/2261f7edb760eb3fe0726187c818b796dc7ea798/stl/inc/semaphore#L207

As a practice to this approach,

----------------]]End Edit1

As a practice for the C++20 atomic::wait/notify_* functions, I wrote a small class to address the waiting performance issue of the busy waiting version, while keep its benefits as much as possible:

• easy to use
• writer do notify only when necessary
• small memory footprint

Here's the code:

class condition_notifier
{
    using uchar = unsigned char;

    static constexpr uchar set_bit = 1;
    static constexpr uchar set_unmask = (uchar)~(unsigned)set_bit;
    static constexpr uchar wait_bit = 2;
    static constexpr uchar wait_unmask = (uchar)~(unsigned)wait_bit;

    //Possible states:
    //unset and no waiter
    static constexpr uchar unset_nowait = 0;
    //set and no waiter
    static constexpr uchar set_nowait = set_bit;
    //unset and waiting
    static constexpr uchar unset_wait = wait_bit;
    //set and canceled wait, should be treated like `set_nowait`
    static constexpr uchar set_cwait = (uchar)((unsigned)set_bit) | ((unsigned)wait_bit);

    std::atomic_uchar atomic_state{ unset_nowait };
public:
    bool is_set(std::memory_order morder = std::memory_order_relaxed) noexcept
    {
        return atomic_state.load(morder) & set_bit;
    }
    void reset(std::memory_order morder = std::memory_order_relaxed) noexcept
    {
        atomic_state.fetch_and(set_unmask, morder);
        //0 -> 0: still unset
        //1 -> 0: resetted
        //2 -> 2: still waiting
        //3 -> 2: set_cwait -> unset_wait, unfortunate but rare and acceptable, see the comment in `wait()`
    }
    void set(std::memory_order morder = std::memory_order_release) noexcept
    {
        uchar old_state = atomic_state.exchange(set_nowait, morder);
        if (old_state == unset_wait)
        {
            atomic_state.notify_all();
        }
    }
    void wait(std::memory_order morder = std::memory_order_acquire) noexcept
    {
        for (;;)
        {
            uchar state = atomic_state.load(morder);
            if (state & (unsigned)set_bit)
                return;
            assert(state == unset_nowait || state == unset_wait);
            if (state == unset_nowait)
            {
                state = atomic_state.fetch_or(wait_bit, morder);
                //0 -> 2: unset, waiting registered
                //1 -> 3: set, waiting canceled
                //2 -> 2: unset, mutiple waiters
                //3 -> 3: set, waiting (multi-)canceled

                if (state == set_nowait)
                {
                    //reset the wait bit
                    //This should prevent bogus `unset_wait` state
                    //  and save a `notify_all()` call, most of the time.
                    uchar bad_state = set_cwait;
                    atomic_state.compare_exchange_strong(bad_state, set_nowait);
                    return;
                }
                if (state == set_cwait)
                {
                    //the one who set the wait bit would reset it
                    return;
                }
            }
            atomic_state.wait(unset_wait, std::memory_order_relaxed);
        }
    }
};


int main()
{
    condition_notifier cond_noti;
    auto wait_func = [&](int thread_id)
    {
        std::printf("thread %d: spin and check\n", thread_id);
        for (int i = 0; i < 256; ++i)
        {
            if (cond_noti.is_set())
                return;
            _mm_pause();
        }

        std::printf("thread %d: yield and check\n", thread_id);
        for (int i = 0; i < 4; ++i)
        {
            if (cond_noti.is_set())
                return;
            std::this_thread::yield();
        }

        std::printf("thread %d: block and waiting for notification\n", thread_id);
        cond_noti.wait();

        std::printf("thread %d: wait success\n", thread_id);
    };

    std::thread thread1{ wait_func, 1 };
    std::thread thread2{ wait_func, 2 };

    using namespace std::chrono_literals;
    std::this_thread::sleep_for(5s);

    cond_noti.set();
    thread1.join();
    thread2.join();
    std::puts("threads returned");

    return 0;
}

I want to know is there any bug in it, and anything to be improved.

Answer 1

It's unclear what this does

I had a hard time understanding this code. If I understand it correctly: wait() waits until the set_bit has been set at any time since the start of the call to wait(). However, when it returns it might be unset again. However, if something set and reset your condition_notifier before the call to wait(), this is not seen. You also can only wait for it to be set, you can't wait for a condition_notifier to become unset.

For a one-shot use of the condition_notifier like in your example main(), this is all fine. However, it looks like you can set and reset multiple times, but that is probably unsafe unless you use other synchronization primitives as well. It's for this reason that std::condition_variable can only be used in conjuction with a std::mutex.

The only advantage I see is that it avoids unnecessary calls to notify_all().

Simplify

The use-case you've shown is similar to that of a std::latch. While that type is bigger than a single char, you could take inspiration from its interface. Consider:

class condition_notifier
{
    …
public:
    condition_notifier(); // constructor, initializes into unset state
    void set();           // set and notify all waiters
    void wait();          // wait for the state to be set
};

Smaller might not be better

If you have lots and lots of condition_notifier variables, then it might make sense to keep them small. But that probably also implies that you have lots of threads notifying then and waiting on them. Please keep in mind that:

• Sharing multiple atomic variables in the same cache line can make atomic operations quite inefficient. To avoid that, you'd have to ensure they are aligned to std::hardware_destructive_interference_size (typically 64 bytes).
• The futex operations used to wait and notify waiters work only on 32-bit values (at least on Linux). This means that you might cause a lot of unnecessary wakeups, unless you ensure your condition_notifier variables are also aligned to at least 4 bytes.