jemallocを読んでみる(その3)

時間がない人はここだけ読んでください、あとはどうでもいいです。

今日はロックを掛けるところを見てみます。jemallocはロックを掛けながらアリーナの競合状態をプロファイリングするという巧妙なことをしています。常識なのかもしれないですが、私は感動しました。

読んでくださってありがとうございます。

前回までのあらすじ

jemallocはFreeBSD 7.0やFireFox3.0で劇的な性能向上を実現しているメモリー管理ライブラリです。Rubyにも組み込もうとCygwinでコンパイルしたらコンパイルに失敗したので、ついかっとなってjemallocを読み始めました。
第1回で最初のコメントを機械翻訳以下のクオリティで翻訳しました。ここの情報は全体を理解するに当たってキーになる予感なので、英語の方を読んでおくと吉です。
第2回でmallocを実行した場合に何をしているのか適当にはしょりながら見ていきました。第3回はその続きで、アリーナをアクセスするためのロックを得る部分です。

今日の本題を詳しく

ではロックを掛けるところを見てみましょう

static inline unsigned
malloc_spin_lock(pthread_mutex_t *lock)
{
	unsigned ret = 0;

	if (__isthreaded) {
		if (_pthread_mutex_trylock(lock) != 0) {
			unsigned i;
			volatile unsigned j;

			/* Exponentially back off. */
			for (i = 1; i <= SPIN_LIMIT_2POW; i++) {
				for (j = 0; j < (1U << i); j++)
					ret++;

				CPU_SPINWAIT;
				if (_pthread_mutex_trylock(lock) == 0)
					return (ret);
			}

			/*
			 * Spinning failed.  Block until the lock becomes
			 * available, in order to avoid indefinite priority
			 * inversion.
			 */
			_pthread_mutex_lock(lock);
			assert((ret << BLOCK_COST_2POW) != 0);
			return (ret << BLOCK_COST_2POW);
		}
	}

	return (ret);
}

ここで、ptheradのAPIを使ってロックを得ています。しかし、この関数はいきなりptheradにロックちょうだい、無ければ寝るから起してねってやるのではなく、_pthread_mutex_trylockとスピンロックを使って何とかオーバッド無しにロックをとるように努力します。待ち時間を倍倍に増やしながら、11回リトライを繰り返します。11回リトライしてダメなら、_pthread_mutex_lockを使って結局ロックが得られまで寝ます。どのくらい待ったか数えておいて(変数ret)、それを返します。

これをどう使うかというと、こんな感じです

static inline void
arena_lock_balance(arena_t *arena)
{
	unsigned contention;

	contention = malloc_spin_lock(&arena->lock);
	if (narenas > 1) {
		/*
		 * Calculate the exponentially averaged contention for this
		 * arena.  Due to integer math always rounding down, this value
		 * decays somewhat faster then normal.
		 */
                /****   1   ****/
		arena->contention = (((uint64_t)arena->contention
		    * (uint64_t)((1U << BALANCE_ALPHA_INV_2POW)-1))
		    + (uint64_t)contention) >> BALANCE_ALPHA_INV_2POW;
		if (arena->contention >= opt_balance_threshold)
			arena_lock_balance_hard(arena);
	}
}

malloc_spin_lockの戻り値をcontention(競合)という名の変数に入れています。

contentionが大きい → ロックを得るのにたくさん待たされた → 競合状態が激しい

となります。
その後/**** 1 ****/で、なにやら面倒な計算をしています。これはcontentionの値は激しく変動するので過去の結果を加えて滑らかにする処理だと思います。このような処理はスケジューラ何かでもよく見ます。その後、滑らかにしたcontentionの値をアリーナのcontentionメンバーに入れます。
もし、contentionが閾値より大きくなると、アリーナを増やして何とか競合状態を緩和しようとがんばります。これが、arena_lockbalance_hardです。

つづく