|
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语言编程学习基地，欢迎关注！
|
