アトミック演算の性能

GCC拡張のロックフリーなアトミック演算機能と、自分でロックしてアトミックに演算するのとではどれくらい違うかを実験してみた。

TCやKCでのユースケース

TCやKCのデータベースオブジェクトでは、ファイルサイズやレコード数をメタデータとして保持している。それらの更新（主に加算）をする操作は頻繁に行われるので、なるべく処理効率を上げたい。

いわずもがな、変数の更新を行うという操作をミクロ視点で見ると、既存の値をメモリから読み出して、その値に対して演算を行って、それをメモリに書き戻す、という3ステップからなる。普通に「+=」演算子などを使うとそれら一連の操作群がアトミックに行われる保証はないので、mutexなどを使ったクリティカルセクションで一連の操作群を包むのが一般的である。

しかし、変数の値を加算するという操作ごときにわざわざロックのオーバーヘッドが伴うのは嫌な感じである。ところで、上述の操作をアトミックに行う機能は大抵のCPUに備わっている（でないとmutexが実装できないはず）わけで、それを呼び出す非標準の方法を使えばもっと効率的にできそうだ。GCCの場合には__sync_fetch_and_add などの組み込み関数として提供されているらしい。ただし、GCC 4.2以上かつi686以上でないと使えないらしいので、configureで判定して該当の場合だけ使う感じにしよう。該当でない場合には普通にロックしてやる。

API

組み込みのアトミック命令が使えないことを前提としてAPIを組み立てる必要があるので、ロックする場合のロックオブジェクトのメソッドとして実装する。例えばMutexの場合には以下のような実装になる。

int64_t Mutex::atomic_add(int64_t* lvp, int64_t rv) {
#if defined(_SYS_GCCATOMIC_)
  return __sync_add_and_fetch(lvp, rv);
#else
  lock();
  int64_t sum = *lvp += rv;
  unlock();
  return sum;
#endif
}

Mutex版、SpinLock版、RWLock版を用意しておけばほとんどのユースケースは全てカバーできるだろう。マクロ_SYS_GCCATOMIC_はconfigureに設定させる。俺や勤め先や友人のほとんどはGCCでi686という条件をパスしているので、実際には単に__sync_add_and_fetchが呼ばれるだけなので、ロックの種類は何でもいいのだが。

性能テスト

さて、GCC組み込みのロックフリーな加算と、各種のロックをして加算するのはどのくらい性能が違うのか。計1000万回の加算にかかる時間をスレッド数を変えながら計測してみた。

予想通り、ロックフリーが全ての計測で最善であることが確かめられた。とはいえ、クリティカルセクションの並列度が1、すなわちあまり衝突が起こらないようなケースでは、ロックフリーとSpinLockの性能はそんなに変わらないということもわかる。同じ変数を狂ったように書き換えまくるようなユースケースでもなければこの部分の並列度は低いわけだから、SpinLockを使うというのも現実的な解だと思う。ただし、何かの手違いで並列度が上がってしまった場合にはSpinLockは悲惨なことになるので、保守的に考える場合にはMutexを使っておくべきだろう。

まとめ

ロックフリーなアトミック演算が可能であれば使うべきだ。Mutexよりは3倍くらい効率的だし、SpinLockのように並列度が上がると遅くなるようなことはない。ただ、ここがボトルネックになることはまずないから、これに血眼になって移植性を下げるようなことがあってはならない。やはりconfigureで判定して使えたらラッキーというくらいの位置づけでいいんじゃないだろうか。

ちなみになんでこれを急に調べたかというと、tmaesaka氏が彼のBlitzDBの実装をDrizzleコミュニティの人に見せたところアトミック演算を使えと言われたというのを横から見ていて、KCでも使えそうだなと思ったからだ。こんな他愛もないやりとりからもDrizzleコミュニティの並列性への情熱が伝わってくるわけで、Drizzleへの期待がさらに膨らむ今日この頃である。