为什么编译器没有合并多余的std :: atomic写入?

问题描述 投票:47回答:9

我想知道为什么没有编译器准备将相同值的连续写入合并到单个原子变量,例如:

#include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
  y.store(1, order);
  y.store(1, order);
}

我尝试过的每个编译器都会发出三次上面的编写。什么合法的,无种族的观察者可以看到上述代码与具有单次写入的优化版本之间的差异(即,不是“假设”规则适用)?

如果变量是易变的,那么显然不适用优化。在我的情况下有什么阻止它?

这是compiler explorer中的代码。

c++ multithreading c++11 compiler-optimization stdatomic
9个回答
35
投票

所编写的C ++ 11 / C ++ 14标准允许将三个商店折叠/合并到最终值的一个商店中。即使在这样的情况下:

  y.store(1, order);
  y.store(2, order);
  y.store(3, order); // inlining + constant-folding could produce this in real code

该标准并不保证在y(带有原子载荷或CAS)上旋转的观察者会看到y == 2。依赖于此的程序会产生数据争用错误,但只有花园种类的错误种类,而不是C ++未定义行为类型的数据竞争。 (只有非原子变量才是UB)。期望有时看到它的程序不一定是错误的。 (见下文:进度条。)

可以在C ++抽象机器上选择任何可能的排序(在编译时)作为始终发生的排序。这是执行中的as-if规则。在这种情况下,就好像所有三家商店在全球订单中背靠背发生一样,y=1y=3之间没有其他线程的负载或商店。

它不依赖于目标架构或硬件;就像compile-time reordering放松的原子操作一样,即使是针对强烈排序的x86也是如此。编译器不必保留您考虑所编译的硬件时可能期望的任何内容,因此您需要屏障。障碍可以编译为零asm指令。


So why don't compilers do this optimization?

这是一个实施质量问题,可以改变实际硬件上观察到的性能/行为。

最明显的问题是进度条。将商店从一个循环中沉没(不包含其他原子操作)并将它们全部折叠成一个将导致进度条保持在0然后在最后100%正确。

没有C ++ 11 std::atomic方法可以阻止它们在你不需要它的情况下这样做,所以现在编译器只需选择永远不会将多个原子操作合并为一个。 (将它们合并为一个操作不会改变它们相对于彼此的顺序。)

编译器编写者已经正确地注意到程序员期望每次源执行y.store()时,原子存储实际上会发生在内存中。 (参见这个问题的大多数其他答案,声称商店需要单独发生,因为可能的读者等待看到中间值。)即它违反了principle of least surprise

但是,有些情况下它会非常有用,例如在循环中避免无用的shared_ptr ref count inc / dec。

显然,任何重新排序或合并都不能违反任何其他订购规则。例如,num++; num--;仍然必须是运行时和编译时重新排序的完全障碍,即使它不再触及num的内存。


正在讨论扩展std::atomic API以使程序员能够控制这种优化,此时编译器将能够在有用时进行优化,即使在非故意低效的精心编写的代码中也可能发生。以下工作组讨论/提案链接中提到了一些有用的优化案例示例:

另请参阅有关Richard Hodges对Can num++ be atomic for 'int num'?的回答的相同主题的讨论(请参阅注释)。另请参阅my answer的最后一节到同一个问题,我更详细地论证了这种优化是允许的。 (在此处简短说明,因为那些C ++工作组链接已经承认当前编写的标准允许它,并且当前的编译器不会故意优化。)


在当前标准中,volatile atomic<int> y将是确保不允许对其进行优化的一种方式。 (正如Herb Sutter points out in an SO answervolatileatomic已经有一些要求,但它们是不同的)。另见cppreference上的std::memory_order's relationship with volatile

不允许对volatile对象的访问进行优化(例如,因为它们可能是内存映射的IO寄存器)。

使用volatile atomic<T>主要修复了进度条问题,但它有点难看,如果/当C ++决定使用不同的语法来控制优化时,它可能看起来很傻,因此编译器可以在实践中开始这样做。

我认为我们可以确信编译器在有办法控制它之前不会开始进行这种优化。希望它会成为某种选择(如memory_order_release_coalesce),当编译为C ++时,它不会改变现有代码C ++ 11/14代码的行为。但它可能类似于wg21 / p0062中的提议:使用[[brittle_atomic]]标记不优化案例。

