是无锁的哈希没有std ::原子保证是线程安全的C ++ 11？ [英] Is lockless hashing without std::atomics guaranteed to be thread-safe in C++11?

问题描述

请考虑以下针对多线程搜索算法的无锁散列表的尝试（受此论文）

  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存储一个 Data 结构的两个64位字的XOR组合。如果两个线程对一个 HashEntry 结构的两个64位字进行了交叉读/写操作，这个想法是读取线程可以再次进行XOR操作来检测并与原始键进行比较。因此，可能由于损坏的散列条目而损失效率，但是在解码的检索关键字与原始匹配的情况下仍然保证正确性。

该文提到它是基于在以下假设：

对于本讨论的剩余部分，假设64位内存
读/写操作是原子的，这是整个64位值是
读/写在一个周期。

我的问题是：没有明确使用 std :: atomic< uint64_t> 保证在C ++ 11中是线程安全的？或者可以通过同时读/写损坏单个64位字？即使在64位平台上？这与旧的C ++ 98标准有什么不同？

非常感谢来自标准的报价。

UPDATE ： 汉斯·伯格对良性数据竞赛的惊人文章，一个简单的方法被编译器从编译器中取消来自 insert_data（）和 data_is_present（） to alway return true ，例如如果它找到一个本地代码片段像

  insert_data（e，h，t）; 
 if（data_is_present（e，h，t））//优化为true，就像在单线程代码中
 read_and_process（e，h，t）; // data race if other thread has written 
  

解决方案

++ 11规范几乎定义了一个线程读取或写入另一个线程正在写为未定义行为的尝试（没有使用原子或互斥体来防止一个线程在另一个线程写入时读/写） 。

各个编译器可能会安全，但C ++ 11规范本身不提供覆盖。同时读取永远不是问题;

这和旧的C ++ 98标准有什么不同？

C ++ 98/03标准不提供关于线程的任何覆盖。就C ++ 98/03内存模型而言，线程不是可能发生的事情。 / p>

Consider the following attempt at a lockless hashtable for multithreaded search algorithms (inspired by this paper)

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);
}

The idea is that a HashEntry struct stores the XOR-ed combination of the two 64-bit words of a Data struct. If two threads have interleaved reads/writes to the two 64-bit words of a HashEntry struct, the idea is that this can be detected by the reading thread by XOR-ing again and comparing against the original key. So one might have a loss of efficiency by corrupted hash entries, but still have guaranteed correctness in case the decoded retrieved key matches the original.

The paper mentions that it is based on the following assumption:

For the remainder of this discussion, assume that 64 bit memory read/write operations are atomic, that is the entire 64 bit value is read/written in one cycle.

My questions are: is the above code without explicit use of std::atomic<uint64_t> guaranteed to be thread-safe in C++11? Or can the individual 64-bit words be corrupted by simultaneous reads/writes? Even on 64-bit platforms? And how is this different from the old C++98 Standard?

Quotes from the Standard would be much appreciated.

UPDATE: based on this amazing paper by Hans Boehm on "benign" data races, a simple way to get bitten is for the compiler to cancel both XORs from insert_data() and data_is_present() to alway return true, e.g. if it finds a local code fragment like

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

解决方案

The C++11 specification defines pretty much any attempt by one thread to read or write a memory location that another thread is writing to as undefined behavior (absent the use of atomics or mutexes to prevent read/writes from one thread while another thread is writing).

Individual compilers may make it safe, but the C++11 specification doesn't provide coverage itself. Simultaneous reads are never a problem; it's writing in one thread while reading/writing in another.

And how is this different from the old C++98 Standard?

The C++98/03 standard doesn't provide any coverage with regard to threading. As far as the C++98/03 memory model is concerned, threading is not a thing that can possibly happen.

这篇关于是无锁的哈希没有std ::原子保证是线程安全的C ++ 11？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！