TOP

C++编程笔记丨世界上最简单的无锁哈希表(二)
2019-04-03 16:12:29 】 浏览:204
Tags:编程 笔记 世界 简单 哈希

tem(uint32_t key, uint32_t value) {
for (uint32_t idx = integerHash(key);; idx++) { idx &= m_arraySize - 1; // Load the key that was there. uint32_t probedKey = mint_load_32_relaxed(&m_entries[idx].key); if (probedKey != key) { // The entry was either free, or contains another key. if (probedKey != 0) continue; // Usually, it contains another key. Keep probing. // The entry was free. Now let's try to take it using a CAS. uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key); if ((prevKey != 0) && (prevKey != key)) continue; // Another thread just stole it from underneath us. // Either we just added the key, or another thread did. } // Store the value in this array entry. mint_store_32_relaxed(&m_entries[idx].value, value); return; } }

这个就是几乎可以精简的最简单的无锁哈希表,这里是它的代码链接: source and header

一个忠告:与ArrayOfItems一样,HashTable1上的所有操作都采用了relaxed memory ordering做限制。因此,当在HashTable1中设置标记,共享一些数据供其他线程访问时,必须事先插入release fence。同样访问数据的线程在调用GetItem前需要acquire fence。

// Shared variables

char message[256];

HashTable1 collection;

 

void PublishMessage()

{

    // Write to shared memory non-atomically.

    strcpy(message, "I pity the fool!");

 

    // Release fence: The only way to safely pass non-atomic data between threads using Mintomic.

    mint_thread_fence_release();

 

    // Set a flag to indicate to other threads that the message is ready.

    collection.SetItem(SHARED_FLAG_KEY, 1)

}

简单样例

对HashTable1的一些测试对比,在上一篇帖子我做个一个类似的测试。它交替执行2个测试:一个采用2个线程,每个线程交替插入6000个key不同的item,另一个每个线程交替插入12000个key相同但是value不同的item。


 

代码放在github上,你可以自己编译和执行。

在HashTable1没有满时—少于80%时—HashTable1表现的很好,我也许应该为这个说法做一些基准测试。但是以以往的常规的哈希表作为基准,我敢肯定你很难实现出性能更好的无锁哈希表。这似乎奇怪,HashTable1基于ArrayOfItems,看起来会很低效。当然,任何哈希表中,总会有发生碰撞的风险,而降阶到ArrayOfItems的风险并不为0。但是使用一个足够大的数组和类似MurmurHash3这样的hash函数,这种情况出现的很少。

在实际的工作中,我已经使用了一个和这个类似的hash-table。这是一个游戏开发的项目,我的工作是解决使用内存分配跟踪工具(memory tracker)之后对一个读写锁激烈的争用。迁移到无锁哈希表的过程非常棘手。相对HashTable1需要更复杂的数据结构,key和value都是指针而不是简单的整数。因此有必要在哈希表内部插入memory ordering。最终在此模式下运行:最坏情况下游戏的帧率提高了4-10 FPS。

博主是一个有着7年工作经验的架构师,对于c++,自己有做资料的整合,一个完整学习C语言c++的路线,学习资料和工具。可以进我的Q群7418,18652领取,免费送给大家。希望你也能凭自己的努力,成为下一个优秀的程序员!另外博主的微信公众号是:C语言编程学习基地,欢迎关注!


C++编程笔记丨世界上最简单的无锁哈希表(二) https://www.cppentry.com/bencandy.php?fid=49&id=217170

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇Gym100920J 下一篇c++静态成员