sile/AMP-CH13.md

## AMP-CH13.md

      
    Raw
  

              AMP-CH13.md
            
          
    13 並列ハッシュと自然な並列

注意:

何故か"item"を"要素"と訳しているところが多いです

13.1 導入

これまでの章:

キューやスタック、カウンタ等の並列性を抽出する方法を学んだ
これらは並列化の機会が少ないようにみえるデータ構造

本章:

並列ハッシュテーブル(ハッシュセット)を実装する

セットの一種

add, remove, contains等が(平均して)定数時間で実行可能


自然に並列化されているように見えるデータ構造

disjoint-access-parallel
並列メソッド呼び出しは異なる場所にアクセスしがちであり、それは同期の必要性の少なさを示唆する


実際には効率的な並列ハッシュテーブルを実装するのは簡単ではない


ロックの有無、オープン／クローズの両方の実装を取り扱う

まずは簡単なロック有りのクローズド・ハッシュテーブルから
! オープンやクローズなハッシュ周りの説明が必要なら口頭で補足


補足:

メモリは増やせるけど、CPUは難しいから、両者のトレードオフが発生した場合は、メモリサイズより処理の軽さを優先します
事例的な事実: ほとんどのアプリケーションでは「containsが90%、addが9%、removeは1%」
テーブルサイズの拡張は重要だけど、縮小はそうでのないので今回は省略 (興味のある人は演習問題で)

13.2 クローズド・ハッシュセット

Pragma 13.2.1


List<T>インタフェースを使う

add(x)、get(i)、contains(x)、etc


実装はArrayListクラス


まず今回扱う並列クローズド・ハッシュセット全てに共通するベースハッシュセットを実装する。
この実装はハッシュセットに必要な全メソッドを備えている訳ではない:

acquire, release, policy, __resize__は、これを継承した具体的なハッシュセットクラスが実装する

// Figure 13.1, 13.2
public abstract class BaseHashSet<T> {
  protected List<T>[] table;
  protected int setSize;

  public BaseHashSet(int capacity) {
    setSize = 0;
    table = (List<T>[]) new List[capacity];
    for (int i = 0; i < capacity; i++) {
      table[i] = new ArrayList<T>();
    }
  }

  public boolean contains(T x) {
    acquire(x); // ロック獲得
    try {
      int myBucket = x.hashCode() % table.length;
      return table[myBucket].contains(x);
    } finally {
      release(x); // ロック解放
    }
  }

  public boolean add(T x) {
    boolean result = false;
    acquire(x);
    try {
      int myBucket = Math.abs(x.hashCode() % table.length);
      if (! table[myBucket].contains(x)) {
        table[myBucket].add(x);
        result = true;
        size++;
      }
    } finally {
      release(x);
    }
    if (policy())
      resize();
    return result;
  }
}
定数期待時間を保証するためには、バケット配列（テーブル）はどの程度の大きなすべきか？

addメソッドは次の二段階の処理を行う:


xのハッシュ値を計算する: O(1)


バケットの末尾に要素を追加する: O(length(バケット))


=> 定数時間を期待するのは、バケットのサイズが定数オーダーである必要がある
=> バケット配列のサイズは、要素数に比例したものである必要がある


要素数は時間の経過とともに変化するので、テーブルのリサイズ処理は必須

いつリサイズするか、と、どうやって他のメソッドと同期を取るか、も決める必要がある:

たくさんの妥当な選択肢がある
シンプルな戦略:

平均バケットサイズが固定の閾値を超えた場合にリサイズする


別の戦略:

バケット閾値とグローバル閾値を考慮する:

(例えば)1/4以上のバケットがバケット閾値を超えた場合に、テーブルのサイズを二倍にする or
一つのバケットのサイズがグローバル閾値を超えた場合に、テーブルのサイズを二倍にする


どちらの戦略も上手くいくだろう(in practice)、他の戦略でも同様
オープン・ハッシュの場合は、もっと複雑 (詳細は後の節で)

13.2.1 粗粒な(coarse-grained)ハッシュセット

粗粒なハッシュセットの実装:

BaseHashSet<T>を継承
単一の再入可能ロック
平均バケットサイズが4を超えたらリサイズ (テーブルのサイズを二倍に)

// Figure 13.3, 13.4

public class CoarseHashSet<T> extends BaseHashSet<T> {
  final Lock lock;

  CoarseHashSet(int capacity) {
    super(capacity);
    lock = new ReentrantLock();
  }

  public final void acquire(T x) {
    lock.lock();
  }

  public void release(T x) {
    lock.unlock();
  }

  public boolean policy() {
    return setSize / table.length > 4;
  }

