免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: zylthinking

[算法] 多线程读写无锁链表: 之前有没有相同的实现? (更新) [复制链接]

论坛徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2017-04-18 16:36 |显示全部楼层
folklore 发表于 2017-04-18 12:25
第一次听到无锁读***写***队例, 就觉得很神奇。怎么可能无锁呢??????
想啊想, 还是觉得怎么可能无 ...

lockfree不是不要锁的意思
In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)
From wiki Non-blocking algorithm

论坛徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2017-04-18 16:40 |显示全部楼层
zylthinking 发表于 2017-04-18 11:49
上边是你推崇的 boost , 下边是我的 lkf; 测试的是 1读1写的; 你自己看结果, 单线程下是我的占优势;  ...

spsc queue就是single producer/single consumer的意思啊,本来就是限制了只能有一个写一个读

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2017-04-18 16:42 |显示全部楼层
更多的人在意的是函数的名称中是否有 lock 或 wait 的字眼

—_— 94,没锁怎么写服务器

论坛徽章:
14
水瓶座
日期:2014-06-10 09:51:0215-16赛季CBA联赛之江苏
日期:2017-11-27 11:42:3515-16赛季CBA联赛之八一
日期:2017-04-12 14:26:2815-16赛季CBA联赛之吉林
日期:2016-08-20 10:43:1215-16赛季CBA联赛之广夏
日期:2016-06-23 09:53:58程序设计版块每日发帖之星
日期:2016-02-11 06:20:00程序设计版块每日发帖之星
日期:2016-02-09 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-25 16:40:3515-16赛季CBA联赛之广夏
日期:2015-12-22 09:39:36程序设计版块每日发帖之星
日期:2015-08-24 06:20:002015亚冠之德黑兰石油
日期:2015-08-07 09:57:302015年辞旧岁徽章
日期:2015-03-03 16:54:15
发表于 2017-04-18 17:11 |显示全部楼层
本帖最后由 lxyscls 于 2017-04-18 17:13 编辑
cokeboL 发表于 2017-04-18 16:42
更多的人在意的是函数的名称中是否有 lock 或 wait 的字眼

—_— 94,没锁怎么写服务器

一读一写场景,在"顺序一致性内存模型"下,确实就不需要lock,七十年代Lamport已经证明了(L. Lamport. Concurrent reading and writing. Commun. ACM, 20(11):806–811, 1977.),链接超慢且全是公式,只是证明有这回事就是了
不过目前的物理设备还没有哪个是支持"Sequential consistency"的,Java的volatile和C++的atomic(默认)是支持的

这个是C++关于seq_cst的解释:http://en.cppreference.com/w/cpp ... consistent_ordering

论坛徽章:
36
子鼠
日期:2013-08-28 22:23:29黄金圣斗士
日期:2015-12-01 11:37:51程序设计版块每日发帖之星
日期:2015-12-14 06:20:00CU十四周年纪念徽章
日期:2015-12-22 16:50:40IT运维版块每日发帖之星
日期:2016-01-25 06:20:0015-16赛季CBA联赛之深圳
日期:2016-01-27 10:31:172016猴年福章徽章
日期:2016-02-18 15:30:3415-16赛季CBA联赛之福建
日期:2016-04-07 11:25:2215-16赛季CBA联赛之青岛
日期:2016-04-29 18:02:5915-16赛季CBA联赛之北控
日期:2016-06-20 17:38:50技术图书徽章
日期:2016-07-19 13:54:03程序设计版块每日发帖之星
日期:2016-08-21 06:20:00
发表于 2017-04-18 17:33 |显示全部楼层
回复 64# lxyscls

我不看我不看

