互斥地圖數據結構

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