「データ構造とアルゴリズム」再入門

Chain型ハッシュ: 並行処理編 Part 2

ソースはGitHubに移行しました。

FineGrained Hash Table (細粒度ハッシュテーブル)

細粒度ハッシュテーブルを実装する。実装自体は素直で非常に簡単だが、ベンチマーク結果は思ったほどではない。 使いどころを選ぶのだろうが、並行プログラミングはいろいろと難しい。
ハッシュ全般とこのアルゴリズムの位置付けについてはこちらを必読。

ソースはGitHubに移行しました。

なお、通常のアルゴリズム解説ならば必須の、ハッシュ関数に関する議論は一切行わない。 ここではハッシュ関数hashCode()を"keyをテーブルサイズで割った余り"で定義する。

static unsigned int hashCode(lkey_t key, const hashtable_t * ht)
{
    return (key % ht->table_size);
}

データ構造

データ構造node_t、list_t、hashtable_tを定義する。 hashtable_tはハッシュテーブルの本体、 list_tはハッシュテーブルの各要素に付属するList、node_tはListに連結するnodeのデータ構造である。

以降、共通のデータ型として"common.h"に"bool_t"、"lkey_t"、"val_t"を定義する。 "bool_t"は自明、 "lkey_t"はnodeのkey、"val_t"はnodeのvalを保持する。

common.h:

typedef bool bool_t;
typedef uint64_t lkey_t;
typedef int64_t  val_t;

次に、nodeとlist、およびhashtableのデータ構造を示す。

RefinableHash.h

typedef struct _node_t
{
  lkey_t key;            /* key */
  val_t value;           /* 値 */

  struct _node_t *next;  /* 次のnodeへのポインタ*/
} node_t;

typedef struct _list_t
{
  node_t *head;
  pthread_mutex_t *mtx;
} list_t;

typedef struct _hashtable_t
{
  unsigned long int setSize;        /* 全node数 */

  list_t *bucket;                   /* ハッシュテーブル本体 */
  unsigned int table_size;          /* ハッシュテーブルの大きさ(長さ) */

  list_t *old_bucket;               /* resizeする際に、一時的に利用するハッシュテーブル */
  unsigned int old_table_size;      /* old_bucketの大きさ = resize前のテーブルの大きさ */

} hashtable_t;

node_tは(key,val)のペアと、次のnodeへのポインタを保持する。

list_tにはリストの先頭headが確保される。
リストの要素毎にpthread_mutexでLockをかけられるようにしている。

hashtable_tには全ノード数を記録するsetSize、 ハッシュテーブル本体であるbucketとその大きさを記録するtable_size、 およびresize()でテーブルサイズを変更する際に、一時的にこれまでのテーブル(へのポインタ)を保持する old_bucketとそのサイズを記録するold_table_sizeがある。

基本関数

ハッシュテーブルの生成

/*
 * bool_t *init_list(list_t *l)
 *
 * list_t *lにノードheadを生成する。
 *
 * 成功すればtrue、失敗ならfalseを返す。
 *
 */
static bool_t list_init(list_t * l)
{

  if ((l->head = (node_t *) calloc(1, sizeof(node_t))) == NULL) {
    elog("calloc error");
    return false;
  }
  l->head->next = NULL;

  /* mtxの設定はinit_bucket()で行う */
  if ((l->mtx = (pthread_mutex_t *) calloc(1, sizeof(pthread_mutex_t))) == NULL) {
    elog("calloc error");
    free (l->head);
    return false;
  }

  return true;
}
/*
 * bool_t init_bucket(hashtable_t * ht, const unsigned int init_table_size, const unsigned int new_table_size)
 *
 * ハッシュテーブルhtの各要素を初期化(リストの初期化)する。
 *
 * 成功すればtrue、失敗すればfalseを返す。
 */
static bool_t
init_bucket(hashtable_t * ht, const unsigned int init_table_size,
	    const unsigned int new_table_size)
{
    unsigned int i;
#ifdef PTHREAD_MUTEX_FAST_NP
    pthread_mutexattr_t mtx_attr;
#endif

    if ((ht->bucket =
	 (list_t *) calloc(new_table_size, sizeof(list_t))) == NULL) {
      elog("calloc error");
      return false;
    }

    for (i = 0; i < new_table_size; i++) {
      if (list_init(&ht->bucket[i]) != true)
	return false;

      if (i < init_table_size) {
	ht->bucket[i].mtx = ht->old_bucket[i].mtx;
      }
      else {
#ifdef PTHREAD_MUTEX_FAST_NP
	pthread_mutexattr_init(&mtx_attr);
	pthread_mutexattr_settype(&mtx_attr, PTHREAD_MUTEX_FAST_NP);
	pthread_mutex_init(ht->bucket[i].mtx, mtx_attr);
	pthread_mutexattr_destroy(&mtx_attr);
#else
	pthread_mutex_init(ht->bucket[i].mtx, NULL);
#endif
      }
    }

    return true;
}