  public void resize() {
    // サイズを二倍にした新しいテーブルを用意して、そこに要素を詰め直しているだけ
    int oldCapacity = table.length;
    lock.lock();
    try {
      if (oldCapacity != table.length) {
        return; // someone beat us to it
      }

      int newCapacity = 2 * oldCapacity;
      List<T> oldTable = table;
      table = (List<T>[]) = new List[newCapacity];
      for (int i = 0; i < newCapacity; i++)
        table[i] = new ArrayList<T>();
      for (List<T> bucket : oldTable) {
        for (T x : bucket) {
          table[x.hashCode() % table.length].add(x);
        }
      }
    } finally {
      lock.unlock();
    }
  }
}
13.2.2 縞々な(striped)ハッシュセット

粗粒なハッシュセットは理解が用意で実装も簡単:

不運なことに逐次ボトルネックがある
メソッド呼び出しは無駄に全体をロックしてしまう

並列性がより高く、競合がより少ないハッシュセットを紹介する:

全体を同期する単一のロックは廃止し、セットを独立して同期されるピース群に分割する
lock striping と呼ばれるテクニックを導入

実装:

最初にバケットの数と等しい数のロックを用意する
ロックの数はテーブルのリサイズの際にも変化しない (理由は後述)
バケットとロックの対応:

i番目のバケット用にはi mod ロック数番目のロックを使用する
図13.6
各ロックが対応するバケットの配置は連接ではなくstriped


ロックをリサイズしない理由:

ロックとバケットが一対一の対応だと、テーブルサイズが大きい場合のメモリ消費量が心配

競合が小さい場合は割に合わない


テーブルのリサイズは単純だけど、(使用中の)ロック配列の場合はより複雑 (詳細は13.2.3)

resizeメソッドの実装はCarseHashSetの時とほぼ同様:

リサイズ前後でのロックの獲得対象が、一つから複数(全部)に変わった
並列呼び出し時にデッドロックしないか？

ロック獲得順序が決まっているから大丈夫


// Figure 13.5, 13.7
public class StripedHashSet<T> extends BaseHashSet<T> {
  final ReentrantLock[] locks;

  public StripedHashSet(int capacity) {
    super(capacity);
    locks = new Lock[capacity];
    for (int j = 0; j < locks.length; j++) {
      locks[j] = new ReentrantLock();
    }
  }

  public final void acquire(T x) {
    locks[x.hashCode() % locks.length].lock();
  }

  public final void release(T x) {
    locks[x.hashCode() % locks.length].unlock();
  }

  public void resize() {
    int oldCapacity = table.length;
    for (Lock lock : locks) {
      lock.lock();
    }
    try {
      if (oldCapacity != table.length) {
        return; // someone beat us to it
      }
      int newCapacity = 2 * oldCapacity;
      List<T>[] oldTable = table;
      table = (List<T>[]) new List[newCapacity];
      for (List<T> bucket : oldTable) {
        for (T x : bucket) {
          table[x.hashCode() % table.length].add(x);
        }
      }
    } finally {
      for (Lock lock : locks) {
        lock.unlock();
      }
    }
  }
}
まとめると:

縞々ロックは、単一の粗粒ロックよりも、高い並列性を許可する

異なるロックにハッシュされる要素に対するメソッド呼び出し同士は、並列に処理を進めることが可能なため


add、contains、__remove__は定数期待時間を取る

__resize__は線形時間となり、それは"stop-the-world"な操作
テーブル容量の増加中は、全ての並列メソッド呼び出しが停止させられる


13.2.3 改良可能(refinable)なハッシュセット

どうすればロック配列のサイズを変更できるか？

テーブルサイズが増加しても、一つの縞(ロック)が扱う要素が増えないように(粒度を維持可能に)したい
リサイズはまれにしか行われないので、他のメソッドの効率を(極力)劣化させずにリサイズできるようにしたい
=> 相互排他用のフラグを一つ追加すれば実現可能

実現方法:

ownerフィールドを追加する (Figure 13.8)

型はAtomicMarkableReference<Tread>
マーク(boolean)は「リサイズ中かどうか」を示す
値には「リサイズ中のスレッド」を格納している (リサイズ中ではないならnull)

! マークは不要では？ (マークがfalseの場合は値も常にnullになり、逆も同様)


ownerはresize()と他のメソッドの相互排他フラグとして使用される:

! 本では「他のメソッド」ではなく「any of the add() methods」と書かれているが、add以外のも影響ありそう
リサイズ中には、成功する更新処理は存在しない
更新中には、成功するリサイズ処理は存在しない


aqruireメソッド:

ownerがいる間はビジーループ
その後、対象要素に対応するロックを獲得するが、もし以下の条件のいずれかが満たされた場合はリトライする

