以原子方式更新整数数组元素 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> 的研究中，我忘记了构造原子对象也构造了受保护的成员。（还有很多答案解释了为什么你不能做 std::vector<std::atomic<int> > ）

Answer 1

一种方式：

// 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<>复制构造函数，因此vector不能调整大小，需要用元素的最终计数进行初始化。

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

// 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);

Answer 2

C++20 / C++2a（或任何你想称呼它的东西）将添加 std::atomic_ref<T> ，它允许你对不是 [= 的对象执行原子操作13=] 开头。

它还不可用作为大多数编译器的标准库的一部分，但[=80=有一个有效的实现] / 其他带有 GNU 扩展的编译器。

以前，对 "plain" 数据的原子访问仅适用于一些特定于平台的函数，例如 Microsoft 的 LONG 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 到您想要访问的元素。（在任何 "normal" C++ 实现上，它都可以免费实例化为本地，至少当它是无锁时）。

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

尚未在 libstdc++ 或 libc++ 中实现 gcc/clang。

#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，这些编译完全符合我们希望使用 GCC 的方式，使用 C++ 工作组提案中链接的示例实现（用于实现 GNU 扩展的编译器）。 https://github.com/ORNL/cpp-proposals-pub/blob/master/P0019/atomic_ref.hpp

From the Godbolt compiler explorer with g++8.2 -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 中是如何工作的。

大多数非 x86 ISA（如 AArch64）当然需要 LL/SC 重试循环来实现原子 RMW，即使内存顺序宽松也是如此。

这里的重点是构造/销毁atomic_ref不需要任何成本。它的成员指针完全优化掉了。所以这 和 vector<atomic<int>> 一样便宜，但没有令人头疼的问题。

只要您注意不要通过调整矢量大小或访问元素而不通过 atomic_ref 来创建数据争用 UB。（如果 std::vector 重新分配内存与另一个索引到它的线程并行，它可能会在许多实际实现中表现为释放后使用，当然你会原子地修改一个陈旧的副本。）

如果你不小心尊重 std::vector 对象本身不是原子的事实，并且编译器不会阻止你做非原子的，这肯定会给你上吊的绳索在其他线程开始使用它之后访问底层 v[idx]。

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

update integer array elements atomically C++

thread-safety

c++11

stdatomic