再帰ロック (recursive mutex/lock) の偽共有 (False sharing) を改善する

nikezono,•misc
Back

この記事は，どこかのアドベントカレンダーにでも投稿しようと思ったけど忙しくてできなかった残滓です．

TL;DR;

背景: 再帰ロックとは

STLの std::recursive_mutex (opens in a new tab) とかでよく知られるもの．

std::recursive_mutex mutex;
mutex.lock();
mutex.lock(); // No deadlock
mutex.unlock();
mutex.unlock();

というふうに同じスレッドが複数回ロックを取ってもデッドロックしないのが特徴．これを使えばロックを保持する関数内で再帰を使えたりする．あとは，

void foo() {
  mutex.lock();
  bar();
  mutex.unlock();
}
void bar() {
  mutex.lock();
  ... // something critical...
  mutex.unlock();
}

といったふうに， foo() と bar() という二つのインタフェースが用意してあるが， bar() を直接呼び出すこともできますよ，という仕様を提供したい場合にも使われる．

ざっとgithubで std::recursive_mutex や pthread_mutex_recursive と検索したところ，pytorchとか，godotとか，XRPとか，かなり幅広いプロジェクトで使用されている．

余談: 再帰ロックは良くない

広く使われている再帰ロックだが，あまり好まれていないインタフェースでもある．

他にも様々なところで議論されているので，検索すると面白い．理由は様々だが，よく見かけるのは「ロックは原則，同じスコープ内（コンテクスト）で外そうや」，という一語につきる，というもの．
基本的に再帰ロックを使いたくなるときは再帰あるいは関数の呼び出しがあり，スコープの移動を伴うことが多い．スコープの移動を伴うとアンロックまでの時間をコードベース上で見積もるのが一気に難しくなり，意図せず長期間ロックを保持するコードになりがちだ（呼び出し元の関数がロックを取ってきている可能性を意識して関数を書くなんて難しい）．長すぎるクリティカルセクションはパフォーマンスの劣化をもたらしてしまう．いざパフォーマンスを最適化しようと思ったときにも，スコープをまたいでいるとロックをコードから削除する難易度が一気に上がっている．

しかし，そんな批判を受けていてもなお，多くのプロジェクトで今でも再帰ロックは使われている．これがなかなか趣深い．あるいは，使うのは簡単でも除去するのは大変，という話かもしれない．bitcoinでは再帰ロックを通常のロックに変えるPR (opens in a new tab) が進行していて，かなり苦労している様子が伺える．

前提: 再帰ロックの実装 101

再帰ロックの典型的な実装を図解する． 一般的な再帰ロックはロックフラグとは別にカウンタを用意している．ユーザはまずロックを獲得してから，カウンタをインクリメントすることで再帰の回数を記録する．本質的にはなくても実装できるが， lock_owner のようなフィールドも用意されることが多い．

2回目以降のロック獲得では，ロックフィールドの更新は省略され，カウンタのみをインクリメントするだけでいい．他のスレッドから見た状況はなんら変わらない（カウンタが1でも2でも「排他ロックされている」という情報量は同じ）．

問題(?): pthread の recursive_mutex

それはそれとして，ある日，glibcの再帰ロック実装を目にする機会があった． そこでこんなコード (opens in a new tab)を見た．

      /* Recursive mutex.  */
 
      /* Check whether we already hold the mutex.  */
      if (mutex->__data.__owner == id)
	{
	  /* Just bump the counter.  */
	  if (__builtin_expect (mutex->__data.__count + 1 == 0, 0))
	    /* Overflow of the counter.  */
	    return EAGAIN;
 
	  ++mutex->__data.__count;
 
	  return 0;
	}

ほうなるほど， mutex オブジェクトの中に __count というメンバーがあって，そのメンバーをインクリメント/デクリメントして再帰の深さ（呼び出し回数）を記録している．これは再帰ロックの最も典型的な実装パターンだ．

この __data はこういう型 (opens in a new tab)になっている．

