Differential Reference Countingのメモ

【書籍】CppConcurrencyInActionを読んでて全然わからんな、と思っていたDifferential Reference Countingだが、 1024coresに解説を発見。ただなかなか難しいので、ここにメモを取りつつ考える。なお、本ポストではDRCと略す。

なぜ単なるリファレンスカウントに出来ないのか？

DRCの解説で良くわからない事としては、一体何をしようとしているのか、という所に思う。そもそもになんでリファレンスカウントをatomicなカウンターに持つだけではうまくいかないのか？という事をはっきりさせたい。

問題設定

やりたい事は、まず何らかのホルダー、holderのようなものを作りたい。これはオブジェクトへの参照で、並列に「違うオブジェクトがアサイン」されたりする。そしてこのホルダーに格納されるオブジェクトをリファレンスカウントで寿命管理したい。これがやりたい事に思う。

寿命管理は、

auto obj = holder.acquire();

objについての操作

obj.release();

のような感じでやりたい。holderから参照されている間はobjは当然活かし、またacquireで誰かが保持している間も活かす。 releaseの時はholderに入っているオブジェクトが変わる場合も考えればreleaseはobjにしたいだろう。

objにアトミックなリファレンスカウントをもたせるだけでは何故うまくいかないのか？

holderにobjへのポインタを持たせて、objにリファレンスカウントをもたせる、というのが一番普通に考えた時に出てくるアイデアだろう。だがこれは、

objというポインタをたどる事
objのリファレンスカウントをインクリメントする

の２つをアトミックに出来ない、という問題がある。例えば以下のようになっているとしよう。

struct Object {
  std::atomic<int> count;
  // そのほかデータ
};

struct Holder {
  Object* obj;

  Object* acquire() {
    auto o = obj;
    // この間でobjを削除されるかもしれない
    o->count++;
    return o;
  }
};

このacquireは、objからポインタを取り出した後にオーナーシップを宣言しようとするのでまずい。だが、カウンタを上げつつobjの参照を取る、という事をatomicにやる方法が無い。

ABA問題とか削除されるとかの問題を無視すれば、やりたいatomicオペレーションを無理やり言葉にするなら、「objがoと等しい時にo->countをインクリメントする」となる気がする。

objをatomicにしてcountをatomicにしても、コンペアするatomic（objの事）と++するatomicが別になるので、これは並列プリミティブとしてはうまく行かない。単なる隣の位置のdouble wordのCASよりもさらに複雑だろう。

holderにアトミックなカウンタを持つだけでは何故うまくいかないか？

objを参照する前にリファレンスカウントを上げるなら、holderにカウンタをもたせれば良さそうな気はする。 holderのカウンタを上げるのとobjをderefするのをアトミックにする必要はあるけれど、 objのポインタとリファレンスカウントは同じ場所にあるので、先程のobjとobjの中のcountのような全然別の場所とは違うから、だいぶどうにかなりそう。そこはだいたいのDRCで解説がある所で分からない所でも無いのでいいだろう。

だが、これも少し考えるとダメな事が分かる。それは、holderがacquireされている間に別のobj2をassignされると、 obj1のリファレンスカウントがクリアされるしか無いからだ。

obj1とobj2が順番に入れられると、以下のようになる。これはまずそう。

obj1をholderに入れる。holderのカウンタが1になる。
obj2をholderに入れる。obj1のカウンタが失われてしまう。

少し考えれば、2の時にobj1のカウンタに移動すれば良さそう、という事でDRCのアイデアに到達する事になる。

DRCによる解決策

この２つを混ぜた解決策がDRCとなる。まずholderにリファレンスカウントをもたせる。そしてobjにもリファレンスカウントを２つもたせる。一つはholderからリファレンスされている数、もうひとつはobj自身のリファレンスカウント。

つまり、全部でリファレンスカウントは３つになる。

holderのリファレンスカウント
objの、holderから参照されている数を表すリファレンスカウント（ohrefカウントと呼ぶ事にする）
obj自身のリファレンスカウント（basicリファレンスカウント、obrefカウントと呼ぶ事にする）

2と3を工夫して一つにする事も出来るけれど、そういう事を最初にやると意味がわからなくなるので、まずはこの３つで考えるのが良いと思う（1024coresもこの３つで考えている）。

holderからobjを取り出して作業する時は、

holderのリファレンスカウントを++する
objで作業する
objのbasicリファレンスカウントを–する

holderのリファレンスカウントとobrefのリファレンスカウントが別の場所にある、というのがポイントその1。 1と3の数がマッチング（1を負にすると3になる）と作業している人がいない、という事を表す。

また、holderがリファレンスしている間はいつもobjは削除されないために、参照がなくなるまでは削除の事は考えなくて良い。

削除の条件

削除の条件は

作業中の人が居ない
objを参照しているholderが無い

の２つになる。 obj2がアサインされる事を考えなければ、 holderのカウントとobjのobrefが足すと0になり、さらにholderからの参照がなくなる時（objのohrefが0になる時）が削除条件になる。

だが、obj2がholderにアサインされるケースも合わせて考える方がシンプルになる。 obj2がholderにアサインされると、

objのohrefを–
objのobrefにholderのリファレンスカウントを移動（足す）

となる。

これを行った後では、削除条件は「obrefが0かつohrefが0」になる。

削除されうる場所は、

objのrelease
holderへの（別のオブジェクトの）assign

の２つの場所になる。

参照の種類をまとめる

参照は２つの場所からの参照がある。

holderからobjへの参照
holderにacquireをした人の持つ参照

もう一度大雑把なアイデアをまとめる

同じような話を何度もする事になるが、自分の理解のためのメモなので仕方なし。

大雑把なアイデアとしては、

holderにaddRefするカウントをholderにもたせて
objにreleaseするカウントはobjに持たせる
けれどholderから参照を外す時にこのholderのカウントをobjに移動させる。

という事だな。こうする事でholderにobj2が入れられた時に、 holderのリファレンスカウントをobjに移す事が出来て、以後はobjのリファレンスカウントだけで寿命が管理出来る。

holderからリファレンスされている間は死ぬ事は無いので考えなくて良い。

h1とh2からobjが参照された場合とかもうちょっと真面目に考える事はあるけれど、基本的にはこれ。

holderのリファレンスカウントの解釈

rのリファレンスカウントは最終的にはobjに移動されるのだが、一時的にacquireのカウントをholderにキャッシュしているようなもの、と考えられる。このキャッシュはポインタのそばに置く事でobjの取得と同時に変更出来る。

このキャッシュは最終的にはobjに戻される訳だが、この時にどのオブジェクトに戻すかはカウントと同時に取得出来るのでこの対応関係は壊されないように出来る。

キャッシュはh1, h2、とホルダーの数だけあり、それぞれのホルダー経由で取得されたリファレンスの数を数えているという事か。

h1のキャッシュは、h1から参照している間はobjは削除されないので、h1から参照がなくなる時に移せば十分な事が保証されている。

イメージとしてはh1とかh2に入れるとその間はリファレンスカウントがそれぞれのホルダーにキャッシュされて、ホルダーから削除する時にこのカウントを移す。あとは通常のobjのリファレンスカウントと考える事が出来る。

これでキューのheadとか複数の場所から参照されるオブジェクトのホルダーのようなものが実現出来て、しかも格納するオブジェクトはリファレンスカウントで管理出来る。

よし、だいたい理解出来た！