スレッドセーフとインテルTBBのコンテナ

インテルTBBを通じて学ぶ並列処理(3)

並列ハッシュマップ：concurrent_hash_map

　キーと値を対応付け、それを素早く取り出せると便利な状況がたくさんあります。例えば、商品と価格、名前と電話番号などは対となるデータであり、それを直接管理できればプログラミングがやりやすくなります。このような時はハッシュテーブルを使用します。

　ハッシュテーブルとは、簡単に言うと整数以外のキーが使える配列のようなものです。配列はi[1]の様に添え字として自然数を使いますが、ハッシュテーブルはキーとして色々なオブジェクトが使えるので、文字列などのデータ型も使用できます。ハッシュテーブルでは、キーはハッシュ関数により値が決められ、そのキーに基づいて要素が格納されます。こうすることにより効率的な探索が可能となります。

　従来のC++プログラミングでは、一般的にはmapが使用されており、mapとconcurrent_hash_mapを比較すると使い方が分かると思います。従来のSTLの方はサンプルプロジェクトMap、TBBの方はConcurrent_Hash_Mapを用意したので見比べてください。

Map：mapコンテナを使用した従来のプログラム

#include <iostream>
#include <string>
#include <utility>
#include <map>
using namespace std;

//書籍の題名と税込価格のペアを宣言
typedef pair< string, int > BookPair;

//コードが読みやすいように別名を用意する
typedef map< string, int >::iterator BookIterator;

/*-------------------------------------------------------------------------------

    メインプログラム

----------------------------------------------------------------------------------*/
int main(void)
{
    //よく使う書籍を変数で用意する
    string ctm = "コンピュータプログラミングの概念・技法・モデル";

    //書籍データを作る
    BookPair books[] = {
        BookPair( "最新コンパイラ構成技法", 5040 ),
        BookPair( "ディジタル回路設計とコンピュータアーキテクチャ", 5040 ),
        BookPair( "実践 アジャイルテスト", 5040 ),
        BookPair( "オブジェクト指向入門 第2版　原則・コンセプト", 7200 ),
        BookPair( "オブジェクト指向入門 第2版　方法論・実践", 7140 ),
        BookPair( "ユースケースによるアスペクト指向ソフトウェア開発", 4725 ),
        BookPair( "ジェネレーティブ プログラミング", 8190 ),
        BookPair( ctm, 8610 ),
        BookPair( "コンピュータアーキテクチャ 定量的アプローチ 第4版", 8610 ),
        BookPair( "コンピュータアーキテクチャのエッセンス", 3990 )
    };
    int count = sizeof( books ) / sizeof( BookPair );

    //書籍テーブルを作成
    map< string, int > bookMap;
    for ( int i = 0; i < count; i++ ) {
        bookMap.insert( books[ i ] );
    }

    //書籍テーブルの内容を表示
    cout << "購入希望書籍一覧" << endl;
    for ( BookIterator i = bookMap.begin(); i != bookMap.end(); i++ ) {
        cout << "【" << i->first << "】価格：" << i->second << endl;
    }
    cout << endl;

    //幾つかの要素を削除
    cout << ctm << "と"
        << "オブジェクト指向入門 第2版　原則・コンセプト" << "を購入したのでリストから消します・・・"
        << endl;
    bookMap.erase( ctm );
    bookMap.erase( "オブジェクト指向入門 第2版　原則・コンセプト" );

    //再び書籍テーブルの内容を表示
    cout << "購入希望書籍一覧" << endl;
    for ( BookIterator i = bookMap.begin(); i != bookMap.end(); i++ ) {
        cout << "【" << i->first << "】価格：" << i->second << endl;
    }
    cout << endl;

    //検索をする
    cout << ctm << "は購入済み？：";
    BookIterator result = bookMap.find( ctm );
    if ( result == bookMap.end() ) {
        cout << "Yes!" << endl;
    } else {
        cout << "No!" << endl;
    }

    //終了
    cout << endl;
    return 0;
}

Concurrent_Hash_Map：TBBのconcurrent_hash_mapを使用したプログラム

#include <iostream>
#include <string>
#include <utility>
#include "tbb/concurrent_hash_map.h"
using namespace std;
using namespace tbb;

//書籍の題名と税込価格のペアを宣言
typedef pair< string, int > BookPair;