struct __pthread_mutex_s
{
  int __lock __LOCK_ALIGNMENT;
  unsigned int __count;
  int __owner;
#if __WORDSIZE == 64
  unsigned int __nusers;
#endif

ここの __LOCK_ALIGNMENT はおそらくほとんどのアーキテクチャで空 (opens in a new tab)になっている．

#define __LOCK_ALIGNMENT

ここで一つ気になった．このアラインメントがないということは，ロックビットとカウンタのアドレスが隣接することになるが，それによって偽共有は生じないのだろうか？

偽共有についての説明は以下を拝借したい．

以下に簡単な図を書いた． 同じキャッシュラインにデータが載っているとき，いずれかのアドレスへの更新はキャッシュコヒーレンストラフィックを引き起こし，バスを経由して他のCPUに影響を与える．

つまり，先ほどの例でいえば，

      /* Check whether we already hold the mutex.  */
      if (mutex->__data.__owner == id)
	{
	  /* Just bump the counter.  */
	  if (__builtin_expect (mutex->__data.__count + 1 == 0, 0))

この部分のインクリメントによって偽共有が起こる． ロックを司るのは __data.__lock なので， 他のスレッドはこのアドレスしか興味がない．ロック獲得のためにこのアドレスをキャッシュラインに入れてループすることになるが，他のアドレスは使わない．とくに，再帰の深さがどれくらいになっているのかを示す __data.__count は他のスレッドに通知する必要が全くない情報なので，これを共有してしまうのはまさに「偽共有」だ．

他の実装

これはglibcだけの話なのかもしれない．他の実装はどうなっているのか見てみた．

android (bionic)

android (bionic) の実装はより悪く (opens in a new tab)，glibcでいう __data.__lock と　__data.__count が同じメンバ mvalue にまとめられている．たしかにロックが{1,0}の2値しか取らないのなら，カウンタも同じ場所にまとめて2,3,4... と再帰の深さを記録するのは効率的なアプローチに見える．（bool locked() { return 0 < __data.count__}といった感じで実装できる）しかし，他のスレッドとの排他が不要で，ただの mov で実装できるはずのカウンタのインクリメントに高価なアトミック命令を使うことになってしまっている．

Java (openjdk)

bionicとほぼ同じ．同じフィールドでロックとカウンタを両立 (opens in a new tab)している．

LLVM

まだ実装されていない (opens in a new tab)ように見える．

結論として，この偽共有はほぼあらゆるアプリケーション（pthread実装）で起こりうる．

提案: パディングの追加

そこで，簡単にコードを書いて実験してみた．

 struct Lock {  
    alignas(cache_line_size()) std::atomic<uint64_t> lock_;
    alignas(cache_line_size()) size_t counter_;
};

こんな感じで，C++の alignas キーワードを使えばキャッシュラインのサイズ分のパディングができる．これを使えばカウンタとロックを異なるキャッシュラインに配置できる．こんな小さい改変で性能がガラリと変わったりするものだろうか？

追加の提案: バックオフと再帰

実験に移る前に，もう一つ追加で改善を考えてみた． ロックというのは基本的に同じアドレスへのアトミック命令で実装されることが一般的だ．たとえば，上記の __data.__lock をロックとみなした場合，以下のような疑似コードで実装する．

constexpr int UNLOCKED = 0;
constexpr int LOCKED   = 1;
 
void lock() {
  int expected = UNLOCKED;
  while (expected == UNLOCKED){
    atomic_compare_exchange(expected, mutex->__data.__lock);
  }
}

実際のglibcも __sync_bool_compare_and_swap (opens in a new tab)で実装していて，まあ似た感じ．

これ，compare_and_swap というCPU的にはかなり高価な（時間のかかる）命令を使うわけで，そのオーバヘッドを避けるためにバックオフを設けて「アンロックされるだろうな」という見込みができるまで必要以上にロックを取りにいかないのがよくある実装になっている．その見込みというのはヒューリスティクスで実装されがちで，一般的にはバックオフを使う． 前述のglibcでも __data.__spins というメンバが用意されていて，これまでにロックにかかったスピン回数の統計（前例）からバックオフ時間を粗く見積もっている．

このバックオフは（統計情報を持たない場合）指数関数バックオフなどで実現されるのが一般的だが，より精度を上げるために，再帰の深さを取り入れるのはどうだろうか？ たとえば，__data.__count が10まで到達するようなユースケースだと，下手すると10回も同じ回数が再帰で呼ばれていることになる．これはアンロックまで相当な時間になりそうだ． その場合は，「このロックは10回再帰することもあるぞ」ということを他のスレッドに伝えることで，バックオフの回数を綺麗に設定できないだろうか？ これも実際に実装してみた．

size_t i = 1;
while (true){	
  if (try_lock()) break;
  if constexpr (SleepType::Exponential) {
	  std::this_thread::sleep_for(std::chrono::nanoseconds(1 << i);
  } else if constexpr (SleepType::AdaptiveBackoff) {
    const size_t adaptive = lock.recursive_count_metric;
    std::this_thread::sleep_for(std::chrono::nanoseconds(1 << i * (adaptive)));
	}
	i++;
}

ざっくりこんな感じ． i * adaptive のところは仮決めしたが，より良い解もあるだろう．

ベンチマーク

軽くベンチマークを取ってみた． 実験対象は5つ．

  1. std::recursive_mutex (上述，glibc環境で実施したのでパディングなし)
  2. lock: シンプルなユーザランドのロック実装．スピンロック．バックオフなし．
  3. +AFS: alignas によるパディングを追加．
  4. +AS: カウンタの値を参考にバックオフの値を調整． カウンタがとった最大の値（再帰の深さ）をアンロック時にロックオブジェクトの上位32ビットに記録しておき，バックオフ時に加算あるいは乗算するといったアプローチ．ロックはミニマルな実装だと1ビットしか必要としないためこのような最適化のためのスペースがいくらでもある．
  5. +AFS,AS: AFSとASをそれぞれ実装．

ベンチマークは

David Dice, Virendra J. Marathe, and Nir Shavit. 2015. Lock Cohorting: A General Technique for Designing NUMA Locks. ACM Trans. Parallel Comput. 1, 2, Article 13 (January 2015), 42 pages. https://doi.org/10.1145/2686884

で提案されている LBench というものを実装した．ひたすら以下を繰り返すベンチマークだ．

  1. ロックを獲得する
  2. 何かしらの変数を二つインクリメントする
  3. アンロックする

以下に実験結果を示す． Y軸がOPS (lock/unlock の実行数)で，X軸が同時実行するスレッド数．すべてのスレッドが同じロックに対して処理を行う．（そんなアプリケーションある？っていう話は野暮）

再帰の深さを4にした場合

lock() を同じスレッドが最大で4回呼び出すパターンでの実験結果は以下． AS,AFSはそれぞれ有効に機能していて，特にAFS (パディング)の効果が大きい．やはりカウンタのインクリメント/デクリメントがキャッシュコヒーレンスプロトコルに与える影響は大きい．二つの最適化をともに有効にした場合 (+AFS,AS) は最大で lock より2.5倍程度のスループット向上が観測された． 1スレッドでも性能が大きく向上することについても気になるが，分析はまた後日する．

再帰の深さを1にした場合

再帰の深さを1にした場合，性能はほぼ横並びで変わらない結果になった．再帰ロック特有のアプローチを改善しているので，この結果は違和感がない．

同じ条件でAWS環境でも実験してみた．EC2のc8g.16xlargeで実行．再帰の深さを4にした場合． この場合は，+AFS,AS 以外は大きく性能が落ちていく結果となった．コア数が増えたこと（に伴いNUMA環境で実行されているであろうこと）やHWが仮想化されているであろうことから，偽共有のオーバヘッドやアトミック命令の高価さがより性能に影響を与えるようになった．したがって，パディングの重要性もバックオフの重要性も増した．ここでは最大で6倍程度の性能向上が見られた．

その後のダイジェスト

この実験結果が取れたあたりで大体満足したのだが，以下のようなことが気になった．

これについて一年くらい，主に風呂に入っているときに考えていたのだが，全く思いつかなかった． 総じて，この改善はなんとつまらない仕事だろうか？と思ってしまったので，ここに供養する．

せっかくなので書いたコードもここに置いておく． https://github.com/nikezono/retlock (opens in a new tab)

以上．

© nikezono.devRSS