a. 自分以外の誰かがリサイズ中
b. ロック配列が更新(リサイズ)された
要はロック獲得に用いた配列が古くなっているならリトライする


resizeメソッド:

StripedHashSetのものとほぼ同様
ロック方法が「ownerフラグをセット => quiesceメソッドでロック群が未使用になるのを待機」となっているのが差異
クリティカルセクションの中では、単純に配列のサイズを二倍にしているだけ


// Figure 13.8, 13.9, 13.10, 13.11

// Figure 13.8
public class RefinableHashSet<T> extends BaseHashSet<T> {
  AtomicMarkableReference<Thead> owner;
  volatile ReentrantLock[] locks;

  public RefinableHashSet(int capacity) {
    super(capacity);
    locks = new ReentrantLock[capacity];
    for (int i = 0; i < capacity; i++) {
      locks[i] = new ReentrantLock();
    }
    owner = new AtomicMarkableReference<Thead>(null, false);
  }

  // Figure 13.9
  public void acquire(T x) {
    boolean[] mark = {true};
    Thread me = Thread.currentThread();
    Thread who;
    while (true) {
      do {
        who = owner.get(mark);
      } while (mark[0] && who != me);
      ReentrantLock[] oldLocks = locks;
      ReentrantLock oldLock = oldLocks[x.hashCode() % oldLocks.length];
      oldLock.lock();
      who = owner.get(mark);
      if ((!mark[0] || who == me) && locks == oldLocks) {
        return;
      } else {
        oldLock.unlock();
      }
    }
  }

  public void release(T x) {
    locks[x.hashCode() % locks.length].unlock();
  }

  // Figure 13.10
  public void resize() {
    int oldCapacity = table.length;
    boolean[] mark = {false};
    int newCapacity = 2 * oldCapacity;
    Thead me = Thread.concurrentThread();
    if (owner.compareAndSet(null, me, false, true)) {
      try {
        if (table.length != oldCapacity) { // someone else resized first
          return;
        }
        quiesce();
        List<T>[] oldTable = table;
        table = (List<T>[]) new List[newCapacity];
        for (int i = 0; i < newCapacity; i++)
          table[i] = new ArrayList<T>();
        locks = new ReentrantLock[newCapacity];
        for (int j = 0; j < locks.length; j++) {
          locks[j] = new ReentrantLock();
        }
        initializeFrom(oldTable);
      } finally {
        owner.set(null, false);
      }
    }
  }

  // Figure 13.11
  protected void quiesce() {
    for (ReentrantLock lock : locks) {
      while (lock.isLocked()) {}
    }
  }
}
まとめると:

バケットとロックの両方の数を継続的にリサイズできるハッシュテーブルはデザイン可能
このアルゴリズムの制限:

スレッドはテーブルのリサイズ中には要素にアクセスすることができない


13.3 ロックフリーハッシュセット

ロックフリーなハッシュセットを実装する:

リサイズはインクリメンタルに行われる

各addメソッドがリサイズ処理の小さな一部分を実行する
"stop-the-world"なリサイズが不要になり、contains/add/removeメソッドは定数期待時間で実行可能


個別のバケットをロックフリーにするだけでは、テーブル全体はロックフリーにはならない

リサイズ処理は古いバケット群から新しいバケット群へのアトミックなエントリ移動を要求するため
アトミックに移動できないとしたら、エントリの一時的な喪失や重複が生じてしまうかもしれない


ロックは使わないので、CAS等のアトミックメソッド使って同期数r必要がある

不運なことに、これらのメソッドは単一のメモリ位置に対してのみ作用する
これは、一つのリンクリストから別のリストにアトミックにノードを移動するのを難しくする


13.3.1 再帰的な分割順序(Recursive Split-Ordering)

慣習的なハッシュ構造を裏返したハッシュセットの実装について述べる:

バケット群の中に要素群を入れる代わりに、要素群の間にバケット群を差し挟む

より具体的にいえば:

全ての要素を一つのロックフリーリストで保持する (ex. 9章のLockFreeList)
バッケットは、そのリストへの参照に過ぎない

リストのサイズが増えるに従い、バケットの参照を追加する
全ての要素が、その前に位置するバケットから離れすぎないようにするため


このアルゴリズムは、一度要素がリスト内に格納されたら、以後は決して移動しないことを保証する

ただし、要素はrecursive split-orderアルゴリズムに従って挿入されることが要求される


ロックフリーハッシュセットの構成要素:

図13.12のパートbを参照

二つの構成要素を持つ:

ロックフリーリンクリスト
リストへの参照の拡張可能な配列: この参照は論理的なバケットとなる