wg21 / p0062警告说,即使是volatile atomic也无法解决所有问题,并且不鼓励将其用于此目的。它给出了这个例子:

if(x) {
    foo();
    y.store(0);
} else {
    bar();
    y.store(0);  // release a lock before a long-running loop
    for() {...} // loop contains no atomics or volatiles
}
// A compiler can merge the stores into a y.store(0) here.

即使使用volatile atomic<int> y,也允许编译器将y.store()if/else中剔除,只需执行一次,因为它仍然只使用相同的值进行1次存储。 (这将在else分支中的长循环之后)。特别是如果商店只有relaxedrelease而不是seq_cst

volatile确实停止了问题中讨论的合并,但是这指出对atomic<>的其他优化也可能对实际性能有问题。


不优化的其他原因包括:没有人编写复杂的代码,允许编译器安全地进行这些优化(不会出错)。这还不够,因为N4455说LLVM已经实现或者可以轻松实现它提到的几个优化。

然而,令人困惑的程序员理由肯定是合理的。无锁代码很难在一开始就正确编写。

在使用原子武器时不要随意:它们不便宜并且不会进行太多优化(目前根本没有)。但是,使用std::shared_ptr<T>避免冗余原子操作并不总是那么容易,因为它没有非原子版本(尽管one of the answers here提供了一种简单的方法来为gcc定义shared_ptr_unsynchronized<T>)。


41
投票

你指的是淘汰死亡店。

不禁止消除原子死存储,但是更难以证明原子存储符合这样。

传统的编译器优化(例如死存储消除)可以在原子操作上执行,甚至是顺序一致的。 优化器必须小心避免跨同步点这样做,因为另一个执行线程可以观察或修改内存,这意味着传统的优化必须考虑比考虑优化原子操作时通常更多的干预指令。 在消除死存储的情况下,仅仅证明原子存储在后面占优势并且别名为另一个以消除其他存储是不够的。

来自N4455 No Sane Compiler Would Optimize Atomics

在一般情况下,原子DSE的问题在于它涉及寻找同步点,在我的理解中,这个术语意味着代码中的点,其中在线程A上的指令和另一个线程B上的指令之间存在关系。 。

考虑一下线程A执行的代码:

y.store(1, std::memory_order_seq_cst);
y.store(2, std::memory_order_seq_cst);
y.store(3, std::memory_order_seq_cst);

它可以优化为y.store(3, std::memory_order_seq_cst)

如果线程B正在等待查看y = 2(例如,使用CAS),如果代码得到优化,它将永远不会观察到。

但是,根据我的理解,在y = 2上进行B循环和CASsing是一个数据竞争,因为两个线程的指令之间没有总顺序。 在B循环之前执行A指令的执行是可观察的(即允许的),因此编译器可以优化到y.store(3, std::memory_order_seq_cst)

如果线程A和B在线程A中的存储之间以某种方式同步,那么将不允许优化(将引发部分顺序,可能导致B可能观察到y = 2)。

证明没有这样的同步是很困难的,因为它涉及考虑更广泛的范围并考虑到架构的所有怪癖。

至于我的理解,由于原子操作的年龄相对较小以及难以推断内存排序,可见性和同步,编译器不会对原子进行所有可能的优化,直到用于检测和理解必要的更强大的框架为止。条件已建立。

我相信你的例子是上面给出的计数线程的简化,因为它没有任何其他线程或任何同步点,我可以看到,我想编译器可以优化三个存储。


9
投票

当您在一个线程中更改原子的值时,某些其他线程可能正在检查它并根据原子的值执行操作。您给出的示例是如此具体,以至于编译器开发人员认为不值得优化。但是,如果一个线程正在设置,例如原子的连续值:012等,另一个线程可能是在原子的值所指示的槽中放入一些东西。


5
投票

简而言之,因为标准(例如[intro.multithread]中20和20左右的paragaraphs)不允许它。

必须满足之前发生的事先保证,除其他事项外,还排除重新排序或合并写入(第19段甚至明确说明了重新排序)。

如果你的线程一个接一个地将三个值写入内存(比如说1,2和3),则另一个线程可能会读取该值。例如,如果您的线程被中断(或者即使它并发运行)并且另一个线程也写入该位置,那么观察线程必须以完全相同的顺序看到操作(通过调度或巧合,或者无论什么原因)。这是一个保证。

