Is it possible to create an atomic vector or array in C++?

Question

I have some code which uses an array of int (int[]) in a thread which is activated every second.

I use lock() from std::mutex to lock this array in this thread.

However I wonder if there is a way to create an atomic array (or vector) to avoid using a mutex? I tried a couple of ways, but the compiler always complains somehow?

I know there is a way to create an array of atomics but this is not the same.

Solution 1

In practice, at the CPU level, there are instructions which can atomically update an int, and a good compiler will use these for std::atomic<int>. In contrast, there are are no instructions which can atomically update a vector of ints (for any architecture I am aware of), so there has got to be a mutex of some sort somewhere. You might as well let it be your mutex.

---

For future readers who haven't yet written code with the mutex:

You can't create a std::atomic of int[10], because that leads to a function which returns an array - and you can't have those. What you can do, is have a std::atomic<std::array<int,10>>

int main()
{
  std::atomic<std::array<int,10>> myArray;
}

Note that the compiler/library will create a mutex under the hood to make this atomic. Note further that this doesn't do what you want. It allows you to set the value of the whole array atomically.

It doesn't allow you to read the whole array, update one element, and write the whole array back atomically.

The reads and the writes will be individually atomic, but another thread can get in between the read and the write.

You need the mutex!

Solution 2

You can put arrays in atomics, but not directly. Like the other answer explain you can use std::array. I answered this question and explained how to do something similar for a struct.

Having said that and explained the technical viability, I have to tell you something else:

PLEASE DON'T DO THAT

The power of atomic variables come from the fact that some processors can do their operations with one instruction. The C++ compiler will try to make your atomic operations happen in one instruction. If it fails, it'll initiate a bus lock, which is like a global lock of everything, until that array is updated. It's equivalent to a mutex that locks all your variables in your program. If you're concerned about performance, don't do that!

So for your case, a mutex is not a bad idea. At least you can control what is critical and improve performance.

Comments

[463035818_is_not_a_number]

what are the ways you tried and how exactly did the compiler complain?

[Robinson]

Possible duplicate of (preferably boost) lock-free array/vector/map/etc?

[Jarod42]

BTW, atomic doesn't guaranty lock-free, so implementation can do thing similarly to mutex.

[rainbow]

@tobi303 I tried to make some combinations like this: std::atomic<int[]> myArray = {0,0,0}; or like this: std::atomic<int[10]> myArray; and so on.

[463035818_is_not_a_number]

please add the code to the question and also add the compiler errors

[Richard Hodges]

There are some very good CPPCON talks on lock-free programming and performance measuring. The short answer is don't bother unless the mutex version cannot meet the performance expectations of your users. If that's the case then in all likelihood it's your design that's wrong. An atomic store takes ~10 times as long as a non-atomic one. If you're doing a run of stores, you're better off holding a lock and doing them without atomics.

[rainbow]

@Robinson I don't want to use boost.

[Robinson]

Lock-free programming is hard. If you're going to use something, might as well use something that's already tried and tested.

[Richard Hodges]

@Robinson lock-free programming is also almost always completely un-necessary. ;-)

[Richard Hodges]

It's probably also worth mentioning that mutexes are not actually that slow on a good implementation running on a good OS (e.g. linux). In the uncontended case (the majority of cases if your design is any good), the acquisition and release of the mutex is an atomic operation.

[Martin Bonner supports Monica]

@RichardHodges : If the access is only once a second, it's definitely unnecessary. If there were a million accesses a second, lock free might be a good idea.

[Martin Bonner supports Monica]

... and I believe a Microsoft "CriticalSection" is the same.

[peterh]

You can relative easily create atomic chained lists, as pointer arithmetics are atomic everywhere.

[sailfish009]

why doing this?

[Martin Bonner supports Monica]

@peterh : No they aren't! Or at least, you can't rely on other threads seeing the updated values in the order you updated them. What's scary about this, is that it will almost always work - right up until the time you demo it to a really, really, important customer.

[peterh]

@MartinBonner Typically, atomic data structures aren't very smart. I am thinking on a list which could be appended by listVar->last = newItem;. Of course it can be only an unidirectional list, where the last element is registered in the container, and all the elements have only a ->prev field.

[Martin Bonner supports Monica]

@peterh: My point is that void * on its own is not atomic. You need std::atomic<void *> for that.

[Richard Hodges]

