c++ - tbb:concurrent_unordered_map() - vector 中每个唯一元素的 ID？

Question

我想知道我编写的这段代码是否是线程安全的。我想为 vector 中的每个元素分配一个唯一的 ID，如果它能正常工作那就太好了:

• 唯一的名称始终具有相同的 ID。
• 两个不同的名称不能具有相同的 ID。

它使用Intel TBB(线程构建模块)作为concurrent_unordered_map。

C/C++ 代码:

#include "iostream"
#include <vector>
// Intels Threading Building Blocks (TBB).
// Installing:
// - Intel compiler: tick the "TBB" box in project config.
//-  MSVC compiler: Install vcpkg, then use: vcpkg install tbb:x64-windows.
#include "tbb/concurrent_unordered_map.h"

#include <atomic>

using namespace std;

std::atomic<int> id { 1 };

inline int GetUniqueId()
{
    return id++;
}

int main()
{
    // Imagine this has 10 million elements.
    vector<string> names {"tom", "bob", "harry", "harry", "harry", "harry", "peter"}; 

    // We want each name to have a unique ID.
    tbb::concurrent_unordered_map<string,int> nameToId;

    #pragma omp parallel for
    for(int i=0;i<names.size();i++) {
        if (nameToId.count(names[i]) == 0) {
            nameToId[names[i]] = GetUniqueId();
        }
    }

    for(auto& name : names) {
        cout << name << ": ID=" << nameToId[name] << "\n";
    }
}

输出:

tom: ID=1
bob: ID=2
harry: ID=3
harry: ID=3
harry: ID=3
harry: ID=3
peter: ID=4

Answer 1

检查和分配之间存在数据竞争。如果 ID 的分配和首次使用之间存在障碍或其他同步(如 OP 的示例中所示)，则假设 ID 连续体中允许存在漏洞，则可以忽略竞争。

如果您想在同一并行部分中使用“else”分支(ID 分配和使用之间没有障碍)或不允许出现空洞，则无论如何都需要锁。因为即使可以使用原子 CAS 和原子增量来实现分配协议(protocol)，它也会有一个繁忙的循环，因为我们需要一个具有两个原子操作的事务，其中一种或其他方式相当于自旋锁(除非使用不过多伦多证券交易所)。因此，请毫不犹豫地使用concurrent_hash_map及其锁定机制。避免锁争用的一个技巧是使用双重检查模式以及隐藏的(但已使用的)internal_fast_find 函数:

// Can really use tbb::concurrent_hash_map directly if it is not a data analytics app with this function on the hot path
template<typename K>
struct fast_map : public tbb::concurrent_hash_map<K, int> {
  using base_t=tbb::concurrent_hash_map<K, int>;
  using base_t::concurrent_hash_map;

#if !WORKAROUND_BUG // TBB_INTERFACE_VERSION < 11007 && TBB_INTERFACE_VERSION > ???
  typename base_t::const_pointer fast_find(const typename base_t::key_type& k) {
    return this->internal_fast_find(k);
  }
#else
  // See https://github.com/anton-malakhov/nyctaxi/blob/master/group_by.h#L78-L97
#endif
};

template<typename K>
int allocateId(const K &k, fast_map<K> &m) {
    auto *x = m.fast_find(k);
    if(x && x->second >= 0)
        return x->second;
    else {
        typename fast_map<K>::accessor a;
        bool uniq = m.insert(a, make_pair((K)k, int(-1)));
        if (!uniq) {
            return a->second;
        } else {
            return a->second = GetUniqueId();
        }
    }
}

(完整代码并在此处运行:http://coliru.stacked-crooked.com/a/4c29a2c95883c945)