如果 RMW 操作没有任何改变,是否可以针对所有内存顺序对其进行优化?

If a RMW operation changes nothing, can it be optimized away, for all memory orders?

在C/C++内存模型中,编译器是否可以只合并然后删除redundant/NOP原子修改操作,例如:

x++,
x--;

甚至只是

x+=0; // return value is ignored

对于原子标量 x?

这适用于顺序一致性还是仅适用于较弱的内存顺序?

(注意:对于仍然做某事的较弱的记忆顺序;对于放松,这里没有真正的问题。再次编辑:在这种特殊情况下实际上没有一个严重的问题。请参阅我自己的答案。甚至不放松已获准移除。)

编辑:

问题不在于针对特定访问的代码生成:如果我想在第一个示例中看到在 Intel 上生成两个 lock add,我会让 x 易变。

问题是这些 C/C++ 指令是否有任何影响:编译器是否可以过滤并删除这些 nul 操作(不是松散的顺序操作),因为一种源到源的转换?(或抽象树到抽象树的转换,可能在编译器中 "front end")

编辑 2:

假设总结:

可选假设:

如果你愿意,你可以假设原子的地址没有被占用,所有访问都是按名称进行的,并且所有访问都有一个 属性:

  1. 在任何地方都不能访问那个变量,有一个宽松的 load/store 元素:所有加载操作都应该有获取,所有存储都应该有释放(所以所有 RMW 应该至少 load/store =104=]).

  2. 或者,对于那些放宽的访问,访问代码除了更改它之外不会读取值:放宽的 RMW 不会进一步保存值(并且不会测试该值以决定下一步做什么)。换句话说,除非负载具有获取.

  3. ,否则原子对象的值没有数据或控制依赖性
  4. 或者说原子的所有访问都是顺序一致的。

那是我对这些(我相信很常见的)用例特别好奇。

注意:不考虑访问 "completely relaxed",即使它是使用宽松的内存顺序完成的,当代码确保观察者具有相同的内存可见性时,所以这被认为对 (1) 和 (2) 有效:

atomic_thread_fence(std::memory_order_release);
x.store(1,std::memory_order_relaxed);

因为内存可见性至少与 x.store(1,std::memory_order_release);

一样好

这被认为对 (1) 和 (2) 有效:

int v = x.load(std::memory_order_relaxed);
atomic_thread_fence(std::memory_order_acquire);

出于同样的原因。