全ての要素はリストの先頭から到達可能、バケット参照は検索の際のショートカットを提供する
主要な挑戦は、セット内の要素の数が増加しても、バケットがよく分散されていることを保証すること

バケットは、全てのノードへの定数時間アクセスを許すように配置されているべき
新しいバケットは、リスト上の領域を疎にカバーするように割り当てられなければならない


前提および用語:

ハッシュセットの容量 N は、ニの累乗とする
バケット配列の初期サイズは2:

最初の値は、空のリストを参照する
残りの値はnullとなる


bucketSizeという変数を、この可変なバケット構造の容量を示すために使用する
バケット配列の各エントリは、最初にアクセスされた際に初期化され、その後リスト内のノードを参照する
検索時等のハッシュコードの計算方法やバケットの選択方法は以前と同様

リサイズについて:

テーブル(バケット配列)のサイズを二倍にするタイミングは以前と同様にpolicy()が決定する
ただし、リサイズはインクリメンタルに行われるので、明示的なresize()メソッドは存在しない
仮にテーブルサイズを2^iとすると、バケットインデックスはキーの下位iビットで決定される

バケットbは、以下のハッシュコードkに該当する要素群を含んでいることになる
b = k mod 2^i  ※ 本の式は間違っている？


このハッシュ関数はテーブルサイズに依存するので、リサイズ時には注意を払う必要がある

テーブルのリサイズ前に挿入された要素は、新旧の両方のバケット群からアクセス可能である必要がある
サイズが2^(i+1)になったとしたら、バケットbに含まれる要素軍は、以下の二つのバケットに分割される:

b = k mod 2^(i+1)の場合: (= 新ビットが0の場合)

引き続きバケットbに含まれる


b + 2^i = k mod 2^(i+1)の場合: (= 新ビットが1の場合)

バケットb + 2^iに移る


上のバケット分割に、このアルゴリズムのキーアイディアがある:

それらの二つのグループに属する要素群が、リスト上では順々になって(連接して)いることを保証している
そのため、バケット分割は、単にバケットb+2iを、一番目のグループの後かつ二番目のグループの前、にセットすることで達成できる
これは二番目のグループに属する要素に、バケットbからアクセスできることを維持する


図13.12での例 (詳細は本を参照)

recursive split-ordering:

上のアルゴリズムは、リスト内の要素の全順序を導く
キーの順序は、キーのハッシュコードのビット値を反転させたもの、となる (図13.12も参照)
これを"recursive split-ordering"と呼ぶ

要点をまとめると:

分割順(split-ordered)ハッシュセットは:

バケットの配列
それぞれのバケットは、一つのロックフリーリスト(内のノード)への参照
リストには、ノードがビット反転ハッシュコード順にソートされて格納されている


バケット数は動的に増加する
それぞれのバケットはアクセスされた際に初めて初期化される

番兵ノード:

境界的なケースでの煩雑な処理を避けるために、決して削除されない番兵ノードを追加する

「バケットが参照しているノードが削除されたらどうしよう」と考え無くて良くなる


具体的には:

テーブルサイズを2^(i+1)とする
バケットb + 2^iがアクセスされた最初のタイミングで、b + 2^iのキーを持つ番兵ノードが生成される
このキーはバケットb + 2^iの親であるバケットb経由でリストに挿入される
番兵ノードは、バケットb内の全てのノードよりも後で、バケットb+2^iの全てのノードよりも前だよ、とか


番兵ノード(sentinel)と通常ノード(ordinary)の見分け方:

通常ノードの最上位ビットを1に設定する (番兵ノードは0)
図13.14のmakeOrdinaryKey()とmakeSentinelKey()がそれぞれの対応物


図13.13:

新要素の挿入がどのようにバケットの初期化を起こし得るかを示している
キーが10の要素を追加した場合の例 (軽く口頭で説明)

リサイズタイミングについて:

テーブルはインクリメンタルに育つので、明示的なリサイズ操作はなし
リサイズメカニズムは、いつリサイズするかを決定するためのポリシーとは独立している
例を具体的に保つために、以下のポリシーを実装する:

addメソッド呼び出しがバケットの平均的なloadをトラック可能なように、共有カウンタを使う
平均loadが閾値を跨いだ時に、テーブルサイズを二倍にする


バケット配列の実装について:

技術的な注意散漫を避けるために、バケット配列は、巨大な固定サイズの配列だとしておく
初めは配列の最初のエントリだけを使い、セットが育つにつれて徐々に配列の他の要素も使っていく
addメソッドが未初期化のバケットに最初にアクセスした時に、初期化を行う
概念的にはシンプルだが、このデザインは理想からはほど遠い:

固定サイズの配列は、ものすごく巨大な数のバケット群を制限する