/*-------------------------------------------------------------------------------

    //ハッシュコードの作成と比較を定義する構造体

----------------------------------------------------------------------------------*/
struct BookHashCompare
{
    //題名の一文字目を使ってハッシュ
    static size_t hash( const string& title )
    {
        return static_cast< size_t >( title[ 0 ] );
    }

    //題名が等しい場合true
    static bool equal ( const string& x, const string& y )
    {
        return x == y;
    }
};
//コードが読みやすいように別名を用意する
typedef concurrent_hash_map< string, int, BookHashCompare > BookTable;
typedef concurrent_hash_map< string, int, BookHashCompare >::iterator BookIterator;

/*-------------------------------------------------------------------------------

    メインプログラム

----------------------------------------------------------------------------------*/
int main(void)
{
    //よく使う書籍を変数で用意する
    string ctm = "コンピュータプログラミングの概念・技法・モデル";

    //書籍データを作る
    BookPair books[] = {
        BookPair( "最新コンパイラ構成技法", 5040 ),
        BookPair( "ディジタル回路設計とコンピュータアーキテクチャ", 5040 ),
        BookPair( "実践 アジャイルテスト", 5040 ),
        BookPair( "オブジェクト指向入門 第2版　原則・コンセプト", 7200 ),
        BookPair( "オブジェクト指向入門 第2版　方法論・実践", 7140 ),
        BookPair( "ユースケースによるアスペクト指向ソフトウェア開発", 4725 ),
        BookPair( "ジェネレーティブ プログラミング", 8190 ),
        BookPair( ctm, 8610 ),
        BookPair( "コンピュータアーキテクチャ 定量的アプローチ 第4版", 8610 ),
        BookPair( "コンピュータアーキテクチャのエッセンス", 3990 )
    };
    int count = sizeof( books ) / sizeof( BookPair );

    //書籍テーブルを作成
    BookTable bookMap;
    for ( int i = 0; i < count; i++ ) {
        bookMap.insert( books[ i ] );
    }

    //書籍テーブルの内容を表示
    cout << "購入希望書籍一覧" << endl;
    for ( BookIterator i = bookMap.begin(); i != bookMap.end(); i++ ) {
        cout << "【" << i->first << "】価格：" << i->second << endl;
    }
    cout << endl;

    //幾つかの要素を削除
    cout << ctm << "と"
        << "オブジェクト指向入門 第2版　原則・コンセプト" << "を購入したのでリストから消します・・・"
        << endl;
    bookMap.erase( ctm );
    bookMap.erase( "オブジェクト指向入門 第2版　原則・コンセプト" );

    //再び書籍テーブルの内容を表示
    cout << "購入希望書籍一覧" << endl;
    for ( BookIterator i = bookMap.begin(); i != bookMap.end(); i++ ) {
        cout << "【" << i->first << "】価格：" << i->second << endl;
    }
    cout << endl;

    //検索をする
    cout << ctm << "は購入済み？：";
    BookTable::const_accessor accessor;
    bool result = bookMap.find( accessor, ctm );
    if ( result == false ) {
        cout << "Yes!" << endl;
    } else {
        cout << "No!" << endl;
    }

    //終了
    cout << endl;
    return 0;
}

　このサンプルプロジェクトは、書籍の題名と価格を関連付けた要素を格納するコンテナに対して、挿入／削除／検索を実行する簡単なものです。違いはmapコンテナはハッシュマップではなく、ハッシュを行うための関数の定義が必要ないのに対し、concurrent_hash_mapコンテナはハッシュマップなので定義が必要な点です。残念ながらSTLにはハッシュマップが用意されておらず、従来のプログラミングではmapで代用することが多々ありました。一方、TBBでは最初からハッシュテーブルがあるのでそれを使用します。

　並列ハッシュが定義するべき関数は、ハッシュ値を生成する関数と、要素の等価性を判定する関数です。この2つの関数を用意して、コンテナを定義するのがconcurrent_hash_mapコンテナの基本的な使い方です。

　なお、concurrent_hash_mapコンテナは必ずしも関数が必要というわけではなく、関数の定義を省略して使用できますが、ハッシュテーブルはデータが偏ってしまうと非常に性能が悪くなりますので、使用する際にはハッシュ関数を定義するのがよいでしょう。

　以上で執筆時点で存在するすべてのインテルTBBのコンテナの解説が終わりました。最後に、インテルTBBのコンテナを使用する理由を解説します。