COMS W4995 C++ Deep Dive for C Programmers

Index of 2026-9/code/19

Parent directory
acq-rel-1.cpp
acq-rel-2.cpp
atomic.cpp
concur.cpp
experiments.cpp
Makefile
peterson.cpp
sharedptr.cpp
spin-lock.cpp

acq-rel-1.cpp

#include <atomic>
#include <cassert>
#include <cstring>
#include <thread>

const char* HELLO = "Hello, World!";

const char* data;
std::atomic<bool> ready;

void producer() {
    data = HELLO;
    ready.store(true, std::memory_order_relaxed);
    // ready.store(true, std::memory_order_release);
}

void consumer() {
    // while (!ready.load(std::memory_order_acquire))
    while (!ready.load(std::memory_order_relaxed))
        ;

    assert(data == HELLO);
}

int main() {
    for (int i = 0; i < 1'000'000; ++i) {
        data = nullptr;
        ready = false;
        std::jthread t1(producer);
        std::jthread t2(consumer);
    }
}

acq-rel-2.cpp

#include <atomic>
#include <cassert>
#include <string>
#include <thread>

std::atomic<uint64_t> x{0};
std::atomic<uint64_t> y{0};

void producer() {
    for (size_t i = 0; i < 1000'000'000; ++i) {
        x.fetch_add(1, std::memory_order_relaxed);
        y.fetch_add(1, std::memory_order_relaxed);

        //y.fetch_add(1, std::memory_order_release);
    }
}

void consumer() {
    for (size_t i = 0; i < 1000'000'000; ++i) {
        //uint64_t yy = y.load(std::memory_order_acquire);

        uint64_t yy = y.load(std::memory_order_relaxed);
        uint64_t xx = x.load(std::memory_order_relaxed);

        assert(xx >= yy);
    }
}

int main() {
    std::jthread t1(producer);
    std::jthread t2(consumer);
}

atomic.cpp

#include <iostream>
#include <chrono>
#include <thread>
#include <atomic>

using namespace std;
using namespace std::chrono;

struct wallet {
    std::atomic<uint64_t> money {0};
    operator uint64_t() const {
        return money;
        // return money.load(std::memory_order_relaxed);
    }

    wallet& operator++() {
        ++money;
        // money.fetch_add(1, std::memory_order_relaxed);
        return *this;
    }
};

// Built-in types are lock-free on most systems.
static_assert(atomic<uint64_t>::is_always_lock_free);

void f(wallet& sum, uint64_t count) {
    while (count--) {
        ++sum;
    }
}

int main() {
    constexpr uint64_t count = 1'000'000;
    wallet sum;

    auto time0 = high_resolution_clock::now();

    {
        jthread t1 { f, ref(sum), count };
        jthread t2 { f, ref(sum), count };
    }

    auto time1 = high_resolution_clock::now();
    auto dt = duration_cast<microseconds>(time1 - time0);
    cout << "elapsed: " << dt.count() << " microsec\n";
    cout << "result: " << sum << '\n';
}

concur.cpp

#include <iostream>
#include <chrono>
#include <thread>
#include <mutex>

using namespace std;
using namespace std::chrono;

struct wallet {
    mutex m;
    uint64_t money = 0;
    operator uint64_t() const { return money; }

    wallet& operator++() {
        {
            scoped_lock lck{m};
            ++money;
        }

        return *this;
    }
};

void f(wallet& sum, uint64_t count) {
    while (count--) {
        ++sum;
    }
}

int main() {
    constexpr uint64_t count = 1'000'000;
    wallet sum;

    auto time0 = high_resolution_clock::now();

    {
        jthread t1 { f, ref(sum), count };
        jthread t2 { f, ref(sum), count };
    }

    auto time1 = high_resolution_clock::now();
    auto dt = duration_cast<microseconds>(time1 - time0);
    cout << "elapsed: " << dt.count() << " microsec\n";
    cout << "result: " << sum << '\n';
}

experiments.cpp

#include <atomic>
#include <barrier>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <thread>

