"获取"和"消费"内存顺序有何不同,何时"消费"更可取？

Question

C++ 11标准定义了一个内存模型(1.7,1.10),它包含内存排序,大致是"顺序一致","获取","消费","释放"和"放松".同样粗略地说,程序只有在没有竞争的情况下才是正确的,如果所有动作都可以按照某个动作的顺序放在另一个动作之前,则会发生这种情况.动作 X发生的方式 - 在动作Y 之前是X在Y之前(在一个线程内)被排序,或者X在线程间 - 在Y之前发生.其中,后者的条件是在何时

• X与Y同步,或
• X在Y之前是依赖排序的.

当X是在某个原子变量上具有"释放"排序的原子存储时发生同步,并且Y是在同一变量上具有"获取"排序的原子加载.作为依赖项,订购前发生了类似的情况,其中Ÿ是负载"消费"排序(和合适的内存访问).的概念下同步,与延伸的之前发生关系传递性跨越的行动被测序,之前彼此线程内,但被相关性排序,之前只有通过严格的子集传递性扩展测序,之前叫依赖于大规模规则的依赖性,特别是可以被中断std::kill_dependency.

那么,"依赖性排序"概念的目的是什么？与简单的排序 - 先前/同步 -排序相比,它提供了什么优势？由于它的规则更严格,我认为可以更有效地实施.

你能举一个程序的例子,从发布/获取到发布/消费的转换是正确的,并提供一个非平凡的优势吗？何时能std::kill_dependency提供改进？高级别参数会很好,但硬件特定差异的奖励点.

Answer 1

N2492引入了数据依赖性排序 ,其基本原理如下:

有两个重要的用例,当前的工作草案(N2461)不支持某些现有硬件可能的可扩展性.

• 读访问很少编写的并发数据结构

很少编写的并发数据结构在操作系统内核和服务器式应用程序中都很常见.示例包括表示外部状态的数据结构(例如路由表),软件配置(当前加载的模块),硬件配置(当前使用的存储设备)和安全策略(访问控制权限,防火墙规则).读写比率远远超过十亿比一是非常普遍的.

• 用于指针介导的发布的发布 - 订阅语义

线程之间的许多通信是指针介导的,其中生产者发布指针,消费者可以通过该指针访问信息.在没有完全获取语义的情况下,可以访问该数据.

在这种情况下,使用线程间数据依赖性排序已经导致了数量级的加速,并且在支持线程间数据依赖性排序的机器上的可伸缩性方面也有类似的改进.这样的加速是可能的,因为这样的机器可以避免昂贵的锁定获取,原子指令或者否则需要的存储器栅栏.

强调我的

提供的激励用例rcu_dereference()来自Linux内核

Answer 2

Jeff Preshing有一篇很棒的博客文章回答了这个问题.我不能自己添加任何东西,但想想有关消费与收购的人应该阅读他的帖子:

http://preshing.com/20140709/the-purpose-of-memory_order_consume-in-cpp11/

他展示了一个特定的C++示例,其中包含跨三种不同架构的相应基准测试汇编代码.相比之下memory_order_acquire,memory_order_consume可能在PowerPC上提供3倍的加速,在ARM上加速1.6倍,在x86上加速可忽略不计,无论如何都具有很强的一致性.问题是,当他写这篇文章的时候,只有GCC实际上处理的语义与获取有任何不同,可能是因为一个bug.尽管如此,它证明了如果编译器编写者可以弄清楚如何利用它,则可以获得加速.

Answer 3

负载消耗很像负载获取,除了它导致之前的关系仅发生在依赖于负载消耗的数据表达式评估之前.将表达式包含kill_dependency在一个值中,该表达式不再包含load-consume的依赖项.

关键用例是编写器按顺序构造数据结构,然后将共享指针摆动到新结构(使用release或acq_rel原子).读者使用load-consume来读取指针,并取消引用它以获取数据结构.取消引用会创建数据依赖关系,因此读者可以保证看到初始化的数据.

std::atomic<int *> foo {nullptr};
std::atomic<int> bar;

void thread1()
{
    bar = 7;
    int * x = new int {51};
    foo.store(x, std::memory_order_release);
}