如果你只做了一半的写入(甚至只有一次写入),这怎么可能?事实并非如此。

如果你的线程写出1 -1 -1而另一个偶尔写出2或3怎么办?如果第三个线程观察到该位置并等待一个从未出现的特定值,因为它已被优化,该怎么办?

如果未按要求执行存储(以及加载),则无法提供给出的保证。所有这些,并以相同的顺序。


5
投票

NB:我打算对此发表评论,但这有点过于罗嗦。

一个有趣的事实是,这种行为不是在C ++数据竞争方面。

第14页的注释21很有意思:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3690.pdf(我的重点):

程序的执行包含数据争用,如果它在不同的线程中包含两个冲突的动作,其中至少有一个不是原子的

另见第11页注5:

“轻松”原子操作不是同步操作,即使像同步操作一样,它们也无法为数据竞争做出贡献。

因此,就C ++标准而言,对原子的冲突行为绝不是数据竞争。

这些操作都是原子的(并且特别放松),但这里没有数据竞争!

我同意在任何(合理的)平台上这两者之间没有可靠/可预测的差异:

include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
  y.store(1, order);
  y.store(1, order);
}

include <atomic>
std::atomic<int> y(0);
void f() {
  auto order = std::memory_order_relaxed;
  y.store(1, order);
}

但是在提供C ++内存模型的定义中,它不是数据竞争。

我不能轻易理解为什么提供这个定义,但它确实向开发人员提供了一些卡片,以便他们可能知道(在他们的平台上)在统计上可以工作的线程之间进行偶然的通信。

例如,将值设置3次然后将其读回将显示该位置的某种程度的争用。这些方法不是确定性的,但许多有效的并发算法不是确定性的。例如,超时的try_lock_until()总是一种竞争条件,但仍然是一种有用的技术。

看起来C ++标准为你提供了围绕'数据竞赛'的确定性,但允许某些有竞争条件的娱乐和游戏,最终分析不同的东西。

简而言之,标准似乎指出,其他线程可能会看到值被设置3次的“锤击”效果,其他线程必须能够看到该效果(即使它们有时可能不会!)。在其他线程可能在某些情况下看到锤击的几乎所有现代平台都是如此。


2
投票

模式的实际用例,如果线程在不依赖或修改y的更新之间执行重要操作,则可能是:*线程2读取y的值以检查线程1进行了多少进度。

因此,也许线程1应该将配置文件加载为步骤1,将其解析后的内容作为步骤2放入数据结构中,并将主窗口显示为步骤3,而线程2则等待步骤2完成,以便它可以并行执行另一个任务,取决于数据结构。 (当然,这个例子调用了获取/释放语义,而不是放松的排序。)

我很确定一致的实现允许线程1不在任何中间步骤更新y - 虽然我没有仔细考虑语言标准,如果它不支持另一个线程轮询y可能永远不会看到的硬件,我会感到震惊价值2。

但是,这是一个假设的实例,它可能是最重要的,以优化状态更新。也许编译器开发人员会来这里说出为什么编译器选择不这样做,但是一个可能的原因是让你自己开枪,或者至少让自己陷入脚趾。


0
投票

让我们走一点距离三个商店紧挨着的病态案例。让我们假设在商店之间进行了一些非平凡的工作,并且这样的工作根本不涉及y(因此数据路径分析可以确定三个存储实际上是多余的,至少在这个线程内),并且本身不会引入任何内存障碍(因此其他东西不会强制商店对其他线程可见)。现在很有可能其他线程有机会在商店之间完成工作,也许那些其他线程操纵y并且这个线程有一些理由需要将它重置为1(第二个商店)。如果前两个商店被删除,那将改变行为。


-1
投票

编译器编写器不能只执行优化。他们还必须说服自己,优化在编译器编写者打算应用它的情况下是有效的,它不会在无效的情况下应用,它不会破坏事实上被破坏的代码但是“ “适用于其他实施。这可能比优化本身更多的工作。

另一方面,我可以想象在实践中(即在应该完成工作的程序中,而不是基准测试),这种优化将节省很少的执行时间。

因此,编译器编写者将查看成本,然后查看收益和风险,并可能决定反对。


-2
投票

由于期望std :: atomic对象中包含的变量可以从多个线程访问,因此应该期望它们至少表现得像使用volatile关键字声明它们一样。