実際上は、マルチレベルのツリー構造としてバケット群を表現するほうが好ましい

マシンのメモリをフルに使うことが可能
詳細は演習問題で


13.3.2 BucketListクラス

図13.14:

BucketList<T>クラス: バケット配列の実装
LockFreeListクラスと本質的に同様だが、二つの重要な差異がある


要素の並び順がrecursive-split order


キーの値の詳細はmakeOrdinaryKey()およびmakeSentinelKey()を参照


番兵ノードの数が異なる


LockFreeListは先頭と末尾の二つのみ
BucketList<T>は各バケットの先頭に、それぞれ一つの番兵ノードが配置されている

リストの途中に番兵ノードを格納したり、そこからリストの探索を開始する能力が必要


public class BucketList<T> implements Set<T> {
  // 13.14
  static final int HI_MASK = 0x80000000;
  static final int MASK = 0x00FFFFFF;
  Node head;

  public BucketList() {
    head = new Node(0);
    head.next =
      new AtomicMarkableReference<Node>(new Node(Integer.MAX_VALUE), false);
  }

  public int makeOrdinaryKey(T x) {
    int code = x.hashCode() & MASK; // take 3 lowest bytes
    return reverse(code | HI_MASK);
  }

  private static int makeSentinelKey(int key) {
    return reverse(key & MASK);
  }
図13.15:

containsメソッドの実装
LockFreeListとほぼ同様 (検索キーの生成にmakeOrdinaryKeyを使っている点が異なる)

// 13.15
  public boolean contains(T x) {
    int key = makeOrdinaryKey(x);
    Window window = find(head, key);
    Node curr = window.curr;
    return (curr.key == key);
  }
図13.16:

getSentinelメソッドの実装
バケットのインデックスに対応するバケットを検索する
もし存在しない(未初期化)なら追加する

  // 13.16
  public BucketList<T> getSentinel(int index) {
    int key = makeSentinelKey(index);
    boolean splice;
    while (true) {
      Window window = find(head, key);
      Node pred = window.pred;
      Node curr = window.curr;
      if (curr.key == key) {
        return new BucketList<T>(curr);
      } else {
        Node node = new Node(key);
        node.next.set(pred.next.getReference(), false);
        splice = pred.next.compareAndSet(curr, node, false, false);
        if (splice)
          return new BucketList<T>(node);
        else
          continue;
      }
    }
  }
13.3.3 LockFreeHashSetクラス

図13.17:

LockFreeHashSet<T>クラス

public class LockFreeHashSet<T> {
  // 13.17
  protected BucketList<T>[] bucket;
  protected AtomicInteger bucketSize; // 使用中のバケットサイズ (リサイズとともに増加)
  protected AtomicInteger setSize;    // 要素数(リサイズタイミングの決定のために用いる)

  public LockFreeHashSet(int capacity) {
    bucket = (BucketList<T>[]) new BucketList[capacity];
    bucket[0] = new BucketList<T>();
    bucketSize = new AtomicInteger(2);
    setSize = new AtomicInteger(0);
  }
図13.18:

addメソッド
containsメソッドやremoveメソッドのほぼ同様に動作する

  // 13.18
  public boolean add(T x) {
    int myBucket = BucketList.hashCode(x) % bucketSize.get();
    BucketList<T> b = getBucketList(myBucket);
    if (!b.add(x))
      return false;
    int setSizeNow = setSize.getAndIncrement();
    int bucketSizeNow = bucketSize.get();
    if (setSizeNow / bucketSizeNow > THRESHOLD)
      bucketSize.compareAndSet(bucketSizeNow, 2 * bucketSizeNow);
    return true;
  }
図13.19:

getBucketListメソッドおよびその関連メソッド
getBucketListメソッド:

指定された位置のバケットを取得、もし存在しないなら初期化


initializeBucketメソッド:

指定されたバケットを初期化する
もし親バケットが未初期化の場合は、再帰的に親の初期化を行う


getParentメソッド:

与えられたインデックスのバケットの親のインデックスを計算する
親のインデックスは「子よりも小さい値」かつ「子に極力近い値」である必要がある
非0の最上位ビットを0にすることで、親のインデックスを計算する


  // 13.19
  private BucketList<T> getBucketList(int myBucket) {
    if (bucket[myBucket] == null)
      initializeBucket(myBucket);
    return bucket[myBucket];
  }

  private void initializeBucket(int myBucket) {
    int parent = getParent(myBucket);
    if (bucket[parent] == null)
      initializeBucket(parent);
    BucketList<T> b = bucket[parent].getSentinel(myBucket);
    if (b != null) // ! このnullチェックは必要か？
      bucket[myBucket] = b;
  }