it might be worth mentioning that this array would be about as useful as a chocolate teapot. All you would be able to do is take copies of the entire array or replace the entire array from a copy.

[rainbow]

Short and elegant explanation. Thank you. This is answer I looked for.

[463035818_is_not_a_number]

cppref states "std::atomic may be instantiated with any TriviallyCopyable type T:" and afaik arrays are trivially copyable, or am I wrong?

[Martin Bonner supports Monica]

bus lock: Do you have a cite for that? Surely creating a mutex under the hood is going to be much easier to implement (and much more performant).

[Martin Bonner supports Monica]

@RichardHodges : Yes, I wrote this before cycling to work. As I walked out the door, I realized that problem!

[The Quantum Physicist]

@MartinBonner Not right now, no. I have to dig a little. I remember reading this somewhere; probably in this book. On another note (not defending not providing a reference, but just for the sake of a fruitful discussion), how else can this be done? How can you ensure atomicity (done/not done with no intermediate state) without a global lock?

[Martin Bonner supports Monica]

How can it be done? Easy. None of the member functions of std::atomic allow direct access to the underlying value, so give each std::atomic a mutex, lock the mutex at the start of each member function, release it at the end. I have a feeling that you may be mis-remembering how some architectures implement atomic operations on eg a word.

[Martin Bonner supports Monica]

@tobi303 : Hmm. According to cppreference, arrays of trivially copyable types are trivially copiable. That may mean there is an error in cppreference, or there is a defect in the standard. Requiring that the library allow you to instantiate std::atomic<int[10]> when there can be no way of obtaining the value (because operator T would have to return int[10]) is pointless.

[The Quantum Physicist]

@MartinBonner You may be right. But let me point out a very subtle point here: It's not about thread-safety as this is not what the program has to guarantee, and that's the problem. It's about atomicity and its semantic meaning. The definition of an atomic variable is: It's a variable with operations that can be either done or not done. It cannot be in any state in between. It's not about locking access to the variables. But again, I might be misremembering this, however, I would never do atomics for more than 16 bytes.

[Martin Bonner supports Monica]

std::atomic<std::array<unsigned char, 256>> provides exactly that. Internally, there may be intermediate states - but they are unobservable by any C++ programme with defined behaviour. (And if the program has undefined behaviour, it becomes impossible to reason about.)

[The Quantum Physicist]

@MartinBonner The observability is the subtle part that makes me worry about such usage of atomics. Let me think about this. I'll come back after I have resolved this (will probably be a while).

[MSalters]

Martin is correct. A c++ std::atomic<T> has the same type from the perspective of all threads. They all must access the T values via the std::atomic interface. It's this interface which exhibits the observable atomic behavior, but it also is the only interface to access the underlying T.

[463035818_is_not_a_number]

yes, I got your point, I just am not familiar enough with the standard to prove cppref wrong

[Yakk - Adam Nevraumont]

Transactional memory should be mentioned.

[Yakk - Adam Nevraumont]

@RichardHodges I'm not sure why this is about as useful as a chocolate teapot. You'd also be able to compare-and-set, right?

[Martin Bonner supports Monica]

@Yakk: Yes, but it's not going to be myArray.load()[3] = 2; - that code will compile, but won't do what you want. You need auto vExpected = myArray.load(); decltype(vExpected) v; do { v = vExpected; v[3] = 2; } while (!myArray.compare_exchange_weak( vExpected, v ); - and there are probably bugs there!

[Richard Hodges]

@Yakk CAS works on one memory word. An array is a bunch of contiguous words, none of which in themselves are atomic. you could have std::atomic<std::array<std::atomic<X>>> I guess... oh no you couldn't - atomics aren't copyable or moveable.

[Yakk - Adam Nevraumont]

@RichardHodges This -- sure not the ASM instruction, but writing "compare and set" isn't impossible.

[Richard Hodges]

@Yakk yes I see but one wonders whether just using a mutex is actually just quicker in practice. Cache lines and all that.

[Yakk - Adam Nevraumont]

@RichardHodges Oh, that atomic is almost certainly implemented as a mutex guarded instance of array. You can check this by asking if it is lockfree.

[Richard Hodges]

@Yakk no, I mean being able to update elements of the array without copying the whole thing twice.

[KeksArmee]

I feel like "If it fails, it'll initiate a bus lock" isn't exactly true. Take a look at the signature of atomic::load: cplusplus.com/reference/atomic/atomic/load You can specify memory_order_xxx