Cache and Interleaved Memory Access

If one thread sets all odd bits in a zeroed array and another thread sets all even bits, what does memory contain?

The Short Answer #

The final value is not deterministic unless the updates are atomic. In C and C++, unsynchronized concurrent writes to the same storage form a data race, thus the program has undefined behavior.

Cache coherence keeps cache lines consistent across cores, but it does not turn a read-modify-write sequence into a single indivisible operation. If two threads update different bits in the same byte or word with ordinary stores, one update can overwrite the other because both threads may read the same old value, modify it locally, and then write back a stale copy.

Why Cache Lines Do Not Solve the Race #

Coherence operates at cache-line granularity. That matters for performance, because two threads that touch the same line will bounce ownership back and forth.

It does not matter for correctness, because the race happens above the cache protocol:

1. Thread A reads the shared word.
2. Thread B reads the same word.
3. A sets its bits and writes back.
4. B sets its bits based on the stale value and writes back.

The last write wins for the bytes it touches, thus earlier bit updates can disappear.

When the Result Is Stable #

The answer becomes deterministic if each update is an atomic bitwise operation:

atomic_fetch_or_explicit(&word, mask, memory_order_relaxed);

In that case, the hardware and the language runtime serialize the modification of the shared word, thus the final value becomes the bitwise OR of all updates.

The same result also holds when each thread writes to a disjoint byte, word, or cache line. The important part is not “odd bits versus even bits”; the important part is whether two writes can overlap at the storage unit that the machine updates atomically.

Practical Rule #

• For packed bitsets, use atomic read-modify-write operations.
• For hot concurrent counters or flags, partition the data so threads do not share the same cache line.
• For plain performance work, remember that false sharing hurts throughput even when the logical data is disjoint.