Thread-safe lock-free array

Question

I have a C++ library, which supposed to do some computations on multiple threads. I made independent threads code (i.e. there are no shared variables between them), except for one array. The problem is, I don't know how to make it thread-safe.

I looked at mutex lock/unlock (QMutex, as I'm using Qt), but it doesn't fit for my task - while one thread will lock the mutex, other threads will wait!

Then I read about std::atomic, which looked like exactly what I needed. Nevertheless, I tried to use it in the following way:

std::vector<std::atomic<uint64_t>> *myVector;

And it produced compiler error (use of deleted function 'std::atomic::atomic(const std::atomic&)'). Then I found the solution - use special wrapper for std::atomic. I tried this:

struct AtomicUInt64
{
    std::atomic<uint64_t> atomic;

    AtomicUInt64() : atomic() {}

    AtomicUInt64 ( std::atomic<uint64_t> a ) : atomic ( atomic.load() ) {}

    AtomicUInt64 ( AtomicUInt64 &auint64 ) : atomic ( auint64.atomic.load() ) {}

    AtomicUInt64 &operator= ( AtomicUInt64 &auint64 )
    {
                atomic.store ( auint64.atomic.load() );
    }
};

std::vector<AtomicUInt64> *myVector;

This thing compiles succesfully, but when I can't fill the vector:

myVector = new std::vector<AtomicUInt64>();

for ( int x = 0; x < 100; ++x )
{
    /* This approach produces compiler error:
     * use of deleted function 'std::atomic<long long unsigned int>::atomic(const std::atomic<long long unsigned int>&)'
     */
    AtomicUInt64 value( std::atomic<uint64_t>( 0 ) ) ;
    myVector->push_back ( value );

    /* And this one produces the same error: */
    std::atomic<uint64_t> value1 ( 0 );
    myVector->push_back ( value1 );
}

What am I doing wrong? I assume I tried everything (maybe not, anyway) and nothing helped. Are there any other ways for thread-safe array sharing in C++?

By the way, I use MinGW 32bit 4.7 compiler on Windows.

Do you want an fixed size (in multithreaded part) array of _shared elements_ or _shared array_ of elements. I mean, do insertions and deletions in array have place in _multithreaded_ part of code? — Lol4t0, Jun 04 '13 at 14:06
The array has fixed size - I don't have insertions or deletions in threads. — ahawkthomas, Jun 04 '13 at 14:07
@ahawkthomas: You push_back, that usually changes the size... — PlasmaHH, Jun 04 '13 at 14:12
Well, how can initialize `std::vector` without using `push_back`? Sorry for such dumb questions, but I don't know anything but `std::vector t = { 0, 0, 0 }` - and this approach is obviously unuseful with large amount of items. — ahawkthomas, Jun 04 '13 at 14:16
Also, do you understand, that your wrapper operations _are not atomic operations_. — Lol4t0, Jun 04 '13 at 14:16

score 6 · Accepted Answer · answered Jun 04 '13 at 14:31

Here is a cleaned up version of your AtomicUInt64 type:

template<typename T>
struct MobileAtomic
{
  std::atomic<T> atomic;

  MobileAtomic() : atomic(T()) {}

  explicit MobileAtomic ( T const& v ) : atomic ( v ) {}
  explicit MobileAtomic ( std::atomic<T> const& a ) : atomic ( a.load() ) {}

  MobileAtomic ( MobileAtomic const&other ) : atomic( other.atomic.load() ) {}

  MobileAtomic& operator=( MobileAtomic const &other )
  {
    atomic.store( other.atomic.load() );
    return *this;
  }
};

typedef MobileAtomic<uint64_t> AtomicUInt64;

and use:

AtomicUInt64 value;
myVector->push_back ( value );

or:

AtomicUInt64 value(x);
myVector->push_back ( value );

your problem was you took a std::atomic by value, which causes a copy, which is blocked. Oh, and you failed to return from operator=. I also made some constructors explicit, probably needlessly. And I added const to your copy constructor.

I would also be tempted to add store and load methods to MobileAtomic that forwards to atomic.store and atomic.load.

Please tell me how to access that vector? I want to know what is stored in the vector. — Aditya kumar, Mar 21 '19 at 11:19

Mike Seymour · Answer 2 · 2013-06-04T15:06:21.860

You're trying to copy a non-copyable type: the AtomicUInt64 constructor takes an atomic by value.

If you need it to be initialisable from atomic, then it should take the argument by (const) reference. However, in your case, it doesn't look like you need to initialise from atomic at all; why not initialise from uint64_t instead?

Also a couple of minor points:

The copy constructor and assignment operator should take their values by const reference, to allow temporaries to be copied.
Allocating the vector with new is a rather odd thing to do; you're just adding an extra level of indirection with no benefit.
Make sure you never resize the array while other threads might be accessing it.

Thank you very much for minor points explanation, and especially for `const` reference, I didn't know about such basics. — ahawkthomas, Jun 04 '13 at 15:04

score 1 · Answer 3 · answered Jun 04 '13 at 14:18

This line

AtomicUInt64 ( std::atomic<uint64_t> a ) : atomic ( atomic.load() ) {}

You're completely ignoring the argument you pass in, You probably want it to be a.load() and you probably want to take elements by const reference so they aren't copied.

AtomicUInt64 (const std::atomic<uint64_t>& a) : atomic (a.load()) {}

As for what you're doing, I'm not sure if it is correct. The modification of the variables inside the array will be atomic, but if the vector is modified or reallocated (which is possible with push_back), then there's nothing to guarantee your array modifications will work between threads and be atomic.

Thread-safe lock-free array

3 Answers3

Linked