#if 0
constexpr uint64_t THRESHOLD = 1'000'000;
constexpr size_t ITERATIONS = 500'000;
std::barrier<> trial_barrier{5};
std::atomic<bool> start{false};

alignas(256) std::atomic<uint64_t> x1{0};
alignas(256) std::atomic<uint64_t> x2{0};
alignas(256) std::atomic<uint64_t> z1{0};
alignas(256) std::atomic<uint64_t> z2{0};

uint64_t observed_by_1 = 0;
uint64_t observed_by_2 = 0;

void wait_for_start() {
    while (!start.load(std::memory_order_acquire)) {
        std::this_thread::yield();
    }
}

void producer1() {
    for (size_t iteration = 0; iteration < ITERATIONS; ++iteration) {
        trial_barrier.arrive_and_wait();
        for (size_t i = 0; i < THRESHOLD; ++i) {
            x1.fetch_add(1, std::memory_order_relaxed);
            z1.fetch_add(1, std::memory_order_release);
        }
        trial_barrier.arrive_and_wait();
    }
}

void producer2() {
    for (size_t iteration = 0; iteration < ITERATIONS; ++iteration) {
        trial_barrier.arrive_and_wait();
        for (size_t i = 0; i < THRESHOLD; ++i) {
            x2.fetch_add(1, std::memory_order_relaxed);
            z2.fetch_add(1, std::memory_order_release);
        }
        trial_barrier.arrive_and_wait();
    }
}

void consumer1() {
    wait_for_start();
    for (size_t i = 0; i < THRESHOLD; ++i) {
        uint64_t zz = z1.load(std::memory_order_acquire);
        uint64_t xx = x1.load(std::memory_order_relaxed);

        /* assert((xx - zz) < 4000); */
        assert(xx >= zz);
    }
}

void consumer2() {
    wait_for_start();
    for (size_t i = 0; i < THRESHOLD; ++i) {
        uint64_t zz = z2.load(std::memory_order_acquire);
        uint64_t xx = x2.load(std::memory_order_relaxed);

        /* assert((xx - zz) < 4000); */
        assert(xx >= zz);
    }
}

void observer1() {
    for (size_t iteration = 0; iteration < ITERATIONS; ++iteration) {
        trial_barrier.arrive_and_wait();
        for (;;) {
            uint64_t r1 = z1.load(std::memory_order_acquire);

            if (r1 >= THRESHOLD) {
                observed_by_1 = z2.load(std::memory_order_acquire);
                break;
            }
        }
        trial_barrier.arrive_and_wait();
    }
}

void observer2() {
    for (size_t iteration = 0; iteration < ITERATIONS; ++iteration) {
        trial_barrier.arrive_and_wait();
        for (;;) {
            uint64_t r2 = z2.load(std::memory_order_acquire);

            if (r2 >= THRESHOLD) {
                observed_by_2 = z1.load(std::memory_order_acquire);
                break;
            }
        }
        trial_barrier.arrive_and_wait();
    }
}


int main() {
    std::cout << "&x1: " << (void*) &x1 << '\n';
    std::cout << "&x2: " << (void*) &x2 << '\n';
    std::cout << "&z1: " << (void*) &z1 << '\n';
    std::cout << "&z2: " << (void*) &z2 << '\n';
    std::thread t1(producer1);
    std::thread t2(producer2);
    std::thread t3(observer1);
    std::thread t4(observer2);

    for (size_t iteration = 0; iteration < ITERATIONS; ++iteration) {
        x1.store(0, std::memory_order_relaxed);
        x2.store(0, std::memory_order_relaxed);
        z1.store(0, std::memory_order_relaxed);
        z2.store(0, std::memory_order_relaxed);

        trial_barrier.arrive_and_wait();
        trial_barrier.arrive_and_wait();

        assert(observed_by_1 == THRESHOLD || observed_by_2 == THRESHOLD);
    }

    t1.join();
    t2.join();
    t3.join();
    t4.join();
}
#endif

constexpr size_t ITERATIONS = 1'000'000;
std::barrier trial_barrier{3};
alignas(256) std::atomic<int> x{0};
alignas(256) std::atomic<int> y{0};
int r1 = -1;
int r2 = -1;

