以原子方式更新整数数组元素 C++

Question

给定一个共享的整数计数器数组，我想知道线程是否可以在不锁定整个数组的情况下自动获取和添加数组元素？

这是使用互斥锁锁定对整个数组的访问的工作模型的说明。

// thread-shared class members
std::mutex count_array_mutex_;
std::vector<int> counter_array_( 100ish );

// Thread critical section
int counter_index = ... // unpredictable index
int current_count;
{
  std::lock_guard<std::mutex> lock(count_array_mutex_);
  current_count = counter_array_[counter_index] ++;
}
// ... do stuff using current_count.

我希望多个线程能够同时获取添加单独的数组元素。

到目前为止，在我对std::atomic<int>I 的研究中，构造原子对象也构造了受保护的成员。（还有很多答案解释了为什么你不能做一个std::vector<std::atomic<int> >）

Answer 1

C++20/C++2a（或任何你想叫它的std::atomic_ref<T>名字）将添加它让你对一个不是atomic<T>开始的对象进行原子操作。

它尚未作为大多数编译器的标准库的一部分提供，但有一个适用于 gcc/clang/ICC/其他带有 GNU 扩展的编译器的工作实现。

以前，对“纯”数据的原子访问仅适用于某些特定于平台的功能，例如 MicrosoftLONG InterlockedExchange(LONG volatile *Target, LONG Value);或 GNU C/C++
type __atomic_add_fetch (type *ptr, type val, int memorder)（与 GNU 编译器的 C++ 库用于实现的内置函数相同std::atomic<T>。）

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0019r8.html包含一些关于动机的介绍内容。CPU 可以很容易地做到这一点，编译器已经可以做到这一点，而且 C++ 没有以可移植的方式公开此功能令人讨厌。

因此，不必与 C++ 搏斗以在构造函数中完成所有非原子分配和初始化，您只需让每次访问都为要访​​问的元素创建一个 atomic_ref。（在任何“普通”C++ 实现上，至少在无锁时，可以自由地实例化为本地对象）。

这甚至可以让您std::vector<int>在确保没有其他线程访问向量元素或vector控制块本身之后执行诸如调整大小之类的操作。然后你可以通知其他线程恢复。

它尚未在用于 gcc/clang 的 libstdc++ 或 libc++ 中实现。

#include <vector>
#include <atomic>

#define Foo std   // this atomic_ref.hpp puts it in namespace Foo, not std.
// current raw url for https://github.com/ORNL/cpp-proposals-pub/blob/master/P0019/atomic_ref.hpp
#include "https://raw.githubusercontent.com/ORNL/cpp-proposals-pub/580934e3b8cf886e09accedbb25e8be2d83304ae/P0019/atomic_ref.hpp"


void inc_element(std::vector<int> &v, size_t idx)
{
    v[idx]++;
}

void atomic_inc_element(std::vector<int> &v, size_t idx)
{
    std::atomic_ref<int> elem(v[idx]);
    static_assert(decltype(elem)::is_always_lock_free,
           "performance is going to suck without lock-free atomic_ref<T>");

    elem.fetch_add(1, std::memory_order_relaxed);  // take your pick of memory order here
}

对于 x86-64，使用 C++ 工作组提案中链接的示例实现（用于实现 GNU 扩展的编译器）完全按照我们希望使用 GCC 的方式进行编译。 https://github.com/ORNL/cpp-proposals-pub/blob/master/P0019/atomic_ref.hpp

来自带有 g++8.2 的 Godbolt 编译器资源管理器-Wall -O3 -std=gnu++2a：

inc_element(std::vector<int, std::allocator<int> >&, unsigned long):
    mov       rax, QWORD PTR [rdi]          # load the pointer member of std::vector
    add       DWORD PTR [rax+rsi*4], 1      # and index it as a memory destination
    ret

atomic_inc_element(std::vector<int, std::allocator<int> >&, unsigned long):
    mov       rax, QWORD PTR [rdi]
    lock add  DWORD PTR [rax+rsi*4], 1     # same but atomic RMW
    ret

原子版本是相同的，除了它使用lock前缀使读-修改-写原子化，确保没有其他内核可以在该内核进行原子修改时读取或写入缓存行。 以防万一你好奇原子在 asm 中是如何工作的。

大多数像 AArch64 这样的非 x86 ISA 当然需要一个 LL/SC 重试循环来实现原子 RMW，即使内存顺序很宽松。

这里的重点是构建/破坏atomic_ref不需要任何费用。 它的成员指针完全优化掉了。因此，这与完全一样便宜vector<atomic<int>>，但不会令人头疼。

只要您小心不要通过调整向量大小或不通过atomic_ref. （如果 std::vector 与另一个索引到它的线程并行地重新分配内存，它可能会在许多实际实现中表现为释放后使用，当然你会以原子方式修改过时的副本。）

如果您不仔细尊重std::vector对象本身不是原子的这一事实，并且编译器不会阻止您v[idx]在其他线程开始使用后对底层进行非原子访问，那么这绝对会让您陷入困境它。

Answer 2

单程：

// Create.
std::vector<std::atomic<int>> v(100);
// Initialize.
for(auto& e : v)
    e.store(0, std::memory_order_relaxed);

// Atomically increment.
auto unpredictable_index = std::rand() % v.size();
int old = v[unpredictable_index].fetch_add(1, std::memory_order_relaxed);

请注意，std::atomic<>复制构造函数被删除，因此向量无法调整大小，需要使用元素的最终计数进行初始化。

由于 的调整大小功能std::vector丢失，std::vector您也可以使用std::unique_ptr<std::atomic<int>[]>，例如：

// Create.
unsigned const N = 100;
std::unique_ptr<std::atomic<int>[]> p(new std::atomic<int>[N]);
// Initialize.
for(unsigned i = 0; i < N; ++i)
    p[i].store(0, std::memory_order_relaxed);

// Atomically increment.
auto unpredictable_index = std::rand() % N;
int old = p[unpredictable_index].fetch_add(1, std::memory_order_relaxed);