C++ minimal threadsafe array based on std::deque

Question

Here is a minimal example of a threadsafe array I want to build on for a timeseries application, with the following characteristics:

• Ever-growing, and the already contained elements remain constant
• (Usually) a single writer calling push_back
• Multiple dependent readers

Here is the corresponding implementation, or rather an early attempt of it:

template<typename T>
struct threadsafe_array
{
    auto operator[](int i) const
    {
        return deq[i];
    }

    auto size() const
    {
        return deq_size.load(std::memory_order_acquire);
    }

    void push_back(T const& t)
    {
        std::unique_lock<std::mutex> lock(mut);
        deq.push_back(t);
        lock.unlock();
        deq_size.fetch_add(1, std::memory_order_release);
    }

private:
    std::deque<T> deq;
    std::atomic<int> deq_size{0};
    std::mutex mut;
};

My underlying ideas:

1. reads of the available elements through operator[](int) are carried out lock-free.
2. a std::deque is used as the underlying container because it does not invalidate concurrent reads when doing a push-back (--in contrast, a std::vector could as it potentially does a reallocation)
3. the push_back is forwarded to the underlying deque, on which it is applied in an atomic way through locking the std::mutex. Thereafter, the variable deq_size of type std::atomic<int> variable is adjusted using release semantics (so that the previous push_back is not reordered after the fetch_add).
4. if there are reads occurring in between adding an element to the deque and the adjustment of the size, they have have to get along with a smaller size(), i.e. as if the array had not been updated. Calling operator[size()] therefore does not need to be undefined behvaiour as it is for std::deque (but that's more an inconsistency than a feature).

Questions:

• Is this thing already threadsafe and doing what I wrote, or am I missing some points?
• Are the memory orders in the atomic operations ok, or are there better choices (e.g. memory_order_relaxed for the load in size())?
• Is it preferable doing the update of the size in push_back() under the lock (and thus, if I see it right, limit the size difference between size() and the underlying std::deque::size() to only one)?

Answer 1

Your code isn't thread-safe, as executing a read with .operator[]() and a write with .push_back() isn't synchronized in any way.
Even though no references to elements are invalidated by std::deque<T>::push_back(), it can change the data-structure to retrieve those references.

What you want to look into is called a readers-writer-lock, which is the primitive for allowing either multiple readers or only a single writer access at the same time.
C++17 provides it as std::shared_mutex, so you might have to use boost::shared_mutex unless your library is already there.

Answer 2

On a scale of 1 to 100, how confident are you in your ability to use memory_order_acquire and memory_order_release correctly?

---

The common implementation of std::deque as a double-ended array of pointers to arrays will definitely hit the bug that Deduplicator describes, whenever the deque reallocates its array-of-pointers.

Here's a reproducer for libc++'s deque, which reallocates on the 1024th call to push_back: https://wandbox.org/permlink/3nyt9fGZAiS9yScK

Reproducing on libstdc++ is left as an exercise for the reader.

---

You should always use std::lock_guard<std::mutex> whenever you're manipulating mutex locks. Your manual mutex-fiddling here will cause a deadlock whenever T's copy-constructor throws.

---

Consider providing push_back(T&&) and possibly a template emplace_back(Args&&...) in addition to your push_back(const T&). Of course this just increases the surface area exposed to the deadlock bug above; so start using lock_guard first and add these member functions afterward.

---

Now, on a scale of 1 to 100, how confident are you in your ability to use memory_order_acquire and memory_order_release correctly? (For comparison, I rate myself at about a 15... and I'm able to spot bugs like the above fairly easily. Given that you didn't spot those bugs, should you be using memory orders other than seq_cst? Why or why not?)