static void free_bucket(list_t * bucket, const unsigned int table_size)
{
    int i;
    for (i = 0; i < table_size; i++) {
      pthread_mutex_destroy(bucket[i].mtx);
      free(&(*bucket[i].head));
    }
    free(bucket);
}

/*
 * hashtable_t *init_hashtable(const unsigned int table_size)
 *
 * 大きさtable_sizeのハッシュテーブルを生成する。
 *
 * 成功すれば、そのポインタを返す。失敗すればNULLを返す。
 * 
 */

hashtable_t *init_hashtable(const unsigned int table_size)
{
    hashtable_t *ht;

    if ((ht = (hashtable_t *) calloc(1, sizeof(hashtable_t))) == NULL) {
      elog("calloc error");
      return NULL;
    }

    ht->table_size = table_size;
    ht->setSize = 0;

    if (init_bucket(ht, 0, table_size) != true) {
	free(ht);
	return NULL;
    }

    return ht;
}

void free_hashtable(hashtable_t * ht)
{
    free_bucket(ht->bucket, ht->table_size);
    free(ht);
}

ノードの追加

/*
 * bool_t add_node_op(list_t * l, node_t * newNode)
 *
 * ノードnewNodeをリストlに追加する。
 *
 * 成功すればtrue、失敗ならfalseを返す。
 *
 */
static bool_t add_node_op(list_t * l, node_t * newNode)
{
    node_t *pred, *curr;
    bool_t ret = true;

    assert(l->head != NULL);
    pred = l->head;
    curr = pred->next;

    if (curr == NULL) {
	l->head->next = newNode;
	newNode->next = NULL;
    } else {

	while (curr != NULL && curr->key < newNode->key) {
	    pred = curr;
	    curr = curr->next;
	}

	if (curr == NULL || newNode->key != curr->key) {
	    newNode->next = curr;
	    pred->next = newNode;
	} else
	    ret = false;

    }
    return ret;
}


/*
 * bool_t add_node(list_t * l, const lkey_t key, const val_t val)
 *
 * リストlにノード(key,val)を生成して追加する。
 *
 * 成功するとtrue、失敗するとfalseを返す。
 *
 */
static bool_t add_node(list_t * l, const lkey_t key, const val_t val)
{
    node_t *newNode;

    if ((newNode = create_node(key, val)) == 0)
	return false;

    if (add_node_op(l, newNode) != true) {
	free_node(newNode);
	return false;
    }

    return true;
}

/*
 * bool_t add(hashtable_t * ht, const lkey_t key, const val_t val)
 *
 * ハッシュテーブルhtにnode(key,val)を追加する。
 *
 * 成功すればtrue、失敗すればfalseを返す。
 */
bool_t add(hashtable_t * ht, const lkey_t key, const val_t val)
{
    unsigned int myBucket, table_size;
    bool_t ret = false;
    int retry = 2;


    do {
	table_size = ht->table_size;
	myBucket = hashCode(key, ht);	/* T1: */
	lock(ht->bucket[myBucket].mtx);	/* T2: */

	if (table_size == ht->table_size)	/* T1とT2の間でresize()が実行された場合の対処 */
	{
	    if (add_node(&ht->bucket[myBucket], key, val) == true) {
		ht->setSize++;
		ret = true;
		unlock(ht->bucket[myBucket].mtx);
		break;
	    }
	}

	unlock(ht->bucket[myBucket].mtx);
    }
    while (retry-- > 0);

    if (policy(ht)) {
      resize(ht);
      fprintf (stderr, "Resized\n");
    }
    return ret;
}

関数add_node()内部で呼ぶnode生成関数create_node()を示す。

/*
 * node_t *create_node(const lkey_t key, const val_t val)
 *
 * (key, val)を持つnodeを生成する。
 *
 * 成功すればnodeへのポインタを返す。失敗すればNULLを返す。
 */
static node_t *create_node(const lkey_t key, const val_t val)
{
    node_t *newNode;

    if ((newNode = (node_t *) calloc(1, sizeof(node_t))) == NULL) {
      elog("calloc error");
	return NULL;
    }

    newNode->key = key;
    newNode->value = val;
    return newNode;
}

nodeの削除

