c++ - 对于C++中的原子更新，最有效的CAS实现是什么？

我编写了并行程序，该程序使用CAS操作对线程之间的共享内存进行更新。 (C++，Linux，x86)

以下是我对“更新”功能的实现，该功能对变量a所指向的内存位置(由f(* a，b)返回的值)应用更新。

inline bool CAS (int64_t* ptr, int64_t old_val, int64_t new_val) {
    return __sync_bool_compare_and_swap(ptr, old_val, new_val);
}

inline void Update(int64_t* a, int64_t& b) {
    volatile int64_t expected, result;
    do {
        expected = *a;
        result = f(expected, b);
    } while (!CAS(a, expected, result));
}

我看到大多数其他实现都使用几乎相同的代码。

但是我只是想知道它是否是最有效的，因为我从Vtune探查器中看到了相当高的CPI率(1.2〜1.5)。

如果从嵌套计算循环的最内部循环调用Update函数，则 do ... while()带有分支的循环会引起严重的分支错误预测。但是考虑到CAS的语义包括要进行比较的分支，这可能是不可避免的。

在任何情况下，上面的Update函数是否都具有首选的实现方式？
例如，在某些情况下，compare-exchange-strong可以战胜compare-exchange-weak。如果Update函数中的函数f用于加法运算，则首选使用std::atomic提供的atomic_fetch_and_add。

//这是带有注释的更新代码(未观察到性能提升，我在进行微优化。但是，无论如何，在最坏的情况下它可能会更好)

inline bool CAS (int64_t* ptr, int64_t& old_val, int64_t new_val) {
    return (std::atomic_compare_exchange_weak((std::atomic<int64_t>*) ptr, &old_val, new_val);
}

inline void Update(int64_t* a, int64_t& b) {
    int64_t expected, result;
    do {
        expected = *a;
        result = f(expected, b);
    } while (!CAS(a, expected, result));
}

最佳答案

标准库在<atomic>函数系列 atomic_compare_exchange_weak() 中对此具有可移植的实现。您可能会因此获得更好的性能。如果读取器线程仅需要一些快照，则可以用宽松的内存顺序进行原子读取，如果需要最新的则可以进行获取。宽松的内存顺序可能和读取内存一样简单。

但是，大多数性能改进可能来自更好的免等待数据结构和算法。对于CAS，单链接列表通常是非常快速的免等待结构。

有一些特殊情况。我相信您知道，如果只有一个线程是编写者，那么其他线程就可以简单地读取具有获取/释放语义甚至放松的内存顺序的更新。 (或者，作为一个gcc/clang扩展名，通过volatile*来匹配您所使用的内置函数。)

如果您经常看到其他线程完成并尝试同时进行更新，则可能有一种方法可以更改算法以将工作人员隔开。在某些算法中，可能有原因的线程看到更新后退并屈服于其他线程。

也要警惕A-B-A错误。您似乎没有对其进行检查。如果不需要，您可以立即使用cmpxch16b指令对16字节结构的CAS进行操作，从而获得比对单个指针进行CAS更好的原子更新。

关于c++ - 对于C++中的原子更新，最有效的CAS实现是什么？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/42940616/