论坛徽章:
9
程序设计版块每日发帖之星
日期:2015-10-18 06:20:00程序设计版块每日发帖之星
日期:2015-11-01 06:20:00程序设计版块每日发帖之星
日期:2015-11-02 06:20:00每日论坛发贴之星
日期:2015-11-02 06:20:00程序设计版块每日发帖之星
日期:2015-11-03 06:20:00程序设计版块每日发帖之星
日期:2015-11-04 06:20:00程序设计版块每日发帖之星
日期:2015-11-06 06:20:00数据库技术版块每周发帖之星
日期:2015-12-02 15:02:47数据库技术版块每日发帖之星
日期:2015-12-08 06:20:00
发表于 2017-04-18 18:13 |显示全部楼层
本帖最后由 wlmqgzm 于 2017-04-18 18:33 编辑

回复 55# lxyscls


对的, 这个才是正确版本的 wait_free_queue, 性能的评测也完全正确, 确实这种写法的wait_free_queue可以达到每秒2亿。
我公司的wait_free_queue代码与此代码大同小异, 要继续提高性能,主要是靠改善内存的依存性来解决, 就是利用 alignas 64 和内存对生产者和消费者的内存进一步划分, 甚至要将一部分const 内存变量拷贝2份分别存放来提高性能。

凡是在代码中没有 一行 std::memory_order 的 所谓“wait_free_queue", 基本就是 连基本正确性都无法保证的东西
。除非楼主将整个wait_free体系都推翻。

楼主的代码也看了,虽然有点不好听,我说句实话,lock_free/wait_free领域, 楼主还有很长的路要走。。。。。
我只说两点,

1) 凡是代码中有 CAS spin 循环代码的, 实质都是lock_free,  wait_free的实现是不会有CAS Spin,
wait_free 主要是靠std::memeory_order来保证 数据的原子性,数据的正确性。。
wait_free方面的论文很多了,基本讨论的就是内存的一致性这些东西。

2)楼主的测试代码有问题,按照楼主的测试报告,wait_free_queue的整数传递性能是: 17毫秒传送10万数据, 计算下来 boost wait_free_spsc_queue 每秒只有588万TPS, 这个数据拿到任何地方都会被笑话的。
总之,我们的测试代码都是 测出标准版的 wait_free_spsc_queue大约每秒2亿TPS, 与楼主的测试代码,有近40倍的性能差距。



论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2017-04-18 18:26 |显示全部楼层



真是够扯淡的, 我也送你句: 你还需要继续加强编程能力,加强理论学习
为啥这么说, 下面是理由
1. 你知道你吹牛逼的 boost 里面的 atomic 实现里用了 CAS 吗
2. 你知道 gcc builtin 系列函数本身自带了内存屏障效果吗, 你知道 std::memeory_order 不等于机器指令吗, 你知道相同的指令会以你不知道的面目出现吗?
3. 你知道我用的机器不是你用的机器吗, 你知道看性能对比是看相同外部条件下的表现吗? 你知道你那句话拿到任何地方都会被笑话的吗






论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2017-04-18 18:26 |显示全部楼层
本帖最后由 zylthinking 于 2017-04-18 18:43 编辑


测试代码有问题请指出来, 那一句有问题, 有什么问题
张嘴就说有问题, 却不说什么问题;

就和张嘴就说你的是 lock free, 不是 wait free 一样, 你别把自己太当回事, 没有证据的话, 基本上就是风

论坛徽章:
9
程序设计版块每日发帖之星
日期:2015-10-18 06:20:00程序设计版块每日发帖之星
日期:2015-11-01 06:20:00程序设计版块每日发帖之星
日期:2015-11-02 06:20:00每日论坛发贴之星
日期:2015-11-02 06:20:00程序设计版块每日发帖之星
日期:2015-11-03 06:20:00程序设计版块每日发帖之星
日期:2015-11-04 06:20:00程序设计版块每日发帖之星
日期:2015-11-06 06:20:00数据库技术版块每周发帖之星
日期:2015-12-02 15:02:47数据库技术版块每日发帖之星
日期:2015-12-08 06:20:00
发表于 2017-04-18 18:41 |显示全部楼层
本帖最后由 wlmqgzm 于 2017-04-18 18:43 编辑

