HTMの第一人者にして、obstruction-freeやwait-freeなどの厳密な定義や、CAS命令の数学的な意義を証明し、The Art of Multiprocessor Programmingの著者で、ロックフリーでもSTMでも八面六臂の活躍をしているMaurice Herlihy先生が連名している最近の論文を流し読み。
Aleksandar Dragojevic, Maurice Herlihy, Yossi Lev, Mark Moir: On the power of hardware transactional memory to simplify memory management. PODC 2011: 99-108
「トランザクショナルメモリのパワーでメモリ管理を簡略化する」という感じ。
GCを使わない環境下においてメモリ管理は鬼門になってて、そのせいでC++のロックフリーなマルチスレッド対応ライブラリ数はJavaに大きな遅れを取っている。だからHTMを使ってメモリ管理を上手く行えるようになればC++のライブラリもゆくゆくは充実していくんじゃね？というのを起点にしている。
ここでいうメモリ管理は例えばABA問題回避策の一つであるスタンプ技法を使っても解決しない。共有されているデータがいつどの瞬間に消されるかわからないのできちんとした対策はかなり厳しい。実を言うとJavaでもGCのコストを避けるためにメモリプールを自前管理している場合にはこの問題にぶち当たる場合がある。
正しく回避する方法で現状広く知られているのはGC、Hazard Pointer、Repeat Offender Problem一派、RCU。何のこっちゃという人が多いと思うので簡単に説明すると
GCは言わずもがなマルチスレッド環境に対応してくれるGCが必要。実質Lock-freeなコードを書くのにJVMが適している最大の理由。shared_ptrのような参照カウンタ式のGCはカウントのup/downの為にアトミック命令を使う必要があって速度ペナルティが酷い事になるのでこのような場面では使い物にならない。なると思う人は以前僕が作ったC++実装の並行SkipList https://github.com/kumagi/sl を使い物にしていただきたい…。検索のために2*log n回のアトミック命令…。
Hazard Pointerは各スレッドが他のスレッドから見える場所にスレッドローカルストレージを置いて、その中に「俺が見てるからな！捨てるなよ！どうしても捨てるなら後にしろよ！」と、庇護して欲しいポインタを明示する物。データを解放したくなったら他のスレッドのスレッドローカルストレージも全て見て回って、自分の捨てたいデータが存在しない事を確かめてから解放する。もし他のスレッドのスレッドローカルストレージに置かれている場合には、自スレッドの他者から見れない場所に「あとで消す」リストとして保持しておいて、次回の調査時にそれらが解放できるかどうかもついでにチェックしてから解放する。スレッドローカルストレージを並べる分、移植性のある実装が難しいしスレッドを動的に作ったり壊したりする場合の動作はどうなるのかよくわからない（まだ論文読み込んでない）。局所的なGCを実装しているという見方もできる。
Repeat Offender Probrem一派、いわゆるROPは、大まかにHazard Pointerのように自分のアクセスしている最中のポインタを削除対象にさせないように庇護する目的は一緒。スレッドローカルストレージではなくて、グローバル変数として一本の配列を用意して、各スレッドは必要な処理の間その配列の一部分を自分用として予約してから使う。配列の各要素が警備員であり、スレッドはその警備員一人にポインタ（再犯者）を割り当てて監視させる。最初の警備員獲得時にはアトミック命令を使う必要はあるけれど監視対象変更はメモリバリアさえきちんとしていれば良い。メモリを解放するときは自分の雇った警備員を全て解任（グローバルな配列に返す）して、他の警備員が自分の開放したい対象を監視していないかを調べさせて、監視されていない物をLiberateする。RepeatOffenderProbrem一派と書いているのは、その警備員の確保から監視、解放までの間でどこに最適化するかでバリエーションが考えられるので一言には言えないから。元論文の中ではPass The Buck（なすり付け法）という手法が紹介されていた。まだ論文無しに実装できる気がしない。
RCUはOS側の機能を利用して「1回の操作の間（クリティカルセクション）にプリエンプションを禁じる」「自分が捨てようと思ってポインタを外部から不可視に書き換えてから、自分以外のスレッドが最低1回プリエンプションしてたら少なくとも全員操作の外に居るので自分以外のスレッドからは絶対にそのデータが見えるはずがない」という前提に立ってデータの削除タイミングを見極める物。具体的には捨てたいと思ってから自分の今居るプロセッサに自分以外の全てのスレッドが1度でもマイグレーションされたら、マイグレーション≒プリエンプションなので数え上げれる、などが簡単な判定方法の例。クリティカルセクションの中でロックを取る事ができるバリエーションなどがあるという噂もあって全く理解できない。OSの機能を使っているので移植性が不味い上、カーネル内部以外で利用されている姿を見たことがない。userspace rcuというライブラリも出ているけれど全くわからない。一言で言うと今回の範囲外。
で、Hazard PointerやROP一派はメモリの解放時の安全確認のため「自分以外のスレッドが現在使っているデータのリスト」を作成する必要があるのだけれど、そのコストがあまりに高く速度面で大きな足かせとなっていたので、そこにHTM使う事でとても簡単で高速にできるよ。というのがこの論文最大の趣旨。HazardPointerというよりはROPに近いので「ROPのHTM版」というのが近いような気がする。HTMはその物理的特性上、O(1)のサイズのメモリまでしか一回のトランザクションで操作できない（ROCKというプロセッサではWrite Bufferのサイズなので大きさが32などと書いてあったけれど単位がわからない）が、それでも解決可能であることを示している。
具体的に言うとList Basedな手法とArray Basedな手法があって、List Basedな方は速度ペナルティがある物の興味深い技法（telescoping）があって、Array Basedな方はArray Sizeが動的に変わるという鬼畜な想定でもHTMの力で無理やりねじ伏せれるという物。論文には動的なArrayの場合の擬似コードがかかれいている。HTMは細かいトランザクションが得意だけど、O(n)回のトランザクションを行うスキャンは本当に大丈夫なのかわからない。
メモリを守りたい時には、「このポインタを庇護してください」という関数（register）を呼ぶ、その関数では新しくポインタを作って、そのポインタがglobalな配列の一要素を指すような状態を作り、その指している先の１要素の中に保護対象のポインタを保存し、作ったポインタを返す。ユーザーは保護を解除させる場合にはポインタを引数に渡しながら解放させる関数を呼ぶ(deregister)、配列は常に先頭から順に使い、解放するときには対象を配列の利用済み分の末尾とスワップした上で末尾を消去する。そしてスキャン操作は１要素ずつ１トランザクションで舐めていくけれど、この際に配列を末尾から舐めていく事が最大のポイント、スキャン操作は実は擬陽性が有っても問題ないし、同じ要素を２回以上登録しても問題ないので、deregster操作と厳密な線形化ポイントが取れなくても実用上問題ない。それよりもregister操作との一貫性の為のトランザクションがどうなっているのか気になったけれど書いていないので困る。そもそもRepeat Offender Problemの段階から既にそこの問題は無かったのかも知れない。
結論から言うと、HTM版のROPのような手法で、トランザクションをふんだんに使って、局所的に「捨ててもOK」なスレッド間共有メモリを簡単に洗い出せる手法を考えました。という物。