void precreated_thread1()
{
    for (size_t i = 0; i < ITERATIONS; ++i) {
        trial_barrier.arrive_and_wait();
        x.store(1, std::memory_order_relaxed);
        r1 = y.load(std::memory_order_relaxed);
        trial_barrier.arrive_and_wait();
    }
}

void precreated_thread2()
{
    for (size_t i = 0; i < ITERATIONS; ++i) {
        trial_barrier.arrive_and_wait();
        y.store(1, std::memory_order_relaxed);
        r2 = x.load(std::memory_order_relaxed);
        trial_barrier.arrive_and_wait();
    }
}

void run_precreated_threads()
{
    std::thread t1(precreated_thread1);
    std::thread t2(precreated_thread2);

    for (size_t i = 0; i < ITERATIONS; ++i) {
        x.store(0, std::memory_order_relaxed);
        y.store(0, std::memory_order_relaxed);
        r1 = r2 = -1;
        trial_barrier.arrive_and_wait();
        trial_barrier.arrive_and_wait();
        assert(r1 != -1 && r2 != -1);
        assert(r1 != 0 || r2 != 0);
    }

    t1.join();
    t2.join();
}

// ----------------------------------------

void run_create_and_join_each_iteration()
{
    std::atomic<int> local_x{0};
    std::atomic<int> local_y{0};

    for (size_t i = 0; i < ITERATIONS; ++i) {
        int local_r1 = -1;
        int local_r2 = -1;

        local_x.store(0, std::memory_order_relaxed);
        local_y.store(0, std::memory_order_relaxed);

        std::thread t1([&] {
            local_x.store(1, std::memory_order_release);
            local_r1 = local_y.load(std::memory_order_acquire);
        });
        std::thread t2([&] {
            local_y.store(1, std::memory_order_release);
            local_r2 = local_x.load(std::memory_order_acquire);
        });

        t1.join();
        t2.join();

        assert(local_r1 != 0 || local_r2 != 0);
    }
}

void run_seq_cst_store_buffering()
{
    for (size_t i = 0; i < ITERATIONS; ++i) {
        alignas(256) std::atomic<bool> local_x{false};
        alignas(256) std::atomic<bool> local_y{false};
        alignas(256) std::atomic<int> local_z{0};

        std::thread a([&] {
            local_x.store(true, std::memory_order_relaxed);
        });
        std::thread b([&] {
            local_y.store(true, std::memory_order_relaxed);
        });
        std::thread c([&] {
            while (!local_x.load(std::memory_order_relaxed))
                ;
            if (local_y.load(std::memory_order_relaxed))
                ++local_z;
        });
        std::thread d([&] {
            while (!local_y.load(std::memory_order_relaxed))
                ;
            if (local_x.load(std::memory_order_relaxed))
                ++local_z;
        });

        a.join();
        b.join();
        c.join();
        d.join();
        assert(local_z.load(std::memory_order_seq_cst) != 0);
    }
}

void run_seq_cst_store_buffering_precreated()
{
    alignas(256) std::atomic<bool> local_x{false};
    alignas(256) std::atomic<bool> local_y{false};
    alignas(256) std::atomic<int> local_z{0};
    std::barrier sync{5};

    std::thread a([&] {
        for (size_t i = 0; i < ITERATIONS; ++i) {
            sync.arrive_and_wait();
            local_x.store(true, std::memory_order_release);
            sync.arrive_and_wait();
        }
    });
    std::thread b([&] {
        for (size_t i = 0; i < ITERATIONS; ++i) {
            sync.arrive_and_wait();
            local_y.store(true, std::memory_order_release);
            sync.arrive_and_wait();
        }
    });
    std::thread c([&] {
        for (size_t i = 0; i < ITERATIONS; ++i) {
            sync.arrive_and_wait();
            while (!local_x.load(std::memory_order_acquire))
                ;
            if (local_y.load(std::memory_order_acquire))
                ++local_z;
            sync.arrive_and_wait();
        }
    });
    std::thread d([&] {
        for (size_t i = 0; i < ITERATIONS; ++i) {
            sync.arrive_and_wait();
            while (!local_y.load(std::memory_order_acquire))
                ;
            if (local_x.load(std::memory_order_acquire))
                ++local_z;
            sync.arrive_and_wait();
        }
    });

    for (size_t i = 0; i < ITERATIONS; ++i) {
        local_x = false;
        local_y = false;
        local_z = 0; 
        sync.arrive_and_wait();
        // std::this_thread::sleep_for(std::chrono::milliseconds(500));
        sync.arrive_and_wait();
        // std::cout << "z: " << local_z.load(std::memory_order_seq_cst) << '\n';
        assert(local_z.load(std::memory_order_seq_cst) != 0);
    }

    a.join();
    b.join();
    c.join();
    d.join();
}

