Big bag of pagesで型情報を節約する

言語実装アドベントカレンダー20174日目の記事です。

言語実装、特に動的型付け言語の実装においては、実行時に値を扱う際、値本体の他に型などのメタ情報を持たせる必要がある。 静的に解析が可能な言語と違って実行時にしか解析ができないからだ。 しかし、言語の特性を考慮して実装をしないと非効率的なメモリの使い方をしてしまう場合がある。 その対応策として Big bag of pages というメモリの扱い方があるので、どういう部分で有用なのか紹介する。

例えば、C言語で純粋に実装をすると、ゲスト言語*1上で整数を解釈する場合

// guest language input: 35

typedef struct lang_value {
        union {
                int i;
                double d;
                struct fat_struct object;
        } val;
        enum lang_type type;
} lang_value;

lang_value* p = malloc(sizeof(lang_value));
p->val.i = 35;
p->type = Int;

と記述するのが最も簡易的であるし、様々なアーキテクチャ間での互換性を保つことができる。 しかし、この方法で例えば1 + 2 + 3 + ... といった整数値の確保を大量に行うのであれば、 unionによってintのサイズより大きく確保されている構造体を扱う必要があるし、 メタ情報も毎回確保しなければならないので非効率になる。

こういった実装を効率化する方法として、javascriptやmruby、CRubyのなどの処理系では、 ビットの未使用区間を再利用することで、ポインタそのものに型情報を付与するNaN boxingやTagged pointerの手法が取られたりしている。

Big bag of pages

Big bag of pages（以下、bibop）は、ビットそのものに工夫をするといった方法を取らず、ヒープ領域を独自に管理することによって、 値のメタ情報の提供を外部テーブルに任せる仕組みである。具体的には下図のように、ヒープに対して予め型ごとにページを決定しておき、 実行時は決められた領域の先頭アドレスを返すだけでメタ情報がメモリアクセスをすること無く引くことができる。

単純な構想では番地ごとにメタ情報が必要なように見えるが、図のようにパターンがある場合は型情報はビット演算で算出することも可能である。 また、こうして割り当てられている型ごとのページは、それぞれの型の純粋なサイズで確保されるため、unionを使った共通部分の不要なメモリを削減することもできる。

glibcなどの提供するメモリ管理機構におんぶ抱っこすることができないため、実装コストは大きくなるが、 メモリ使用量・メモリアクセス共に効率化を図ることができる。

サンプル実装

sbrk(2)を用いて非常に小さなサンプルを実装した。free_listなどの実装を含んでいないため、メタ情報に使用状況を載せている。 また、出力に用いた部分の実装などは本質ではないため省いている。必要であればリポジトリを参考*2。

#define TYPE_NUM 3
#define MAX_PAGE 6

enum type {
    Integer,
    Float,
    Char
};

enum state {
    Free,
    Used
};

typedef struct page_info {
    type t;
    void* p;
    int state;
} page_info;

int main(int argc, char** argv) {
    int i, j;

    page_info pages[MAX_PAGE];

    void *start_address, *end_address;
    size_t total_size;
    size_t type_size[3] = {
        sizeof(int),
        sizeof(float),
        sizeof(char),
    };

    total_size = type_size[0] + type_size[1] + type_size[2];
    start_address = sbrk(0);

    // 型の要求サイズ * ページ分ヒープを拡張
    end_address = sbrk(total_size * MAX_PAGE);

    // ページの先頭アドレスとメタ情報を紐付ける
    for (i = 0; i < MAX_PAGE; i++) {
        size_t size_offset = 0;

        for (j = 0; j < (i % TYPE_NUM); j++) {
            size_offset += type_size[j];
        }

        pages[i].t = (type)(i % TYPE_NUM);
        pages[i].p = start_address + (total_size * (i / TYPE_NUM)) + size_offset;
        pages[i].state = Free;
    }

    // 全ページ出力
    print_page_info(pages);

    // ページの4つ目（int）に対して値を割り当てる
    int* same_value = (int*)pages[3].p;
    pages[3].state = Used;
    *same_value = 100;

    // 全ページ出力
    print_page_info(pages);

    return 0;
}

出力はこんな感じ

start_address: 0x1ef4000
end_address: 0x1ef4000
page[0]:
    pointer: 0x1ef4000
    type is Integer
    State: free
page[1]:
    pointer: 0x1ef4004
    type is Float
    State: free
page[2]:
    pointer: 0x1ef4008
    type is Char
    State: free
page[3]:
    pointer: 0x1ef4009
    type is Integer
    State: free
page[4]:
    pointer: 0x1ef400d
    type is Float
    State: free
page[5]:
    pointer: 0x1ef4011
    type is Char
    State: free


Try allocate integer value 100 to pages[3]
page[0]:
    pointer: 0x1ef4000
    type is Integer
    State: free
page[1]:
    pointer: 0x1ef4004
    type is Float
    State: free
page[2]:
    pointer: 0x1ef4008
    type is Char
    State: free
page[3]:
    pointer: 0x1ef4009
    type is Integer
    Value: 100
page[4]:
    pointer: 0x1ef400d
    type is Float
    State: free
page[5]:
    pointer: 0x1ef4011
    type is Char
    State: free

page[3]に意図した通りの値が載ってる。よかったね。

*1:実装する言語をホスト、実装される言語をゲストと呼び分ける

*2:GitHub - s4ichi/big_bag_of_pages: sample implementation of big bag of pages