標準のstd::shared_mutexを自前のスピンロックに変えるとスループットが改善するという話を以前の記事に書いた。今回はそれを改良して、優先度のポリシーを変えたり、共有ロックを保持したまま排他ロックに格上げするアップグレード機能を実装したりする。
本題に入る前に、自前のスピンロックの効能について少し掘り下げてみたい。スピンロックであることで、ロック失敗時にCPU使用率が上がるという副作用と引き換えに性能向上が図れることは以前の記事で述べた。もう一つの美点は、構造体のサイズが小さいことだ。sizeof(std::mutex) は40バイトで、sizoeof(tkrzw::SpinLock)は1バイトである。sizeof(std::shared_mutex)とsizeof(std::shared_timed_mutex)はともに56バイトで、sizeof(tkrzw::SpinSharedLock)は4バイトである。つまり、単純化した分、1/40または1/12に小さくなっている。単純化したスピンロックはアトミック変数1個で実装できるので、当然といえば当然だ。
ところで、Tkrzwのハッシュデータベースはバケットを128個のスロットに分けてロックしているが、以前は128*56で7168バイトのメモリを使用していた。これが128*4の512バイトに減らせたのはなかなか大きい。これなら、スロット数を増やして衝突率をさらに下げることも可能だ。とはいえ、私のノートPCのCPUのL1キャッシュが32KBほど、L2キャッシュが256KBほどであることを勘案すると、収穫逓減状態のパラメータをあまり大きくしても全体的に損になるので、今のままでいいだろう。
共有ロックの実装を単純化した副作用のもう一つとして上げられるのは、いわゆるリソーススタベーションの問題である。今の実装は、Read-preferring RW lockというカテゴリのポリシーを実装していることになる。すなわち、共有ロックの要求が連続的に続く中では、排他ロックは永遠に獲得できない。よって、Getクエリがひっきりなしに続く中でSetクエリが交じると、Setクエリは永遠に処理されないことになる。ただ、現実的に考えて、Getクエリだけが本当に絶え間なく続くユースケースというのは少し考えづらい、一定の割合でSetクエリが交じるのであれば、そのうち処理待ちのキューがSetだけになるので、そのどれかが排他ロックを獲得するだろう。この言い草は前段にタスクキューがあることを前提としているが、そうでなくても、かなり恣意的にタイミングを図らないとリソーススタベーションは起こせない。そもそもデータベース層のロックはバケット単位やページ単位で細分化されているので、同じリソースに対するロック要求が衝突することが稀なのだ。ファイル層のロックでは、排他ロックはファイルサイズを倍々ゲームで拡張する瞬間にしかかからないので、衝突頻度はとても低い。よって、Tkrzwの内部で使う限りにおいては、共有ロックはRead-preferringで構わない。それが最速だから。仮にリソーススタベーションの問題が表面化したとしたら、おそらくは、Get等の参照系クエリにも確率的に排他ロックを取得させる対処を行うだろう。
ちなみに、std::shared_mutexの仕様ではロックの優先順位ポリシーについて規定されていないので、実装によってはRead-preferringかもしれないし、Write-preferringかもしれないし、FIFOやラウンドロビンかもしれない。Linux上だとstd::shared_lockはpthread_rwlock_tで実装されているが、そのデフォルトポリシーはPTHREAD_RWLOCK_PREFER_READER_NPなので、つまりRead-preferringだ。これをPTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NPに変えるとWrite-preferringにできるが、C++標準ではそのような制御はできない。
さて、共有ロックを獲得している状態で、それを排他ロックにアップグレードする機能を考えよう。共有ロックをアンロックをしてから排他ロックを獲得しなおすのではなく、共有ロックを保持しつつ、排他ロックに変化させたいのだ。
確実にアップグレードできるメソッドは提供できない。なぜなら、共有ロックを獲得しているスレッドが2つ以上いる状態で、それらがアップグレードを同時に試みたら、デッドロックしてしまうからだ。ただし、アップグレードを試みる try_upgrade とかいうメソッドなら提供できる。このメソッドは、他に共有ロックを保持しているスレッドがいれば失敗し、そうでなければ成功して、保持している共有ロックが排他ロックに格上げされる。成功して排他ロックに格上げされたなら、アンロックは unlock_shared ではなく、unlock で行わねばならないとする。
実装は単純で、以下のようにcompare_exchangeを使えばよいだろう。共有ロックのカウンタが1の場合のみ、つまり共有ロックを持っているのが自分自身だけの場合にのみ、カウンタをINT32MAXに設定して、その成否を返す。
bool try_upgrade() {
uint32_t old_value = 1;
return compare_exchange_strong(old_value, INT32MAX);
}排他ロックを確保しているスレッドがいる状態では、そいつはupgradeを呼ばないと分かっているので、そいつの終了を待つことでデッドロックはしない。よって、以下のように書き換えても良い。希望がある限り待つためのwaitというフラグを導入する。
bool try_upgrade(bool wait = false) {
while (true) {
uint32_t old_value = 1;
if (count_.compare_exchange_strong(old_value, INT32MAX)) {
return true;
}
if (!wait || old_value < INT32MAX) {
return false;
}
std::this_thread::yield();
}
}しかし、このメソッドの成功率は低いだろう。shared_mutexの典型的なユースケースは、多数の共有ロックが同時に取得される中で、少数の排他ロックが交じる場合だ。排他ロックが多数なのであれば、複数の共有ロックが同時に取得される可能性が低いので、スループットが上がらない。だったら普通のmutexを使った方がマシということになってしまう。よって、多数の共有ロック要求が常にあるということは前提とすべきだ。同じ理由で、排他ロックの確保を試みるtry_lockの成功率も低い。しかし、lockで排他ロックを確保するまでビジーループで待機するなら、いつかできるであろう「隙」をついて成功する。一方で、try_upgradeは無条件のビジーループで待つわけにはいかない。それはデッドロックを起こしてしまう。よって、上述のような条件付きのビジーループ待機という折衷案にならざるを得ない。
アップグレード機能を有効活用するには、そのshared_mutexはWrite-preferringな方が都合が良い。そのためには、排他ロックを要求しているスレッド（ワナビーと呼ぶ）の数をアトミックに数えねばならない。atomic_uint32_tのwannabe_countというメンバを追加しよう。そして、lockメソッドは以下のようになる。
void lock() {
wannabe_count_.fetch_add(1);
uint32_t old_value = 0;
while (!count_.compare_exchange_weak(old_value, INT32MAX)) {
std::this_thread::yield();
old_value = 0;
}
wannabe_count_.fetch_sub(1);
}一方で、共有ロックを確保しようとするlock_sharedメソッドは以下のようになる。wannabe_count_が0でない場合には遠慮するというわけだ。
void lock_shared() {
while (wannabe_count_.load() != 0 || count_.fetch_add(1) >= INT32MAX) {
uint32_t old_value = count_.load();
if (old_value > INT32MAX) {
count_.compare_exchange_weak(old_value, INT32MAX);
}
std::this_thread::yield();
}
}アップグレードを試みるtry_upgradeメソッドは以下のようになる。共有ロックを確保しているスレッドがいたとしても、それがワナビーでなければ、つまりワナビーが自分だけであれば、ビジーループを続けてもよい。ここが肝だ。
bool try_upgrade(bool wait = false) {
wannabe_count_.fetch_add(1);
while (true) {
uint32_t old_value = 1;
if (count_.compare_exchange_strong(old_value, INT32MAX)) {
wannabe_count_.fetch_sub(1);
return true;
}
if (!wait || (old_value < INT32MAX && wannabe_count_.load() > 1)) {
wannabe_count_.fetch_sub(1);
return false;
}
std::this_thread::yield();
}
}排他ロックから共有ロックにダウングレードする機能も定義できる。単にカウントを1にすればOK。
void downgrade() {
count_.store(1);
}さて、これを実装したクラスの名前は、SpinWPSharedMutexとしよう。try_upgradeの最初のバージョンは元々のSpinSharedMutexに組み込む。となると、新しいバージョンの特徴は、アップグレード機能があることではなく、Write-preferringであることなので、その旨を名前に表す。リンク先は実際のソースなので、興味があればご覧頂きたい。
当然ながら、SpinWPSharedMutexは空間効率も時間効率も元々のSpinSharedMutexに劣る。sizeof(SpinWPSharedMutex) は8に増えてしまった。排他ロックの確保に必要なアトミック変数の操作の最低回数が1回から3回に増え、共有ロックの確保に必要なアトミック変数の操作の最低回数が1回から2回に増えた。よって、用途に応じて使い分けてもらう感じになる。
どれだけ遅くなるか知りたいので、性能評価をしてみた。10スレッドを立てて、各スレッドが1億回ずつ、ロックとアンロックを繰り返すという操作にかかる時間を測った。結果の単位はミリ秒である。
| SpinLock#lock+unlock | 2373 |
| SpinSharedLock#lock+unlock | 4830 |
| SpinSharedLock#lock_shared+unlock_shared | 5388 |
| SpinSharedLock#lock_shared+try_upgrade+unlock(_shared) | 7131 |
| SpinWPSharedLock#lock+unlock | 9242 |
| SpinWPSharedLock#lock_shared+unlock_shared | 5797 |
| SpinWPSharedLock#lock_shared+try_upgrade+unlock(_shared) | 17897 |
排他ロックだけで考えると、SpinLockが最速であり、SpinSharedLockが次点で、SpinWPSharedLockがビリという順当な結果だ。面白いのは、SpinSharedLockの共有ロックとSpinWPSharedLockの共有ロックはそんなに変わらない結果だということだ。共有ロックのテストでは、全スレッドが共有ロックを試みるので、つまりワナビーが居ない状態である。その場合、SpinSharedLockとSpinWPSharedLockの違いは、ワナビーが居るかどうかを調べるためにアトミック変数のloadを呼ぶかどうかであり、そのコストはかなり小さいということが分かる。つまり、共有ロックの割合が高い典型的なユースケースの場合、SpinSharedLockの速度とSpinWPSharedLockの速度はそんなに変わらないということだ。これは意外だった。スピン共有ロックに限って言えば、Write-preferringにするコストは実用上はそんなに高くないと言えそうだ。
lock_sharedの後にtry_upgradeを呼ぶテストケースでは、SpinSharedLockではアップグレードの成功率は1.9%、SpinWPSharedLockではアップグレードの成功率は66.6%であった。ちゃんと優先度が反映されているようだ。SpinSharedLockではほとんどアップグレードに失敗するので、追加のコストは総計2秒と小さい。SpinWPSharedLockは半分以上成功するので、追加のコストは12秒近くにもなった。とはいえ1回の操作あたりに換算すると12ナノ秒なので、許容範囲だろう。
Write-preferringはRead-preferringより必ずしも優れているポリシーだというわけではない。逆の問題を引き起こすからだ。今度は、SetクエリがひっきりなしのところにGetクエリが混ざると、Getクエリが永遠に実行されないのだ。この場合、共有ロックの確保に何度か失敗したら排他ロックを確保するといったワークアラウンドが考えられる。排他ロックが多いのにshared_mutexを使うケースは少ないだろうが、アクセスパターンが時間によって変化するみたいなことは十分あり得るので、考えておいて損はない。 SpinWPSharedLockの中で確率的にポリシーを切り替えるとかすると面白いのかもしれないけれど、そういう実装を聞いたことがないので、おそらく使いにくいものになってしまうだろう。
まとめ。アップグレード可能な共有ロックを実装するのが目的であったが、ついでに優先度のポリシーをWrite-preferringに変えた実装も書いた。Write-preferringに変えることで実装は複雑化したが、そのオーバーヘッドは実用上では気にしなくていいレベルだと言えるだろう。そして、アップグレード機能は12ナノ秒程度のオーバーヘッドで実装することができた。成功率に優先度のポリシーがきちんと反映されることも確認した。
