c++ 为什么没有一个主要的编译器优化这个检查值是否已经设置的条件存储?

ymdaylpp  于 2023-05-19  发布在  其他
关注(0)|答案(4)|浏览(144)

我偶然发现了this Reddit帖子,这是对以下代码片段的一个笑话,

void f(int& x) {
    if (x != 1) {
        x = 1;
    }
}
void g(int& x) {
    x = 1;
}

说明这两个函数不等同于“编译器”。我确信任何主要的C++编译器都会将条件赋值优化为无条件存储,从而为fg发出相同的汇编代码。
However, they don't.
有谁能给我解释一下为什么会这样?
我的想法是这样的:无条件存储很可能会更快,因为我们无论如何都要访问内存来读取比较的值,并且分支代码会给分支预测器带来压力。此外,存储不应被编译器(AFAIK)视为副作用,即使后续的内存访问可能会更快或更慢,这取决于f中的分支是否被采用,这是由于缓存的局部性。
那么,编译器是不是就不能解决这个问题呢?虽然fg的等价性不一定是微不足道的证明,但我觉得这些编译器能够解决更困难的问题。那么是我错了,这些函数并不等价,还是这是怎么回事?

2uluyalo

2uluyalo1#

对象可能是const

static const int val = 1;存在于只读存储器中是不安全的。无条件存储版本将在尝试写入只读内存时发生segfault。
首先检查的版本在C++抽象机中调用该对象是安全的(通过const_cast),因此优化器必须考虑任何未写入的对象最初是const并且在只读内存中的可能性。

在一个系统,默默地忽略了尝试写一个只读地址,或只有读+写RAM,这不会是一个问题。但是像x86-64这样的主流非嵌入式平台确实有内存保护,一些嵌入式目标可能会在尝试存储到ROM时出错。在抽象机中写一个const对象仍然是C++ UB,但是理论上,编译器可以在为一个系统生成asm时发明已经存在的值的写入,如果其他限制不阻止它的话。如果编译器开发人员实际上编写和维护代码来花费编译时间寻找这种优化,这是不可能的。

线程安全(这种情况下可能没问题)