  private int getParent(int myBucket) {
    int parent = bucketSize.get();
    do {
      parent = parent >> 1;
    } while (parent > myBucket);
    parent = myBucket - parent;
    return parent;
  }
計算時間について:

add/remove/containsメソッドは、キーの検索が定数期待ステップ数で済むことを要求する
ただし、バケットサイズが N のテーブルのバケットの初期化には(再帰的に) log(N) のステップを要する可能性がある

例: Fig 13.20
このようなケースでの合計複雑さは(定数ではなく)対数オーダーとなる
ただし、そのような再帰列の期待長は定数だと見做すことができ、ハッシュセットの操作群の全体期待複雑さも定数オーダとなる


13.4 オープン・ハッシュセット

並列オープン・ハッシュアルゴリズムに注意を向ける:

各テーブルのエントリが単一のアイテムを保持する

クローズド・ハッシュよりも並列化するのが難しそうに見える


カッコウ(Cuckoo)ハッシュとして知られる逐次アルゴリズムをもとにする

13.4.1 カッコウハッシュ

カッコウハッシュ(Cuckoo hashing):

逐次ハッシュアルゴリズム
新しく追加された要素は、同じスロットに既に存在していた要素を追い出す
Nサイズのハッシュセットの実装のためには、table[2][k = N /2]の二次元配列を使用する

table[0]とtable[1]の要素群には、それぞれ独立したハッシュ関数が適用される:

h0,h1: KeyRange -> 0,...k-1


値xがセット内にいるかどうかの判定方法: table[0][h0(x)] == x or table[1][h1(x)] == x

図13.21:

addメソッド
最も興味深い
全ての衝突要素がスロットを持つまで連続的に"kicks out"を行う
以下のケースではリサイズが必要

テーブルが満杯
追い出しが循環している
=> その判定用に追い出し回数の上限を設定しておく必要がある


図13.22は連鎖追い出しの例

// Figure 13.21
public boolean add (T x) {
  if (contains(x)) {
    return false;
  }
  for (int i = 0; i < LIMIT; i++) {
    if ((x = swap(0, hash0(x), x)) == null) {
      return true;
    } else if ((x = swap(1, hash1(x), x)) == null) {
      return true;
    }
  }
  resize();
  add(x);
}
逐次カッコウハッシュはその簡潔さが魅力:

定数時間のcontains/remove関数を提供する
時間と共に、それぞれのaddメソッドによる平均追い出し数が、定数となることを示すことが可能
実験証拠は逐次カッコウハッシュが実際に上手く動くことを示している

13.4.2 並列カッコウハッシュ

カッコウハッシュを並列化する際の主要な障害は、addメソッドが長いスワップ列を実行する必要があること。
この問題に対処するために、別のカッコウハッシュアルゴリズムを定義する:

PhasedCuckooHashSet<T>クラス
それぞれのメソッド呼び出しをフェーズ列に解体する
各フェーズは、単一の要素xの追加／削除／追い出し、を行う
要素群の二次元テーブルはやめて、プローブセットの二次元テーブルを使用する

プローブセットは、同じハッシュコードを有する要素群の定数サイズのセット
各プローブセットは最大でPROBE_SIZE個の要素を保持する

ただし、このアルゴリズムはセットがquiescentの時には、各プローブセットがTHRESHOLD < PROBE_SIZE以下の要素を保持するように試みる
quiescent: no method calls are in progress


図13.24はPhasedCuckooHashSet構造の例

PROBE_SIZE=4, THRESHOLD=2


図13.24:

PhasedCuckooHashSet<T>クラス
同期の問題を後回しにするために、このクラスは抽象クラスとして定義されている

BaseHashSet<T>と同様の抽象メソッド群を備えている
acquire/release/resize


public abstract class PhasedCuckooHashSet<T> {
  volatile int capacity;
  volatile List<T>[][] table;
  public PhasedCuckooHashSet(int size) {
    capacity = size;
    table = (List<T>[][]) new java.util.ArrayList[2][capacity];
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < capacity; j++) {
        table[i][j] = new ArrayList<T>(PROBE_SIZE);
      }
    }
  }
鳥瞰図的な観点からすればPhasedCuckooHashSet<T>は以下のように動作する:

要素の追加・削除の際には、最初に、両方のテーブルの対応するプローブセットをロックする:

削除処理は逐次版と同様:

(それぞれの)プローブセットをチェックして、もし要素が含まれているなら削除する


追加時には、どちらかのプローブセットへの要素の追加を試みる:

要素のプローブセットは、長い連続追い出しシーケンス用の一時オーバーフローバッファとして機能する
THRESHOLD変数は、逐次アルゴリズムでの、実質的なプローブセットの上限
プローブセットが既にたくさんの要素を保持していいた場合に、PROBE_SIZE-THRESHOLDのオーバフロースロットに格納される
その後、プローブセットからの別の要素の再配置を試みる (要素数が閾値を下回るまで)

どの要素を選択するからは多様なポリシーがあり得る
ここでは古い要素ほど先に選択されるようなポリシーを採用する


逐次版と同様に再配置は連鎖し得る


図13.24は追加処理の実行例:

(a) キー13の要素はブローブセットに余裕のあるtable[1]に格納される
(b) キー14の要素はtable[0]に格納され、閾値を超えたので、代わりにキー23の要素が再配置される


図13.25:

removeメソッド

コードの通り


containsメソッドも同様に動作する

