以下は、perfbook の１０章の kanda.motohiro@gmail.com による全訳です。編集に不便なので、ファイルを分けました。perfbook の訳の他の部分は、親文書を参照。
１０章 データ構造
データへの効率的なアクセスは致命的に重要です。このため、アルゴリズムの議論は、関連するデータ構造の時間複雑性を含みます。しかし、並列プログラムにとっては、時間複雑性の測定値はさらに並列同時実行効果も含まないといけません。これらの影響は、3章に述べたように他を圧倒するほど大きいことがあります。ということは、同時実行するデータ構造の設計はシーケンシャル時間複雑性の時以上に、同時実行性に焦点を当てる必要があるということを意味します。
１０．１節は、動機となるアプリケーションを紹介します。それは、この章で提示されるデータ構造を評価するのに使われます。
６章で議論したように、高いスケーラビリティを得る優れた方法は、分割です。これは、分割可能なデータ構造への道を示します。１０．２節で取り上げる題材です。９章は、あるアクションを遅延させることで性能とスケーラビリティが大いに改善することができるかを見ました。特に９．３節は、怠慢の素晴らしい力を、性能とスケーラビリティの追求に役立てるにはどうしたらいいかを示しました。これは１０．３節で取り上げます。
分割可能なデータ構造ばかりとは限りません。１０．４節は、やや分割不可能なデータ構造の例を見ます。この節では、それを、リードがほとんどの部分と、分割可能な部分に分け、高速でスケーラブルな実装を可能とする方法を示します。
この章はこれまでに使われたすべての同時実行するデータ構造の詳細まで見ることは不可能なので、１０．５節は最も一般的で重要なもののいくつかを簡単にサーベイします。最高の性能とスケーラビリティは設計から生まれるのであって、後から現実に基づいて行われるマイクロ最適化から生まれるのではありません。とはいえ、マイクロ最適化が、絶対可能な最高性能とスケーラビリティを達成するためには重要な位置を占めるのは事実なので、１０．６節はこの題材を取り上げます。
最後に、１０．７節はこの章のまとめです。
１０．１ 動機となるアプリケーション
性能を評価するために、シュレディンガーの動物園アプリケーションを使います。シュレディンガーは動物園を持っており、多くの動物がいます。そして彼は、それらをインメモリのデータベースで追跡したいと思っています。動物園のそれぞれの動物が、データベースのデータアイテムで表されます。それぞれの動物には一意の名前があり、それがキーに使われます。それぞれの動物ごとに多様なデータが追跡されます。
誕生、捕獲、あるいは購入は、挿入に、死亡、解放、そして売却は削除になります。シュレディンガーの動物園には、ねずみや昆虫のように短命な動物が大量にいますので、データベースは高い更新数をサポートしなくてはいけません。
シュレディンガーの動物に興味のある人はだれでも、問い合わせをすることができます。しかし、シュレディンガーは、彼の猫に対する極端に高い問い合わせに気が付きました。これはねずみが、データベースを使って、自分たちの敵を調べているためでないかと、彼は疑っています。こういうことがあるので、シュレディンガーのアプリケーションは、単一のデータ要素に対する高い問い合わせ数をサポートしなくてはいけません。
これからいろいろなデータ構造が出てきますから、このアプリケーションを覚えておいて下さい。
１０．２ 分割可能データ構造
現在使われているデータ構造はあまりに多数あり、このためそれを扱う教科書は何冊もあります。この短い節は単一のデータ構造、つまり、ハッシュテーブルに焦点を当てます。こうして焦点を絞ったアプローチを取ることによって、同時実行がどのようにデータ構造と相互作用するのか、より深い調査が可能です。そしてそれは、現実に頻繁に使われているデータ構造に焦点を当てることでもあります。１０．２．１節は設計の概観を示し、１０．２．２節は実装を示します。最後に、１０．２．３節は結果となる性能とスケーラビリティを議論します。
１０．２．１ ハッシュテーブルの設計
６章では、それなりの性能とスケーラビリティを得るためには、分割を適用する必要が有ることを強調しました。なので、分割可能性は、データ構造を選ぶときの第一級の基準です。並列処理の働き馬であるハッシュテーブルはこの基準を良く満足します。ハッシュテーブルは概念的に単純です。ハッシュバケツの配列からなります。ハッシュ関数が、ある要素のキーをこの要素が格納されるハッシュバケツにマップします。このため、それぞれのハッシュバケツは、ハッシュチェーンと呼ばれる要素の連結リストを持ちます。適切に設定された場合、このハッシュチェーンはとても短く、ハッシュテーブルであるキーを持つ要素をアクセスするのはとても効率よく行えます。
クイッククイズ１０．１
でも、ハッシュテーブルには多くの種類があって、ここで示されるチェーンされたハッシュテーブルはその一つに過ぎません。なぜ、チェーンされたハッシュテーブルに焦点を合わせるのですか？
さらに、それぞれのバケツは自分自身のロックを持てます。なので、あるハッシュテーブルの異なるバケツの要素は完全に独立に、追加、削除、そして検索ができます。このため、多くの要素を持つ大きなハッシュテーブルは素晴らしいスケーラビリティを提供します。
１０．２．２ ハッシュテーブルの実装
図１０．１（hash_bkt.c）は、単純な、チェーンとハッシュバケツごとのロックを使う固定長のハッシュテーブルで使われるデータ構造のセットです。図１０．２は、これらを全部まとめた図です。hashtab 構造体（図１０．１の１１から１４行目）は、４つの ht_bucket 構造体（図１０．１の６から９行目）を含み、->bt_nbuckets フィールドはバケツの数を制御します。バケツのそれぞれは、リストヘッダ ->htb_head とロック ->htb_lock を持ちます。リストヘッダは、ht_elem 構造体（図１０．１の１から４行目）をそれらの->hte_next フィールドでチェーンします。さらに、それぞれのht_elem 構造体は、対応する要素のハッシュ値を、->hte_hash フィールドにキャッシュします。ht_elem 構造体は、ハッシュテーブルに置かれる、より大きな構造体に含まれるでしょう。この大きな構造体は複雑なキーを持つこともあるでしょう。
図１０．２は、バケツ０に２つの要素、バケツ２に１つの要素を持ちます。
図１０．３は、マップとロック関数です。１と２行目がマクロ HASH2BKT() であり、ハッシュ値を対応する ht_bucket 構造体にマップします。このマクロは単純な剰余を使います。よりアグレッシブなハッシュが必要なら、コール元はキーをハッシュ値にマップする時に、それを実装する必要があります。残りの２つの関数は、指定されたハッシュ値に対応する ->htb_lock を確保、解放します。
図１０．４は hashtab_lookup() です。これは、指定されたハッシュとキーを持つ要素があればそのポインタ、なければNULL を返します。この関数は、ハッシュ値とキーへのポインタの両方を取ります。なぜならば、そうすればこの関数のユーザは任意のキーと任意のハッシュ関数を使うことができるからです。キー比較関数は、cmp() で渡されます。これは、qsort() に似た方法です。１１行目はハッシュ値を対応するハッシュバケツへのポインタにマップします。１２から１９行目をまたぐループのそれぞれのパスは、バケツのハッシュチェーンの一つの要素を調べます。１５行目で、ハッシュ値が等しいか見て、だめなら、１６行目で次の要素に進みます。１７行目で実際のキーが等しいか見て、そうなら、１８行目でマッチした要素へのポインタを返します。どの要素もマッチしなければ、２０行目でNULLを返します。
クイッククイズ１０．２
図１０．４の１５から１８行目の二重の比較は、キーが unsigned long に入るときには非効率でないですか？
図１０．５は、hashtab_add() と hashtab_del() 関数で、それぞれ、要素をハッシュテーブルに追加、削除します。
hashtab_add() 関数は、６行目で単純に要素のハッシュ値を設定し、それを７と８行目で対応するバケツに追加します。hashtab_del() 関数は単純に、指定された要素を、それがどのハッシュチェーンにいるかにかかわらず、取り除きます。それは、ハッシュチェーンリストが二重連結リストであるために可能です。この２つの関数のいずれかを呼ぶ前に、コール元は同じバケツを、他のスレッドがアクセスあるいは変更していないことを保証する必要があります。例えば、事前に hashtab_lock() を呼ぶことによって。
図１０．６は、hashtab_alloc() と hashtab_free() で、それぞれ、ハッシュテーブルの確保と解放をします。確保は、７から９行目で、元となるメモリの確保から始まります。１０行目で、メモリがない時は、１１行目で、コール元にNULL を返します。そうでない場合、１２行目でバケツの数を初期化し、１３から１６行目にまたがるループで、バケツ自身を初期化します。それには、１４行目のチェーンリストヘッダと１５行目のロックが含まれます。最後に、１７行目は新しく確保されたハッシュテーブルのポインタを返します。２０から２３行目の hashtab_free() 関数は、直裁的です。
１０．２．３ ハッシュテーブルの性能
図１０．７は、８CPU 2GHz Intel Xeon システムで、１０２４バケツの、バケツロックのハッシュテーブルの性能結果です。性能はほぼ線形にスケールしますが、たった８CPUでも、理想の性能レベルの半分強という程度です。この減少の理由の一つは、単一CPUではロック確保と解放はキャッシュミスを起こさないのに２CPU以上では実際にそれを起こすことです。
そして、図１０．８でわかるように、より多くのCPU数では、事態は悪くなるばかりです。理想性能を示す線は必要ありません。９以上のCPUの性能は最低以下です。これは明らかに、ほどほどのCPU数での性能を外挿する危険を裏付けます。
もちろん、性能の崩壊の一つの可能な原因は、より多くのバケツが必要だったことかもしれません。結局、私達は、それぞれのハッシュバケツを完全なキャッシュラインに詰めることをしませんでした。なので、キャッシュラインあたり、複数のハッシュバケツがあります。その結果起きるキャッシュスラッシングが、９CPUであらわになったのはありえます。これはもちろん、ハッシュバケツ数を増やすことで簡単にテストできます。
クイッククイズ１０．３
単純にハッシュバケツ数を増やす代わりに、今あるハッシュバケツをキャッシュアラインする方が良くありませんか？
しかし、図１０．９でわかるように、バケツ数を増やすことで性能はいくらかは上がりますが、スケーラビリティは依然ひどいものです。特に、９CPU以上で今までどおりの鋭利な低下が見られます。さらに、８１９２バケツから１６３８４バケツにしても、ほとんど性能向上はありません。明らかに、何か他のことが起きているのです。
問題は、これがマルチソケットシステムだということです。表１０．１に示すように、CPU０から７と３２から３９が、最初のソケットにマップされます。このため、最初の８CPUに閉じ込められたテストランはとても高性能でした。しかし、ソケット０のCPU０から７に加えて、ソケット１のCPU８を含むテストは、データをソケット境界を越えて渡すオーバヘッドを引き起こします。これは、３．２．１節に述べたように、激しく性能を落とすことがあります。要するに、大きなマルチソケットシステムは、完全な分割に加えて、良い参照の局所性が必要です。
クイッククイズ１０．４
ソケットをまたがるときのシュレディンガーの動物園のアプリケーションの負のスケーラビリティのことを考えると、単純にそのアプリケーションの複数コピーを、それぞれのコピーは動物のサブセットを持って、単一ソケットで動作するように封じ込めたらどうでしょう？
以前述べたシュレディンガーの動物園の実行の鍵となる性質の一つは、それがすべてリードオンリーなことです。それは、ロック確保が引き起こすキャッシュミスによる性能低下を、よりずっと苦痛に満ちたものとします。元となるハッシュテーブル自身を更新していないのに、私達はなおメモリに書き込む対価を払っているのです。もちろん、ハッシュテーブルが一切更新されないのであれば、相互排他など全く除くことができます。このアプローチはとても直裁的で、読者への課題とします。しかし、更新が稀であっても、ライトを避けることはキャッシュミスを避け、リードがほとんどのデータを全てのキャッシュに複製するのを許します。それはまた、参照の局所性を促進します。
なので、次の節は更新が稀だけどもいつでも起きることのある、リードがほとんどのケースに行うことのできる最適化を調べます。
１０．３ リードがほとんどのデータ構造
分割したデータ構造はしばしば素晴らしい性能を発揮しますが、NUMA 効果により性能とスケーラビリティが著しく落ちることがあります。さらに、リードがほとんどの場合、リーダーがライターを排除する必要が性能を落とすことがあります。しかし、私達は、９．３節で紹介した RCU を使うことで、性能とスケーラビリティを得ることができます。同様の結果は、ハザードポインタ(hazptr.c) でも得られ、この節で示す性能結果に含まれます。
１０．３．１ RCU 保護されたハッシュテーブル実装
バケツロックを使う、RCU 保護されたハッシュテーブルでは、更新者は１０．２節に示したのと全く同じくロックを使いますが、リーダーはRCUを使います。データ構造は、図１０．１に示したのと同じです。HASH2BKT(), hashtab_lock()、hashtab_unlock() 関数も、図１０．３に示したのと同じです。しかし、リーダーは、図１０．１０に示す hashtab_lock_lookup() と hashtab_unlock_lookup() が提供する軽量の同時実行制御を使います。
図１０．１０は、バケツロックを使う、RCU 保護されたハッシュテーブルのための hashtab_lock_lookup() です。これは、図１０．４と同じですが、cds_list_for_each_entry() が、cds_list_for_each_entry_rcu() になっています。このプリミティブはいずれも、htb->htb_head の参照するハッシュチェーンを順にたどりますが、cds_list_for_each_entry_rcu() はさらに、同時実行する挿入の場合にメモリオーダリングを正しく強制します。これは、この二つのハッシュテーブル実装の重要な違いです。純粋なバケツごとのロック実装と違って、RCU保護された実装は、検索が、挿入や削除と同時実行するのを許します。そして、RCU に留意した cds_list_for_each_entry_rcu() などのプリミティブは、この追加された同時実行制御を正しく扱う必要があります。また、hashtab_lookup() の呼び出し元は、RCU リード側クリティカルセクション内にいなくてはいけないことに注意下さい。例えば、呼び出し元は、hashtab_lookup() を呼ぶ前に、hashtab_lock_lookup() を呼ばないといけません。（もちろん、しばらく後には hashtab_unlock_lookup() を呼ばないといけません。）
クイッククイズ１０．５
でも、ハッシュテーブルの要素が検索と同時実行して削除されることがあるならば、それは、検索が、検索した直後に削除されたデータ要素への参照を返すことがあるのを意味しませんか？
図１０．１２は、hashtab_add() と hashtab_del() です。どちらも、図１０．５の、RCUでない対応するものととても似ています。hashtab_add() 関数は、cds_list_add() の代わりに cds_list_add_rcu() を使います。これは、検索と同時に、要素がハッシュテーブルに追加される時に正しいオーダリングを保証するためです。hashtab_del() 関数は、cds_list_del_init() の代わりに、cds_list_del_rcu() を使います。これは、要素が、ちょうど削除される前に検索される時のためです。cds_list_del_init() と違って、cds_list_del_rcu() はフォワードポインタをそのままとしますから、hashtab_lookup() は新しく削除された要素に続くものを、たどることができます。
もちろん、hashtab_del() を呼んだ後、コール元は、今削除した要素のメモリを解放あるいは再使用する前に、RCUグレースピリオド（例えば、synchronize_rcu() を呼ぶことで）を待たなくてはいけません。
１０．３．２ RCU 保護されたハッシュテーブルの性能
図１０．１３は、RCU 保護もしくは、ハザードポインタで保護されたハッシュテーブルの、リードオンリーの性能を、前の節のバケツごとのロック実装と比べたものです。見てわかるように、RCUとハザードポインタは、多数のスレッドとNUMA効果にもかかわらず、理想に近い性能とスケーラビリティを達成します。グローバルなロックの実装の結果も示しました。それは、予想されたことですが、バケツごとのロック実装よりさらに悪いものです。RCUはわずかにハザードポインタよりも勝りますが、その差は、このログスケールのグラフではわかりにくいものです。
図１０．１４は、線形スケールで同じデータを示します。ここでは、グローバルロックの線はX軸に落ちて見えません。RCUとハザードポインタの性能の差はよりわかりやすいです。どちらも、３２CPUで傾きに変化が現れます。これは、ハードウェアマルチスレッディングのためです。３２以下のCPUでは、それぞれのスレッドはコアを専有します。この領域では、RCUはハザードポインタより優れます。それは、ハザードポインタのリード側メモリバリアがコア内のデッドタイムになるからです。要するに、単一のハードウェアスレッドの場合、RCUはハザードポインタに比べて、コアを有効活用できます。
この状況は３２CPU以上で変わります。RCU は、シングルハードウェアスレッドで、それぞれのコアのリソースを半分以上使っていますから、それぞれのコアに２つ目のハードウェアスレッドが現れても比較的少ない利益しか得られません。ハザードポインタの線の傾きも３２CPUで減りますが、それほどではありません。なぜならば、２つ目のハードウェアスレッドは、最初のハードウェアスレッドがメモリバリア遅延のためにストールしている時間を埋めることができるからです。以降の節で見るように、ハザードポインタの、２つ目のハードウェアスレッドの利点はワークロードに依存します。
以前に述べたように、シュレディンガーは彼の猫の人気に驚きましたが、この人気を彼の設計に反映させる必要を認識しました。図１０．１５は、６０CPUの結果です。猫の検索だけをするCPUの数を変えています。RCUとハザードポインタは、この挑戦にもうまく応えています。しかし、バケツロックは負にスケールします。最後には、性能はグローバルロックより悪くなります。これは驚きではありません。なぜならば、もし全てのCPUが猫の検索だけをするならば、猫のバケツに対応するロックは、事実上、グローバルロックなのです。
この猫だけのベンチマークは、完全に分割された sharding アプローチの一つの潜在的問題を明らかにします。猫の分割に対応付けられたCPUだけが猫をアクセスできます。それは、猫だけのスループットを制限します。もちろん、多くのアプリケーションは良い負荷分散の性質を持ちます。これらのアプリケーションにとって、sharding はとてもうまくいきます。
しかし、sharding は「ホットスポット」をうまく扱えません。シュレディンガーの猫で示されたホットスポットが良い例です。
もちろん、私達がデータを読むだけならば、そもそも、同時実行制御は要りません。図１０．１６は、なので、更新の効果を示します。このグラフの左側の極限では、全ての６０CPUが検索をしており、右側では、全ての６０CPUが更新をしています。全ての４つの実装において、ミリ秒あたりの検索数は、更新しているCPUの数が増えるに連れて減少します。もちろん、全ての６０CPUが更新をしている時には、ミリ秒あたりゼロ検索になります。RCUはハザードポインタと比べると優れています。ハザードポインタのリード側メモリバリアが、更新があるときにはより大きなオーバヘッドを起こす事実のためです。なので、現代的なハードウェアはメモリバリア実行を大いに最適化しますが、リードオンリーの場合に特に、メモリバリアオーバヘッドが大いに減らせるというのはありえることです。
図１０．１６は、検索に対して更新の比率を増やした時の効果を示しましたが、図１０．１７は、更新自身に対して更新の比率を増やした時の効果を示します。ハザードポインタとRCUは最初はとても有利に始まります。なぜならば、バケツロックと違って、リーダーは更新者を排除しませんから。しかし、更新するCPU数が増えるに連れて、更新側のオーバヘッドが見えてきます。最初はRCUで、次に、ハザードポインタで。もちろん、これら全ての３つの実装は、グローバルロックよりはずっと良いです。
もちろん、更新比率の差が、検索性能の差に影響していることは十分にありえます。これをチェックする一つの方法は、人工的に、バケツごとのロックとハザードポインタの時の更新比率を調整して、RCUのそれに等しくすることです。そうしても、バケツごとのロックの検索性能はそれほど改善しませんでしたし、ハザードポインタとRCUのギャップは狭くなりませんでした。しかし、ハザードポインタのリード側メモリバリアを除いた（それは、ハザードポインタの安全でない実装になります）結果、ハザードポインタとRCUのギャップは実際、ほとんどなくなりました。この安全でないハザードポインタ実装は、通常は、ベンチマーク用途としては十分に信頼できますが、本番使用にはもちろん、おすすめできません。
クイッククイズ１０．６
１０．２．３節で、８CPUから６０CPUに外挿する危険は、とても明らかに示されましたが、６０以上のCPUに外挿するのは、より安全なのはなぜですか？
１０．３．３ RCU保護されたハッシュテーブルの議論
RCUとハザードポインタ実装の一つの結果は、二つの同時実行するリード側が、猫の状態について、意見の不一致を見ることがあることです。例えば、リーダーの一つは、猫のデータ構造のポインタを、それが削除されるちょうど前にフェッチし、もうひとつのリーダーは、同じポインタを、その後でフェッチするかもしれません。すると最初のリーダーは猫は生きていると判断し、２つ目のリーダーは猫は死んでいると思います。
もちろん、この状況は、シュレディンガーの猫にとっては完全に正しいことです。しかしそれは、普通の、量子的でない猫にとっても、とても合理的であることがわかります。
その理由は、ある動物が生まれたり死んだりするのが正確にいつであるかを決めるのは不可能だからです。
それを見るために、猫の死を心臓の鼓動で検出するとしましょう。これは、最後の鼓動から正確にどれだけ待てば、死を宣言できるかという問題を提起します。１ミリ秒しか待たないのは明らかにばかげています。そうすると、生きている健康な猫も、毎秒何度も、死んでいると宣言され、すぐに生き返ることになります。１ヶ月待つのも、同じくらいばかげています。そのころには、あわれな猫の死はにおいでわかります。
動物の心臓は、何秒か止まって、また動き出すことがあるので、死のタイムリーな検出と誤った警告の間にはトレードオフがあります。獣医の間でも、最後の鼓動からどれだけ待てば、死を宣言できるかについて意見の不一致があるでしょう。例えば、一人は、３０秒待つかもしれず、もう一人は、１分待つことを主張するかもしれません。この場合、二人の獣医は、最後の鼓動から２つ目の３０秒期間の間、猫の状態について意見が一致しません。これは、図１０．１８に描かれるとおりです。
もちろん、ハイゼンベルクは私達に、こういう不確定性と付き合っていくように教えました。それは良いことです。なぜならば、計算機ハードウェアとソフトウェアは、同じように振る舞うからです。例えば、あなたは、ある計算機ハードウェアの部品がこわれたことを、どのように知るでしょう？しばしば、それがタイムリーに応答しないことによってでしょう。猫の鼓動と同じく、これは、ハードウェアがこわれたかどうかについて、不確定なウィンドウを開くことになります。
さらに、ほとんどの計算機システムは、外部世界と相互作用するように作られています。なので、外部世界との一貫性は、とても重要です。しかし、１９２ページの図９．２６で見たとおり、内部的な一貫性を増すためには、外部的な一貫性を減らす必要が有ることがあります。RCUやハザードポインタのようなテクニックは、ある程度の内部的な一貫性をあきらめることで、外部的な一貫性の改善を達成します。
要するに、内部的一貫性は、全ての問題領域の自然な部分ではありません。そしてしばしば、性能、スケーラビリティ、外部的な一貫性、あるいはそれら全部、に対して、大きな犠牲を要求します。
１０．４ 分割不可能データ構造
固定長のハッシュテーブルは、完璧に分割可能です。しかし、サイズ変更可能なハッシュテーブルは、拡張あるいは縮小するときに、図１０．１９に楽しく描かれるように、分割への挑戦を課します。しかし、高性能の、スケーラブルなRCU保護されたハッシュテーブルを構成するのが可能であることがわかりました。以下の節で説明します。
１０．４．１ サイズ変更可能なハッシュテーブルの設計
２０００年代初めの状況とは異なり、嬉しい事に、今では少なくても３つ以上の異なるタイプのスケーラブルRCU保護されたハッシュテーブルがあります。最初（そして最も単純）のは、Linuxカーネルのために、Herbert Xu によって開発され、以下の節で説明します。他の２つは、１０．４．４節で簡単に述べます。
最初のハッシュテーブル実装の背後にある鍵となる洞察は、それぞれのデータ要素は２つのセットのリストポインタを持てるということです。一つのセットは、現在のRCUリーダー（そしてRCUでない更新）に使い、もう一つは、新しいサイズ変更したハッシュテーブルを作成するのに使います。このアプローチは、検索、追加、削除と、サイズ変更操作（そして、それら互いにも）とが全て、同時実行するのを許します。
サイズ変更操作は、図１０．２０から１０．２３に示すように進みます。最初の２バケツ状態が図１０．２０です。図ごとに、時間が進みます。最初の状態は、インデックスゼロのリンクをハッシュバケツに要素をチェーンするのに使います。４バケツの配列が確保され、インデックス１のリンクが、これらの４つの新しいハッシュバケツに要素をチェーンするために使われます。この結果、図１０．２１の (b) の状態になり、リーダーはまだ元の２バケツ配列を使っています。
新しい４バケツの配列がリーダーに公開され、グレースピリオド操作が全てのリーダーを待ちます。この結果、図１０．２２の (c) の状態になります。この状態では、全てのリーダーは新しい４バケツの配列を使っています。ということは、古い２バケツの配列は今では解放できるということです。この結果、図１０．２３の (d) の状態になります。
この設計は、比較的、直裁的な実装につながります。それについては次の節で。
１０．４．２ サイズ変更可能なハッシュテーブルの実装
サイズ変更は、古典的なアプローチである、間接レベルをはさむことで行われます。この場合、図１０．２４の１２から２５行目の ht 構造体です。２７から３０行目の hashtab 構造体は、現在の ht 構造体へのポインタと、スピンロックだけを持ちます。スピンロックは、ハッシュテーブルを同時にサイズ変更する試みをシリアライズするために使われます。もし、古典的なロックやアトミック操作を元とする実装を使っていたならば、この hashtab 構造体は性能とスケーラビリティの観点から厳しいボトルネックになっていたことでしょう。しかし、サイズ変更操作は比較的まれなので、RCU を活用することができます。
ht 構造体は、ハッシュテーブルの大きさを、１３行目の ->ht_nbuckets フィールドに持ちます。この大きさは、バケツの配列（２４行目の ->ht_bkt[] ）と同じ構造体に格納されます。これは、サイズと配列の間のミスマッチを防ぐためです。１４行目の ->ht_resize_cur フィールドは、サイズ変更操作が実行中でない限り－１です。その時は、それは、１５行目の ->ht_new が参照する新しいハッシュテーブルにおいて、要素が挿入されるバケツのインデックスを示します。サイズ変更操作が実行中でない時、->ht_new は NULL です。なので、サイズ変更操作は新しい ht 構造体を確保して、それを ->ht_new ポインタで参照して、そして古いテーブルのバケツに対して、->ht_resize_cur を進めることで行われます。全ての要素が新しいテーブルに追加されたら、新しいテーブルは hashtab 構造体の ->ht_cur フィールドにつながります。全ての古いリーダーが完了したら、古いハッシュテーブルの ht 構造体は解放できます。
１６行目の ->ht_idx フィールドは、このハッシュテーブルインスタンスで、リストポインタの２つの組のうちどちらが使われるかを示します。それは、３行目の ht_bucket 構造体の ->hte_next[] 配列をインデックスするために使われます。
１７から２３行目の ->ht_hash_private, ->ht_cmp(), ->ht_gethash(), そして ->ht_getkey() フィールドは、全部で、要素ごとのキーとハッシュ関数を定義します。->ht_hash_private は、ハッシュ関数に摂動を加えることを可能とします。それは、ハッシュ関数で使われるパラメタを統計的に推測することを元とするサービス拒否攻撃を防ぐために使われます。->ht_cmp() 関数は指定したキーを指定した要素のキーと比較します。->ht_gethash() は指定したキーのハッシュを計算し、->ht_getkey() はキーを、それを取り囲むデータ要素から抜き出します。
ht_bucket 構造体は前と同じです。ht_elem 構造体は、前の実装と、リストポインタ配列を一つでなくて二つ持つところだけが違います。
固定長のハッシュテーブルでは、バケツ選択はとても直裁的でした。ハッシュ値を単純に対応するバケツインデックスに変換しました。それに対して、サイズ変更する時は、古いのと新しいの、どちらのバケツのセットを選ぶのかを決める必要があります。古いテーブルから選択されるはずのバケツが既に新しいテーブルに移動されていたならば、バケツは新しいテーブルから選択されなくてはいけません。逆に、古いテーブルから選択されるはずのバケツがまだ移動されていなければ、バケツは古いテーブルから選択されるべきです。
図１０．２５は、バケツ選択を示します。１から８行目に ht_get_bucket_single() が、１０から２４行目に ht_get_bucket() があります。ht_get_bucket_single() 関数は、指定されたハッシュテーブルの指定されたキーに対応するバケツへの参照を返します。サイズ変更は考慮されません。それはまた、キーに対応するハッシュ値を、５と６行目で、パラメタ b が指すところに格納します。７行目はそして対応するバケツの参照を返します。
ht_get_bucket() 関数は、ハッシュテーブルの選択をします。１６行目で ht_get_bucket_single() を呼んで、現在のハッシュテーブルのハッシュに対応するバケツを選択し、パラメタ b にハッシュ値を格納します。１７行目でテーブルがサイズ変更の途中だと判断し、かつ１６行目のバケツが既に新しいハッシュテーブルに移動されているならば、１８行目は新しいハッシュテーブルを選択し、１９行目は新しいハッシュテーブルのハッシュに対応するバケツを選択し、同様にパラメタ b にハッシュ値を格納します。
クイッククイズ１０．７
図１０．２５のコードは、ハッシュを２回計算します！なぜこんな明らかに非効率なことをするのです？
２１行目でパラメタ i が NULL でないなら、２２行目は選択されたハッシュテーブルのポインタの組のインデックスを格納します。最後に２３行目は選択されたハッシュバケツへの参照を返します。
クイッククイズ１０．８
図１０．２５のコードは、サイズ変更プロセスがバケツを選択した後に進行するのに、どうやって対処しますか？
この ht_get_bucket_single() と ht_get_bucket() 実装は、サイズ変更操作と検索と変更が同時実行するのを許します。
リード側の同時実行制御は、図１０．１０で見たように、RCU によって行われます。しかし、更新側の同時実行制御関数 hashtab_lock_mod() と hashtab_unlock_mod() は今回は図１０．２６に示すように同時実行するサイズ変更操作の可能性にも対処しなくてはいけません。
hashtab_lock_mod() は、図の１から１９行目です。９行目でRCU リード側クリティカルセクションに入って、データ構造がトラバースの間に解放されるのを防ぎます。１０行目で現在のハッシュテーブルへの参照を確保し、１１行目でこのハッシュテーブルの、キーに対応するバケツへの参照を取ります。１２行目でそのバケツのロックをとります。それは、同時実行するサイズ変更操作がバケツに干渉するのを防ぎます。ただしもちろんそれは、サイズ変更操作が既にバケツを移動していたら何の効果も持ちません。次に１３行目は同時実行するサイズ変更操作が既にこのバケツを新しいハッシュテーブルに移動したかを判定します。もしそうでなければ、１４行目は選択したハッシュバケツのロックを持ったまま（そして同時にRCUリード側クリティカルセクションに入ったまま）戻ります。
そうでなければ、同時実行するサイズ変更操作が既にこのバケツを移動したので、１５行目で新しいハッシュテーブルに進んで、１６行目でキーに対応するバケツを選びます。最後に、１７行目でバケツのロックを取って、１８行目で古いハッシュテーブルのバケツのロックを放します。繰り返しますが、hashtab_lock_mod() はRCU リード側クリティカルセクションに入ったまま終了します。
クイッククイズ１０．９
図１０．２５と１０．２６のコードは、更新の時にハッシュの計算とバケツ選択論理を２回します！なぜこんな明らかに非効率なことをするのです？
hashtab_unlock_mod() 関数は、hashtab_lock_mod() で取ったロックを放します。２８行目で、現在のハッシュテーブルをピックアップして、２９行目で ht_get_bucket() を呼んでキーに対応するバケツの参照を得ます。もちろん、このバケツは、新しいハッシュテーブルのものであることがあります。３０行目でバケツのロックを放し、最後に３１行目は RCU リード側クリティカルセクションを抜けます。
クイッククイズ１０．１０：
あるスレッドが、サイズ変更操作の間に、新しいハッシュテーブルに要素を挿入するとします。この挿入が完了する前に、後から来たサイズ変更操作が完了することによって挿入された要素が失われることが無いのはなぜでしょう？
さて、これで、バケツ選択と同時実行制御の説明をしたので、サイズ変更可能ハッシュテーブルの検索と更新に進みましょう。図１０．２７は、hashtab_lookup(), hashtab_add(), そして hashtab_del() 関数です。
図の１から２１行目の hashtab_lookup() 関数は、ハッシュ検索をします。１１行目で現在のハッシュテーブルをフェッチし、１２行目で指定されたキーに対応するバケツの参照を得ます。このバケツは、古いハッシュテーブルにおいて、目的のデータ要素を含むバケツを越えてサイズ変更操作が進んだ時には、新しいハッシュテーブルに位置づきます。なお、１２行目は、それぞれの要素にある対から正しいポインタのセットを選択するのに使われるインデックスも返すことに注意下さい。１３から１９行目にあるループは、バケツを探し、１６行目でマッチすれば、１８行目でそれを取り囲むデータ要素へのポインタを返します。そうでなければ、マッチしないので、２０行目で NULL を返して失敗を知らせます。
クイッククイズ１０．１１：
図１０．２７の hashtab_lookup() 関数で、検索している要素が既に同時実行するサイズ変更操作によって移動されているならば、コードは注意深く新しいハッシュテーブルから正しいバケツを見つけます。これは、RCU 保護された検索に対しては、むだに思われます。この場合は、古いハッシュテーブルにとどまってはいけないのですか？
図の２３から３７行目にある hashtab_add() 関数は、新しいデータ要素をハッシュテーブルに追加します。前と同様に、３２から３４行目でキーに対応するハッシュバケツへのポインタを得ます（インデックスも）。３５行目は新しい要素をテーブルに追加します。コール元は、同時実行制御を処理する必要があります。例えば、hashtab_add() を呼ぶ前に hashtab_lock_mod() を呼び、その後、hashtab_unlock_mod() を呼ぶというように。この２つの同時実行制御関数は、同時実行するサイズ変更操作に対して、正しく同期を取ります。このデータ要素が追加されるべきバケツを越えてサイズ変更操作が進んでいたならば、その要素は新しいテーブルに追加されます。
図の３９から５２行目の hashtab_del() 関数は、既存の要素をハッシュテーブルから除きます。４８から５０行目は前と同様にバケツとインデックスを与えます。５１行目は指定された要素を除きます。hashtab_add() と同様に、コール元は同時実行制御の責任があります。それは、同時実行するサイズ変更操作と同期します。
クイッククイズ１０．１２：
図１０．２７の hashtab_del() 関数は、常に古いハッシュテーブルから要素を除くのではありません。これは、リーダーがこの、今削除された要素をそれが解放された後にアクセスすることがあることを意味しませんか？
実際のサイズ変更は、２５４ページの図１０．２８にある hashtab_resize で行われます。１７行目は、条件付きで、トップレベルの ->ht_lock を取り、もし確保が失敗したら、１８行目は -EBUSY を返してサイズ変更が既に実行中であることを示します。そうでなければ、１９行目は現在のハッシュテーブルの参照をピックアップします。２１から２４行目で目的の大きさの新しいハッシュテーブルを確保します。ハッシュとキーの関数の新しいセットが指定されていれば、新しいテーブルではそれが使われ、そうでないときは古いテーブルのものがそのまま使われます。２５行目でメモリ確保に失敗したら、２６行目で ->htlock を放して２７行目で失敗を返します。
２９行目は、古いテーブルの ->ht_new フィールドに新しいテーブルの参照を設定することによって、バケツ移動処理を始めます。３０行目で、新しいテーブルに気がついていない全てのリーダーがサイズ変更処理を続行する前に完了していることを保証します。３１行目は現在のテーブルのインデックスをピックアップして、それを逆にして新しいハッシュテーブルに格納します。これによって、２つのハッシュテーブルがお互いの連結リストを上書きしないことを保証します。
３３から４４行目のループのそれぞれのパスは、古いハッシュテーブルのバケツの一つの内容を新しいハッシュテーブルに移動します。３４行目で古いテーブルの現在のバケツの参照をピックアップして、３５行目でそのバケツのスピンロックを取ります。３６行目で ->ht_resize_cur を更新して、このバケツが移動されることを示します。
クイッククイズ１０．１３：
図１０．２８の hashtab_resize() 関数で、hashtab_lookup(), hashtab_add(), そして hashtab_del() の観点から見て、２９行目の ->ht_new の更新が３６行目の ->ht_resize_cur の更新よりも先に起きたように見えるのを保証するのは何ですか？
３７から４２行目のループのそれぞれのパスは、現在の古いテーブルのバケツから対応する新しいテーブルのバケツに一つのデータ要素を追加します。追加操作の間、新しいテーブルのバケツのロックを持っています。最後に、４３行目で古いテーブルのバケツロックを放します。
全ての古いテーブルのバケツが新しいテーブルに移動されたら、４５行目に来ます。４５行目では、新しく作成されたテーブルを、現在のものとして設定します。４６行目は全ての古いリーダー（まだ古いテーブルを参照しているかもしれません）が完了するのを待ちます。次に４７行目でサイズ変更をシリアライズするロックを放し、４８行目で古いハッシュテーブルを解放し、４９行目で成功を返します。
１０．４．３ サイズ変更可能なハッシュテーブルの議論
図１０．２９は、ハッシュテーブルに要素が 2048, 16,384, そして 131,072 ある時に、サイズ変更可能なハッシュテーブルを対応する固定長のものと比べました。図は、それぞれの要素数ごとに３つの線を示します。一つは、固定長の１０２４バケツのハッシュテーブル、もうひとつは、固定長の２０４８バケツのハッシュテーブル、３つ目は、１０２４と２０４８バケツの間を行ったり来たりするサイズ変更可能なハッシュテーブルです。サイズ変更操作の間には、１ミリ秒の遅延があります。
一番上の３つの線は、２０４８要素のハッシュテーブルです。上の線は固定長の２０４８バケツのハッシュテーブル、真ん中の線は固定長の１０２４バケツのハッシュテーブル、下のが、サイズ変更可能なハッシュテーブルです。この場合、ハッシュチェーンが短いので、通常の検索オーバヘッドはとても小さく、サイズ変更のオーバヘッドが目立ちます。しかし、大きい方の固定長ハッシュテーブルは大いに性能優位ですから、少なくても、サイズ変更操作の間に十分な時間をおけば、サイズ変更はとても有利と言えます。１ミリ秒は、明らかに、短すぎます。
真ん中の３つの線は、16,384 要素のハッシュテーブルのものです。同様に、上の線は固定長の２０４８バケツのハッシュテーブルですが、真ん中の線は今回はサイズ変更可能なハッシュテーブルで、下の線が固定長の１０２４バケツのハッシュテーブルです。しかし、サイズ変更可能なのと１０２４バケツのとの性能差はとても小さいです。要素数が８倍に増えた（そして同時にハッシュチェーンの長さも）一つの結果は、ひんぱんなサイズ変更は、小さすぎるハッシュテーブルを維持することよりも、悪いことではなくなったということです。
下の３つの線は、131,072 要素のハッシュテーブルのものです。上の線は固定長の２０４８バケツのハッシュテーブルで、真ん中の線はサイズ変更可能なハッシュテーブル、下の線が固定長の１０２４バケツのハッシュテーブルです。この場合、ハッシュチェーンが長い結果、検索オーバヘッドが大きくなり、この検索オーバヘッドの方が、ハッシュテーブルをサイズ変更するオーバヘッドよりも主要になりました。しかし、131,072 要素レベルの３つのアプローチ全ての性能は、２０４８要素レベルのと較べて、一桁以上も悪いですから、最も良い戦略は、ハッシュテーブルサイズをただ６４倍に増やすことだと言えます。
このデータの鍵となる点は、RCU保護されたサイズ変更可能なハッシュテーブルは固定長のものと比べて、性能もスケーラビリティもほぼ同じくらいに良いということです。実際のサイズ変更操作の間の性能は、もちろん、それぞれの要素のポインタが更新される結果起きるキャッシュミスのために少しは悪くなるでしょう。そしてこの効果は、ハッシュテーブルのバケツリストが短い時に最も顕著です。これが意味することは、ハッシュテーブルは一度にかなりな量、サイズ変更するべきで、サイズ変更操作があまりにひんぱんに起きることによる性能低下を防ぐために慣性を適用するべきだということです。メモリが豊富な環境では、ハッシュテーブルのサイズを大きくするのは、小さくするときに比べてずっとアグレッシブに行なって良いでしょう。
もう一つの鍵となる点は、hashtab 構造体は分割不可能ですが、それは同時にリードがほとんどです。ということは、RCUの使用が適切です。このサイズ変更可能ハッシュテーブルの性能とスケーラビリティがRCU保護された固定長ハッシュテーブルに非常に近いことから、このアプローチはとても成功したと結論づけても良いでしょう。
最後に、挿入、削除と検索操作はサイズ変更操作と同時実行できることに注意するのは重要です。この同時実行性は、巨大なハッシュテーブルをサイズ変更するときには致命的に重要です。アプリケーションが厳しい応答時間制限を満たす必要のある時は特にそうです。
もちろん、ht_elem 構造体の、ポインタセットが２つあることは、メモリオーバヘッドをある程度課します。それについては次の節で。
１０．４．４ その他のサイズ変更可能なハッシュテーブル
この節のはじめに説明したサイズ変更なハッシュテーブルの一つの欠点は、メモリ消費です。それぞれのデータ要素は一つでなくて二つの連結リストポインタの対を持ちます。RCU保護されたサイズ変更なハッシュテーブルであって、ただ一つだけの対でうまくできるものを作ることは可能でしょうか？
答えは、「はい」であることがわかりました。Josh Triplett 達は、相対的ハッシュテーブルを作りました。それは、対応するハッシュチェーンをインクリメンタルに分離、結合します。このため、リーダーは常に、サイズ変更操作の間のいかなる時点でも有効なハッシュチェーンを見ます。このインクリメンタルな分離と結合は、リーダーがどこか他のハッシュチェーンにあるべきデータ要素を見ても無害だという事実に依存します。これが起きても、リーダーは単純に余分なデータ要素を、キーの不一致のために無視します。
図１０．３０に、相対的ハッシュテーブルを２分の１に縮小するプロセスを示しました。この場合、２つのバケツのハッシュテーブルを一つのバケツのハッシュテーブル、要するに線形リスト、に縮小します。このプロセスは、古い大きなハッシュテーブルのバケツの対を、新しい小さいハッシュテーブルにおいて単一のバケツに結合することによって動作します。このプロセスが正しく働くためには、明らかに、２つのテーブルのハッシュ関数を制限する必要があります。そのような制限の一つは、両方のテーブルに同じ元となるハッシュ関数を使い、ただ、大から小に縮小するときには低オーダーのビットを捨てることです。例えば、古い２バケツのハッシュテーブルは値の２つの最上位ビットを使い、新しい１バケツのハッシュテーブルは値の１つの最上位ビットを使えばよいです。このようにすれば、古い大きなハッシュテーブルの隣接する偶数と奇数のバケツの対は、新しい小さいハッシュテーブルにおいて一つのバケツに結合できます。その時、一つのハッシュ値が、その単一のバケツにある要素全てをカバーし続けることができます。
初期状態を図の一番上に示します。時間は、初期状態 (a) から始まって、上から下に進みます。縮小プロセスは、まず、新しいより小さいバケツ配列を確保することから始めます。そしてこの新しいより小さいバケツ配列のそれぞれのバケツが、古いより大きいハッシュテーブルの対応する対の一つの最初の要素を指すようにします。これで、状態 (b) になります。
次に、２つのハッシュチェーンをつなぎます。これで、状態 (c) になります。この状態で、偶数番の要素を検索するリーダーは何も変化を見ませんし、要素１と３を検索しているリーダーも変化を見ません。しかし、それ以外の奇数番を検索するリーダーは要素０と２もトラバースします。これは無害です。なぜならば、どんな奇数もこれらの２つの要素と比較して等しくはならないからです。性能の低下はあるかもしれませんが、一方、これは、新しい小さいハッシュテーブルが完全に使われた時に起きる性能低下と全く同じです。
次に、新しい小さいハッシュテーブルがリーダーからアクセスできるようになります。これで、状態 (d) になります。古いリーダーが、まだ、古い大きいハッシュテーブルをトラバースしているかもしれないことに注意下さい。なので、この状態では、両方のハッシュテーブルが使用中です。
次のステップは、全ての既存のリーダーが完了するのを待つことです。これで、状態 (e) になります。この状態で、すべてのリーダーは新しい小さいハッシュテーブルを使っているので、古いより大きいハッシュテーブルのバケツは解放できます。これで、最後の状態 (f) になります。
相対的ハッシュテーブルを拡張するのは、縮小プロセスを逆にします。しかし、より多くのグレースピリオドのステップを必要とします。初期状態 (a) を図１０．３１の一番上に示します。時間は、上から下に進みます。
まず、新しい、大きな２バケツのハッシュテーブルを確保することから始めます。これで、状態 (b) になります。これらの新しいバケツはそれぞれ、そのバケツのための最初の要素を指していることに注意下さい。これらの新しいバケツはリーダーに公開されます。これで、状態 (c) になります。グレースピリオド操作の後、すべてのリーダーは新しい大きなハッシュテーブルを使っています。これで、状態 (d) になります。この状態では、偶数値のハッシュバケツをトラバースするリーダーだけが、要素０をトラバースします。なので、それを白く塗ってあります。
この時点で、古い小さなハッシュバケツを解放できます。しかし、多くの実装では、この古いバケツを、要素のリストをそれぞれの対応するバケツに「取り分ける」処理の進行を追跡するために使い続けるようです。最初の偶数値の連続するつながりの、最後の要素は、ここで、その next ポインタが、それに続く偶数値の要素を指すように更新されます。訳注。ゼロの次は２。その後のグレースピリオド操作の後、状態 (e) になります。垂直の矢印は、取り分けられる次の要素を示します。要素１は黒く塗られ、奇数のハッシュバケツをトラバースするリーダーだけがそれにたどりつけることを示します。
次に、最初の奇数値の連続するつながりの、最後の要素は、ここで、その next ポインタが、それに続く奇数値の要素を指すように更新されます。その後のグレースピリオド操作の後、状態 (f) になります。最後の取り分け操作（グレースピリオド操作を含む）の後、最後の状態 (g) になります。
要するに、相対的ハッシュテーブルは、要素ごとのリストポインタの数を減らします。そのために、サイズ変更操作の間、追加のグレースピリオドの発生というコストを払います。これらの追加のグレースピリオドは通常は問題となりません。なぜならば、挿入、削除そして検索はサイズ変更操作と同時実行して進行できるからです。
O(1) 削除を保ちながら、要素ごとのメモリオーバヘッドをポインタの対から単独のポインタに減らすことが可能であることがわかりました。これは、split-order list を、RCU 保護で補強することで達成されました。ハッシュテーブルのデータ要素は、単一のソートされた連結リストに配置されます。それぞれのハッシュバケツはそのバケツの最初の要素を指します。要素を削除するには、その next ポインタの低オーダービットを設定します。そしてこの要素は、後に、それを参照したトラバースの時に、リストから除かれます。
このRCU 保護された split-order list は複雑です。しかし、全ての挿入、削除、そして検索操作に対して、ロックフリーの進行保証を提供します。そのような保証は、実時間アプリケーションで重要なことがあります。実装は、ユーザ空間 RCU ライブラリの最近のバージョンで入手可能です。
１０．５ 他のデータ構造
これまでの節は、分割（１０．２節）、リードがほとんどのアクセスパターンの効率的な扱い（１０．３節）、あるいは、リードがほとんどの場合のテクニックを使って分割不可能性を回避する（１０．４節）などによって、同時実行性を強化したデータ構造に焦点を当ててきました。この節は、他のデータ構造の簡単なレビューをします。
並列使用でのハッシュテーブルの最大の利点の一つは、それが完全に分割可能なことです。少なくても、サイズ変更しない限り。分割可能性とサイズ非依存を保つ一つの方法は、radix tree を使うことです。trie とも呼ばれます。trie は、検索キーを分割します。それぞれ、続くキーの分割を、trie の次のレベルをトラバースするのに使います。なので、trie をネストしたハッシュテーブルのセットと考えることができます。必要な分割可能性は、このようにして得られます。trie の一つの欠点は、キーの空間が疎だと、メモリ使用が非効率になることです。この欠点を回避するために使うことのできる多くの圧縮テクニックがあります。それには、トラバースの前に、キーの値をより小さいキー空間にハッシュするというのもあります。radix tree は、現実に大いに使われており、Linuxカーネルも含まれます。
ハッシュテーブルと trie の一つの重要な特別ケースは、たぶん、最も古いデータ構造である、配列とその多次元の仲間である行列です。行列が完全に分割可能であるという性質は、同時実行する数値計算アルゴリズムで大いに活用されています。
自己バランスする木は、シーケンシャルコードで大いに使われています。AVL 木と赤黒木がたぶん、最も有名な例でしょう。初期の、AVL 木を並列化する試みは、複雑で、それほど効率的ではありませんでした。しかし、より最近の、赤黒木の研究は、リーダーにRCUを使い、リードと更新を守るためにロックのハッシュした配列をそれぞれに使うことで、より良い性能とスケーラビリティを提供します。
脚注。
そこでは、swissTM が使われています。それは、ソフトウェアトランザクショナルメモリの変種で、開発者が共用されないアクセスにフラグをつけます。
赤黒木はアグレッシブに再バランスを行います。それは、シーケンシャルプログラムにはうまく働きますが、並列使用ではあまり良くないことがわかってきました。このため、最近の研究は、RCU保護された、「盆栽木」を使います。それは、再バランスはそれほどアグレッシブに行わず、最適な木の深さと、より効率的な同時実行する更新とのトレードオフを行います。
同時実行する skip list は、RCUリーダーにうまく適合し、実際、RCUに似たテクニックが初期に学術的に使われた例となりました。
同時実行する double-ended queue は、６．１．２節で議論しました。同時実行するスタックとキューは長い歴史を持ちます。ただ、性能とスケーラビリティは通常、注目するほどではありませんでした。とはいっても、それらは同時実行ライブラリの共通の機能です。研究者は、最近、スタックとキューのオーダリング制限を緩める提案をしました。ある研究は、オーダーをゆるめたキューは、実際には、厳格な FIFO キューよりも優れたオーダリング属性を持つことを示しました。
同時実行データ構造に関するこれからも続く研究が、驚くべき性質を持つ新規なアルゴリズムを作り出すかもしれないというのは大いにありうることでしょう。
１０．６ マイクロ最適化
この節で示したデータ構造は、直裁的にコードされました。元となるシステムのキャッシュ階層への適応はされていません。さらに、実装の多くは、キーからハッシュへの変換のための関数へのポインタを使っています。他の頻繁な操作についても同じです。このアプローチは単純で移植性も良いのですが、多くの場合に、それはある程度の性能を犠牲とします。
以下の節は、特殊化、メモリ削減、そしてハードウェアの考察に触れます。これらの短い節が、この題材の決定的な扱いであると誤解しないで下さい。特定のCPUに対する最適化については、完全な本が何冊も書かれています。現在一般的なCPUファミリーのセットについてはもちろんです。
１０．６．１ 特殊化
１０．４節で示したサイズ変更可能ハッシュテーブルは、キーに不透明型を使いました。これは大きな柔軟性を可能とします。どのようなキーでも使えます。しかしそれは、関数をポインタ経由で呼ぶことに由来する大きなオーバヘッドを起こします。今では、現代的なハードウェアは、洗練された分岐予測テクニックを使って、このオーバヘッドを減らそうとします。しかし一方では、実世界のソフトウェアはしばしば、今日の大きなハードウェア分岐予測テーブルであってもそれに入りきらないほど大きいのです。これは、ポインタ経由での呼び出しには特に当てはまります。その場合、分岐予測ハードウェアは、分岐がされたかされなかったかの情報に加えて、ポインタも記録しないといけません。
このオーバヘッドは、ハッシュテーブル実装を、特定のキーの型とハッシュ関数に特殊化することで除くことができます。そうすると、２４９ページの図１０．２４に示される ht 構造体にある、->ht_cmp(), ->ht_gethash(), そして ->ht_getkey() 関数ポインタがなくなります。それはまた、それらのポインタ経由の対応する呼び出しを削除しますから、コンパイラは結果となる固定関数をインラインにして、呼び出し命令のオーバヘッドだけでなく、引数のマーシャリングも除くことができるかもしれません。
さらに、このサイズ変更可能ハッシュテーブルは、バケツ選択と同時実行制御を分離する API に適するように設計されています。これにより、単一の拷問テストがこの章の全てのハッシュテーブル実装をテストできますが、それはまた、多くの操作が、ハッシュを計算して、さらに、起こりうるサイズ変更操作と相互作用することを、１度でなくて２度行わなくてはいけないことを意味します。性能が重要な環境では、hashtab_lock_mod() 関数は、選択したバケツへの参照も返すべきです。そうすれば、次の ht_get_bucket() 呼び出しがいりません。
クイッククイズ１０．１４
hashtorture.h コードを変更して、ht_get_bucket() 機能も持つ hashtab_lock_mod() バージョンも含めるようにできませんか？
クイッククイズ１０．１５
これらの特殊化は、実際にどれだけお得なのです？本当に、やる価値があるのですか？
とは言え、私が１９７０年代初頭にプログラムを学び始めた頃にあったハードウェアと今のを比べると、今のの大きな利点の一つは、特殊化の必要性がずっと小さいことです。それは、４KB アドレス空間の日々に可能であったのと比べると、はるかに大きい生産性を可能とします。
１０．６．２ ビットとバイト
この章で議論したハッシュテーブルは、メモリを節約するためにはほとんど何もしません。例えば、２４９ページの図１０．２４にある ht 構造体の ->ht_idx フィールドは、ゼロか１の値しか持ちませんが、３２ビットのメモリ全部を占めます。それは、例えば、->ht_resize_key フィールドからビットをもらえば、除くことができます。->ht_resize_key フィールドは、メモリの全てのバイトを指定するだけの十分な大きさがあります。そして、ht_bucket は１バイト以上の大きさがあります。なので、->ht_resize_key は、何ビットか、余分があるので、うまくいくはずです。
この種のビットパッキングトリックは、Linux カーネルの page 構造体のようにとてもたくさん複製されるデータ構造でしばしば使われます。しかし、私たちのリサイズ可能ハッシュテーブルの ht 構造体は、それほど多く複製されるわけではありません。その代わり、ht_bucket に焦点を合わせるべきです。ht_bucket 構造体を小さくするには、２つの主な選択肢があります。（１）->htb_lock フィールドを、->htb_head ポインタの一つの、低オーダーのビットに置く。（２）必要なポインタの数を減らす。
最初の選択肢は、Linux カーネルの include/linux/bit_spinlock.h ヘッダファイルで提供されるビットスピンロックを使うことになるかもしれません。それは、Linux カーネルのスペースがクリティカルなデータ構造で使われますが、それ固有の欠点もあります。
１ 普通のスピンロックプリミティブより、かなり遅いです。
２ Linux カーネルの lockdep デッドロック検知ツールに参加できません。
３ ロックの所有者を記録しないため、さらにデバッグを困難にします。
４ -rt カーネルにおいて、優先度ブーストに参加しません。ということは、ビットスピンロックを保持しているときは、プリエンプションを無効にしなくてはならず、実時間遅延を悪化させることがあります。
これらの欠点がありますが、ビットスピンロックは、メモリがとても重要なときには、極めて便利です。
２つめの選択肢の一つの側面は、１０．４．４説で述べました。そこでは、リサイズ可能ハッシュテーブルで、１０．４節で述べたリサイズ可能ハッシュテーブルで必要であった２つのバケツリストポインタのセットの代わりに、たった一つしかポインタのセットを必要としませんでした。別のアプローチは、この章で使った、２重連結リストの代わりに、１重の連結バケツリストを使うものでしょう。このアプローチの一つの欠点は、削除に追加のオーバヘッドが必要なことです。それは、なくなる要素のポインタを後に削除するために印をつけておくとか、削除されるその要素をバケツリストから探す必要があることです。
要するに、最小のメモリオーバヘッドと、性能と単純さの間には、トレードオフがあります。幸い、最近のシステムでは比較的大きなメモリが利用可能なので、メモリオーバヘッドよりは、性能と単純さを優先できることが多いようです。しかし、今日の巨大メモリシステムであっても、時には、メモリオーバヘッドを減らすために極端な方法をとる必要のある時もあります。
脚注。
何ギガバイトものメモリを持つスマートフォンを持ってる人、いますか？
１０．６．３ ハードウェア考察
現代的計算機は、典型的に、CPUと主記憶の間で、データを３２バイトから２５６バイトの固定長のブロックで移動します。このブロックをキャッシュラインと呼び、それは３．２節で述べたように、高い性能とスケーラビリティに極めて重要です。性能とスケーラビリティの両方を殺す一つの古典的な方法は、両立しない変数を同じキャッシュラインに置くことです。例えば、サイズ変更可能なハッシュテーブルのデータ要素が、ht_elem 構造を、とてもひんぱんに加算されるカウンタと同じキャッシュラインに置いたとします。ひんぱんな加算は、キャッシュラインを、加算をしているCPUだけにあってそれ以外には無いようにします。もし他のCPUが、その要素を含むハッシュバケツリストをトラバースしようとしたら、高価なキャッシュミスを引き起こし、性能とスケーラビリティの両方を落とします。
６４バイトキャッシュラインを持つシステムでこの問題を解く一つの方法を、図１０．３２に示します。ここでは、gcc の aligned 属性を使って、->counter と、ht_elem 構造体が別々のキャッシュラインに乗るように強制します。こうすれば、CPUは、ひんぱんな加算があっても、ハッシュバケツリストをフルスピードでトラバースできます。
もちろん、これは、「キャッシュラインが６４バイトだってどうやって知っていたのですか？」という疑問を引き起こします。Linux システムでは、この情報は、/sys/devices/system/cpu/cpu*/cache/ ディレクトリから得られます。また、インストール処理で、アプリケーションをシステムのハードウェア構造に適合するように再ビルドすることさえ可能です。しかし、あなたがご自分のアプリケーションを Linux 以外のシステムでも走らせたいならば、それはずっと難しくなります。さらに、あなたが Linux でだけ走らせるので満足だとしても、そのような自己変更するインストールは検証への挑戦を引き起こします。
幸い、実際にかなりうまくいく大まかな規則があり、１９９５年の論文にまとめられています。
脚注。
ここでは、Orran Krieger の許可を得て、これらの規則のいくつかを別の言葉で言い換えたり拡張したりしています。
最初の規則のグループは、キャッシュジオメトリに適合するように構造体を再配置することに関連します。
１ リードがほとんどのデータを、ひんぱんに更新されるデータから分離しなさい。例えば、リードがほとんどのデータを、構造体の先頭において、ひんぱんに更新されるデータを最後に置きます。可能なら、ほとんどアクセスされないデータをその間に置きます。
２ もし構造体が、フィールドのグループを持ち、それぞれのグループが独立したコードパスによって更新されるならば、これらのグループを互いに離しなさい。
繰り返しますが、ほとんどアクセスされないデータをグループの間に置くのは良いことです。場合によっては、そのような個々のグループを、元の構造体から参照される別の構造体に分離するのも意味のあることです。
３ 可能なら、更新がほとんどのデータを、CPU、スレッドあるいはタスクに関連付けなさい。５章のカウンタ実装に、この規則のとても効果的な例がいくつかありました。
４ 実際、可能なら、あなたはご自分のデータを、CPUごと、スレッドごと、あるいはタスクごとに分けるべきです。８章で議論したとおりです。
最近、トレースをベースに、構造体フィールドを自動で再配置するための研究がいくつか行われました。この研究は、マルチスレッドのソフトウェアから素晴らしい性能とスケーラビリティを得るために必要な苦痛に満ちた作業の一つを少し楽にしてくれるかもしれません。
おおまかな規則の他のセットは、ロックに関連します。
１ ひんぱんに変更されるデータを守るロックが大いに競合するならば、以下のアプローチの一つを試しなさい。
(a)ロックを、それが守るデータと別のキャッシュラインに置きます。
(b)高い競合に適したロックを使います。例えば、キュードロック。
(c)ロック競合を減らすように再設計します。（このアプローチは最適です。しかし、かなり手間がかかるかもしれません。）
２ 競合しないロックを、それが守るデータと同じキャッシュラインに置きなさい。このアプローチは、ロックを現在のCPUに持ってくるキャッシュミスは、そのデータも持ってくることを意味します。
３ リードがほとんどのデータは、RCUで守りなさい。あるいは、RCUを使うことができず、クリティカルセクションがとても長く続くなら、リーダーライターロックを使いなさい。
もちろん、これらはおおまかな規則で、絶対ではありません。あなたの特定の状況にとって、どれが最も効果があるかを判断するには、少しばかりの実験が必要です。
１０．７ まとめ
この章は主に、ハッシュテーブルに焦点を当てました。それには、完全に分割可能でないサイズ変更可能なハッシュテーブルが含まれます。１０．５節はハッシュテーブル以外のデータ構造のいくつかの短い概説をしました。とはいえ、このハッシュテーブルの解説は、高性能でスケーラブルなデータアクセスに関する多くの問題への優れた導入でした。それには以下があります。
１ 完全に分割可能なデータ構造は小さいシステム、例えば、単一ソケットシステムでうまく動きます。
２ より大きなシステムは、参照の局所性と、完全な分割を必要とします。
３ ハザードポインタとRCUのような、リードがほとんどの場合のテクニックは、リードがほとんどのワークロードにおいて良い参照の局所性を提供します。このため、より大きなシステムにおいても、優れた性能とスケーラビリティを提供します。
４ リードがほとんどの場合のテクニックは、サイズ変更可能なハッシュテーブルのような、ある種の分割不可能なデータ構造に対しても、うまく動きます。
５ データ構造を特定のワークロードに特殊化することで、さらなる性能とスケーラビリティを得ることができます。例えば、一般的なキーを、３２ビット整数に変更することで。
６ 移植性と最大の性能への要求はしばしば矛盾します。しかし、この２つの要求の間の良いバランスを得ることのできるデータ構造レイアウトのテクニックがいくつかあります。
とはいえ、性能とスケーラビリティは、信頼性がなくては役に立ちません。なので、次の章は、検証についてです。
以上