Resize a vector of atomic?

Question

How to resize a vector of atomics ?

As an example, the following code does not compile:

#include <iostream>
#include <vector>
#include <atomic>

int main()
{
    std::vector<std::atomic<int>> v;
    v.resize(1000); // Problem here!
    v[0] = 1;
    return 0;
}

Error:

In file included from /usr/local/gcc-4.8.1/include/c++/4.8.1/vector:62:0,
                 from main.cpp:2:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/stl_construct.h: In instantiation of ‘void std::_Construct(_T1*, _Args&& ...) [with _T1 = std::atomic<int>; _Args = {std::atomic<int>}]’:
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/stl_uninitialized.h:75:53:   required from ‘static _ForwardIterator std::__uninitialized_copy<_TrivialValueTypes>::__uninit_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = std::move_iterator<std::atomic<int>*>; _ForwardIterator = std::atomic<int>*; bool _TrivialValueTypes = false]’
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/stl_uninitialized.h:117:41:   required from ‘_ForwardIterator std::uninitialized_copy(_InputIterator, _InputIterator, _ForwardIterator) [with _InputIterator = std::move_iterator<std::atomic<int>*>; _ForwardIterator = std::atomic<int>*]’
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/stl_uninitialized.h:258:63:   required from ‘_ForwardIterator std::__uninitialized_copy_a(_InputIterator, _InputIterator, _ForwardIterator, std::allocator<_Tp>&) [with _InputIterator = std::move_iterator<std::atomic<int>*>; _ForwardIterator = std::atomic<int>*; _Tp = std::atomic<int>]’
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/stl_uninitialized.h:281:69:   required from ‘_ForwardIterator std::__uninitialized_move_if_noexcept_a(_InputIterator, _InputIterator, _ForwardIterator, _Allocator&) [with _InputIterator = std::atomic<int>*; _ForwardIterator = std::atomic<int>*; _Allocator = std::allocator<std::atomic<int> >]’
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/vector.tcc:556:42:   required from ‘void std::vector<_Tp, _Alloc>::_M_default_append(std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::atomic<int>; _Alloc = std::allocator<std::atomic<int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int]’
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/stl_vector.h:667:41:   required from ‘void std::vector<_Tp, _Alloc>::resize(std::vector<_Tp, _Alloc>::size_type) [with _Tp = std::atomic<int>; _Alloc = std::allocator<std::atomic<int> >; std::vector<_Tp, _Alloc>::size_type = long unsigned int]’
main.cpp:8:17:   required from here
/usr/local/gcc-4.8.1/include/c++/4.8.1/bits/stl_construct.h:75:7: error: use of deleted function ‘std::atomic<int>::atomic(const std::atomic<int>&)’
     { ::new(static_cast<void*>(__p)) _T1(std::forward<_Args>(__args)...); }
       ^
In file included from main.cpp:3:0:
/usr/local/gcc-4.8.1/include/c++/4.8.1/atomic:601:7: error: declared here
       atomic(const atomic&) = delete;
       ^

Answer 1

You can't...

A std::atomic<T> is neither copy/move-constructible, nor can you assign one std::atomic<T> to another; this means that it doesn't have the requirements to use std::vector<...>::resize(size_type).

23.3.6.2 vector constructors, copy, and assignment [vector.const]

void resize (size_type sz);

Requires: T shall be CopyInsertable into *this.

