互斥地图数据结构

Question

问题

• 我有一个目录D，我希望把(K, V)双为
• void save(K, V)与内容V保存文件名K到目录D
  • 有“火忘记“语义 - 函数可能会在实际上将文件保存到磁盘之前返回
• 目录D是定义save功能
• 呼叫至void save(K, V)类C的领域应该同时运行
  • 使用tbb::task并发
  • 没有两个文件中写入了相同的密钥可以同时运行
  • 也就是说，如果两个线程同时调用save(K, V1)和save(K, V2)，则结果应该是D中名为K的文件，其内容等于要么V1或V2（但不损坏）

计划的方法

• 选择一个散列函数H映射K到std::size_t
• 选择一个整数N > 1
• 授课C互斥tbb::mutex mutex_map[N]
• void save(K, V)等待的阵列，以获取有关mutex_map[H(K) % N]锁履行其写入文件

问题

• 这是一个明智的做法？
• 你能想出一个可能比这更有优势的替代方案吗？
• 是否有一些tbb数据结构已经封装了这个互斥量映射的概念？
  • 想象一个像std::map<TKey, tbb::mutex>的东西，但界面给出了每个可能的键同时具有关联的互斥体的外观。

Answer 1

是的，这是一个非常明智的做法。我想不出一个替代方案（除了使用std::mutex而不是tbb:mutex这些简单的替代方案。）

你应该选择N较大的互斥量，你认为它会被同时锁定。该birthday paradox说，如果你希望有ķ线程同时试图锁定，则具有至少一个伪哈希冲突的概率大于50％，直到你得到N >Ø（K ）。

我不知道tbb数据结构就像是一个互斥体地图。但内部我相信tbb :: malloc使用你所暗示的技巧（线程被随机分配给独立的malloc数据结构），并且tbb :: concurrent_hash_map被实现为每个哈希桶都有一个互斥锁。

Answer 2

我的实现为后人

#include <vector> 
#include <functional> 
#include <tbb/mutex.h> //could of course use std::mutex instead, if available 

template <typename Key, typename Hash = std::hash<Key>> 
class mutex_map 
{ 
public: 
    typedef Key key_type; 
    typedef tbb::mutex value_type; 
    static const std::size_t default_bucket_count = 16; 

private: 
    std::vector<value_type> mutexes; 
    Hash hash; 

public: 
    mutex_map(
     std::size_t bucket_count = default_bucket_count, 
     const Hash& hash = Hash()) 
     : hash(hash) 
    { 
     mutexes.resize(bucket_count); 
    } 

    std::size_t size() const 
    { 
     return mutexes.size(); 
    } 

    value_type& get(const Key& key) 
    { 
     auto n = hash(key) % size(); 
     n += (n < 0) * size(); 
     return mutexes[n]; 
    } 
};