MRI Array実装メモ(2.2.0-dev現在)

MRIのArray実装を追いかけたのでメモ。

データ構造

include/ruby/ruby.h

struct RBasic {
    VALUE flags;
    const VALUE klass;
};

struct RArray {
    struct RBasic basic;
    union {
         struct {
            long len;
            union {
                long capa;
                VALUE shared;
            } aux;
            const VALUE *ptr;
        } heap;
        const VALUE ary[RARRAY_EMBED_LEN_MAX];
    } as;
};

種類

単にArrayといってもMRIの内部的には3種類ある。

Embed Array

as.aryの部分。

配列の長さがRARRAY_EMBED_LEN_MAX(現状3)以下であればRArray構造体の中にデータを入れてしまう。

こうすることで配列用のmallocとfreeを減らせるので少メモリ・高速化を図れる。

この配列の長さ(0〜3)はbasic.flagsの中に2bit分の領域を確保してあり、マスクを掛ければ長さが取れるようになっている。

include/ruby/ruby.h

#define RARRAY_LEN(a) \
    ((RBASIC(a)->flags & RARRAY_EMBED_FLAG) ? \
     (long)((RBASIC(a)->flags >> RARRAY_EMBED_LEN_SHIFT) & \
      (RARRAY_EMBED_LEN_MASK >> RARRAY_EMBED_LEN_SHIFT)) : \
     RARRAY(a)->as.heap.len)

Normal Array

as.heapの部分。

ptr: 配列の長さが4以上だとRArrayに入りきらない。なので別領域にメモリを確保してそのポインタを覚えておく。

len: Rubyオブジェクトとしての配列の長さ。

aux.capa: 配列のメモリを確保している分の長さ。len以下にはならない。メモリ確保(malloc)は一般的に重いので、大きめに確保しておいてRubyオブジェクトの長さはlenで表す。例えばArray#popはaux.capaはそのままでlenを1つだけ減らしているだけで表現できる。これによりmallocとfreeの回数を減らしている。

Shared Array

as.heap.aux.sharedの部分

CopyOnWriteを実現するための機能。表には出ないけどかなりの部分で使われている重要な概念。

basic.flagsにはこのオブジェクトがsharedかどうかのフラグを1bit分持っている。

array.c

# define ARY_SHARED_P(ary) \
    (assert(!FL_TEST((ary), ELTS_SHARED) || !FL_TEST((ary), RARRAY_EMBED_FLAG)), \
     FL_TEST((ary),ELTS_SHARED)!=0)

#define ARY_SHARED_ROOT_P(ary) (FL_TEST((ary), RARRAY_SHARED_ROOT_FLAG))

Normal Arrayをsharedすると、freezeして間接的に参照するだけのARY_SHARED_ROOTを作る。自身はこのROOT参照するShared Arrayになる。

どのRubyオブジェクトを参照しているかをas.heap.aux.sharedで覚えておく。
また、SharedArrayのas.heap.ptrはSharedRootArrayのas.heap.ptrと同じものを見ている。

ROOTはいくつのArrayをsharedしているかをas.heap.aux.capaに書き込む。これによりShared Arrayのcapaはそれぞれで持っているので開いている領域を再利用している。

Arrayの破壊的なメソッドではrb_ary_modifyでSharedArrayだったらshared状態を解除するようになっている。

これにより、ただコピーしただけでは参照先の配列分malloc&freeしなくて良くなる。配列の長さが長いほど効果的。

Array#shiftではSharedしてから自身のas.heap.ptrを右にずらすという荒業(？)で高速化している(memmoveだと処理速度がサイズに比例する)。SharedしたROOTにはメモリを確保した箇所を覚えているのでfreeできるようになっている。

Sharedを解除する場合はShared数が1個だけならmemmoveして領域を使いまわす。新たに領域を確保してコピーしてfreeとするよりエコロジーになる。それ以上のShared数ならしょうがないので単にメモリ領域を確保してコピーする。

わからないこと

• Array#shiftでSharedじゃないオブジェクトかつ引数が指定されている場合単にメモリを全部ずらしている。 引数なしの時はary_make_sharedするのに引数ありだとしないときがあるのは何故だろう？
  • 引数が0,1,2,3の時だけ遅いようなのでバッチを書いた。 => https://github.com/ruby/ruby/pull/537
• ARY_DEFAULT_SIZEは何故16？
• Shared数をcapaに書くようにしているのは何故だろう？(unionでshared_lenという名前にするとか)うーん。sharedとかぶってよりややこしくなるのかな？

参考