• Not sure if to do lock-free or lock. Maybe locks are simpler for now?

Related material

• Anthony Williams C++ concurrency in action
• C++ con talks that you liked
• Quasar’s writeup

Lock

#include <mutex>
#include <condition_variable>
#include <optional>
#include <vector>

template<typename T>
class LockedQueue {
    std::vector<T> buf;
    size_t head = 0, tail = 0, sz = 0;
    std::mutex mtx;
    std::condition_variable cv;

public:
    explicit LockedQueue(size_t cap) : buf(cap) {}

    bool push(T val) {
        std::unique_lock lock(mtx);
        if (sz == buf.size()) return false;
        buf[tail] = std::move(val);
        tail = (tail + 1) % buf.size();
        ++sz;
        cv.notify_one();
        return true;
    }

    std::optional<T> pop() {
        std::unique_lock lock(mtx);
        cv.wait(lock, [this] { return sz > 0; });
        T val = std::move(buf[head]);
        head = (head + 1) % buf.size();
        --sz;
        return val;
    }
};

Lock-free

• be careful of aba problem
  1. Thread 1 reads ptr P as A
  2. Thread 2 changes P from A → B → A
  3. Thread 1’s CAS succeeds because P == A, but the state changed underneath
• in this case lock-free is actually quite trivial but is the perf return there?

changed.

#include <atomic>
#include <vector>
#include <optional>

template<typename T>
class LockFreeQueue {
    struct alignas(64) Slot {
        T val;
        std::atomic<bool> ready{false};
    };

    std::vector<Slot> buf;
    alignas(64) std::atomic<size_t> head{0};
    alignas(64) std::atomic<size_t> tail{0};

public:
    explicit LockFreeQueue(size_t cap) : buf(cap) {}

    bool push(T val) {
        size_t t = tail.load(std::memory_order_relaxed);
        size_t next = (t + 1) % buf.size();

        if (next == head.load(std::memory_order_acquire))
            return false;

        buf[t].val = std::move(val);
        buf[t].ready.store(true, std::memory_order_release);
        tail.store(next, std::memory_order_release);
        return true;
    }

    std::optional<T> pop() {
        size_t h = head.load(std::memory_order_relaxed);

        if (!buf[h].ready.load(std::memory_order_acquire))
            return std::nullopt;

        T val = std::move(buf[h].val);
        buf[h].ready.store(false, std::memory_order_release);
        head.store((h + 1) % buf.size(), std::memory_order_release);
        return val;
    }
};