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

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

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

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

auto size() const
{
}

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

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)?

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.

• Thanks for your answer. I know the reader-writer lock and decided against ... in fact, the whole idea of this question is a lock-free read. So again, why is it not thread-safe? A call to push_back adds an element to the deque, but leaves (references to) the rest untouched. Reading any element except the one just about to push_back is imo safe, you agree? – davidhigh Jul 31 '17 at 5:48
• Now to the last element: a reader thread is allowed to read it only after it really exists, as is indicated by the size() variable which changes only after the push_back is finished. Reading elements outer the size is undefined behavior, as it's for a normal single-threaded vector. So when one accepts this by definition, where is the code non-threadsafe? – davidhigh Jul 31 '17 at 5:51
• Yes, it leaves references to the rest untouched. That doesn't mean it leaves the datastructure to get that reference untouched. – Deduplicator Jul 31 '17 at 9:43
• Subtle point, but I got it. Although I can't think of a mechanism that would invalidateoperator[], it's not guaranteed by the standard that it really does. An that kills it... I'll mark your answer as accepted on behalf of your comment. – davidhigh Jul 31 '17 at 10:45

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?)

• Seems then that I'm a five, and there's lots to learn ahead, so thanks for your comments. (i) the deque-access error is there from the principles, and it's also good to see it in action. Probably a stable, non-contigouos T** is more appropriate here. (ii) I didn't want to focus on the copy-constructor, so I'd have it better deleted, but as it is it's implicitly there and thus surely a bug, so thanks for pointing. – davidhigh Aug 1 '17 at 14:26
• (iii) With respect to the memory order: as far I know std::memory_order_seq_cst does not prevent the reordering of non-atomic accesses to after the respective position, and I wanted the previous push_back happen first ... this is why I chose std::memory_order_release. The std::memory_order_acquire then came in rather intuitively (this is why I asked whether it's correct). The main question was, whether the update strategy is resp. can be made correct, i.e. lock only the write accesses (which are always push_backs) and don't lock the read accesses unlocked. What do you mean? – davidhigh Aug 1 '17 at 14:31
• (i) Nothing wrong with a deque as long as you take the mutex lock at the right times. I think you'll find the same problems cropping up with raw T**, although I admit I'm not sure exactly what you're thinking of. (ii) threadsafe_array's copy and move ops are implicitly deleted because threadsafe_array has non-moveable members (the atomic and the mutex). – Quuxplusone Aug 1 '17 at 17:12
• (iii) My only point re memory-orders is that you'll probably get them wrong even if you think hard about them — and certainly if you go by "intuition"! Prefer the safety of seq_cst, especially on x86 where the different memory-orders give identical codegen anyway. Ask yourself: is it worth the extra keystrokes, if all you're doing is introducing bugs for ARM users? :) – Quuxplusone Aug 1 '17 at 17:15