多线程 unordered_map

Question

我在多线程环境中工作。基本上，我有一个 unordered_map 可以同时被多个线程访问。现在，我的算法是：

function foo(key) {
  scoped_lock()
  if key exists {
    return Map[key]
  }

  value = get_value()
  Map[key] = value
}

显然，此实现的性能不佳。有什么 algorithm/approach 可以用来提高性能吗？

编辑：

我做了很多测试，我想到了双重检查锁定。所以，我修改了代码：

function foo(key) {
  if key exists {
    return Map[key]
  }

  scoped_lock()
  if key exists {
    return Map[key]
  }

  value = get_value()
  Map[key] = value
}

实际上我只是在 scoped_lock() 之前添加了另一个检查。在这种情况下，假设函数被调用 N 次。如果第一个 m 调用 foo，其中 m < N 填充了地图，而下一个 N - m 调用仅从地图获取值，我不需要独占访问.此外，在 scoped_lock 之后还有另一个确保线程安全的检查。我对吗？无论如何，第一个代码的执行需要~208s，而第二个代码~200s。

Answer 1

这是一个实用工具class:

template<class T, class M=std::mutex, template<class...>class S=std::unique_lock, template<class...>class U=std::unique_lock>
struct mutex_protected {
  template<class F>
  auto read( F&& f ) const
  -> typename std::result_of<F&&(T const&)>::type
  {
    auto l = lock();
    return std::forward<F>(f)(data);
  }
  template<class F>
  auto write( F&& f ) 
  -> typename std::result_of<F&&(T&)>::type
  {
    auto l = lock();
    return std::forward<F>(f)(data);
  }
  mutex_protected(mutex_protected&&)=delete;
  mutex_protected& operator=(mutex_protected&&)=delete;

  template<class...Args>
  mutex_protected( Args&&...args ):
    data( std::forward<Args>(args)... )
  {}
private:
  mutable M m;
  T data;

  U<M> lock() { return U<M>(m); }
  S<M> lock() const { return S<M>(m); }
};

它，尤其是在 c++14 中，可以让您以易于编写的方式与受互斥锁保护的数据实例进行交互。

在c++14中你可以使用std::shared_timed_mutex，在c++17中你可以像这样使用std::shared_mutex：

template<class T>
using rw_guarded = mutex_guarded< T, std::shared_mutex, std::shared_lock >;

这样可以同时拥有多个 reader。但是你应该首先确定简单的互斥量是否足够快。

struct cache {
  using Key=std::string;
  using Value=int;
  using Map=std::unordered_map< Key, Value >;
  Value get( Key const& k ) {
    Value* r = table.read([&](Map const& m)->Value*{
      auto it = m.find(k);
      if (it == m.end()) return nullptr;
      return std::addressof( it->second );
    });
    if (r) return *r;
    return table.write([&](Map& m)->Value{
      auto it = m.find(k);
      if (it != m.end()) return it->second;
      auto r = m.insert( std::make_pair(k, 42) ); // construct data here
      return r.first->second;
    });
  }
private:
  mutex_guarded< std::unordered_map< Key, Value > > table;
};

将 mutex_guarded 升级到 rw_guarded 并切换到 reader-writer 锁。

这是一个更复杂的版本：

有两张地图；一个为了价值，一个为了共享未来的价值。

使用 reader 写锁（又名共享互斥）。

获取，获取共享锁。检查它是否在那里。如果是，return.

解锁第一张地图。锁定第二张地图以进行写作。如果密钥下还没有共享的未来，请添加一个。解锁地图2，不管你加不加，都等着共同的未来吧

完成后，锁定第一张地图以供阅读；检查结果是否已经存在。如果是，return它。如果没有，解锁，重新锁定写入，将数据移动到映射 1（如果不存在），return 第一个映射中的数据。

这旨在最大程度地减少映射 1 被独占锁定的时间，从而允许那里的最大并发性。

其他设计会优化其他考虑。

不使用operator[]。不要不要在没有激活某种锁的情况下与任何地图交互。知道哪些锁对应于哪些地图。请注意，在某些情况下可以在没有锁定的情况下读取元素（不是查找）。有时需要阅读共享事物的副本，而不是共享事物。查看每种类型的文档以确定哪些操作需要哪些锁。

多线程 unordered_map

Multithreading unordered_map

c++

multithreading

hashtable

c++11