3 ms·

Only if you use synchronization "manually" (and... you probably are doing that if you are writing atomics), do you have to think about memory fences. I was thi

Only if you use synchronization "manually" (and... you probably are doing that if you are writing atomics), do you have to think about memory fences. 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? I've also been thinking about implementing the above system without atomic pointers. Instead, the system would have an update phase where all writes to the AABB tree happen at once, then all of the actors are allowed to run concurrently for one game loop tick. In both cases, I'm thinking of placing the AABB tree into shared memory, but my brief experience with using shared memory makes me wary of performance problems. (1) Persistent in this sense, of course: https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure

dragontamer 7y ago
> 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.
- stcredzero 7y ago
  Thanks. That was indeed helpful. A part of the problem is that I'm most familiar with barriers used in GC algorithms, and in sandboxing. So seeing the term "memory fence" was confusing. (I should've just read the Wikipedia page!)

dragontamer 7y ago

> 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.

stcredzero 7y ago
Thanks. That was indeed helpful. A part of the problem is that I'm most familiar with barriers used in GC algorithms, and in sandboxing. So seeing the term "memory fence" was confusing. (I should've just read the Wikipedia page!)