一般来说,编译器不能对抽象机器没有写的对象进行写操作,以防另一个线程也在写它,而我们会踩到这个值。例如,x.store(x.load())可以将x重置回较早的值,使另一个线程的x++丢失计数。(除了原子RMW是安全的,就像一个比较交换,只有当值已经是0时,它才原子地存储0
由于我们已经读取了对象(并且在读取和潜在的写入之间没有任何其他线程可以同步),我们可以假设没有其他线程写入,因为这将是无条件读取的数据竞争UB。
在这种情况下,看到任何其他值都将导致存储,因此任何对其他线程存储的值的步进都可以同样很好地解释为if也在其他存储之后运行,并且看到非1值,然后决定存储1。(除非无条件存储可能存在内存排序问题?我认为在一个无竞争的程序中可能不会,尤其是在为具有强有序内存模型的x86编译时。
我认为线程安全对于这种情况来说不是一个真实的的问题,假设在asm中存储int是原子地完成的,所以在no-UB情况下,其他线程都将读取1,其中没有任何其他写入器可以与此函数的执行重叠。
但一般来说,发明非原子加载+存储回相同的值在实践中一直是编译器的线程安全问题(例如我似乎记得阅读到IA-64 GCC对奇数长度memcpy或位字段或其他东西的数组末尾的字节进行了处理,当它位于uint8_t lock旁边的结构中时,这是个坏消息。)因此编译器开发人员有理由不愿意发明存储。

  • Crash with icc: can the compiler invent writes where none existed in the abstract machine?一个ICC在自动向量化时发明写入的真实的案例(对于更正常的条件替换循环),导致字符串字面量崩溃,以及线程不安全。这是/曾经是一个编译器错误,AVX-512屏蔽存储解决了这类问题。(或者通过编写像arr[i] = arr[i] == x ? new : arr[i];这样的源代码来无条件地存储 something,在这种情况下,你当然不能在只读内存中调用它,并且让编译器知道它不必担心在其他线程的情况下避免非原子RMW。它可以通过屏蔽来优化存储,但它不能发明新的存储)。
  • https://herbsutter.com/2013/02/11/atomic-weapons-the-c-memory-model-and-modern-hardware/在他的演讲的第2部分提到了一些已经被修复的现实世界的编译器bug,其中编译器确实以违反C++11内存模型的方式发明了写操作,并导致了一些问题,比如我提到的IA-64问题。
  • LWN:Who's afraid of a big bad optimizing compiler?-编译器 * 可以 * 对非原子非易失性访问执行的操作的清单,如果您试图跳过volatile进行访问,则滚动您自己的原子(如Linux内核所做的)可能会出现问题。虚拟存储只可能用于已经明确存储到对象的代码路径,但虚拟加载总是可能用于实际对象或C引用,尽管不是指针derefs。(C引用是不可空的,我认为只能在有效对象上使用,不像指向数组末尾的指针。但是John Bollinger指出引用可能比原始对象更持久,变得陈旧。在有这种可能性的情况下,如果指向的内存可能已经被系统调用取消Map,那么虚构的加载就不安全了。)
    注1:原子性

对于大多数C实现,原子存储是trivial in asm,这需要int对齐,并在具有寄存器和内部数据路径的机器上运行,至少与int一样宽。但在这种情况下,原子性实际上并不是必需的:一次存储1字节也是可以的。如果没有其他写入器,则用已经存在的值重写每个字节不会更改该值。如果有其他作者,在C抽象机中有UB,我们只是改变了症状。例如,如果另一个线程在我们存储了4个字节中的3个之后存储了-1,则最终结果是0x00ffffff
问题是暂时在内存中留下不同的值,例如通过清除整个东西为零,然后设置低位,就像超级猫建议的那样。这将允许在抽象机器中真正发生的赋值。(但可能只有在Deathstation 9000编译器故意敌对并在尽可能多的情况下使用UB破坏代码时才有可能。与真实的的编译器相反,真正的编译器设计时考虑了系统/内核编程和手动原子,如Linux内核使用的。
因为C变量不是atomic<>,所以我们不能破坏由不同线程领导的发布序列。在ISO C中,没有什么可以合法地在普通的-int上加载acquire。但在GNU C++中,它们可以使用__atomic_load_n(&x, __ATOMIC_ACQUIRE)

尊重源代码选择的性能原因

如果多个线程在同一对象上运行此代码,则无条件写入在正常CPU架构上是安全的,但要慢得多(对该高速缓存行的MESI独占所有权的争用,与共享。)
弄脏高速缓存行也是可能不期望的。
(And因为它们都存储相同的值。如果甚至一个线程正在存储不同的值,如果它碰巧不是修改顺序中的最后一个,则它可能使该存储被覆盖,该修改顺序由CPU获得高速该高速缓存行的所有权以提交它们的存储的顺序确定。
这种写前检查的习惯用法实际上是一些多线程代码会做的事情,以避免在变量上的缓存行乒乓,如果每个线程都写入已经存在的值,那么这些变量将高度竞争:

还有相关的CPU架构注意事项:

  • x86如何处理存储条件指令?(它不会,除了AVX或AVX-512掩蔽商店。这不是很相关,因为您仍然必须首先读取以生成条件。x86 cmpxchg执行==而不是!=比较。使用lock cmpxchg来获取原子RMW以确保没有线程安全问题,总是会弄脏该高速缓存行。)
  • What specifically marks an x86 cache line as dirty - any write, or is an explicit change required?-硬件中的静默存储优化可能是两全其美的,当软件对已经存在的值进行无条件存储时,可能甚至不需要该高速缓存获得行的独占所有权。但是据我所知,没有CPU实际上对L1 d进行静默存储优化。不幸的是,一些用于L3的(Skylake and Ice Lake用于存储全零缓存行)具有disabled it in microcode,因为可能存在数据依赖定时侧通道。
  • 通过内联汇编锁定内存操作-以及关于Does cmpxchg write destination cache line on failure? If not, is it better than xchg for spinlock? re:纯读之后是写的事实可能导致该高速缓存行的两个核外请求:一个用于使其处于MESI共享状态,然后是读取所有权(RFO)以获得独占所有权。这与自旋锁或互斥锁的问题相同,如果您开始悲观,并在尝试lock cmpxchgxchg之前先检查只读,尽量不干扰其他核心。

在这种情况下,如果您不希望在大部分时间内避免存储,那么您应该无条件地这样做,这样就只有来自写请求的RFO,而不是更早的共享请求。(这也避免了可能的分支错误预测,或者在32位ARM上,其中Assert存储是可能的,避免了等待加载的停顿。store buffer可以将执行与提交到缓存的缓存未命中存储分离。)

nle07wnf

nle07wnf2#

这是否构成优化取决于x为非1的频率,这是C编译器事先不知道的。如果x几乎总是1,那么if( x != 1 ) return可能比x = 1快。
(有趣的是,一些虚拟机,如Java虚拟机,确实在运行时分析执行模式,并在运行中执行这样的优化,如果事实证明他们的假设是错误的,他们甚至可以撤销这样的优化,所以理论上,他们可以在某些边缘情况下胜过C
,如果我们相信在运行时分析执行模式的开销小于它们保存的开销。我真的不知道。我只是觉得他们这样做很有趣。)

u3r8eeie

u3r8eeie3#

对我来说,最明显的答案是,这种优化不值得努力实现。这不是频繁发生的代码模式,并且执行优化的增益太小。在编写编译器时,总是要权衡要实现哪些优化。添加优化需要时间,并且增加了代码的复杂性,并且对于在“真实的代码”中很少发生的事情或者增益非常小的事情这样做只是浪费时间。类似这样的东西只有在从更一般的优化中自然福尔斯时才能被优化。

zqdjd7g9

zqdjd7g94#

编译器可以指定它的输出必须以这样一种方式被链接和使用,即所有可以从代码中访问的对象--包括标记为const的对象--都将位于存储器中,该存储器被配置为使得任意数量的写入相同值的操作一旦被执行就将无效。所指示的优化变换在记录了关于如何使用其输出的这种限制的编译器上将是合理的。
然而,大多数编译器供应商可能会认为,使生成的代码在更广泛的上下文中可用的价值高于由于这种限制而可能实现的任何附加优化的价值,特别是因为依赖于这种限制的代码将不能与由未被设计为支持它们的其他实现或环境处理的代码互操作。

相关问题