When is dequeue size call not thread safe?

Question

In general, operations on the standard containers are not thread safe (mostly). The size call on a std::vector, for example, may fail when reallocations are happening.

Since a dequeue does not reallocate or move the elements like a standard vector does, are there still conditions when calling size on a dequeue can be unsafe? The most likely scenario seems to be when adding/removing elements in a different thread as the size call is being made, but since accessing an integer is mostly safe, I'm having trouble thinking of how calling size from a separate thread would be problematic.

*I'm having trouble thinking of how calling size from a separate thread would be problematic.* UB causes all sorts of issues. Best to just avoid it. — NathanOliver, Feb 28 '20 at 21:56
What (re)allocation (or its absence) has to tread safety? Containers are not synchronized in any way, ergo they are not thread safe. Only case where you can use STL container as thread safe is when it is not muted at all just read. For example when coding in functional style. — Marek R, Feb 28 '20 at 21:59
@MarekR one of the users in the comments of the SO links suggested the case where you're computing end() - begin(), but mid computation one of those changes so you get a negative unsigned int. This particular case doesn't seem to be possible for deque, since the memory isn't guaranteed to be contiguous. Does that make sense? — en_Knight, Feb 28 '20 at 22:01
Unless `dequeue::size()` is guaranteed to be thread safe, implementations are free to do any thread unsafe behavior to calculate the value. The function could iterate through all elements and return the count. It could read a member variable `size`, sleep for 20 seconds, and read `size` again then return the average. — JohnFilleau, Feb 28 '20 at 22:03
@NathanOliver agreed. I'm just wondering if there is *really* a case where the size call will be problematic, since the behavior seems *slightly* different than std vector where the question was already answered. If the answer is "can't think of an exact case but it's still not a good idea" I'm fine with that — en_Knight, Feb 28 '20 at 22:04
Even if `size()` just reads a variable you can have a data race if another thread causes an update at the same time. Data races are always undefined behavior. — Blastfurnace, Feb 28 '20 at 22:05
@en_Knight Maybe yous should read about memory ordering before stating such things. [Take a look on that cool lecture](https://scs.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=e152f2c8-dc26-4dec-84da-eb6eef4984dd). — Marek R, Feb 28 '20 at 22:06
Accessing an unsynchronized `int` across threads is **not** safe. The link you provided does not say it's "mostly safe". — François Andrieux, Feb 28 '20 at 22:07
The gcc implementation of `deque` seems to use a similar process as you described in `vector`. `return this->_M_impl._M_finish - this->_M_impl._M_start;` https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_deque.h — JohnFilleau, Feb 28 '20 at 22:07
Is your question really, "is it thread safe to read a `size_t`"? — JohnFilleau, Feb 28 '20 at 22:09
@... a few people :) I'm getting a general answer: (1) I'm too optimistic (/naive/misunderstood/whatever) about how nice a read operation is, (2) the behavior from the other answer about vectors applies here anyways. If this is correct, and someone puts it in an answer, I'd be happy to accept it! — en_Knight, Feb 28 '20 at 22:12

score 4 · Accepted Answer · answered Feb 28 '20 at 22:14

Ever. Because it's not required to be so in any standard.

The GCC implementation here https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/stl_deque.h is the result of a subtraction:

      // [23.2.1.2] capacity
      /**  Returns the number of elements in the %deque.  */
      size_type
      size() const _GLIBCXX_NOEXCEPT
      { return this->_M_impl._M_finish - this->_M_impl._M_start; }

Even if size were stored in a size_t, or even an uint8_t, and size() were an inline function to return this variable, C++ makes no guarantees about the atomicity of different ints. Never assume something is threadsafe unless it is guaranteed to be so.

Tarek Dakhran · Answer 2 · 2020-02-28T22:04:50.680

0

For example like this

std::deque<int> dq;
dq.push_back(1);

// thread0
void printElementIfExist() {
    if (dq.size() > 0) {
        std::cout << dq[0] << std::endl;
    }
}
// thread1
void removeElementFromDeque() {
    if (dq.size() > 0) {
        dq.pop_back();
    }
}

race condition could allow to access dq[0] which is already deallocated.

Back to the size() call itself. There are architectures where the read operation is not an atomic operation.

edited Feb 28 '20 at 22:04

answered Feb 28 '20 at 22:02

Tarek Dakhran

2,021
11
21

1

here I believe it's the access that causes the problem, not the size check, correct? All my accesses, in this scenario, are guarded by locks – en_Knight Feb 28 '20 at 22:03

When is dequeue size call not thread safe?

2 Answers2