代码之家 › 专栏 › 技术社区 › MaiaVictor

是否可以将此无锁32位哈希表算法用于64位密钥?

atomic hashmap parallel-processing algorithm c

7

MaiaVictor · 技术社区 · 7 年前

问题和背景

This post描述了一种无锁的32位哈希表算法。算法的核心是无锁线性搜索,用于在(逻辑)列表中插入密钥val对:

void ArrayOfItems::SetItem(uint32_t key, uint32_t value)
{
    for (uint32_t idx = 0;; idx++)
    {
        uint32_t prevKey = mint_compare_exchange_strong_32_relaxed(&m_entries[idx].key, 0, key);
        if ((prevKey == 0) || (prevKey == key))
        {
            mint_store_32_relaxed(&m_entries[idx].value, value);
            return;
        }
    }
}

对于特定的问题,我需要在表中插入随机密钥val对。因此,我至少需要64位密钥,因为对于32位,65536次插入后有50%的机会发生冲突,这太低了。不幸的是,我 do not have 64位cmpxchg作为原语。

问题

是否可以仅使用32位cmpxchg将上面的哈希表泛化为64位密钥?

1 回复 | 直到 7 年前

1

2

Paul McGee 7 年前

我不确定您是否仍然希望保留无锁特性,或者只是希望让64位密钥/值存储正常运行。(?)

@kol在这里发布了一个64位杂音3: hashing a small number to a random looking 64 bit integer

显然,如果引入了第二个数组来断言密钥位置所有权,并将其用于值存储,则可以分两步读取和cas 64位值,然后释放所有权。当然,这不能让你开锁。

————————————————————————————————————————————编辑:---
作者的哈希表上至少有两个视频,都是2007年的:

编程语言中的高级主题:无锁哈希表 https://www.youtube.com/watch?v=HJ-719EGIts

快速无等待哈希表
https://youtu.be/WYXgtXWejRM

他把他的程序流程与一个有限状态机联系起来。不考虑增长表的问题,在一个位置应用潜在的突变之前,该位置可以处于四种状态。键/值=[nil/nil],[x/nil],[x/x],[nil/x]。

在并发情况下,读取准备变异的状态并不能保证应用变异时的状态保持不变。

对于32位操作,我们有以下逻辑:
-如果read键=所需的键,则可以将该值写入该位置。
-如果read key=nil,而value=non nil,则另一个线程正在改变位置。
-如果read key=nil,value=nil,则可以通过成功的密钥ca写入位置。

如果要使用32位原子操作存储64位数据而不进行锁定,则状态图的大小会增加,故障状态也会增加,例如:
-你可以读一个半创建的密钥。
-值项的一半的cas更新可能被另一个线程停止,在第二个cas上失败。
-一个cas创建一个密钥项的一半可能会被另一个线程踩踏,在第二个cas上失败。
-数组初始值“nil”的32位表示形式不应作为64位键或值的一半出现

增加表大小的过程也增加了一些需要考虑的状态。