3
\$\begingroup\$

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)?
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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? \$\endgroup\$ – davidhigh Jul 31 '17 at 5:48
  • \$\begingroup\$ 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? \$\endgroup\$ – davidhigh Jul 31 '17 at 5:51
  • 1
    \$\begingroup\$ Yes, it leaves references to the rest untouched. That doesn't mean it leaves the datastructure to get that reference untouched. \$\endgroup\$ – Deduplicator Jul 31 '17 at 9:43
  • \$\begingroup\$ 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. \$\endgroup\$ – davidhigh Jul 31 '17 at 10:45
1
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – davidhigh Aug 1 '17 at 14:26
  • \$\begingroup\$ (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? \$\endgroup\$ – davidhigh Aug 1 '17 at 14:31
  • \$\begingroup\$ (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). \$\endgroup\$ – Quuxplusone Aug 1 '17 at 17:12
  • \$\begingroup\$ (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? :) \$\endgroup\$ – Quuxplusone Aug 1 '17 at 17:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.