int main()
{
    // run_precreated_threads();
    // run_create_and_join_each_iteration();
    // run_seq_cst_store_buffering();
    run_seq_cst_store_buffering_precreated();
}


/*

~EXPERIMENTS~

1. Dekker -- no barrier, thread creation in loop
   run_create_and_join_each_iteration()
    * relaxed: trips on O0 & O1
    * rel_acq: passes on O0 & trips on O1 (even with no alignment)
        * according to gemini O0 produces LDAR and and O1 produces LDAPR. they
        * map to seq_cst and acquire in C++.
    * seq_cst: passes on O0 & O1 (even O3, even with no alignment)


2. IRIW (cppreference) -- no barrier, thread creation in loop
   run_seq_cst_store_buffering()
    * relaxed: Passes on O3 (even with alignment)

3. IRIW (cppreference) -- barriers & pre-created threads
   run_seq_cst_store_buffering_precreated()
    * relaxed: trips consistently at O0, but inconsistently at O1,O2,O3.
        * chatgpt notes that O0 calls go through library, O1 is inline
    * rel_acq: passes on O0 & 03 (even with alignment)


4. Increment Threshold (variant of IRIW)

*/

Makefile

CC       = g++
CXX      = g++

CXXFLAGS = -Wall -g -std=c++20 -pthread -O3
LDFLAGS  = -pthread

executables = atomic   acq-rel-1   acq-rel-2   experiments   peterson   spin-lock   sharedptr   concur
objects     = atomic.o acq-rel-1.o acq-rel-2.o experiments.o peterson.o spin-lock.o sharedptr.o concur.o

.PHONY: default
default: $(executables)

$(executables):

$(objects):

.PHONY: clean
clean:
	rm -f a.out core $(executables) $(objects)

.PHONY: all
all: clean default

peterson.cpp

#include <iostream>
#include <chrono>
#include <thread>
#include <atomic>
using namespace std;
using namespace std::chrono;

struct peterson_lock {
    std::atomic<bool> flag[2] = {false, false};
    std::atomic<int> turn = 0;

    void lock(int self) {
        int other = 1 - self;
        // Declare my intent
        flag[self].store(true, std::memory_order_seq_cst);
        // Yield to other thread
        turn.store(other, std::memory_order_seq_cst);
        // Wait if the other thread has intent and it's their turn
        while (flag[other].load(std::memory_order_seq_cst) &&
               turn.load(std::memory_order_seq_cst) == other)
            ;
    }

    void unlock(int self) {
        // Release my intent
        flag[self].store(false, std::memory_order_seq_cst);
    }
};

int main() {
    uint64_t counter = 0;
    peterson_lock mtx;

    auto f = [&](int id) {
        for (uint64_t i = 0; i < 1'000'000; ++i) {
            mtx.lock(id);
            ++counter;
            mtx.unlock(id);
        }
    };

    {
        jthread t0 { f, 0 };  // self=0, other=1
        jthread t1 { f, 1 };  // self=1, other=0
    }

    cout << "result: " << counter << '\n';
}

sharedptr.cpp

#include <atomic>
#include <string>
#include <thread>
#include <cassert>
#include <iostream>
using namespace std;

