Hash在多线程下面怎么做到高效的修改？

lxyscls

一个比较困扰的问题

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

nuclearxin

哈哈上面已经有人说过了。
没看中间的回复。。。。

wlmqgzm

windoze 发表于 2016-12-02 21:42
回复 19# lxyscls

不要直接改，删一个加一个，这样你就可以随便折腾新元素，折腾好了再插进去就行。

这个办法好

nuclearxin

可以参考linux slab 高速缓存 slab 分配
1. 使用指针
2. 内存消耗 参考 完成预先分配内存 和管理 slab.  
3 .在使用锁
这个应该比较  比较中性。
具体优化还要看你的修改行为 特色

18856152726

windoze

回复 19# lxyscls

不要直接改，删一个加一个，这样你就可以随便折腾新元素，折腾好了再插进去就行。

lxyscls

windoze 发表于 2016-12-01 23:23
用open address hash table，删除用mark deletion，这样增删改只需一个指针的cas。
至于存放元素的内存管 ...

猫哥好晚啊

增删能理解，但是“改”怎么做到一个cas呢？pair(const k, v)，挂上个新的v也算是改了？

也就是说v其实是块新内存（新指针）？read-copy-write？

windoze

用open address hash table，删除用mark deletion，这样增删改只需一个指针的cas。
至于存放元素的内存管理，你可以用slab，这玩意就是个链表，也可以无锁并发。

唯一的缺点就是整个hash table需要定期重建。

lxyscls

回复 16# codechurch

单读单写啦，是没我提的问题
我想知道如果支持“多读后再多写”（不改变位置，算是个“原位操作”）怎么玩？

codechurch

每个桶上有一个自旋锁

lxyscls

回复 14# wlmqgzm

读锁和写锁，２个锁互不干扰

我再多问一下，如果互不干扰的话，怎么做到“写时不读”和“读时不写”呢？两个锁判断的东西都不一样，一个是mutex，一个是cas retry。或者说两个在底层的还是用到了同一个atomic进行cas操作，只是逻辑不一样？
PS
    两把锁在Intel TBB里面也有，const accessor和accessor，不过Intel的代码实在是稀烂，没有看的欲望，相较Folly的代码整齐多了。

    目前还是想办法找现成的用起来先