在CPU架构引入缓存行等之前,这是标准和推荐的做法。

[EDIT2]有人可能会说std :: atomic <>是多核时代的volatile变量。正如在C / C ++中定义的那样,volatile仅足以同步来自单个线程的原子读取,ISR修改变量(在这种情况下,实际上是从主线程看到的原子写入)。

我个人感到宽慰的是,没有编译器会优化写入原子变量。如果写入被优化掉,那么如何保证其他线程中的读者可能会看到这些写入中的每一个?不要忘记这也是std :: atomic <>契约的一部分。

考虑这段代码,结果会受到编译器的狂野优化的极大影响。

#include <atomic>
#include <thread>

static const int N{ 1000000 };
std::atomic<int> flag{1};
std::atomic<bool> do_run { true };

void write_1()
{
    while (do_run.load())
    {
        flag = 1; flag = 1; flag = 1; flag = 1;
        flag = 1; flag = 1; flag = 1; flag = 1;
        flag = 1; flag = 1; flag = 1; flag = 1;
        flag = 1; flag = 1; flag = 1; flag = 1;
    }
}

void write_0()
{
    while (do_run.load())
    {
        flag = -1; flag = -1; flag = -1; flag = -1;
    }
}


int main(int argc, char** argv) 
{
    int counter{};
    std::thread t0(&write_0);
    std::thread t1(&write_1);

    for (int i = 0; i < N; ++i)
    {
        counter += flag;
        std::this_thread::yield();
    }

    do_run = false;

    t0.join();
    t1.join();

    return counter;
}

[编辑]起初,我并没有提出volatile是原子实现的核心,但......

由于似乎怀疑volatile是否与原子有关,我调查了这个问题。这是VS2017 stl的原子实现。正如我所推测的那样,volatile关键字无处不在。

// from file atomic, line 264...

        // TEMPLATE CLASS _Atomic_impl
template<unsigned _Bytes>
    struct _Atomic_impl
    {   // struct for managing locks around operations on atomic types
    typedef _Uint1_t _My_int;   // "1 byte" means "no alignment required"

    constexpr _Atomic_impl() _NOEXCEPT
        : _My_flag(0)
        {   // default constructor
        }

    bool _Is_lock_free() const volatile
        {   // operations that use locks are not lock-free
        return (false);
        }

    void _Store(void *_Tgt, const void *_Src, memory_order _Order) volatile
        {   // lock and store
        _Atomic_copy(&_My_flag, _Bytes, _Tgt, _Src, _Order);
        }

    void _Load(void *_Tgt, const void *_Src,
        memory_order _Order) const volatile
        {   // lock and load
        _Atomic_copy(&_My_flag, _Bytes, _Tgt, _Src, _Order);
        }

    void _Exchange(void *_Left, void *_Right, memory_order _Order) volatile
        {   // lock and exchange
        _Atomic_exchange(&_My_flag, _Bytes, _Left, _Right, _Order);
        }

    bool _Compare_exchange_weak(
        void *_Tgt, void *_Exp, const void *_Value,
        memory_order _Order1, memory_order _Order2) volatile
        {   // lock and compare/exchange
        return (_Atomic_compare_exchange_weak(
            &_My_flag, _Bytes, _Tgt, _Exp, _Value, _Order1, _Order2));
        }

    bool _Compare_exchange_strong(
        void *_Tgt, void *_Exp, const void *_Value,
        memory_order _Order1, memory_order _Order2) volatile
        {   // lock and compare/exchange
        return (_Atomic_compare_exchange_strong(
            &_My_flag, _Bytes, _Tgt, _Exp, _Value, _Order1, _Order2));
        }

private:
    mutable _Atomic_flag_t _My_flag;
    };

MS stl中的所有特化都在关键函数上使用volatile。

这是关键功能之一的声明:

 inline int _Atomic_compare_exchange_strong_8(volatile _Uint8_t *_Tgt, _Uint8_t *_Exp, _Uint8_t _Value, memory_order _Order1, memory_order _Order2)

你会注意到所需的volatile uint8_t*持有std :: atomic中包含的值。在整个MS std :: atomic <>实现中可以观察到这种模式,gcc团队没有理由,也没有任何其他stl提供者以不同的方式完成它。

© www.soinside.com 2019 - 2024. All rights reserved.