操作和无锁数据结构的重新排序

Question

假设我们有一个 Container 维护一组 int 值，并为每个值加上一个标志，指示该值是否有效。无效值被视为 INT_MAX。最初，所有值都是无效的。当第一次访问一个值时，它被设置为 INT_MAX 并且它的标志被设置为有效。

struct Container {
  int& operator[](int i) {
    if (!isValid[i]) {
      values[i] = INT_MAX; // (*)
      isValid[i] = true;   // (**)
    }
    return values[i];
  }
  std::vector<int> values;
  std::vector<bool> isValid;
};

现在，另一个线程同时读取容器值：

// This member is allowed to overestimate value i, but it must not underestimate it.
int Container::get(int i) {
  return isValid[i] ? values[i] : INT_MAX;
}

这是完全有效的代码，但重要的是 (*) 和 (**) 行按给定顺序执行。

在这种情况下，标准是否保证行按给定顺序执行？至少从单线程的角度来看，行可以互换，不是吗？
如果没有，确保订单的最有效方法是什么？这是高性能代码，所以我不能没有 -O3 并且不想使用 volatile.

Answer 1

这里没有同步。如果您从一个线程访问这些值并从另一个线程更改它们，则会出现未定义的行为。您要么需要锁定所有访问权限，在这种情况下一切都很好。否则，您需要将所有 std::vector 元素设为 atomic<T>，并且您可以使用适当的可见性参数控制值的可见性。

似乎对同步尤其是原子操作的作用存在误解：它们的目的是使代码更快！这可能看起来违反直觉，所以这里是解释：非原子 操作应该尽可能快，并且故意不保证它们如何准确访问内存。只要编译器和执行系统产生正确的结果，编译器和系统就可以自由地做他们需要或想做的任何事情。为了实现良好的性能，假定不存在不同线程之间的交互。

然而，在并发系统中，线程之间存在交互。这是原子操作进入阶段的地方：它们允许 精确指定必要的同步 。因此，它们允许告诉编译器它必须遵守的最小约束才能使线程取消交互正确。编译器将使用这些指标生成最佳代码以实现指定的目标。该代码可能与不使用任何同步的代码相同，尽管在实践中通常还需要防止 CPU 重新排序操作。因此，正确使用同步会产生最高效的代码，并且只需要绝对必要的开销。

棘手的部分是在某种程度上找到需要哪些同步并将它们最小化。简单地没有任何将允许编译器和 CPU 自由地重新排序操作并且将不起作用。

既然问题提到了volatile请注意volatile完全与并发无关！ volatile 的主要目的是通知系统地址指向内存，其访问可能有副作用。它主要用于映射内存 I/O 或访问硬件控制。死于潜在的副作用，它是 C++ 定义程序语义的两个方面之一（另一个是 I/O 使用标准库 I/O 设施）。

操作和无锁数据结构的重新排序

Reordering of operations and lock-free data structures

c++

gcc

c++14

compiler-optimization

lock-free