这对于 (2) 来说是愚蠢的、微不足道的有效(i 只是一个 int

i=x.load(std::memory_order_relaxed),i=0; // useless

因为没有保留来自轻松操作的信息。

这对 (2) 有效:

(void)x.fetch_add(1, std::memory_order_relaxed);

这对 (2) 无效:

if (x.load(std::memory_order_relaxed))
  f();
else
  g();

作为相应的决定是基于轻松的负载,

i += x.fetch_add(1, std::memory_order_release);

注意:(2) 涵盖了原子的最常见用途之一,即线程安全引用计数器。 (更正:目前尚不清楚所有线程安全计数器在技术上是否符合描述,因为获取只能在 0 post 递减时完成,然后根据计数器> 0 做出决定而无需获取;决定什么都不做但还是...)

C++ 内存模型为对同一原子对象的所有原子访问提供 four coherence requirements。这些要求适用而不管 内存顺序如何。如非规范符号所述:

The four preceding coherence requirements effectively disallow compiler reordering of atomic operations to a single object, even if both operations are relaxed loads.

添加了重点。

鉴于这两个操作都发生在同一个原子变量上,第一个肯定 happens before the second (due to being sequenced before 它),这些操作不能重新排序。同样,即使使用 relaxed 操作。

如果这对操作被编译器删除,那将保证没有其他线程会看到增加的值。所以现在的问题是标准是否需要其他线程才能看到增加的值。

没有。如果没有某种方法可以保证 "happen after" 增量 "happen before" 减量,则无法保证任何其他线程上的任何操作一定会看到增值。

这留下了一个问题:第二个操作是否总是撤消第一个操作?也就是说,减量会撤消增量吗?这取决于所讨论的标量类型。 ++ 和 -- 仅为 atomic 的指针和整数特化定义。所以我们只需要考虑那些。

对于指针,减量会撤消增量。原因是递增+递减指针不会导致指向同一对象的相同指针的唯一方法是递增指针本身就是 UB。也就是说,如果指针无效、NULL,或者是指向 object/array 的结束指针。但是编译器不必考虑 UB 案例,因为......它们是未定义的行为。在递增 有效 的所有情况下,指针递减也必须有效(或 UB,可能是由于有人释放内存或以其他方式使指针无效,但同样,编译器不会不必关心)。

对于无符号整数,递减总是会撤消递增,因为环绕行为对于无符号整数是明确定义的。

剩下有符号整数。 C++ 通常将有符号整数 over/underflow 转换为 UB。幸运的是,原子数学并非如此。标准 explicitly says:

For signed integer types, arithmetic is defined to use two's complement representation. There are no undefined results.

二进制补码原子的环绕行为有效。这意味着 increment/decrement 总是会恢复相同的值。

所以标准中似乎没有任何内容可以阻止编译器删除此类操作。同样,不管内存顺序如何

现在,如果您使用非松弛内存排序,则该实现无法完全删除原子的所有痕迹。这些排序背后的实际内存障碍仍然需要发出。但是可以在不发出实际原子操作的情况下发出障碍。

不,绝对不完全是。它至少是线程中的一个内存屏障,用于更强的内存顺序。


对于 mo_relaxed 原子,是的,我认为它在理论上可以完全优化掉,就好像它不存在于源代码中一样。这相当于一个线程根本不属于它可能属于的释放序列的一部分。

如果您使用 fetch_add(0, mo_relaxed) 的结果,那么我认为将它们折叠在一起并仅执行加载而不是 0 的 RMW 可能不完全等价。此线程中围绕宽松 RMW 的障碍仍然对 所有 操作有影响,包括订购宽松操作 wrt。非原子操作使用加载+存储 ,订购存储的东西可以订购原子 RMW,而它们不会订购纯负载。

但我不认为任何 C++ 排序都是这样的:mo_release 存储顺序较早的加载和存储,而 atomic_thread_fence(mo_release) 就像一个 asm StoreStore + LoadStore 屏障。 (Preshing on fences)。所以是的,假设任何 C++ 强加的顺序也适用于松弛的负载,同样适用于松弛的 RMW,我认为 int tmp = shared.fetch_add(0, mo_relaxed) 可以优化为仅负载。


(在实践中,编译器根本不优化原子,基本上像 volatile atomic 一样对待它们,即使是 mo_relaxed and http://wg21.link/n4455 + http://wg21.link/p0062。这太难了/不存在让编译器知道什么时候 不是 的机制。)

但是,纸面上的 ISO C++ 标准并不能保证其他线程实际上可以观察到任何给定的中间状态。

思想实验:考虑在单核协作多任务系统上的 C++ 实现。它通过在需要避免死锁的地方插入 yield 调用来实现 std::thread,但不是在每条指令之间。标准中的任何内容都不需要 num++num-- 之间的让步让其他线程观察该状态。

as-if 规则基本上允许编译器选择 legal/possible 顺序并在编译时决定它每次都会发生。

在实践中,如果 unlock/re-lock 实际上从未给其他线程获取锁的机会,如果 --/++ 组合在一起只是一个内存屏障,这可能会产生公平性问题不修改原子对象!这就是为什么编译器不优化的原因。


一个或两个操作的任何更强顺序可以开始或成为与reader同步的释放序列的一部分。 reader 获取发布 store/RMW 的加载与此线程同步,并且必须将此线程的所有先前效果视为已经发生。

IDK reader 怎么知道它看到的是 this 线程的释放存储而不是以前的一些值,所以一个真实的例子可能很难编造.至少我们可以创建一个没有可能的 UB,例如通过读取另一个松散原子变量的值,这样我们就可以在没有看到该值时避免数据争用 UB。

考虑序列:

// broken code where optimization could fix it
    memcpy(buf, stuff, sizeof(buf));

    done.store(1, mo_relaxed);       // relaxed: can reorder with memcpy
    done.fetch_add(-1, mo_relaxed);
    done.fetch_add(+1, mo_release);  // release-store publishes the result

可以 优化为仅 done.store(1, mo_release);,从而正确地将 1 发布到另一个线程,而不会有 1 可见的风险太快了,在更新 buf 值之前。

但它也可以将取消的 RMW 对优化为松弛存储之后的栅栏,这仍然会被破坏。 (而不是优化的错。)

// still broken
    memcpy(buf, stuff, sizeof(buf));

    done.store(1, mo_relaxed);       // relaxed: can reorder with memcpy
    atomic_thread_fence(mo_release);

我还没有想过这样一个例子,其中安全代码被这种看似合理的优化破坏了。当然,即使它们是 seq_cst 并不总是安全的。


seq_cst递增和递减仍然会造成某种内存障碍。如果不优化它们,早期的存储就不可能交错与后来的负载。为了保留这一点,为 x86 编译可能仍需要发出 mfence.

当然显而易见的事情是 lock add [x], 0,它确实对我们在 x++/x-- 上执行的共享对象执行虚拟 RMW。但我 认为 单独使用内存屏障,不耦合到对实际对象或缓存行的访问就足够了。

当然,它必须充当编译时内存屏障,阻止编译时对跨它的非原子和原子访问进行重新排序。

对于acq_rel或较弱的fetch_add(0)或取消序列,运行时内存屏障可能在x86上免费发生,只需要限制编译时顺序。

另请参阅我在 上的回答的一部分,以及对 Richard Hodges 的回答的评论。 (但请注意,其中一些讨论因关于何时对 ++-- 之间的其他对象进行修改的争论而混淆。当然,必须保留原子暗示的该线程操作的所有顺序。 )


正如我所说,这都是假设,真实的编译器不会优化原子,直到 N4455/P0062 尘埃落定。

In the C/C++ memory model, can a compiler just combine and then remove redundant/NOP atomic modification operations,

不,删除部分是不允许的,至少不允许以问题建议的特定方式进行:这里的目的是描述有效的源到源转换、抽象树到抽象树,或者更确切地说是一个源代码的更高级别描述,它编码了编译后期可能需要的所有相关语义元素。

假设可以在转换后的程序上生成代码,而无需与原始程序进行检查。所以只允许不能破坏任何代码的安全转换

(Note: For weaker memory orders that still do something; for relaxed, there is no real question here.)

没有。即使这样也是错误的:即使是宽松的操作,无条件删除也不是有效的转换(虽然在大多数实际情况下它肯定有效,但大部分正确仍然是错误的,并且"true in >99% practical cases" 与问题无关):

在引入标准线程之前,卡住的程序是一个无限循环是一个空循环执行没有外部可见的副作用:没有输入、输出、volatile 操作并且在实践中没有系统调用。一个永远不会执行可见事物的程序被卡住并且其行为未定义,并且允许编译器假设纯算法终止:仅包含不可见计算的循环必须以某种方式退出(包括异常退出)。

对于线程,这个定义显然是不可用的:一个线程中的循环不是整个程序,一个卡住的程序实际上是一个没有线程可以提供有用的东西的程序,禁止这样做是合理的。

但是卡住的非常有问题的标准定义并没有描述程序执行,而是描述了单个线程:如果线程不执行可能对可观察到的副作用产生影响的副作用,则该线程被卡住,即:

  1. 明显没有观察到(没有I/O)
  2. 没有可能与另一个线程交互的操作

2.的标准定义非常庞大和简单,线程间通信设备上的所有操作都算在内:任何原子操作,任何互斥体上的任何操作。需求全文(相关部分以粗体显示):

[intro.progress]

The implementation may assume that any thread will eventually do one of the following:

  • terminate,
  • make a call to a library I/O function,
  • perform an access through a volatile glvalue, or
  • perform a synchronization operation or an atomic operation.

[ Note: This is intended to allow compiler transformations such as removal of empty loops, even when termination cannot be proven. — end note ]

该定义甚至没有指定:

  • 线程间通信(从一个线程到另一个线程)
  • 共享状态(多线程可见)
  • 一些状态的修改
  • 不是线程私有的对象

这意味着所有这些愚蠢的操作都很重要:

  • 用于 围栏:

    • 在至少完成一次原子存储的线程中执行获取栅栏(即使后面没有原子操作)可以与另一个栅栏或原子操作同步
  • 对于 互斥体:

    • 锁定本地最近创建的、显然无用的函数专用互斥体;
    • 锁定一个互斥量只是将其解锁,而互斥量已锁定;
  • 对于原子:

    • 读取声明为 const 限定的原子变量(不是对非 const 原子的 const 引用);
    • 读取原子,忽略值,即使使用宽松的内存排序;
    • 将非 const 限定原子设置为它自己的不可变值(当整个程序中没有任何内容将其设置为非零值时将变量设置为零),即使是宽松的排序;;
    • 对其他线程无法访问的局部原子变量进行操作;
  • 对于线程操作:

    • 创建一个线程(可能什么都不做)并加入它似乎创建了一个 (NOP) 同步操作。

这意味着没有早期的、本地的程序代码转换这不会留下转换到后期编译器阶段的痕迹,甚至删除最愚蠢和无用的线程间原语根据标准绝对无条件有效,因为它可能会删除循环中最后一个可能有用(但实际上无用)的操作(循环不会不必拼写 forwhile,它是任何循环结构,f.ex。向后 goto).

然而,如果线程间原语上的其他操作留在循环中,或者显然如果 I/O 已完成,则这不适用。

这看起来像是一个缺陷。

有意义的要求应基于:

  • 不仅在使用线程原语上,
  • 不是关于孤立的任何线程(因为你看不到线程是否对任何事情有贡献,但至少要求与另一个线程进行有意义的交互并且不使用私有原子或互斥锁会更好当前要求),
  • 基于做一些有用的事情(程序可观察)和有助于完成某事的线程间交互。

我现在不建议替换,因为线程规范的其余部分我什至不清楚。