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

wlmqgzm

回复 3# lxyscls

我这边研究无锁的技术方案中, 关键核心思想就是要保证 临界区 的数据的完整性  有两种比较常用:

一个方式就是: 新得到一个裸指针 new struct data, 拷贝旧数据到新裸指针的结构中 copy from old struct data, 修改数据 modify new struct data, 一次性更新裸指针 change point,

另外一种方式是公司的内部库,  不用new和copy, 因此性能要高出很多, 主要的思路是:atomic_memeory_release/accquire, 以及一些保护性内存单元, 来保护 临界区 的数据的完整性, 比spin_lock开销更小更快,
实现有限条件的并发, 读多线程并发,写单线程并发, 或者说是读写分离的方式

lxyscls

回复 11# wlmqgzm

您的方案

一个方式就是: 新得到一个裸指针 new struct data, 拷贝旧数据到新裸指针的结构中 copy from old struct data, 修改数据 modify new struct data, 一次性更新裸指针 change point,

1、如何获取一个裸指针？内存从哪里来？new or malloc？
2、怎么保证old struct data在拷贝过程中一直有效呢？假设还有一个writer完成了修改，这个时候只要它修改了指针，那么这块old data对它来说就没用了，也许就被它给释放掉了
3、您说的这种方案其实是“SPMC”的？“MPMC”怎么弄呢？

PS，您讲的这个跟我最初的某个想法挺相似的，不过当时我也没考虑copy过程中的有效性问题

3、用一块新的内存去替换原来的，只涉及一个atomic update reference的操作，但是需要分配内存

sditmaner

我知道你的意思，就是想怎么访问hash并修改数据最快，方法可能很多

lxyscls

回复 14# wlmqgzm

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

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

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

codechurch

每个桶上有一个自旋锁

lxyscls

回复 16# codechurch

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

windoze

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

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

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

回复 19# lxyscls

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

18856152726