isbits 型からなる型共用体の最適化

Julia の Array 型は “ビットの” 値を保持することも、ヒープアロケートの “ボックス化された” 値を保持することもできます。この違いは値がインラインに (配列用にアロケートされたメモリに直接) 保存されるか、それとも別の場所にアロケートされたオブジェクトに対するポインタが配列のメモリに保存されるかを定めます。性能的に言えば、インラインに保存された値に直接アクセスする方がポインタをたどって実際の値を取得するよりも優れています。一般に Julia の型が「isbits である」とは、その型の値が固定された確定のサイズを持ち、他のオブジェクトを指すフィールドが存在しないことを言います (参照: isbitstype)。

Julia は型共用体 (type union) もサポートします。これはまさに文字通り、いくつかの型を合併unionしたものを表します。アプリケーションが Julia の名前的な型システム (つまり明示的な部分型関係) と “食い違う”、本来であれば関係のない型の集まりに対してメソッドや機能を定義するとき、独自の型共用体を定義すると非常に便利なことがあります。しかしコンパイラからすれば、型共用体の扱いは難題です。ナイーブなアプローチ (Julia が 0.7 以前で実際に使っていたアプローチ) は、最初に触れた「ボックス化された」値と同じように、値に対して一つずつ「ボックス」を作って実際の値に対するポインタをそこに入れるというものです。しかし「ボックス」を使った間接参照を使わずにアクセスできる小さなプリミティブ isbits 型 (UInt8, Int32, Float64 など) が型共用体で頻繁に使われることを考えれば、このアプローチは無駄が大きいと言えます。バージョン 0.7 以降の Julia は主に二つの方法でこの点を最適化しています: 型に含まれる isbits 型共用体フィールドと、isbits 型共用体の配列に関する最適化です。

isbits 型共用体を持つ構造体

現在の Julia は、型 (mutable structstruct など) に含まれる isbits 型からなる型共用体フィールドをインラインに格納する最適化を行います。これは型共用体に対する「インラインサイズ」の計算と「型タグ」の付与で実現されます。インラインサイズとは型共用体に含まれる一番大きな型のサイズであり、例えば Union{UInt8, Int16} のインラインサイズは 2 バイトです。型タグとはインラインに格納された値が実際に表す値を示す値 (UInt8) です。

例えば Union{Nothing, UInt8, Int16} 型のフィールドに対する型タグ 0x02 は、このフィールドの値に対応する 16 ビットのメモリ領域に Int16 型の値が格納されていることを示します。また型タグ 0x01UInt8 型の値が 16 ビットの領域の先頭 8 ビットに保存されることを示します。最後に型タグが 0x00 なら、このフィールドは nothing となります (もちろんシングルトン型のインスタンスは一つしか存在しないので、nothing のサイズはゼロです)。型が持つ型共用体フィールドの型タグバイトは、そのフィールドの (インラインサイズの大きさを持つ) メモリ領域の後に直接格納されます。

isbits 型共用体の配列

現在の Julia は isbits 型からなる型共用体を配列にインラインに格納できるので、isbits 型共用体の配列ではボックスを使った間接参照が必要になりません。この最適化は一要素につき一バイトの「型タグ」からなる配列を実際のデータからなる配列とは別に格納することで実現されます。isbits 型共用体フィールドの場合と同様に、この型タグ配列は配列データに格納されている値が型共用体に含まれるどの型の値かを要素ごとに表します。

レイアウトに関して言うと、Julia の配列は実際のデータの前後に追加のバッファを持つことができるようになっており、ajl_array_t* 型の値とすればそれぞれ a->offseta->maxsize というフィールドで管理されます。型タグの配列は実際のデータを表す jl_array_t* とは別の jl_array_t* として扱われますが、a->offset, a->maxsize, a->len のフィールドを共有します。そのため isbits 型共用体の配列の型タグバイトにアクセスする式は a->data + (a->maxsize - a->offset) * a->elsize + a->offset * 1 となります。つまり起点の a->data から a->maxsize - a->offset 要素分だけ前に進み、そこからさらに a->offset 個の型タグの分だけ前に進んだ場所に (実際に利用される) 型タグが並びます。

日本語 Julia 書籍 (Amazon アソシエイト)
1 から始める Julia プログラミング
Julia プログラミングクックブック―言語仕様からデータ分析、機械学習、数値計算まで
スタンフォード ベクトル・行列からはじめる最適化数学