More C++ Idioms/Thread-safe Copy-on-write

Thread-safe Copy-on-write

edit

Intent

edit

Allow objects to be quickly accessed in a concurrent safe manner without necessary copying, preferably without locks.

Also Known As

edit

Motivation

edit

Many applications allow for configuration changes in runtime but concurrently applying changes to the system requires fast synchronization primitives. Ubiquitous mutual exclusion that might block the executing thread is not a viable solution for latency sensitive applications like game engines. This idiom is an alternative to popular mutual exclusion in situation where reads are common and writes are rare. The reading path is fast and never blocks but incremental writes might require mutual exclusion.

Solution and Sample Code

edit
#pragma once

#include <atomic>
#include <memory>
#include <folly/concurrency/AtomicSharedPtr.h>

template <typename ValT, typename KeyT>
class ThreadSafeCowPtr {
public:
    using DataT = std::unordered_map<KeyT, ValT>;

    ThreadSafeCowPtr() : data{std::make_shared<DataT>()} {
        assert(data.is_lock_free());
    }   

    std::shared_ptr<DataT> read() {
        return data.load();
    }   

    void write(std::shared_ptr<DataT> new_ptr) {
        // does not require mutex if we don't care about previous content
        data.store(new_ptr);
    }   

    // Copy on write
    void update(const KeyT& key, const ValT& val) {
        // note that update() operation requires mutex to guarantee that
        // multiple threads calling update() won't drop any data
        std::lock_guard<std::mutex> lock(update_mut);
        auto new_ptr = std::make_shared<DataT>(*this->read()); // assume valid
        new_ptr->emplace(key, val);
        this->write(new_ptr);
    }   

    private:
    std::mutex update_mut;
    folly::atomic_shared_ptr<DataT> data;
};

Details

edit

This implementation relies on a fact that library folly provides lock free atomic shared pointer. Not all libraries provide lock free smart pointer, even if atomic specialization is available. Namely c++ standard library does not provide lock free atomic pointers[1]. Following code would not evaluate to true.

std::shared_ptr<int> obj;
assert(std::atomic(obj).is_lock_free()); // fails as of c++20

Known Uses

edit
edit

References

edit
  1. Timour, Doumler. "A Lock-free Atomic shared_ptr ACCU 2022" (PDF).