考虑以下针对多线程搜索算法的无锁哈希表的尝试(受此启发paper http://www.cis.uab.edu/hyatt/hashing.html)
struct Data
{
uint64_t key;
uint64_t value;
};
struct HashEntry
{
uint64_t key_xor_value;
uint64_t value;
};
void insert_data(Data const& e, HashEntry* h, std::size_t tableOffset)
{
h[tableOffset].key_xor_value = e.key ^ e.value;
h[tableOffset].value = e.value;
}
bool data_is_present(Data const& e, HashEntry const* h, std::size_t tableOffset)
{
auto const tmp_key_xor_value = h[tableOFfset].key_xor_value;
auto const tmp_value = h[tableOffset].value;
return e.key == (tmp_key_xor_value ^ tmp_value);
}
这个想法是HashEntry
struct 存储 a 的两个 64 位字的异或组合Data
结构。如果两个线程对 a 的两个 64 位字进行交错读/写HashEntry
结构体,其想法是,读取线程可以通过再次异或并与原始结构进行比较来检测到这一点key
。因此,哈希条目损坏可能会降低效率,但如果解码后的检索密钥与原始密钥匹配,仍然可以保证正确性。
论文提到,它基于以下假设:
对于本讨论的其余部分,假设 64 位内存
读/写操作是原子的,即整个 64 位值是
读/写在一个周期内。
我的问题是:上面的代码是否没有明确使用std::atomic<uint64_t>
C++11 保证线程安全?或者单个 64 位字是否会因同时读/写而损坏?即使在 64 位平台上?这与旧的 C++98 标准有何不同?
如果能引用该标准,我们将不胜感激。
UPDATE:基于这篇令人惊叹的论文汉斯·伯姆 (Hans Boehm) 谈“良性”数据竞争 https://www.usenix.org/legacy/event/hotpar11/tech/final_files/Boehm.pdf,一个简单的方法是让编译器取消两个异或insert_data()
and data_is_present()
总是回来true
,例如如果它找到像这样的本地代码片段
insert_data(e, h, t);
if (data_is_present(e, h, t)) // optimized to true as if in single-threaded code
read_and_process(e, h, t); // data race if other thread has written