/* SharedPtr changes
- atomic<int>* count
- no count if ptr is nullptr -> need null checks
    - we did this so move could be noexcept. in general move should be noexcept,
      and just in case thread uses move_ifnoexcept
- detach() factored out & release() so we dont have to assign to empty ptr
- added move so that thread doesnt hold a copy after passing it to functor
- relaxed inc and get_count() because no publishing

*/

template <typename T>
class SharedPtr {
public:
    explicit SharedPtr(T* p = nullptr)
        : ptr{p}, count{p ? new std::atomic<int>{1} : nullptr} {}
    ~SharedPtr() { detach(); }

    // Copy constructor and assignment
    SharedPtr(const SharedPtr<T>& sp) : ptr(sp.ptr), count(sp.count) {
        if (count) count->fetch_add(1, std::memory_order_relaxed);
    }
    SharedPtr<T>& operator=(const SharedPtr<T>& sp) {
        if (this != &sp) {
            // first, detach.
            detach();
            // attach to the new object.
            ptr = sp.ptr;
            count = sp.count;
            if (count) count->fetch_add(1, std::memory_order_relaxed);
        }
        return *this;
    }

    // Move constructor and assignment
    SharedPtr(SharedPtr<T>&& sp) noexcept : ptr(sp.ptr), count(sp.count) {
        sp.ptr = nullptr;
        sp.count = nullptr;
    }
    SharedPtr<T>& operator=(SharedPtr<T>&& sp) noexcept {
        if (this != &sp) {
            // first, detach.
            detach();
            // attach to the new object.
            ptr = sp.ptr;
            count = sp.count;
            sp.ptr = nullptr;
            sp.count = nullptr;
        }
        return *this;
    }

    void release() {
        detach();
        ptr = nullptr;
        count = nullptr;
    }

    T& operator*() const { return *ptr; }
    T* operator->() const { return ptr; }

    operator void*() const { return ptr; } // enables "if (sp) ..."
    T* get_ptr() const { return ptr; } // access to underlying ptr

    // access to reference count
    int get_count() const { 
        return count ? count->load(std::memory_order_relaxed) : 0;
    }

private:
    void detach() {
        // if (count && count->fetch_sub(1, std::memory_order_acq_rel) == 1) {
        if (count && count->fetch_sub(1, std::memory_order_relaxed) == 1) {
            delete ptr;
            delete count;
        }
    }

    T* ptr;                   // the underlying pointer
    std::atomic<int>* count;  // the reference count
};

struct X {
    int x;
    
    X() : x{0} {}
    // X should be mutated before destruction
    ~X() { assert(x == 42); }

    void mutate() { x = 42; }

    // Copy and move not needed for this demo 
    X(const X&) = delete;
    X& operator=(const X&) = delete;
    X(X&&) = delete;
    X& operator=(X&&) = delete;
};

int main() {
    for (int i = 0; i < 100'000'000; ++i) {
        SharedPtr<X> sp { new X{} };

        std::jthread t1(
            [](SharedPtr<X> sp1) {
                assert(sp1.get_count() <= 2);

                sp1->mutate();
                sp1.release();
            },
            sp);

        std::jthread t2(
            [](SharedPtr<X> sp2) {
                assert(sp2.get_count() <= 2);

                sp2.release();
            },
            std::move(sp));
    }
}

spin-lock.cpp

#include <iostream>
#include <chrono>
#include <thread>
#include <atomic>
using namespace std;
using namespace std::chrono;

struct spin_lock {
    std::atomic_flag flag;

    void lock() {
        while (flag.test_and_set(std::memory_order_acquire))
            ;
    }

    void unlock() {
        flag.clear(std::memory_order_release);
    }
};

int main() {
    uint64_t counter = 0;
    spin_lock mtx;

    auto f = [&]() {
        for (uint64_t i = 0; i < 1'000'000'000; ++i) {
            mtx.lock();
            ++counter;
            mtx.unlock();
        }
    };

    {
        jthread t0 { f };
        jthread t1 { f };
    }

    cout << "result: " << counter << '\n';
}