It is KJ!

About Programming, Mathematics and Security

『Rubyのしくみ -Ruby Under a Microscope』の読書メモ<第6~7章>

Rubyのしくみ -Ruby Under a Microscope-

Rubyのしくみ -Ruby Under a Microscope-

第1~5章編はこちら:『Rubyのしくみ -Ruby Under a Microscope』の読書メモ<第1~5章> - It is KJ!

第6章 メソッド探索と定数探索

Rubyの内部では、モジュールとはクラスである

Module

  • Rubyの内部的には、モジュールはクラスを生成する
  • include Moduleは、クラスのスーパークラスの連結リストに、そのモジュールをコピーする形で挿入する
    • この仕組みによって、枝分かれしない一本の継承リストによるシンプルさを保ちつつ、Moduleを利用した多重継承の恩恵を受けることができる
    • また、このスーパークラスチェーンの順番が大事で、スーパークラスで定義されたメソッドはModuleの定義でオーバーライドされうることがわかる

メソッド探索アルゴリズム

  • 単純明朗な以下の探索手順を繰り返す -現在のクラスをレシーバーに設定し、メソッドテーブル内を探索する
    • メソッドが見つからない場合、現在のクラスのスーパークラスを次の探索対象クラスに設定する

メソッドキャッシュ

  • グローバルメソッドキャッシュ
    • レシーバと実装側のクラスの対応を記録する
  • インラインメソッドキャッシュ
    • Rubyが実行するコンパイルされたYARV命令列の側に情報を記録する
  • Rubyは動的言語なので、メソッド探索の結果が変更されてしまう可能性があるため、場合によってはグローバル・インライン両方のメソッドキャッシュをクリアする必要がある

モジュールを追加する仕組み

  • モジュールをインクルードした時、Rubyはメソッドテーブルではなく、RClass構造体をコピーする
    • つまり、インクルードされたクラスは元のモジュールとメソッドテーブルをコピーする
      • インクルードした後でモジュールにメソッドを追加しても、ポインタで共有されているので変更は反映される
    • インクルードした後でモジュールに新しくモジュールをインクルードしても、コピーされないので反映はされない
  • Module#prependを利用した場合、Rubyは以下の仕組みを利用して、モジュールをクラスの「先頭に追加(prepend)」する仕組みを実現している
    • 対象クラスのコピーを作成して、prenpendされたモジュールのスーパークラスとして設定する
    • rb_classext_struct構造体のoriginポインタを使用し、またすべてのメソッドを元のクラスからorigin classへと移す
  • class.crb_include_class_new関数によって、モジュールをインクルードしたときのコピー処理が実装されている

レキシカルスコープ

  • クラス階層でsuperclassをたどる以外に、プログラムの構文的な構造上の区分を示す
    • nd_nextポインタ: 親のレキシカルスコープ(つまり、コードの外側を取り囲む)へのポインタ
    • nd_clssポインタ: 現在のスコープに対応するRubyのクラスかモジュールを示す
  • つまり、Rubyはnd_nextポインタを用いてレキシカルスコープを辿ることで、親の名前空間の定数を見つける

定数探索

  • Rubyはレキシカルスコープチェーン内を先に探索し、次にスーパークラスチェーン内を探索する
    • それでも探索に失敗した場合、const_missingが呼ばれる

第7章 ハッシュテーブル: Ruby内部の働き者

Rubyは内部データの多くをハッシュテーブルに格納する

ハッシュテーブル

  • 主要なstructは、RHash構造体, st_table構造体, st_table_entry構造体
  • 実装はst.cinclude/ruby/st.h, RHash構造体は他のオブジェクトの構造体同様include/ruby/ruby.h

ハッシュの衝突とrehash

  • ハッシュテーブルの各バケットのエントリ数が増えると、エントリー探索時Rubyはkeyのeql?メソッドを呼び出すことから、オブジェクトなどの複雑なデータ型をキーにしていた場合に探索に時間がかかる
  • Rubyは密度(バケットあたりのエントリ数の平均値)を計算し、rehashのタイミングを判断する
    • 実装はst.cの中のrehash関数(st_table_entry構造体を辿って、どのバケットに格納されるかを再計算する)
    • Ruby 2.4では、st_rehash_linearst_rehash_indexedの2種類の実装が存在する

RubyのHash実装

  • Ruby 1.9以降では、2008年に発明された“MurmurHash”と呼ばれるハッシュ関数を利用する
  • Object#hashメソッドは、ターゲットオブジェクトのCのポインタ値(RValue構造体の実際のメモリアドレス)を取得し、Cのhash関数に渡し、値のビットにしたがって再現可能な方法でばらけた整数値を生成する
    • なお、この際ターゲットが文字列や配列の場合、要素全ての累積ハッシュ値を計算する

Hash最適化

  • Ruby 2.0からは、小さなハッシュにはst_table_entryを使用せず、配列を利用する
    • 「packされたハッシュ」と呼ばれる