  public boolean remove(T x) {
    acquire(x);
    try {
      List<T> set0 = table[0][hash0(x) % capacity];
      if (set0.cantains(x)) {
        set0.remove(x);
        return true;
      }
      List<T> set1 = table[0][hash1(x) % capacity];
      if (set1.cantains(x)) {
        set1.remove(x);
        return true;
      }
      return false;
    } finally {
      release(x);
    }
  }
図13.26:

addメソッド

これもコードの通り


  public boolean add(T x) {
    T y = null;
    acquire(x);
    int h0 = hash0(x) % capacity, h1 = hash1(x) % capacity;
    int i = -1, h = -1;
    boolean mustResize = false;
    try {
      if (present(x)) return false;
      List<T> set0 = table[0][h0];
      List<T> set1 = table[1][h1];
      if      (set0.size() < THRESHOLD) { set0.add(x); return true; }
      else if (set1.size() < THRESHOLD) { set1.add(x); return true; }
      else if (set0.size() < PROBE_SIZE) { set0.add(x); i = 0; h = h0; }
      else if (set1.size() < PROBE_SIZE) { set1.add(x); i = 1; h = h1; }
      else {
        mustResize = true;
      }
    } finally {
      release(x);
    }
    if (mustResize) {
      resize(); add(x);
    } else if (!relocate(i, h)) {
      resize();
    }
    return true; // x must have been present
  }
図13.27:

relocateメソッド:

閾値を超えているプローブセットの行(hi)と列(i)を受け取る
そのプローブセットのサイズが閾値を下回るように、要素の(別のプローブセットへの)移動を試みる


再配置試行には上限(LIMIT)がある
それぞれの再配置試行ループは、以下の不変項を維持する:

iSetは縮小を試みているプローブセット
yはiSet内の最も古い要素
jSetはyを移動しようとしている別のプローブセット


  protected boolean relocate(int i, int hi) {
    int hj = 0;
    int j = l - i;
    for (int round = 0; round < LIMIT; round++) {
      List<T> iSet = table[i][hi];
      T y = iSet.get(0);  // 一番古い要素を取得する
      switch(i) {
      case 0: hj = hash1(y) % capacity; beak;
      case 1: hj = hash0(y) % capacity; beak;
      }
      acquire(y);
      List<T> jSet = table[j][hj];
      try {
      if (iSet.remove(y)) {
          // 別スレッドとyの削除が競合していない場合
          if (jSet.size() < THRESHOLD) {
            // 移動先に余裕がある場合は追加して終わり
            jSet.add(y);
            return true;
          } else if (jSet.size() < PROBE_SIZE) {
            // 移動先の閾値を超えている場合は、移動先の再配置を試みる
            jSet.add(y);
            i = 1 - i;
            hi = hj;
            j = 1 - j;
          } else {
            // 移動先の上限を完全に超えている場合は、移動を諦めてリサイズに任せる
            iSet.add(y);
            return false;
          }
        } else if (iSet.size() >= THRESHOLD) {
          // 別スレッドが再配置を行ったが、まだ閾値以上 => リトライ
          continue;
        } else {
          // 別スレッドによる再配置で閾値未満に収まった
          return true;
        }
      } finally {
        release(y);
      }
    }
    // リトライ上限を超えた => 容量が逼迫している可能性が高いのでリサイズに任せる
    return false;
  }
13.4.3 縞々な並列カッコウハッシュ

最初に13.2.2節で扱った lock striping を使った並列カッコウハッシュ実装を見てみる:

StripedCuckooHashSet<T>クラス:

図13.28
PhasedCuckooHashSet<T>クラスを継承
ロック用の(長さLの)二次元配列を提供

lock[i][j]がtable[i][k]に対応: j = k mod L


public class StripedCuckooHashSet<T> extends PhasedCuckooHashSet<T> {
  final ReentrantLock[][] lock;
  public StripedCuckooHashSet(int capacity) {
    super(capacity);
    lock = new ReentrantLock[2][capacity];
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < capacity; j++) {
        lock[i][j] = new ReentrantLock();
      }
    }
  }
