Rubyの配列のsharedフラグ (その1)

この記事では執筆時点最新のCRuby trunk リビジョン45349のソースを参照して書いています。

CRubyの配列の実装にはsharedフラグというものがあります。これは複数の異なる配列オブジェクトが実体メモリを共有するためのものです。

特別にフラグの立っていない配列オブジェクト

この記事ではVALUEやstruct RBasicなどの構造については既知とします。知らない方は以下を読みましょう。

RHG 第2章オブジェクト

まず、これがRArray構造体です。

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;
};

#define RARRAY(obj)  ((struct RArray*)(obj))

特別になんのフラグも立っていない通常の配列の場合を最初に確認しておきます。これをこの記事では通常モードとでも呼びましょう。

通常モードの配列では、RARRAY(ary)->as.heap.ptrに実体メモリのポインタが格納され、この所有権を持ちます。所有権とは、このポインタをfreeする責任は自分が持ちますよ、ということです。
そしてRARRAY(ary)->as.heap.lenに配列の長さが、RARRAY(ary)->as.heap.aux.capaに確保したメモリの大きさが格納されます。とっても普通ですね。

なお、embedフラグの立った配列オブジェクトというものがあって、これは要素数が3以下の配列はRArray構造体の中に実体を格納してしまうというものです。しかしこれはsharedフラグを理解する上で本質的ではないので無視します。

sharedフラグの基礎

"sharedフラグのついた配列オブジェクト"のことを単にsharedオブジェクトと呼ぶことにします。
sharedフラグには次の性質があります。

sharedオブジェクトは実体ptrの所有権をもたない
sharedオブジェクトの"sharedメンバ" にはfrozenな配列オブジェクト(への参照)が格納される。

ここで配列aryのsharedメンバとはRARRAY(ary)->as.heap.aux.sharedのことをいうことにします。

実際の実装はちょっと複雑なので、少し簡略化したものをここでは紹介します。

まずfrozenな配列オブジェクトをdupすると、このオブジェクトを指したsharedオブジェクトが作られメモリが共有されます。
たとえばfrozenな配列aをdupしてbを得たとしたとしたら以下のようになります。

さて、aとbは実体メモリを共有しているわけですが、このままではbを書き換えた時にaにもそれが反映されてしまいます。
そこでsharedオブジェクトを書き換えるときには、実体メモリをコピーしそれへの所有権を持ち通常モードの配列に変化させます。これを行うためRubyでは配列への破壊的なメソッドでは必ずrb_ary_modify()を呼んでいます。

なお、aはfrozenなので、aが書き換わってbにも反映される、という心配はありません。

sharedオブジェクトは実体メモリの所有権を持っていませんが、だからといってオブジェクトは生きているのにGCによって実体メモリが解放されてしまうということはありません。なぜなら、sharedメンバにメモリの所有権を持っているオブジェクトへの参照を持っているからです。

ところでfrozenオブジェクトaを指すsharedオブジェクトbがすでにあって、さらにbをdupして新しい配列cを得るときはどうすればいいでしょう。これは単にaを指すsharedオブジェクトつまりbと同様のものを作ればよいだけですね。

以上の方法でfrozenな配列のdupが定数時間で済みます。
ここまで簡略化したものを紹介しましたが、実はfrozenではない配列をdupしたときにも実体メモリのコピーが起きないように実装されているのです。その仕組みを「その2」の記事で書こうかと思います。

追記(2015/11/29)

この記事を書くために次のような拡張ライブラリを作って動作を確かめました。

dump.c

#include <ruby.h>

#define RARRAY_SHARED_ROOT_FLAG FL_USER5

VALUE dump(VALUE self, VALUE ary){
	Check_Type(ary, T_ARRAY);
	printf("<%" PRIxVALUE, ary);
	if (FL_TEST(ary, RARRAY_EMBED_FLAG)) {
		printf(" embed");
	} else if (FL_TEST(ary,ELTS_SHARED)) {
		printf(" shared ptr=%p, shared=%" PRIxVALUE, RARRAY(ary)->as.heap.ptr, RARRAY(ary)->as.heap.aux.shared);
	} else if (FL_TEST(ary, RARRAY_SHARED_ROOT_FLAG)) {
		printf(" shared_root ptr=%p num=%ld", RARRAY(ary)->as.heap.ptr, RARRAY(ary)->as.heap.aux.capa);
	} else {
		printf(" normal ptr=%p", RARRAY(ary)->as.heap.ptr);
	}
	if (OBJ_FROZEN(ary)) {
		printf(" frozen");
	}
	puts(">");
	return Qnil;
}

VALUE shared(VALUE ary) {
	if (FL_TEST((ary),ELTS_SHARED)!=0) {
		return RARRAY(ary)->as.heap.aux.shared;
	} else {
		return Qnil;
	}
}

void Init_dump(void){
	rb_define_global_function("dump", dump, 1);
	rb_define_method(rb_cArray, "shared", shared, 0);
}

この拡張ライブラリを使うと

dump(ary)

でArrayオブジェクトaryの情報を出力することができます。

ary.shared

でsharedメンバを参照することができます。