/*
 * bool_t delete_node(list_t * l, const lkey_t key, val_t * getval)
 *
 * リストlからノード(key,val)を削除する。
 *
 * 成功するとgetvalにvalを代入してtrueを返す。失敗するとfalseを返す。
 *
 */
static bool_t delete_node(list_t * l, const lkey_t key, val_t * getval)
{
    node_t *pred, *curr;

    pred = l->head;
    curr = pred->next;

    if (curr == NULL)
	return false;

    while (curr != NULL && curr->key < key) {
	pred = curr;
	curr = curr->next;
    }

    if (key == curr->key && curr != NULL) {
	*getval = curr->value;
	pred->next = curr->next;
	free_node(curr);
    } else
	return false;

    return true;
}

/*
 * bool_t delete(hashtable_t * ht, const lkey_t key, val_t * getval)
 *
 * ハッシュテーブルhtからkeyを持つnodeを削除し、そのnodeのvalを*valに書き込む。
 * keyが存在しない場合は失敗。
 *
 * 成功すればtrue、失敗すればfalseを返す。
 */
bool_t delete(hashtable_t * ht, const lkey_t key, val_t * getval)
{
    unsigned int myBucket, table_size;
    bool_t ret = false;
    int retry = 2;

    do {
	table_size = ht->table_size;
	myBucket = hashCode(key, ht);	/* T1: */
	lock(ht->bucket[myBucket].mtx);	/* T2: */

	if (table_size == ht->table_size)	/* T1とT2の間でresize()が実行された場合の対処 */
	{
	    if (delete_node(&ht->bucket[myBucket], key, getval) == true) {
		ht->setSize--;
		ret = true;
		unlock(ht->bucket[myBucket].mtx);
		break;
	    }
	}
	unlock(ht->bucket[myBucket].mtx);
    }
    while (retry-- > 0);

    return ret;
}

ノードの検索

/*
 * bool_t find_node(list_t * l, lkey_t key)
 *
 * リストlにkeyを持つノードがあるか否か調べる。
 *
 * 成功すればtrue、失敗すればfalseを返す。
 */
static bool_t find_node(list_t * l, lkey_t key)
{
    node_t *pred, *curr;

    pred = l->head;
    curr = pred->next;

    if (curr == NULL) {
	return false;
    } else {

	while (curr != NULL && curr->key < key) {
	    pred = curr;
	    curr = curr->next;
	}

	if (curr == NULL || key != curr->key)
	    return false;
    }
    return true;
}

/*
 * bool_t find(hashtable_t * ht, const lkey_t key)
 *
 * ハッシュテーブルhtからkeyを持つnodeを検索し、そのnodeのvalを*valに書き込む。
 * keyが存在しない場合は失敗。
 *
 * 成功すればtrue、失敗すればfalseを返す。
 */
bool_t find(hashtable_t * ht, const lkey_t key)
{
    unsigned int myBucket = hashCode(key, ht);
    bool_t ret;

    lock(ht->bucket[myBucket].mtx);
    ret = find_node(&ht->bucket[myBucket], key);
    unlock(ht->bucket[myBucket].mtx);

    return ret;
}

ハッシュテーブルの再構築(resize())

static bool_t policy(hashtable_t * ht)
{
    return ((int) (ht->setSize / ht->table_size) > 4 ? true : false);
}

static void resize(hashtable_t * ht)
{
    list_t *l;
    node_t *pred, *curr;
    unsigned int i, myBucket, table_size;

    table_size = ht->table_size;
    for (i = 0; i < table_size; i++)
	lock(ht->bucket[i].mtx);

    if (table_size != ht->table_size) {
	for (i = 0; i < table_size; i++)
	    unlock(ht->bucket[i].mtx);
	return;
    }

    ht->old_table_size = ht->table_size;
    ht->old_bucket = ht->bucket;

    if (init_bucket(ht, ht->table_size, ht->table_size * 2) == false)
	return;

    ht->table_size *= 2;

    for (i = 0; i < ht->old_table_size; i++) {
	l = &ht->old_bucket[i];

	pred = l->head;
	curr = pred->next;
	while (curr != NULL) {
	  pred->next = curr->next;	/*      next = curr->next;      pred->next = next; */
	  
	  myBucket = hashCode(curr->key, ht);
	  add_node_op(&ht->bucket[myBucket], curr);
	  
	  curr = pred->next;
	}
    }

    for (i = 0; i < ht->old_table_size; i++)
	unlock(ht->bucket[i].mtx);

    free_bucket(ht->old_bucket, ht->old_table_size);

}

実行

ソースはGitHubに移行しました。

---

---