忘记密码   免费注册 查看新帖 | 论坛精华区

ChinaUnix.net

  平台 论坛 博客 认证专区 大话IT HPC论坛 徽章 文库 沙龙 自测 下载 频道自动化运维 虚拟化 储存备份 C/C++ PHP MySQL 嵌入式 Linux系统
最近访问板块 发新帖
楼主: zylthinking

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

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2014-08-02 06:55 |显示全部楼层
回复 40# __BlueGuy_


    这东西是用在服务器里用来提高多线程服务器数据处理吞吐量的,简而言之:很有用。

论坛徽章:
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-03-29 15:35 |显示全部楼层
我主贴改了你好歹给我升到前面去吧................

论坛徽章:
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-03-29 15:46 |显示全部楼层
mark下来慢慢看

论坛徽章:
3
处女座
日期:2015-03-18 14:35:45羊年新春福章
日期:2015-03-18 14:48:23午马
日期:2015-03-18 14:51:09
发表于 2017-03-30 09:38 |显示全部楼层
不存在真正无锁

论坛徽章:
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-03-30 15:05 |显示全部楼层
wait_free 队列是未来的主流, lock_free 慢慢都会被淘汰,
我们公司目前已经主要应用wait_free_queue的各种实践,性能比有锁队列快的多,  即使是单消费者单生产者队列测试, 都可以跑到199%的CPU占有率,不会被队列阻塞,平均时延大约是1微秒。
Boost库里面有一个wait_free_spsc_queue的实现,值得学习。

论坛徽章:
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-03-31 11:05 |显示全部楼层
本帖最后由 zylthinking 于 2017-03-31 11:22 编辑

回复 45# wlmqgzm

我看了一下说明, 没看实现, 如何理解 [size=13.3333px]single-writer/single-reader?[size=13.3333px]
[size=13.3333px]The [size=13.3333px]spsc_queue[size=13.3333px] class provides a single-writer/single-reader fifo queue, pushing and popping is wait-free.[size=13.3333px]



814     /** Pushes as many objects from the array t as there is space.
815      *
816      * \pre only one thread is allowed to push data to the spsc_queue
817      * \return number of pushed items
818      *
819      * \note Thread-safe and wait-free
820      */
821     size_type push(T const * t, size_type size)
822     {
823         return base_type::push(t, size);
824     }



852     /** Pops a maximum of size objects from ringbuffer.
853      *
854      * \pre only one thread is allowed to pop data to the spsc_queue
855      * \return number of popped items
856      *
857      * \note Thread-safe and wait-free
858      * */
859     size_type pop(T * ret, size_type size)
860     {
861         return base_type::pop(ret, size);
862     }
863



如果照字面意思, 那我觉得还是我的高明些; 我的好歹在 多写/一读 的情况下保证 wait_free

论坛徽章:
33
处女座
日期:2014-06-03 14:14:412015亚冠之莱赫维亚
日期:2015-06-23 13:34:21程序设计版块每日发帖之星
日期:2015-08-30 06:20:00程序设计版块每日发帖之星
日期:2015-12-24 06:20:0015-16赛季CBA联赛之上海
日期:2015-12-27 11:07:07程序设计版块每日发帖之星
日期:2016-01-12 06:20:0015-16赛季CBA联赛之北京
日期:2016-01-15 01:01:2115-16赛季CBA联赛之浙江
日期:2016-01-15 22:38:20程序设计版块每日发帖之星
日期:2016-01-18 06:20:00每日论坛发贴之星
日期:2016-01-18 06:20:0015-16赛季CBA联赛之北控
日期:2016-01-30 21:43:01程序设计版块每日发帖之星
日期:2016-02-08 06:20:00
发表于 2017-04-02 12:35 |显示全部楼层



