免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
123下一页
最近访问板块 发新帖
查看: 6351 | 回复: 23

[算法] Hash在多线程下面怎么做到高效的修改? [复制链接]

论坛徽章:
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
发表于 2016-11-22 10:39 |显示全部楼层
一个比较困扰的问题

Hash本身可以做到线程安全的操作(find/insert/remove),但是如果要修改某个item的内容(譬如是一个struct or class reference),如何做到高效的修改?
目前想到的几种方式:
1、lock 或 spin_lock,保护整个写过程
2、摘下来,写好,放回去
3、用一块新的内存去替换原来的,只涉及一个atomic update reference的操作,但是需要分配内存

论坛徽章:
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
发表于 2016-11-22 22:18 |显示全部楼层
刚做了类似的技术方案.  我的办法是:
1)重新写一个效率更高的hash_map, 大约性能比std::unordered_map提高30%-70%
   无锁的hash_map性能未必更好, 因为要消耗一些资源做内存同步
2)分多组hash_map, 例如256组, 每组一个mutex, 大幅度减少了锁冲突, 几乎没有锁冲突了,  

论坛徽章:
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
发表于 2016-11-23 09:41 |显示全部楼层
回复 2# wlmqgzm

不好意思,我讲得不是这个意思,BTW,您的第二种方案其实也就是Java ConcurrentHashMap,先分segment,然后每个segment才算是一个真正的Hash结构
我的问题是:怎么做到高效的修改Hash中的Item内容,譬如每个Item内容是个strcut,怎么能够 原子的 高效修改这些内容

假设有A B两个线程能够同时拿到这个Item,如果让它们同时修改,肯定会出现不一致的情况

其他Hash的基本操作,我都假设它是线程安全的

论坛徽章:
3
处女座
日期:2015-03-18 14:35:45羊年新春福章
日期:2015-03-18 14:48:23午马
日期:2015-03-18 14:51:09
发表于 2016-11-23 10:41 |显示全部楼层
指针                              

论坛徽章:
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
发表于 2016-11-23 11:05 |显示全部楼层
回复 4# mr_sev

原子的修改指针或者引用是没有问题的,不过这样就意味着新分配内存

论坛徽章:
0
发表于 2016-11-24 14:40 |显示全部楼层
"但是如果要修改某个item的内容(譬如是一个struct or class reference)"
Linux的list_entry,根据某个class中的成员变量值,直接定位到这个class对象的内存地址。我想这样应该是操作上最快的吧。

论坛徽章:
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
发表于 2016-11-24 16:38 |显示全部楼层
回复 6# sxcong

  1. strcut {
  2.     int a;
  3.     int b;
  4.     int c;
  5. }
复制代码
假设每个item是这样的,Hash支持并发的find,多个线程找到这个item之后,肯定需要原子的修改(a,b,c),否则就冲突了我大概问的就是这个意思,难道说没这种需求??

论坛徽章:
0
发表于 2016-11-24 17:19 |显示全部楼层
list_entry是直接查内存地址,只要item的地址有效就可以访问。当然权限高还可以访问其他进程的内存,比如游戏的外挂。都直接写地址了,并不并发有什么关系。

论坛徽章:
0
发表于 2016-11-24 17:21 |显示全部楼层
我知道你的意思,就是想怎么访问hash并修改数据最快,方法可能很多。
但我说的这个方法是跳出一切容器了,直接访问对象的地址。回想一下你学汇编的时候是怎么操作变量的。

论坛徽章:
154
2022北京冬奥会纪念版徽章
日期:2015-08-07 17:10:5720周年集字徽章-年
日期:2022-10-26 16:44:2015-16赛季CBA联赛之深圳
日期:2022-11-02 14:02:4515-16赛季CBA联赛之八一
日期:2022-11-28 12:07:4820周年集字徽章-20	
日期:2023-07-19 08:49:4515-16赛季CBA联赛之八一
日期:2023-11-04 19:23:5115-16赛季CBA联赛之广夏
日期:2023-12-13 18:09:34
发表于 2016-11-25 00:06 |显示全部楼层
2)分多组hash_map, 例如256组, 每组一个mutex, 大幅度减少了锁冲突, 几乎没有锁冲突了,  


这个方案不错,就是类似思维
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP