concurrent_hash_map

concurrent_hash_map#

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

次の例では、キーが文字列で、対応するデータが Data 配列内でそれぞれの文字列が出現する回数である、concurrent_hash_map を構築します。

#include "oneapi/tbb/concurrent_hash_map.h" 
#include "oneapi/tbb/blocked_range.h" 
#include "oneapi/tbb/parallel_for.h" 
#include <string> 

using namespace oneapi::tbb; 
using namespace std; 

// ユーザータイプのハッシュおよび比較操作を定義する構造 
struct MyHashCompare { 
    size_t hash( const string& x ) const { 
        size_t h = 0; 
        for( const char* s = x.c_str(); *s; ++s ) 
            h = (h*17)^*s; 
        return h; 
    } 
    //! 文字列が等しい場合は True 
    bool equal( const string& x, const string& y ) const { 
        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 は、更新 (書き込み) アクセスを表します。要素を指す限り、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(); 
}

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

HashCompare の詳細