> I was thinking about adding atomic pointer references to a partially persistent (1) AABB tree, then allowing multiple actors in multiple threads each implementing a gameloop to query the AABB tree. Do I need to think about memory fences in that application?

Probably?

Let me give an attempt at what a memory-fence actually is, and why I think you may need to think about memory fences.

Atomics solve one PART of the synchronization problem. The second problem, which is far more complex, is that the compiler, CPU, and Memory / Cache system reorders your reads-and-writes in a non-obvious way. These reorderings can lead to obscure bugs.

These reorderings happen because of single-threaded optimization. Programmers expect the compiler, CPU, and L1 cache to reorder statements to go as fast as possible. Ever wonder what the -O2 and -O3 compiler flags do? They'll eliminate variables and change your code in subtle ways.

Even if you run at -O0 optimizations, these conceptual reorderings exist at the CPU (store buffer) and L1 cache levels. So you cannot escape this unfortunate, complex reality.

Therefore: it is the programmer's responsibility to define a "Happens-before" relationship through memory fences / memory barriers. A "happens-before" relationship will kill optimizations (be it a compiler-optimization, CPU store-buffer optimization, or L1 cache optimization) in just the right way to make your code correct.

------------

With that out of the way, lets go into your AABB tree question.

Assume "node" is a node to a binary AABB tree, with "node->left" and "node->right" referring to its two children. Lets assume both "left" and "right" are atomic<> pointers.

Now think of the code:

AABB_Node tmp = malloc();
node->left->store(tmp); // This is a race condition!
tmp.initialize();

The above code is wrong. You can't "publish" the data before it is initialized! "tmp" would contain garbage data (its "fresh" from the malloc). Therefore, you need to write the following code:

AABB_Node tmp = malloc();
tmp.initialize();
node->left->store(tmp);

Okay, now you "think" you've solved the multithreaded issue, but you have NOT. Because the compiler says "tmp is an unnecessary variable" and optimizes it away. So the compiler may decide to emit:

node->left->store(malloc());
node->left->initialize(); // Compiler wants variable-elimination optimization

Uh oh, the compiler "moved" the code around, which is logical in a single-threaded setting. But this reordering destroys your multithreaded logic. Your other threads may get the malloc() before the initialize.

------------

"Happens-before" is the key concept. What we want to say is:

AABB_Node tmp = malloc();
tmp.initialize();

__happens before__

node->left->store(tmp);

Good news: modern C++11 allows you to specify a "happens before" relationship through memory fences.

node->left->store(tmp, memory_order_release);

"Memory_order_release" is the minimum happens-before relationship we want. The C++11 standard states: "A store operation with this memory order performs the release operation: no reads or writes in the current thread can be reordered after this store."

The compiler will emit the low-level code needed to ensure the happens-before relationship will work through lower-level memory fence mechanisms. GPUs will have to clear their L1 cache (due to incoherent memory), while CPUs will only have to wait for the store-buffer to be flushed and MESI messages to be passed around (ARM has the "dmb ish" statement for example)

Regardless of the low-level details, the job of the programmer with memory fences remains the same. Specifying important "happens-before" relationships.

-------------

In the GPU world, where C++11 atomics do not exist yet, the happens-before relationship is created with a threadfence instruction. In CUDA, you would do:

AABB_Node tmp = malloc();
tmp.initialize();

__threadfence_block(); // Block-level synchronization

node->left = tmp;

__threadfence_block() is only a fence that works within a CUDA-workgroup (and is therefore far faster than __threadfence()). Effectively, you only wait for L1 cache (while __threadfence() waits for an L2 cache commit).

-------------

I'll butcher the explanations a bit (real code doesn't work like this, but it may help you to understand things). EDIT: Oh gosh, I got these backwards again in my first draft. I'm pretty sure I put them in the correct order now.

An "acquire-read" operation basically compiles from:

foo();
node->left.load(memory_order_acquire);
bar();

Becomes (approximately)

foo();
register = node->left
__happens before__
bar();

Different CPUs have different memory guarantees. x86 will have __happens before__ be a no-op in this case.

An "release-store" operation compiles from:

foo()
node->left.store(register, memory_order_release);
bar();

Becomes (approximately)

foo();
__happens before__
node->left = register;
bar();

The "strongest" operation is memory_order_seq_cst, which approximately translates into:

foo();
__happens before__
node->left = register;
__happens before__
bar();

But this kind of heavy-ordering is the slowest to implement in practice. Hopefully that explains a few things.