论坛徽章:
5
数据库技术版块每日发帖之星
日期:2015-11-27 06:20:00程序设计版块每日发帖之星
日期:2015-12-01 06:20:00每日论坛发贴之星
日期:2015-12-01 06:20:0015-16赛季CBA联赛之佛山
日期:2017-03-26 23:38:0315-16赛季CBA联赛之江苏
日期:2017-07-17 10:08:44
发表于 2017-04-03 14:21 |显示全部楼层
算是见识了。

论坛徽章:
12
水瓶座
日期:2014-06-10 09:51:0215-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摩羯座
日期:2014-07-21 10:11:2815-16赛季CBA联赛之八一
日期:2017-04-12 14:26:28
发表于 2017-04-04 20:50 |显示全部楼层
wlmqgzm 发表于 2017-03-30 15:05
wait_free 队列是未来的主流, lock_free 慢慢都会被淘汰,
我们公司目前已经主要应用wait_free_queue的各 ...

SPSC Queue已经在七十年代末被Lamport证明在sequence consistent内存模型下是wait-free的

不过网上有好些个论文专门优化SPSC Q的,原始的Lamport SPSC Queue的cache亲和性不太好,P/C需要同时检查head和tail

论坛徽章:
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-11 20:33 |显示全部楼层
回复 46# zylthinking

Wait_free 的实现性能要好一些,最简单的是单消费者单生产者队列, 一般都是先实现这个,
然后再以此为基础实现多生产者 和 多消费者队列,也很简单,基本就是多组映射, 所以, 一般只要实现了
单消费者单生产者队列就OK, 其他都不是问题,
一般传送int这样的简单内容, 3.2G主频下
单消费者单生产者2个线程, 1个生产者1个消费者, wait_free_spsc_queue每秒收发次数可以达到3亿次,lock_free达不到这个性能,
C++模板是个好东西, 实现好一个完整的模块,就可以推广到任意对象,然后就可以方便的替换原来的有锁队列了,

C++ template特化后,还可以支持 std::function 队列, 实现一个高性能的任务调度队列,。。。。
总之,扩展开来,能够做越来越多的组件,工具多了以后,在一些对性能要求高的场合就比较简单,最起码多几个可靠的工具包,实现起来也简单,

最近主要是做KV数据库,优化单机性能中,现在已经比 memcache / redis 快很多了,上个版本查询性能已经比memcache快64%,单核性能也超过redis单核性能,
本周还有一个版本会发布,内部测试中, 还会有大幅度的性能提升,觉得工具包还是要做C++模板,然后才可以适应更多的场合。
最近开发的各类加速的东西,单点测试成功后,最后都是做成了类似std/boost 一样的C++标准库, 开发过程中,全部代码的60%都是能够在下一个项目中使用的标准库。
C/C++的一些库还是有点旧,不少算法都过时了,这几年有不少论文,所以用最新的算法重写会有不少提高,
但是如果算法不变的话,重写基本是毫无意义的,-O3优化下,性能不会有提升。

评分

参与人数 1信誉积分 +10 收起 理由
lxyscls + 10 什么公司?贡献给Boost算了

查看全部评分

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

本版积分规则

SACC2017购票8.8折优惠进行时

2017中国系统架构师大会(SACC2017)将于10月19-21日在北京新云南皇冠假日酒店震撼来袭。今年,大会以“云智未来”为主题,云集国内外顶级专家,围绕云计算、人工智能、大数据、移动互联网、产业应用等热点领域展开技术探讨与交流。本届大会共设置2大主会场,18个技术专场;邀请来自互联网、金融、制造业、电商等多个领域,100余位技术专家及行业领袖来分享他们的经验;并将吸引4000+人次的系统运维、架构师及IT决策人士参会,为他们提供最具价值的交流平台。
----------------------------------------
优惠时间:2017年8月2日前

活动链接>>
  

北京盛拓优讯信息技术有限公司. 版权所有 京ICP备16024965号 北京市公安局海淀分局网监中心备案编号:11010802020122
广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员  联系我们:
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP