Ruby1.9/オブジェクトのC表現を読む

RObject †

Ruby1.9ではObjectのC表現RObject構造体がかなり変わっています。参考までにRuby1.8のRObject構造体はこうです。

struct RObject {
   struct RBasic basic;
   struct st_table *iv_tbl;
};

シンプルです。次にRuby1.9のRObject構造体です。*1

#define ROBJECT_EMBED_LEN_MAX 3
struct RObject {
    struct RBasic basic;
    union {
	struct {
	    long len;
	    VALUE *ptr;
	} heap;
	VALUE ary[ROBJECT_EMBED_LEN_MAX];
    } as;
};
#define ROBJECT_EMBED FL_USER1
#define ROBJECT_LEN(o) \
    ((RBASIC(o)->flags & ROBJECT_EMBED) ? \
    ROBJECT_EMBED_LEN_MAX : \
     ROBJECT(o)->as.heap.len)
#define ROBJECT_PTR(o) \
    ((RBASIC(o)->flags & ROBJECT_EMBED) ? \
     ROBJECT(o)->as.ary : \
     ROBJECT(o)->as.heap.ptr)

すっげー複雑です:-)。読解しましょう。

rb_ivar_set(variable.c) †

インスタンス変数番号テーブル †

Ruby1.8のiv_tblはインスタンス変数のテーブルです。というわけでインスタンス変数を操作する関数を見てみましょう。

    switch (TYPE(obj)) {
      case T_OBJECT:
        klass = rb_obj_class(obj);
        if (!RCLASS_IV_INDEX_TBL(klass))
            RCLASS_IV_INDEX_TBL(klass) = st_init_numtable();

Ruby1.9ではRObject単独でインスタンス変数を管理するのではなくRClassと連動するようです。RClassの定義は以下の通り。*2

typedef struct {
    VALUE super;
    struct st_table *iv_tbl;
} rb_classext_t;

struct RClass {
    struct RBasic basic;
    rb_classext_t *ptr;
    struct st_table *m_tbl;
    struct st_table *iv_index_tbl;
};
#define RCLASS_IV_INDEX_TBL(c) (RCLASS(c)->iv_index_tbl)

先に進みましょう。

        ivar_extended = 0;
        if (!st_lookup(RCLASS_IV_INDEX_TBL(klass), id, &index)) {
            index = RCLASS_IV_INDEX_TBL(klass)->num_entries;
            st_add_direct(RCLASS_IV_INDEX_TBL(klass), id, index);
            ivar_extended = 1;
        }

変数名を示すidからindexを拾う、ないのならエントリの追加を行っています。つまり、RClass.iv_index_tblはこういう構造なようです。

埋め込みVALUE配列の初期化 †

        len = ROBJECT_LEN(obj);
        if (len <= index) {
            VALUE *ptr = ROBJECT_PTR(obj);
            if (index < ROBJECT_EMBED_LEN_MAX) {
                RBASIC(obj)->flags |= ROBJECT_EMBED;
                ptr = ROBJECT(obj)->as.ary;
                for (i = 0; i < ROBJECT_EMBED_LEN_MAX; i++) {
                    ptr[i] = Qundef;
                }
            }

初めてrb_ivar_setが呼ばれた場合、ROBJECT_EMBEDフラグが立っていない*3のでROBJECT_LENマクロはas.heap.lenを選択しますがこちらも0です。というわけでifの中に入ります。ROBJECT_PTRも同様にas.heap.ptrを返すのですが1個目のインスタンス変数はまだ埋め込みVALUE配列に収まるので調整が行われています。

ヒープVALUE配列の確保 †

埋め込みVALUE配列に収まらない場合、ヒープにVALUE配列が確保されています。

            else {
                VALUE *newptr;
                long newsize = (index+1) + (index+1)/4; /* (index+1)*1.25 */
                if (!ivar_extended &&
                    RCLASS_IV_INDEX_TBL(klass)->num_entries < newsize) {
                    newsize = RCLASS_IV_INDEX_TBL(klass)->num_entries;
                }

番号テーブルは全インスタンスで共有されているので、新しい変数が追加されるわけではない場合は現在の番号テーブルサイズがヒープVALUE配列のサイズとして利用されています。例えば、以下のようなケース。

• そのクラスの新しいオブジェクト
• index => 4
• klass->iv_index_tbl->num_entries => 5

ちなみに、klass->iv_index_tbl->num_entriesが8だとifの中は実行されません。必要にならない限りメモリを割り当てないという方針のようです*4。

                if (RBASIC(obj)->flags & ROBJECT_EMBED) {
                    newptr = ALLOC_N(VALUE, newsize);
                    MEMCPY(newptr, ptr, VALUE, len);
                    RBASIC(obj)->flags &= ~ROBJECT_EMBED;
                    ROBJECT(obj)->as.heap.ptr = newptr;
                }
                else {
                    REALLOC_N(ROBJECT(obj)->as.heap.ptr, VALUE, newsize);
                    newptr = ROBJECT(obj)->as.heap.ptr;
                }
                for (; len < newsize; len++)
                    newptr[len] = Qundef;
                ROBJECT(obj)->as.heap.len = newsize;
            }
        }

変数値の設定 †

というわけで値の設定です。

        ROBJECT_PTR(obj)[index] = val;

ところで何故埋め込めるのか †

何で埋め込んでいるのか、は何となくわかると思います。では何故埋め込めるのでしょうか？別の言い方をすると何故埋め込む空間なんてあるのでしょうか？そこら辺はRHGの「2.3.3 構造体の隙間」を見るとわかります。要約すると「オブジェクト構造体用のメモリは全部のオブジェクト構造体をunionしたRVALUE単位で割り当てるので、あるオブジェクト構造体だけでかいと無駄が発生する」ということになります。この無駄な空間をどうせだから埋め込み用に使おうという発想なようです。

まとめ †

Ruby1.8とRuby1.9でのインスタンス変数の扱いをまとめると以下のようになります。

• Ruby1.8
  • 変数の取得方法：id→VALUEのテーブルから取得
  • 各RObjectが変数テーブルを管理
  • 変数追加の際、常にメモリ確保
• Ruby1.9
  • 変数の取得方法：id→indexのテーブルの後、VALUE配列から取得
  • RClassが変数番号テーブルを管理
  • 変数追加の際、必要があったらメモリ確保

スピードはそんなに変わらない気がします。メモリ効率はRuby1.9の方がかなりいいと思います。不真面目なのでベンチマークとか取ったりはしませんが。*5

謝辞 †

「ところで何故埋め込めるのか」の部分は第1回 RHGの逆襲に参加することで知りました。このような会を開いてくださったYuguiさん、会場を用意してくださったよしおかさん、ささださん、その他多くの方に感謝します。

st_table †

Rubyのオブジェクトではありません*6がRuby実装で多く使われているst_table構造体もかなり変わっているので取り上げておきます。

まずRuby1.8のst_tableの宣言です。

st.h

struct st_table {
    struct st_hash_type *type;
    int num_bins;
    int num_entries;
    struct st_table_entry **bins;
};

Ruby1.9では以下のようになっています。

include/ruby/st.h

typedef st_data_t st_index_t;
#define ST_INDEX_BITS (sizeof(st_index_t) * CHAR_BIT)

struct st_table {
    const struct st_hash_type *type;
    st_index_t num_bins;
    unsigned int entries_packed : 1;
    st_index_t num_entries : ST_INDEX_BITS - 1;
    struct st_table_entry **bins;
    struct st_table_entry *head;
};

entries_packedとheadが増えています。なお、num_entriesが1ビット減っていますがもともとintで1ビットは符号に使われていたので格納可能な最大サイズは減っていません。って、2^31個も格納するだけのメモリはないと思いますが:-P

次にst_table_entry構造体（Ruby1.9）です。Ruby1.8に比べてforeとbackが増えています。

st.c

struct st_table_entry {
    unsigned int hash;
    st_data_t key;
    st_data_t record;
    st_table_entry *next;
    st_table_entry *fore, *back;
};

st_init_table_with_size †

Ruby実装ではメソッドテーブルなどいろいろなところでst_init_numtable関数が使われてます。st_init_table関数は、

st_init_numtable(void)
{
    return st_init_table(&type_numhash);
}

st_init_table(const struct st_hash_type *type)
{
    return st_init_table_with_size(type, 0);
}

とst_init_table_with_size関数に処理が委譲されています。

#define MAX_PACKED_NUMHASH 5

st_init_table_with_size(const struct st_hash_type *type, int size)
{
    st_table *tbl;

    size = new_size(size);	/* round up to prime number */

    tbl = alloc(st_table);
    tbl->type = type;
    tbl->num_entries = 0;
    tbl->entries_packed = type == &type_numhash && size/2 <= MAX_PACKED_NUMHASH;
    tbl->num_bins = size;
    tbl->bins = (st_table_entry **)Calloc(size, sizeof(st_table_entry*));
    tbl->head = 0;

    return tbl;
}

というわけでハッシュのタイプがnumhashでsizeがMAX_PACKED_NUMHASH以下だったらentries_packedが1になっています。なお、sizeはnew_size関数により指定sizeより大きくて一番近い素数に書き換えられています。0の場合、11なので先ほどの条件が成り立ちます。

st_add_direct †

それではentries_packedがどう使われているか見てみましょう。RHGだとst_lookup関数の方が先ですがst_lookup関数から見ると理解に苦しむと思うのでst_add_direct関数の方を見ます。

st_add_direct(st_table *table, st_data_t key, st_data_t value)
{
    if (table->entries_packed) {
        int i;
        if ((table->num_entries+1) * 2 <= table->num_bins && table->num_entries+1 <= MAX_PACKED_NUMHASH) {
            i = table->num_entries++;
            table->bins[i*2] = (struct st_table_entry*)key;
            table->bins[i*2+1] = (struct st_table_entry*)value;
            return;
        }
        else {
            unpack_entries(table);
        }
    }
    従来のst_add_direct()
}

何をしているかと言うとbinsの偶数番目にキー、binsの奇数番目に値が入っています。つまり、ハッシュじゃないわけです。従来のst_add_direct関数だと1エントリごとにメモリ確保されているので数が少ないうちはそんなことするより配列に順次つっこんでいった方が格納も検索も速いということでしょう。

st_table_entry.{fore,back} †

次にst_table_entry構造体に増えているforeとbackについて調べてみましょう。従来型st_add_direct関数で呼ばれるADD_DIRECTマクロの関係部分です。

if ((head = table->head) != 0) {\
    entry->fore = head;\
    (entry->back = head->back)->fore = entry;\
    head->back = entry;\
}\
else {\
    table->head = entry->fore = entry->back = entry;\
}\

というわけでエントリをつないでいます。どんな感じにつながっていくかと言うと以下のようになります。

1エントリ目

+---- head ----+
|     ^  ^     |
| back|  |fore |
+-----+  +-----+

2エントリ目

+---- head -- fore --> ent2 ----+
|      ^ ^             |  ^     |
|  fore| |back         |  |back |
|      | +-------------+  |     |
|      +------------------------+
+-------------------------+

3エントリ目

+---- head -- fore --> ent2 -- fore --> ent3 ----+
|      ^ ^             |  ^             |  ^     |
|  fore| |back         |  |back         |  |back |
|      | +-------------+  +-------------+  |     |
|      +-----------------------------------------+
+------------------------------------------+

こうして作られたリストがどこで使われているかと言うといろいろなところで使われているのですが目に見えるところで言うとst_foreach関数で使われています*7。st_foreach関数はHashのeachで使われています。よって例えば、

hash = {}
hash['abc'] = 123
hash['ABC'] = 456
hash['zyx'] = 789
hash.each do |k,v|
  p k, v
end                                                                             

というコードがあった場合、Ruby1.8とRuby1.9で結果が異なります。

Ruby1.8

"ABC"
456
"abc"
123
"zyx"
789                                                                             

Ruby1.9

"abc"
123
"ABC"
456
"zyx"
789

ruby-listで「RubyってHashに格納した順番って保持されないんですか？」と聞かれていた方がいらっしゃったのですがそれへの対応のようです。

まとめ †

Ruby1.9になったからと言って変わってなさそうなst_tableですが実は変わっていたので見てみました。変更点は以下の2つです。

• 数値テーブルの場合、小さいサイズならハッシュではなくただの配列になっている
• ハッシュエントリを格納順につないだ双方向リスト（Hash#eachとかで利用されている）