Race condition and unlocked write

Question

I have a question about race conditions and simultaneous writes.

I have a class who's objects are accessed from different threads. I would like to calculate some values only on demand and cache the result. For performance reasons I'd rather not use locks (before anyone asks - yes it is relevant in my case).

This constitutes a race condition. However, the objects are const and won't be changed. So if different threads calculate values to be cached they are in my use case guaranteed to be identical. Would it be safe to write these values without locking? Or, in broader terms, is it safe to write identical content to memory from different threads without locking?

The values written are of types bool and double and the architectures in question may be x86 and ARM.

EDIT: Thanx to everyone for their input. I have finally decided to find a way that does not involve caching. This approach does seem to much like a 'hack' and there is the problem with using a flag variable.

Answer 1

As you say, this is a race condition. Under C++11 it is technically a data race, and undefined behaviour. It doesn't matter that the values are the same.

If your compiler supports it (e.g. recent gcc, or gcc or MSVC with my Just::Thread library) then you can use std::atomic<some_pod_struct> to provide an atomic wrapper around your data (assuming it is a POD struct --- if it isn't then you have bigger problems). If it is small enough then the compiler will make it lock-free, and use the appropriate atomic operations. For larger structures the library will use a lock.

The problem with doing this without atomic operations or locks is visibility. Whilst there is no problem at the processor level on either x86 or ARM with writing the same data (assuming it really is byte-for-byte identical) from multiple threads/processors to the same memory, given that this is a cache, I expect you'll want to read this data rather than recalculate it if it has already been written. You'll therefore need some sort of flag to indicate done-ness. Unless you use atomic operations, locks or suitable memory barrier instructions then the "ready" flag may become visible to another processor before the data does. This will then really mess things up, as the second processor now reads an incomplete set of data.

You could write the data with non-atomic operations, and then use an atomic data type for the flag. Under C++11 this will generate suitable memory barriers and synchronization to ensure that the data is visible to any thread that sees the flag set. It's still undefined behaviour for two threads to write the data, but it may be OK in practice.

Alternatively, store the data in a block of heap memory allocated by each thread that does the calculation, and use a compare-and-swap operation to set an atomic pointer variable. If the compare-and-swap fails then another thread got there first, so free the data.

Answer 2

You do not need to protect against writes to POD variables from different threads, if the values would be the same. If you have pointers involved, though, you should definitely do an interlocked exchange.

UPDATE: To clarify, for your situation caching and optimizations will not have any adverse effects, since you are writing the exact same value on all threads. For the same reason, you do not need to make the variable volatile. The only things that could potentially be a problem, is if your variable is not aligned to the word size of the machine. See https://stackoverflow.com/a/54242/677131 for more details. By default, variables are automatically aligned, but you can change the alignment explicitly.

There is an alternative approach that avoids this issue altogether. Since the variables will have the same values, either precompute them before concurrent execution starts, or let each thread have its own copy. The latter has the advantage of providing better performance on NUMA machines.

Answer 3

I have to start by saying that using locking is usually the right way of doing that but...

Writing to the same variable from multiple threads can't be unsafe even if data is bigger than processor word size. There is no transitional state where variable can be corrupted because at least one thread will finish writing the value. Other threads will not change it by wring over the same value.

So if there is a guarantee that results of computation will always be the same no matter what thread, there is no danger in doing that by multiple threads. Just check a flag ("is already computed?") before doing calculation. Multiple threads will enter the value computing code but once it is done, of course no other threads will do that any more. Obviously doing the same thing n-times is a waste of time though. Question here is, will using a lock save you any time or to the contrary? Only performance testing can give you the answer. Unless there are other reasons for not using locks.

Answer 4

Ultimately the answer would probably depend on your data structure.

In the "non-portable" realm, you might want to look into compare and swap, which most processors will let you do on a pointer-sized entity. To access that you can use inline assembly (on x86 these are the lock cmpxchg instructions), or perhaps GCC synchronization extensions. Upon seeing an uninitialized value, each thread could eagerly initialize, and issue a compare-and-swap to attempt to set a value. If the compare-and-swap fails it means another thread has beat you to it.

Ultimately usage of that operation often ends up being the equivalent of implementing a spinlock, though, which you may be looking to avoid ...