Jan*_*tke 4 c++ multithreading atomic stdatomic
我想知道经典的“原子计数器动态调度”惯用法的正确内存顺序是什么。那是：
i使用 fetch-add 获取下一个要处理的元素的索引i超出数组末尾，则终止i线程安全地处理元素，因为没有其他线程可以拥有i例如：
#include <atomic>
std::atomic_int counter = 0;
void foo(int *data, int size) {
// we could also write counter++
for (int i; (i = counter.fetch_add(1, std::memory_order::seq_cst)) < size;) {
data[i] *= 2;
}
}
// driver code
#include <thread>
#include <numeric>
#include <cassert>
int main() {
int data[1'000'000];
std::iota(std::begin(data), std::end(data), 0);
std::thread other{foo, data, std::size(data)};
foo(data, std::size(data));
other.join();
for (int i = 0; i < std::size(data); ++i) {
assert(data[i] == i * 2);
}
}
这段代码可以工作，而且应该是安全的，因为在获取下一个索引之前或之后无法对元素的处理进行重新排序，并且所有线程都以一致的总顺序观察所有 fetch-adds。这些要求对我来说似乎过于严格，我相信我们可以使用更宽松的顺序。
std::memory_order_relaxedstd::memory_order::acquire我相信并且太放松了，因为所有线程counter = 0;最初都会观察，并且我们必须确保data[0] *= 2在第一个之前没有移动fetch_add。这两个内存顺序允许这样做。
答案必须是以下之一：
std::memory_order::seq_cststd::memory_order::acq_relstd::memory-order::release在这种情况下哪一个是正确的顺序？
relaxed足够了。每个counter.fetch_add(1, relaxed)都会返回不同的值，并且从0上往下的每个值都会返回一次。原子性本身就保证了这一点，因为所有操作都在同一个原子对象上。
无法保证哪个线程将获得哪个i值，并且操作data[i]没有顺序，但这很好，因为只有一个线程将访问每个线程，data[i]直到thread.join()在写入器和读取器之间创建同步。
C++ 标准中的相关措辞是原子 RMW 必须看到“最新值”并且每个原子对象单独存在一致的修改顺序的部分。在单个线程内，对同一原子对象的操作遵循先序的程序顺序。（即一个fetch_add不能与另一个“重新排序” fetch_add。）
在硬件中，相关行为是 RMW 的原子性和高速缓存一致性，后者保证在原子 RMW 可以执行其加载+添加+存储之前，必须使高速缓存行的所有其他副本无效。（这就是使同一地址上的原子 RMW 可序列化的原因。）
.join()与阅读器同步否则atomic<bool> done，release如果其他线程只是查看counter. 等待线程必须等待，counter == size + nthreads以确保每个线程都完成了一个release在其最后一个操作之后排序的操作data[i] *= 2。（这些形成了一个发布序列，以便读者可以与所有线程同步。）
每个线程在看到 false 后将停止执行增量操作fetch_add() < size。counter第一个看到发生这种情况的线程（按修改顺序）已加载i=size并存储了i=size+1。离开循环的第二个线程将已加载size+1并存储size+2。因此，当 nthreads=1 或 2 时，counter==size+nthreads在他们完成最终存储作为 RMW 的一部分之后。
因此，看到的负载counter == size+nthreads可以确定所有线程都fetch_add在其最后一个之后完成了 a data[i] *= 2;。如果这些是releasefetch_add 并且这是一个加载，则保证在该加载之前发生acquire对对象的存储，因此该线程中的后续代码可以看到修改后的值。data[0..size-1]
（您只能检查所有线程是否已完成；在此之前，不能保证已data[0..counter-1]完成写入或类似的操作。即使有seq_cst增量，您也可以让一个线程声明一个i值，但在访问该值之前会停止或调度很长时间data[i].所以任何数组元素仍然可以被修改。）
fetch_add(128, relaxed)...并循环这些i值？假设是的，但实际上不是。请参阅为什么编译器不合并冗余的 std::atomic 写入？- 编译器根本不优化原子，除了在允许的情况下重新排序非原子操作。
假设，编译器甚至可以静态地决定编译它，因此它总是在一个线程执行所有增量的情况下运行，而另一个线程不执行任何操作。（除了最后一个退出循环的）。例如，首先执行+= 1 mil然后循环这些i值。这不是一个正确性问题，对于编译器来说实际上这样做是非常疯狂的。这不是你需要排除的事情。
即使您使用seq_cst，足够智能的 Deathstation 9000 编译器也可以分析整个程序并发现没有任何内容与 的值同步counter，因此它仍然可以进行相同的转换。如果有任何东西观察到 的最终值counter，它还必须确保counter = size + nthreads它不能只fetch_add(1'000'000)在两个线程中执行。
像 4096 字节或整数这样的批量大小是有意义的。声明要处理 4096 个元素并进行循环i + 0..4095允许内部循环使用 SIMD，并且在下一个慢速原子 RMW 之前有大量正在进行的工作，该 RMW 必须等待counter缓存行在线程之间反弹。
仅让一个线程访问包含一系列data[]值的缓存行可以避免这些缓存行的跳动。因此，如果对齐，一个 64 字节缓存行是您可能想要使用的最小批处理大小data[]，否则您需要更大的批处理，因此只有在批处理末尾进行分割。但无论如何，您都需要更大的批次，因为 64 字节只是几个或几个 SIMD 加载/存储。
如果data[]是页对齐的，那么页大小的块意味着只有一个线程需要该页的 dTLB 未命中，并且现代 x86 CPU 上的硬件预取会在页边界处停止（因为连续的虚拟页可能不是物理上连续的。）所以这是很自然的结束批处理的地方，硬件预取不会为处理下一个块的线程创建争用。
特别是在 x86 上，其中每个原子 RMW 都是有效的seq_cst，并且是 asm 中的完整内存屏障，您希望使批量大小足够大以分摊这些成本。尽可能大，如果一个线程停止或发生其他情况，最后不会留下大量剩余工作。