请教一个c++11 memory-ordering 的问题

wlmqgzm

回复 10# VIP_fuck

我这边近期的研发方向比较超前, 基本上比较新的多线程技术都有可能实践, 最近负责下一代产品 底层库的研发工作, 因此, 对于C++多线程领域看的资料比较多.

主要是多线程下的高性能编程

1)高性能多线程数据交换模型: 高性能多线程无等待队列, 性能已经优化到单队列 数亿TPS 无锁双向数据交换能力, 包括 wait_free_spsc_queue, wait_free_mpsc_queue,   wait_free_spmc_queue ,
    同时与Boost::asio::io_service结合,解决CPU资源统一调度. 支持任意对象T的模板化编程.

    主要的内存模型是: memory_order_release/acquire,   公司内部已经把boost::lock_free_spsc_queue队列彻底抛弃.   

    实践中主要的瓶颈是:io_service启动任务的延迟, 跨线程数据交换基本没有瓶颈.

2)高性能hash_map模型: 目前看在各场景下比std:unordered_map都要更节约内存, 性能上有30%到数倍的性能提高, 查询性能至少提高了70%.  主要模型是优化后的vector环形队列, 彻底抛弃了传统hash_map的模型

3)任意对象的无锁模型: 目前具备了一个以上的通用无锁模型, 可以用于任意对象的无锁编程, 这一块目前主要是测试验证, 不打算在主要核心模块进行推广, 通用模型主要的问题是性能比较低, 存在不值得付出的代价
   
前面答复中谈的  线程 A 线程 B, 就是通用无锁模型的一个范例.

lxyscls

回复 11# wlmqgzm

对于C++多线程领域看的资料比较多

求分享
请问boost::spsc_queue不是wait_free的吗？难不成只是lock_free要cas的？

lxyscls

VIP_fuck 发表于 2016-11-06 10:07
回复 5# lxyscls

关于这个，我推荐您看看下面两个：

Memory Barriers: a Hardware View for Software Hackers

LINUX KERNEL MEMORY BARRIERS

其实我是从Java JSR133(Java Memory Model)看过去的，开始也是捉摸不透

看了这两边文章，其实无论是C/C++11还是Java5都比较好理解了

希望对您有帮助

VIP_fuck

回复 13# lxyscls

非常感谢
对了，提到 wait-free 了，我就请教一下，wait-free 有什么好资料推荐一下。我目前 wait-free 和 lock-free 理解还不到位，书还没看完。原计划一个月看完的书，结果远超预期了。

sditmaner

你看的这个范例, 应该是一个 lock_free_queue, pop部分的代码没有看到, pop部

TiGEr.zZ

实践中的lock-free实现可以认为就是wait-free的，实际上性能也往往更好一些。

VIP_fuck

各位都是大牛啊，以前没接触过这方面的，也没见到有人发帖讨论，好家伙，这么多人精于此道啊。

lxyscls

Non-blocking algorithm
目前还没有看到专门的wait-free，可能也跟我的理解有出入，就不误导了，您可以看看wiki里面的链接

PS，我原本以为wait-free是没有cas retry的，因为如果存在do {} while (cas())的话，那么就没有办法保证bound steps了。SPSC queue可以不用cas，只用memory barrier，所以我“认为”它是wait-free的。看来理解得不到位

Wait-free algorithms usually use such primitives as atomic_exchange, atomic_fetch_add (InterlockedExchange, InterlockedIncrement, InterlockedExchangeAdd, __sync_fetch_and_add), and they do not contain cycles that can be affected by other threads. atomic_compare_exchange primitive (InterlockedCompareExchange, __sync_val_compare_and_swap) is usually not used, because it is usually tied with a "repeat until succeed" cycle.

From 1024cores，看来我理解得还不算太跑偏

VIP_fuck

回复 18# lxyscls

V5
SPSC queue  第一次接触到，多谢。


我很想知道大牛们都在开发神马，为毛我经历的项目都这么水。。

TiGEr.zZ

单一的lock-free操作可以通过一个round-robin帮助过程转换为wait-free操作，容易得到一般性这样的过程时间上界是O(nThread^2)的。这种转换是需要针对每一个lock-free操作的，需要反复处理同样的细节，因此比较麻烦。一种通用的转换方法是先不怕麻烦的构建一个关于操作的wait-free queue，每个lock-free操作都挂到queue上，所有的线程都会尝试帮助逐个完成queue上的操作，时间上界同上述。考虑到帮助过程的额外消耗，可以预见一般性wait-free过程更慢，特别是竞争不那么激烈的情况下。为了弥补这一缺陷，可以使用所谓的fast-path-slow-path算法，就是先尝试几次lock-free过程，失败后再执行wait-free过程。同时，实验表明，实践中lock-free操作都可以完成，所以几乎等同于wait-free。这也十分容易理解，实际系统运行中不可能所有线程都反复执行同一操作，即使是分时调度而不是真正的并行执行情况下，调度的粒度落在同一个竞争节点上的概率趋向0。当然在一些关键领域里，比如飞向外星的控制系统里，使用wait-free的算法还是有必要的，毕竟谁能保证那么长时间的运行里究竟会出现什么情况了，也许外星人会考验一下我们的能力。

read/write操作最多支持两个线程的wait-free操作，又称共识数为2。cas支持任意数量的线程操作，共识数为无穷。