void thread2()
{
    int *y = foo.load(std::memory_order_consume)
    if (y)
    {
        assert(*y == 51); //succeeds
        // assert(bar == 7); //undefined behavior - could race with the store to bar 
        // assert(kill_dependency(*y) + bar == 58) // undefined behavior (same reason)
        assert(*y + bar == 58); // succeeds - evaluation of bar pulled into the dependency 
    }
}

提供负载消耗有两个原因.主要原因是ARM和Power负载保证消耗,但需要额外的防护才能将其转换为获取.(在x86上,所有加载都是获取的,因此在初始编译时,consume不会提供直接的性能优势.)次要原因是编译器可以在以后的操作中移动,而不需要数据依赖,直到消耗之前,它不能用于获取.(启用此类优化是将所有内存排序构建到语言中的重要原因.)

包装值kill_dependency允许计算表达式,该表达式取决于在加载消耗之前要移动到的值.这很有用,例如,当值是先前读取的数组的索引时.

请注意,使用消耗会导致之前发生的关系不再具有传递性(尽管它仍然保证是非循环的).例如,bar商店在foo之前发生,这发生在取消引用之前y,这发生在读取之前bar(在注释掉的断言中),但是商店bar在读取之前没有发生bar.这导致了一个相当复杂的发生之前的定义,但是你可以想象它是如何工作的(从之前的序列开始,然后通过任意数量的release-consume-dataDependency或release-acquire-sequencedBefore链接传播)

Answer 4

我想记录一个局部发现,尽管这不是一个真正的答案,并不意味着没有一个大的赏金给予正确答案.

在盯着1.10一段时间后,特别是第11段非常有用的说明,我认为这实际上并不那么难.同步 -(以下称为s/w)和依赖 - 有序 - 之前(dob)之间的最大区别在于,可以通过将任意顺序(s/b)和s/w 连接在一起来建立之前发生的关系,但是dob 并非如此.注意之前发生的线程间定义之一发生在:

A之前同步X和X排序B

但A之前依赖顺序X的类似语句缺失了!

因此,通过发布/获取(即s/w),我们可以订购任意事件:

A1    s/b    B1                                            Thread 1
                   s/w
                          C1    s/b    D1                  Thread 2

但现在考虑一个像这样的任意事件序列:

A2    s/b    B2                                            Thread 1
                   dob
                          C2    s/b    D2                  Thread 2

在这个序列中,A2 之前发生的事情 仍然是正确的C2(因为A2s/b B2和B2 线程之间 因为C2dob而发生 ;但我们可以争辩说你永远无法告诉!).然而,这是不正确的是A2 之前发生 D2.事件A2并D2没有相互排序,除非它实际上持有C2 依赖性 D2.这是一个严格的要求,并且不存在该需求,A2-到- D2不能"跨越"释放/消耗对进行排序.

换句话说,释放/消费对仅传播从一个到下一个携带依赖性的动作的排序.所有不依赖的东西都不是在发布/消费对中排序的.

此外,请注意,如果我们附加最终的,更强的发布/获取对,则会恢复排序:

A2    s/b    B2                                                         Th 1
                   dob
                          C2    s/b    D2                               Th 2
                                             s/w
                                                    E2    s/b    F2     Th 3

现在,通过引用的规则,D2 线程间发生之前 F2,因此,这样做C2和B2,所以A2 之前发生 F2.但请注意,在A2和之间仍然没有排序D2- 排序仅在之间A2和之后的事件之间.

总之和结束时,依赖性携带是一般排序的严格子集,并且释放/消费对仅在携带依赖性的动作之间提供排序.只要不需要更强的排序(例如,通过通过释放/获取对),理论上就有可能进行额外的优化,因为不依赖链中的所有内容都可以自由地重新排序.

也许这是一个有意义的例子？

std::atomic<int> foo(0);

int x = 0;

void thread1()
{
    x = 51;
    foo.store(10, std::memory_order_release);
}

void thread2()
{
    if (foo.load(std::memory_order_acquire) == 10)
    {
        assert(x == 51);
    }
}

如上所述,代码是无竞争的,并且断言将保持,因为释放/获取对x = 51在断言中加载之前或者存储.但是,通过将"获取"更改为"消费",这将不再是真实的,并且程序将进行数据竞争x,因为x = 51不依赖于商店foo.优化点是这个商店可以自由地重新排序而不用担心foo正在做什么,因为没有依赖性.