R には、バージョン 3.5（2018年リリース）で導入された ALTREP という仕組みがあります。ALTREP は alternative representation の略で、たぶん「通常とは異なるメモリ上の表現」みたいな意味です。要は「普通のベクトルのように扱えるけど中身は実は別物」みたいなものをつくれますよ、というものです。
これが、導入されてもう5年も経つんですが、いまだに公式ドキュメント（Writing R Extension、R Internals）には説明がありません。
R のソースコードがあるレポジトリの、ALTREP というブランチにひっそり入っている以下のドキュメントを読むか、既存のパッケージのコードを読むぐらいしか道がないです。
自分の頭を整理する意味も込めて、わかったことをこのブログ記事にまとめます。
ALTREP の種類
現在、ALTREP がサポートしているのは以下の種類のベクトルです。
- integer
- real
- logical
- character
- raw
- complex
- list (R 4.3.0 から)
ちなみに、ここまで便宜上「ベクトル」と書いてきましたが、実はALTREPの構想自体はさらに別の種類も含んでいます。 これはALTREP とは何か (R language) #R - Qiitaを読んで知りました。 以下のスライドは ALTREP の全体像を示したものですが、赤字で「ALTENV」が書かれています。 しかし、現時点で実装されているのは上に書かれた6つだけです。なので、ALTREP といえば実質ベクトル*1だと考えて問題ないです。
ALTREP に実装すべきメソッド
上の図からもわかるように、ALTREP の概念には階層があります。 ややこしいのですが、それぞれの階層ごとに実装すべきメソッドが決まっています。
ALTREPが持つメソッドLength: オブジェクトの長さを返すメソッドです。Duplicate: オブジェクトを複製するメソッドです。例えば、copy-on-modify が発生するとき（例：x[1] <- valueでxの値の一部を書き換えようとするとき）に呼ばれます。具体的にどういう実装になるかは後述。Coerce: オブジェクトを他の型に変換するメソッドです。例えば、as.character(x)のような型変換ではこれが呼ばれるようです。Inspect:.Internal(inspect)を実行したときにどのように表示するかのメソッドです。実装しなくてもいいですが、クラス名だけでも表示するようにしておいた方がデバッグに便利です。Serialized_state,Unerialize: オブジェクトをシリアライズするときに使われるメソッドです。
ALTVECが持つメソッドDataptr: データのポインタを返すメソッドです。ここで、「データ」というのは、Rの通常のベクトルと同じ型の配列（例：integer ならintの配列）である必要があります。具体的にどうするかは後述。Dataptr_or_null:Dataptrと同じくデータのポインタを返すメソッドですが、メモリアロケーションが発生しない場合のみポインタを返し、発生するなら null を返す、という違いがあります。Extract_subset:subset()するときのメソッドです。
- 個別の型（
ALTINTEGER, ...）が持つメソッドElt: 指定した位置の要素を返すメソッドです。Get_region: 指定した範囲の要素をコピーするメソッドです。Max,Min,Sum,No_NA,Is_Sorted: 型によってあったりなかったりするメソッドです。例えば、ALTRAWは、raw 型には NA がないのでNo_NAはありません。
いっぱいありますが、必須で実装しないといけないのは、
LengthEltDuplicateCoerce
あたりのようです。上2つは、ないと R のセッションがクラッシュします。下2つは、クラッシュはしませんが、duplicateやcoerceはよく発生するので、これが実装されていないとすぐエラーになって不便です。
ALTREP の使い方
ALTREP を使うには、以下の2つのステップが必要です。
- パッケージの（DLL の）ロード時に ALTREP クラスを登録し（
R_make_alt<TYPE>_class()） 、メソッドを設定する（R_set_alt<TYPE>_<METHOD>_method()） - その ALTREP クラスを使ってオブジェクトを作成する（
R_new_altrep()）
まず1.は、そもそもパッケージのロード時に実行するにはどうするかというと、R には initialization routine という仕組みがあり、R_init_<DLL名>() というシンボルがあるとそれが DLL のロード時に実行されます。
具体的にはこういうコードになります。
static void init_altrep_class(DllInfo *dll) { // ここで ALTREP のクラスを登録 } void R_init_savvyExamples(DllInfo *dll) { R_registerRoutines(dll, NULL, CallEntries, NULL, NULL); R_useDynamicSymbols(dll, FALSE); init_altrep_class(dll); }
init_altrep_class()の中身はこういうものです。R_make_altinteger_class() で integer の ALTREP クラスを作って、R_set_alt*_*_method()で必要なメソッド（ここで指定している myclass_* は別の場所で定義されている関数だとします）をそのクラスに紐づけていきます。
static R_altrep_class_t myclass; static void init_altrep_class(DllInfo *dll) { R_altrep_class_t cls = R_make_altinteger_class("クラス名", "パッケージ名", dll); // グローバル変数に格納して後で使えるようにしておく myclass = cls; R_set_altrep_Length_method(cls, myclass_Length); R_set_altvec_Dataptr_method(cls, myclass_Dataptr); R_set_altvec_Dataptr_or_null_method(cls, myclass_Dataptr_or_null); R_set_altinteger_Elt_method(cls, myclass_integer_Elt); R_set_altinteger_Get_region_method(cls, myclass_integer_Get_region); }
ここで、作成したクラスをグローバル変数に保持しているのはなぜかと言うと、実際にこの ALTREP クラスのオブジェクトを作成するときに必要なためです。
具体的にはこう R_new_altrep() を呼ぶことになります。
R_new_altrep(myclass, data1, data2);
ここで、 data1 と data2 は ALTREP の中身ですが、ここには何を入れればいいの？、という点を次に見ていきましょう。
ALTREP の内部実装
前掲のドキュメントに書かれていますが、ALTREP オブジェクトは内部的には pairlist として実装されています。
ALTREPobjects are allocated asCONSobjects and identified by having the altrep bit set in the header. The GC checks for the bit and scans the fields as for aCONScell. TheTAGfield holds class information; theCARandCDRholdSEXPvalues that are used for instance data; they are considered invisible outside of methods for the specific class.
用語がよく分からないと思うので図を引用すると、pairlist はこういう連結リスト（linked list）と呼ばれるデータ構造のものです。
CAR= 現在のオブジェクトのアドレスCDR= 次のオブジェクトのアドレスCONS=CARとCDRのペア
TAG はこの図にはないですが、それぞれの要素に貼られたラベルみたいなものだと思ってください。
この図では3つの CONS がつながっていますが、ALTREP オブジェクトは 1 つの CONS から成り立っています。
先ほど data1 に指定したものが CAR の位置に、data2 に指定したものが CDR の位置に入ります。
myclass はこの CONS についている TAG です。
では、実際に data1 と data2 には何を入れればいいのでしょうか？
これについては、上述のドキュメントはまったく何も指定していません。 おそらく、何を入れるのもすべて自由です。 とはいえ、よくあるパターンはあるようなので、それを次に眺めていきましょう。
data1
data1 には、メインのデータを入れることがほとんどです。ほとんどです、というか、入れないケースを私は見たことがありません。
最もよくあるのは別のデータ構造を external pointer （EXTPTRSEXP）化することですが、もっと単純なケースもあります。
例えば、base の compact_intseq（1:10 とかやるときにできる ALTREP class）は以下のように実装されています。
SEXP info = allocVector(REALSXP, 3); REAL0(info)[0] = (double) n; REAL0(info)[1] = (double) n1; REAL0(info)[2] = (double) inc; SEXP ans = R_new_altrep(R_compact_intseq_class, info, R_NilValue);
さて、ここで data2 には R_NilValue が入っていますね。
では data2 は使われていないのか？、というのを次に見ていきましょう。
data2
data2 は、データを通常のベクトル化（materialize と言ったりします）したものをキャッシュしておくのに使われることが多いです。
どういうことかというと、ALTREP は、理想としては不要なメモリアロケーションなしに使われてほしいですが、実際には、いったん値をすべて展開しないといけないケースが発生します。 例えば、以下のような R コードを考えてみましょう。
x <- 1:5 x[2] <- 99L
この結果、x は c(1L, 99L, 3L, 4L, 5L) になりますが、この結果を得るためには 99L を代入する前にまず 1:5 を c(1L, 2L, 3L, 4L, 5L) に展開する必要があります。
1:5 は、単調に1づつ増加する数列として ALTREP で効率的に表現できますが、ひとつでもそうではない値が入ると実際にひとつひとつの値を持つしかなくなるためです。
こうしたことは複数回発生しうるので、毎回展開して値をコピーするのではなく、いちど展開した値は data2 にキャッシュしておく、というのが一般的な戦略のようです。
例えば、 compact_intseq の場合はこういうコードになっていて、一度 DATAPTR() が呼び出されたらその後はキャッシュされたものが参照されるようになっています。
static void *compact_intseq_Dataptr(SEXP x, Rboolean writeable) { if (R_altrep_data2(x) == R_NilValue) { // ...snip... SEXP val = allocVector(INTSXP, n); int *data = INTEGER(val); // *data に値を展開 R_set_altrep_data2(x, val); UNPROTECT(1); } return DATAPTR(R_altrep_data2(x)); }
MARK_NOT_MUTABLE()
これに加えて、ALTREP クラスは MARK_NOT_MUTABLE() が適用されていることが多いです。
ここには、このようなコメントがつけられています。
MARK_NOT_MUTABLE(ans); /* force duplicate on modify */
こうしないといけない理由があるのかはちょっとピンと来ていないのですが、私の推測としては、
DATAPTR()でポインタを渡してしまうとその値が書き換えられてしまう- そうすると、ALTREP で保持しているデータとキャッシュされている値が乖離してしまう（これが即座に問題あるとは限らない）
ので、キャッシュされた値はそのまま置いておいて、必ずコピーされた値に変更が加わるようにしている、という感じなのかなという気がしています。
（余談）キャッシュは必ず必要？
GitHub を検索する感じ、ほぼすべてのパッケージはこのような戦略を取っているようです。 でも、キャッシュをまったく使わず、ALTREP の中身のデータを書き換える、という戦略もあり得るのではないでしょうか？
そのような戦略が可能になるためには、中身のデータが DATAPTR() で返せるような R と同じ型のデータ構造を持っている必要があります。
ここで、そもそも、
- R の通常のベクトルと同じ型のデータ構造を持っている
- しかし、通常のベクトルとしては扱いたくない
というケースがレアなので、こういう方針があまり見られないだけなののでは...？というのが私の推測です。 いま私が取り組んでいるのはこのレアケースなので、しばらく試行錯誤してみたいと思っています。
追記
完全に理解した。
色々試してて気付いたけど、DATAPTR() とか SET_*_ELT() で中身のデータにアクセスできるようにしたところで、それが実際に呼ばれるシナリオはほとんどない気がしてきました。
なぜかというと、C API からオブジェクトを操作する場合ならいざ知らず、ユーザーが扱う R コードは copy-on-modify で動作するためです。
例えば、以下は手元で実験してた失敗作の実行結果ですが、期待としては x[1L] <- 2L は内部の値を置き換えてほしかったのですが、どうやら x はその場でコピーされて通常のベクトルになってしまっています。
x <- altint_mutable() x #> [1] 1 2 3 .Internal(inspect(x)) #> @0x000001e99ff2ae30 13 INTSXP g0c0 [REF(5)] (MyAltIntMutable) x[1L] <- 2L .Internal(inspect(x)) #> @0x000001e9a210e968 13 INTSXP g0c2 [REF(1)] (len=3, tl=0) 2,2,3
まあ、独自のクラスを作って [<- のメソッドを実装したりすればいいんでしょうけど、そこまでがんばるなら別に ALTREP じゃなくてただの external pointer でいいのでは...、という気もします。
とういうことで、がんばって実装したところであまり便利な機能にはならないのでみんな MARK_NOT_MUTABLE() にしてるんだなあ、と思いました。
おしまい！
