今日は高速化のために Hash の実装や ruby 内部で多用している st_table のテーブルサイズを素数から 2 の累乗にする変更と、先日のメソッド探索の修正で SEGV する可能性があった不具合を再修正しています。
normal: r45384 2014-03-23 08:34:21 +0900
st.c で st_table のハッシュテーブルのサイズに素数を利用していたのを、2の累乗のサイズを使うように変更しています。ハッシュ関数の結果からバケットを決定するのに素数での mod を利用することでより分散しやすくするために(というふうにわたしは理解していましたが)していたのですが、この計算に時間がかかるので 2 の累乗のサイズならビットマスクだけで処理できて高速になるため、高速化を目指して変更したということだそうです。 素数での mod もそもそもハッシュ関数が優秀で充分に分散した結果が得られるなら不要ということだそうで、まあそれはそうですねぇ。 hash の実装はクラスによって異なり再定義も可能なので、どこかで劣化するという可能性もあるのでとりあえず ruby 本体についてはベンチマークを追加してこの効果と衝突が頻繁に起きないかを確認するようにしています。 [ruby-core:59836] [Feature #9425]
まあ外部のライブラリで hash を独自に定義していて、それがあまり充分に分散されていなくて下位ビット部分がほとんど同じだったけど素数による mod で救われてた、というのがあったりする可能性はありますが、まあ気がつくほど劣化してたら hash を直せというのはありかもしれませんね。あとこれにより Hash オブジェクトに限らず ruby 内部で使う場合も st_table の初期テーブルサイズが 11 から 16 に増えているのも若干気になるところです。と思いましたが小さいテーブルの場合は st_table も構造体自体に要素を pack してヒープを使わないモードになるのであんまり影響ないかもしれないですね。
svn: r45385 2014-03-23 08:34:26 +0900
version.h の日付更新。
nobu: r45386 2014-03-23 10:10:12 +0900
r45384 に変更で rb_any_hash() で hash 関数の実装を変更しているところで VALUE の値の構造に依存して 3 という数値を直接書いていたのを #include "id.h" して ID_SCOPE_SHIFT という定数を利用するようにしています。 [ruby-core:59836] [Feature #9425]
nobu: r45387 2014-03-23 11:03:51 +0900
r45367 の include と継承と alias と super の組み合わせてメソッド探索が無限ループする現象の修正で Module での alias と include をしてメソッド呼び出し時に SEGV するケースがあったので再修正しています。 rb_method_entry の klass が 0 になるケースがあるのに対応しています。 [ruby-core:61636] [Bug #9663]
nobu: r45388 2014-03-23 11:03:53 +0900
r45387 の ChangeLog エントリの時刻のみ変更。はて? と思ったら次で r45387 の再修正があったので何か操作ミスがあったのでしょう。 [ruby-core:61636] [Bug #9663]
nobu: r45389 2014-03-23 11:05:52 +0900
r45387 の再修正。条件になぜか ! がまぎれこんで me->klass が 0 の時に利用する分岐に入り込んでしまっていたので ! を削ってます。チケットに投稿されたパッチには ! はなかったので、手作業でパッチを当てる際に間違ってしまったのでしょう。っていうかテストすればすぐ気がついたのでは…。 [ruby-core:61635] [Bug #9663]
自分も短めだったり生煮えのパッチ(このへんが原因じゃないかと思うんだけどどう? みたいな時)はコメントに直接書きがちだけど当てる作業のことを考えると添付するか github でブランチ作るとかしたほうがいいんでしょうねぇ。
nobu: r45390 2014-03-23 23:47:04 +0900
r45384 の hash 関数の変更に追随して .gdbinit の rb_numtable_entry コマンドで参照するバケットのインデックスを取得する際に st_numhash() を利用するように変更しています。