図13.29:

acquire/releaseメソッドの実装
コードの通り

  public final void acquire(T x) {
    lock[0][hash0(x) % lock[0].length].lock();
    lock[1][hash1(x) % lock[1].length].lock();
  }
  public final void release(T x) {
    lock[0][hash0(x) % lock[0].length].unlock();
    lock[1][hash1(x) % lock[1].length].unlock();
  }
図13.30:

resizeメソッド

StripedHashSetのそれとほぼ同様
今回はlock[0]内のロックを昇順に確保しているのが異なる (lock[1]の方は不要)
後はお決まりの話 (他のメソッドとの排他、resize同士のデッドロック防止)


  public void resize() {
    int oldCapacity = capacity;
    for (Lock aLock : lock[]) {
      aLock.lock();
    }
    try {
      if (capacity != oldCapacity) {
        return;
      }
      List<T>[][] oldTable = table;
      capacity = 2 * capacity;
      table = (List<T>[][]) new List[2][capacity];
      for (List<T>[] row : table) {
        for (int i = 0; i < row.length; i++) {
          row[i] = new ArrayList<T>(PROBE_SIZE);
        }
      }
      for (List<T>[] row : oldTable) {
        for (List<T> set : row) {
          for (T z : set) {
            add(z);
          }
        }
      }
    } finally {
      for (Lock aLock : lock[]) {
        aLock.unlock();
      }
    }
  }
13.4.4 改良可能な並列カッコウハッシュ

ロック配列をリサイズするために、13.2.3節の手法を使うことが可能:

RefinableCuckooHashSet<T>クラスを導入

図13.31
ownerフィールドを持つ

リサイズ中にマークがtrueになり、かつ、リサイズ中のスレッドがセットされる


public class RefinableCuckooHashSet<T> extends PhasedCuckooHashSet<T> {
  AtomicMarkableReference<Thread> owner;
  volatile ReentrantLock[][] locks;

  public RefinableCuckooHashSet(int capacity) {
    super(capacity);
    locks = new ReentrantLock[2][capacity];
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j < capacity; j++) {
        locks[i][j] = new ReentrantLock();
      }
    }
    owner = new AtomicMarkableReference<Thread>(null, false);
  }
図13.32:

acquireメソッド

ロック配列が二つになっていることを除けば、RefinableHashSetのそれとほぼ同様


  public void acquire(T x) {
    boolean[] mark = {true};
    Thread me = Thread.currentThread();
    Thread who;
    while (true) {
      do { // wait until not resizing
        who = owner.get(mark);
      } while (mark[0] && who != me);

      ReentrantLock[][] oldLocks = locks;
      ReentrantLock oldLock0 = oldLocks[0][hash0(x) % oldLocks[0].length];
      ReentrantLock oldLock1 = oldLocks[1][hash1(x) % oldLocks[1].length];
      oldLock0.lock();
      oldLock1.lock();
      who = owner.get(mark);
      if ((!mark[0] || who == me) && locks = oldLock1) {
        return;
      } else {
        oldLock0.unlock();
        oldLock1.unlock();
      }
    }
  }

  public void release(T x) {
    locks[0][hash0(x)].unlock();
    locks[1][hash1(x)].unlock();
  }
図13.33:

resizeメソッド

これもロック配列が二つになっていることを除けば、RefinableHashSetのそれとほぼ同様


  public void resize() {
    int oldCapacity = capacity;
    Thread me = Thread.currentThread();
    if (owner.compareAndSet(null, me, false, true)) {
      try {
        if (capacity != oldCapacity) { // someone else resized first
          return;
        }
        quiesce();

        capacity = 2 * capacity;
        List<T>[][] oldTable = table;
        table = (List<T>[][]) new List[2][capacity];
        locks = new RefinableHashSet[2][capacity];

        // ロック初期化
        for (int i = 0; i < 2; i++) {
          for (int j = 0; j < capacity; j++) {
            locks[i][j] = new ReentrantLock();
          }
        }

        // テーブル初期化
        for (List<T>[] row : table) {
          for (int i = 0; i < row.length; i++) {
            row[i] = new ArrayList<T>(PROBE_SIZE);
          }
        }

        // 要素のコピー
        for (List<T>[] row : oldTable) {
          for (List<T> set : row) {
            for (T z : set) {
              add(z);
            }
          }
        }
      } finally {
        owner.set(null, false);
      }
    }
  }

  // Figure 13.34
  protected void quiesce() {
    for (ReentrantLock lock : locks[0]) {
      while (lock.isLocked()) {}
    }
  }
13.5 チャプターノート

省略