我在多线程环境中工作。基本上,我有一个 unordered_map
可以同时被多个线程访问。现在,我的算法是:
function foo(key) {
scoped_lock()
if key exists {
return Map[key]
}
value = get_value()
Map[key] = value
}
显然,此实现的性能不佳。我可以使用任何算法/方法来提高性能吗?
编辑:
我做了很多测试,并考虑了双重检查锁定。所以,我修改了代码:
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
,填充 map 和下N - m
调用仅从 map 获取值,我不需要独占访问权限。此外,在 scoped_lock
之后还有另一个检查这确保了线程安全。我对吗?无论如何,第一个代码的执行需要大约 208 秒,而第二个代码需要大约 200 秒。
最佳答案
这是一个实用类:
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 >;
这使得能够同时拥有许多读者。但是您应该首先确定简单的互斥量是否足够快。
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
并切换为读写锁。
这是一个更复杂的版本:
有两张 map ;一个为了值(value),一个为了共享值(value)的 future 。
使用读写锁(又名共享互斥体)。
获取,获取共享锁。检查它是否在那里。如果是,返回。
解锁第一张 map 。锁定第二张 map 以进行写作。如果 key 下还没有共享的 future ,请添加一个。解锁 map 2,无论是否添加,都等待共同的 future 。
完成后,锁定第一张 map 以供阅读;检查结果是否已经存在。如果是,请返回。如果没有,解锁,重新锁定写入,将数据移动到 map 1(如果不存在),返回第一个 map 中的数据。
这旨在最大限度地减少周期映射 1 被独占锁定,从而允许那里的最大并发。
其他设计会优化其他考虑因素。
不要使用operator[]
。在没有激活某种锁的情况下,不要与任何 map 进行交互。知道哪些锁对应于哪些 map 。请注意,在某些情况下可以在没有锁定的情况下读取元素(不是查找)。有时需要阅读共享事物的拷贝,而不是共享事物。查看每种类型的文档以确定哪些操作需要哪些锁。
关于c++ - 多线程 unordered_map,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49240627/