回复 68# zylthinking

1)标准版的wait_free_queue确实不依靠 CAS spin 工作, 代码如下:

  • #include <cstddef>
  • #include <atomic>
  • template <typename T, int capacity> class spsc_queue {
  •   public:
  •     spsc_queue(const T &val) : head(0), tail(0), invalid_val(val) {
  •         for (int i = 0; i < capacity; i++) {
  •             buf = invalid_val;
  •         }
  •     }
  •     spsc_queue(const spsc_queue &) = delete;
  •     spsc_queue &operator=(const spsc_queue &) = delete;
  •     bool enqueue(const T &data) {
  •         if (buf[tail].load(std::memory_order_acquire) == invalid_val) {
  •             buf[tail].store(data, std::memory_order_release);
  •             tail = (tail + 1) % capacity;
  •             return true;
  •         }
  •         return false;
  •     }
  •     bool dequeue(T &data) {
  •         if (buf[head].load(std::memory_order_acquire) != invalid_val) {
  •             data = buf[head].load(std::memory_order_relaxed);
  •             buf[head].store(invalid_val, std::memory_order_release);
  •             head = (head + 1) % capacity;
  •             return true;
  •         }
  •         return false;
  •     }
  •   private:
  •     static constexpr size_t CACHELINE = 64;
  •     alignas(CACHELINE) unsigned int head;
  •     alignas(CACHELINE) unsigned int tail;
  •     char padding[CACHELINE - sizeof(tail)];
  •     std::atomic<T> buf[capacity];
  •     T invalid_val;
  • };



2. 你知道 gcc builtin 系列函数本身自带了内存屏障效果吗, 你知道 std::memeory_order 不等于机器指令吗, 你知道相同的指令会以你不知道的面目出现吗?
标准版的wait_free主要是靠内存一致性来实现无锁的, 所以必须要靠 std::memeory_order 来保证正确性。具体读代码吧。

3. 你知道我用的机器不是你用的机器吗, 你知道看性能对比是看相同外部条件下的表现吗? 你知道你那句话
拿到任何地方都会被笑话的吗

近40倍的性能差距,你究竟用的是什么机器啊,我当年测试用的是 intel G3258@3.2G 双核CPU, 你的机器比这个还烂40倍???

论坛徽章:
11
未羊
日期:2013-12-16 12:45:4615-16赛季CBA联赛之青岛
日期:2016-04-11 19:17:4715-16赛季CBA联赛之广夏
日期:2016-04-06 16:34:012015亚冠之卡尔希纳萨夫
日期:2015-11-10 10:04:522015亚冠之大阪钢巴
日期:2015-07-30 18:29:402015亚冠之城南
日期:2015-06-15 17:56:392015亚冠之卡尔希纳萨夫
日期:2015-05-15 15:19:272015亚冠之山东鲁能
日期:2015-05-14 12:38:13金牛座
日期:2014-12-04 15:34:06子鼠
日期:2014-10-16 13:40:4715-16赛季CBA联赛之八一
日期:2016-07-22 09:41:40
发表于 2017-04-18 18:47 |显示全部楼层
本帖最后由 zylthinking 于 2017-04-18 18:55 编辑

回复 69# wlmqgzm

你找找我代码里面的 CAS spin 试试?至于机器差异, 这个好办, 我代码都在这里了, 你要不要在你的机器上跑跑? 或者找出来我在测试代码中哪里偏向我自己的实现了;



您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

DTCC2020中国数据库技术大会

【架构革新 高效可控】2020年12月21日-23日第十一届中国数据库技术大会将在北京隆重召开。

大会设置2大主会场,20+技术专场,将邀请超百位行业专家,重点围绕数据架构、AI与大数据、传统企业数据库实践和国产开源数据库等内容展开分享和探讨,为广大数据领域从业人士提供一场年度盛会和交流平台。

http://dtcc.it168.com


大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP