読者です 読者をやめる 読者になる 読者になる

methaneのブログ

このブログに乗せているサンプルコードはすべてNYSLです。

CPython の Core Developer になりました

Python 3.6 に取り込まれた dict の新実装などでコアコミッターに興味を持ってもらい、 Core Developer (要するにコミッター) に推薦しようか?という提案をもらいました。

最初はコミッターとか面倒そうだし、コミットメッセージとかNEWSエントリー(通常パッチをコミットするときにコミッターが書く)とかを英語で書くのも英語が得意な人がやったほうがいいだろうし、とりあえず github に移行するまでは様子見しておこうと思ってたのですが、 dict 関係のパッチがいくつもレビュー待ちでなかなかコミットされないのを見て「やっぱりアクティブなコミッターが全然足りてない」と考え直し、志願することに。

で、先月末にコミット権をもらった(というか push できる権限を持った hg アカウントに ssh 鍵を登録してもらった)のですが、新米コミッターは簡単なパッチでも他のコアコミッターのLGTMなしにコミットしちゃダメだよと釘をさされたので、結局レビュー待ち行列状態は変わらず。1週間以上経って今日始めてコミットを push できました。 (コミット)

コミットしたのは、会社のBlog記事 DSAS開発者の部屋:Python の dict の実装詳解 で言及していた次の問題です。

しかし、この方法ではハッシュテーブル内の密度の偏りの影響を避けられるものの、ハッシュ値の下位ビットが衝突する key は同じ順番に巡回するので線形探索になってしまい効率が悪いという欠点があります。そこで、先程の関数を改造して、次のようにしています。

    for (perturb = hash; ; perturb >>= PERTURB_SHIFT) {  
        i = i * 5 + perturb + 1;

これで、最初のうちはハッシュ値の上位ビットを使って次の位置を決定していき、ハッシュ値を右シフト仕切ったら先ほどのアルゴリズムで確実に巡回する、というハイブリッド型の巡回アルゴリズムになります。 (ちなみに、このforループには最初の衝突のあとにくるので、 perturb の初期値が hash のままだと、hash 値の下位ビットが衝突する key と1つ目だけでなく2つ目も衝突してしまいますね…)

例えば要素数が5以下の場合、ハッシュテーブルの大きさは8なので、5要素中3要素のhashの下位3bitが同じだった場合に、2段階のコンフリクトが発生していました。これが最初の衝突後すぐにハッシュのより上位のビットが使われるようになって、その上位bitが異なれば衝突は最初の1回だけで済むようになった形です。とてもレアケースだと思うので実際のアプリで計測誤差以上の速度差は出ないでしょう。

これからも他人のパッチを自分のLGTMだけでコミットできる真のコミッタになることを目指して気長に徳を積んでいきます。