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
experiments.cpp
Makefile
peterson.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 always lock-free, but custom structs may not be.
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';
}

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
objects     = atomic.o acq-rel-1.o acq-rel-2.o experiments.o peterson.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 mutex;

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

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

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