concurrent_hash_map

concurrent_hash_map<Key, T, HashCompare > は、同時アクセスを許可するハッシュテーブルです。テーブルは、キーから T 型へのマップです。HashCompare 型は、キーをハッシュする方法と 2 つのキーを比較する方法を定義します。

次のサンプルは、キーが文字列で、対応するデータは、配列 Data で各文字列が現れる回数である concurrent_hash_map を構築します。

#include "tbb/concurrent_hash_map.h"
#include "tbb/blocked_range.h"
#include "tbb/parallel_for.h"
#include <string>
 
using namespace tbb;
using namespace std;
 
// ユーザー定義型を扱うハッシュと比較操作を定義する構造体
struct MyHashCompare {
    static size_t hash( const string& x ) {
        size_t h = 0;
        for( const char* s = x.c_str(); *s; ++s )
            h = (h*17)^*s;
        return h;
    }
    //! 文字列が等しい場合は true
    static bool equal( const string& x, const string& y ) {
        return x==y;
    }
};
 
// int に文字列をマップする並列ハッシュテーブル
typedef concurrent_hash_map<string,int,MyHashCompare> StringTable;
 
// 文字列の発生回数を数える関数オブジェクト
struct Tally {
    StringTable& table;
    Tally( StringTable& table_ ) : table(table_) {}
    void operator()( const blocked_range<string*> range ) const {
        for( string* p=range.begin(); p!=range.end(); ++p ) {
            StringTable::accessor a;
            table.insert( a, *p );
            a->second += 1;
        }
    }
};
 
const size_t N = 1000000;
 
string Data[N];
 
void CountOccurrences() {
    // 空のテーブルを構築
    StringTable table;
 
    // 発生回数をテーブルに格納
    parallel_for( blocked_range<string*>( Data, Data+N, 1000 ),
                  Tally(table) );
 
    // 発生回数を表示
    for( StringTable::iterator i=table.begin(); i!=table.end(); ++i )
        printf("%s %d\n",i->first.c_str(),i->second);
}

concurrent_hash_map は、std::pair<const Key,T> 型の要素のコンテナーとして動作します。通常、コンテナー要素にアクセスする場合、その更新または読み取りを行います。concurrent_hash_map テンプレート・クラスは、スマートポインターとして動作する accessor クラスと const_accessor クラスを使用して 2 つの目的をそれぞれサポートします。accessor は、update (write) アクセスを表します。要素を指す限り、accessor が完了するまで、テーブルのキーを参照する操作はすべてブロックされます。const_accessor は、読み取り専用 アクセスであることを除いて同じです。複数の const_accessors で同時に同じ要素を指すことができます。この機能は、要素が頻繁に読み取りされ、ほとんど更新されない状況における並行性 (コンカレンシー) を大幅に向上させます。

find メソッドおよび insert メソッドは、accessor または const_accessor を引数として使用します。この選択は、concurrent_hash_map に更新 と読み取り専用 アクセスのどちらを要求しているかを知らせます。いったんメソッドが返されると、accessor または const_accessor が破棄されるまでアクセスは続きます。要素へのアクセスはほかのスレッドをブロックするため、accessor または const_accessor の存在期間を短くしてください。このために、最内ブロックで宣言を行ってください。アクセスをブロックの終了よりも早く解放するには、release メソッドを使用してください。次のサンプルは、破棄に依存してスレッドの存在期間を終了する代わりに、release を使用するループボディーの再処理を示します。

        StringTable accessor a;
        for( string* p=range.begin(); p!=range.end(); ++p ) {
            table.insert( a, *p );
            a->second += 1;
            a.release();
        }

remove(key) メソッドも同時に操作できます。このメソッドは書き込みアクセスを暗黙的に要求します。そのため、キーを削除する前にその key でほかに残っているアクセスを待機します。

• HashCompare の詳細