^{Note: std::vector::resize (size_type sz, T const& init) isn't applicable either since that requires T to also be MoveInsertable.}

---

Proposed resolution

You will need to use some other container-type which doesn't require already constructed data to be moved, copied, or copy/move assigned, upon modifying the elements already stored inside.

You could also define a wrapper around your std::atomic that fakes copy/moves/assigns, but actually just shallow read/writes the value of the underlying atomic.

Answer 2

std::deque<std::atomic<int> > can be resized. Note that std::deque can also provide O(1) random access just like std::vector.

Example:

#include <iostream>
#include <deque>
#include <atomic>

void print(std::deque<std::atomic<int> >& q) {
    for (auto& x : q) {
        std::cout << x.load() << ',';
    }
    std::cout << std::endl;
}

int main() {
    std::deque<std::atomic<int> > q;

    q.emplace_back(1);
    q.emplace_back(2);
    // 1,2
    print(q);

    q.resize(4);
    // 1,2,0,0
    print(q);

    q.resize(2);
    // 1,2
    print(q);

    //q.resize(5, 233);
    while (q.size() < 5) {
        q.emplace_back(233);
    }
    // 1,2,233,233,233,
    print(q);

    return 0;
}

resize with value does not work for deque because it requires copying the provided value, while std::atomic is not copyable. However, it can be achieved with repetitive emplace_back, which does not introduce much performance penalty because the expansion of deque does not require relocation of the existing data.

References

https://en.cppreference.com/w/cpp/container/deque

https://stackoverflow.com/a/37870930/13688160

Answer 3

Invalidating references to std::atomic objects is a recipe for disaster if they're potentially being accessed by multiple threads at the time. If you need that, you can potentially use std::dequeue< std::atomic<int> > which allocates piecewise so it never moves an element after allocating. (Note that growing a dequeue invalidates iterators, but not references to any individual element.)

But the std::dequeue object itself (and its internal linked list of chunks) is still not atomic, so you can't safely resize while other threads are doing things like q[i].store(v, memory_order_release). Only if you've just passed pointers to certain elements to other threads. (Elements aren't contiguous so there's no guarantee that &q[i+1] == &q[i]+1, so you can't necessarily give other threads access to whole ranges.)

---

If you have a std::vector whose data is sometimes accessed by multiple threads, but other times the whole vector is owned exclusively by one thread for operations like resize, this is a use-case for C++20 std::atomic_ref.

Use std::vector<int> v. When no other threads could accessing elements in it, or calling functions like v.size(), you can resize it as normal.

While no threads are calling functions that could change the control block at all, you can have any number of threads doing things like

   std::vector<int> v;
   // get some elements into v, start some threads
   static_assert(alignof(v[i]) >= std::atomic_ref<int>::required_alignment, "vector elements not guaranteed aligned enough for atomic_ref");

 // while no other threads could be calling v.push_back or any other non-const function except element access
   std::atomic_ref<int>  vi( v[i] );
   vi.store(2, std::memory_order_release);

   vi.fetch_add(1, std::memory_order_relaxed);  // and/or this

   auto tmp = vi.load(std::memory_order_acquire);  // and/or this

(The intended use-case for atomic_ref is to construct a new atomic_ref object every time you want to use it. Don't keep one as a class member anyway, just a local variable.)

Even a .push_back that doesn't reallocate would not be safe, though. That will change the members of the std::vector<int> object itself, which aren't atomic. (And there's no way to make them atomic). So this would be data race UB because other threads are accessing the v object, not just using an int * they already got from v.data().

---

How this would break (or not) if you used it wrong

In practice (but not guaranteed by the standard) it's likely safe for one thread to be doing .push_back() as long as you're below the current capacity, as long as other threads are only indexing into it. A typical implementation will keep a pointer to .data(), a pointer to the end of the reservation, and a pointer to the end of the in-use area, so .size() is return end()-data(). .push_back() will only modify the end pointer, but operator[] will only read the .data() pointer.

If the library header works that way, then you don't even have data race UB in the actual C++ code seen by the compiler itself. ISO C++ doesn't guarantee the internals, but this is a common implementation.

A debug built might also do bounds checking and read the .end() pointer in operator[] like at() does; then you'd have an actual data race. In practice that's also unlikely to be fatal; most implementations for most machines don't have tearing within a naturally-aligned pointer-width object, so readers are going to see either an old or new value. But this is definitely not guaranteed to be portable, and race-detectors will potentially notice.

But as long as you don't expect other threads to actually be accessing newly-pushed vector elements that have appeared since synchronizing with the pushing thread, it will happen to work on typical machines.

I would not recommend this nasty hack of actually pushing while other threads are writing. I describe the details of what would happen just for educational purposes, not as justification for doing so. If you do this anyway and it breaks, you get to keep both pieces.

Obviously actually reallocating could lead to crashes, if a thread got a reference to v[i] and then that reference was invalidated before use. And/or stale data or missed updates from one thread modifying an element after it had already been copied.

---

Feel free to roll your own container with a size or end member used by one thread, with other threads only using the begin / data member. With no conditional reallocate, it would even Just Work for std::atomic<int>, or if you want reallocation while one thread has exclusive ownership, still use atomic_ref<T> as above. Or you could design the push function to take a T, not an atomic<T>, or just have it work like emplace_back.