Hatena::ブログ(Diary)

hogeなlog

プロフィール

hogelog

hogelog

小室 直(こむろ すなお)。電気通信大学2003年入学。2010年修士卒業。プログラミングとかしてます。

カレンダー
1984 | 01 |
2006 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2010 | 01 | 06 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 05 | 08 | 09 | 10 | 12 |
2012 | 01 | 04 | 06 |

February 20(Fri), 2009

[][][] Optimistic Stack Allocation For Java-Like Languages

論文(ACMへのリンク)

発表資料(pdf)

辞書で単語の意味を調べて繋げると「Javaライクな言語のための楽観的なスタック割り当て」ということになります。題名から予想するに「Javaライクな言語だったらだーいたいスタック割り当てで大丈夫っしょ〜」みたいな内容なのでしょう。誰ですかオブジェクト指向プログラミング言語にヒープ割り当てとガーベジコレクションが必須だなんて言ったのはプフー

なんか違う気がする。「Javaライクな言語のための最適化スタック割り当て」といったところでしょうか。自分なりにまとめてみます。翻訳ではありません。

概要

スタック割り当てはキャッシュメモリを効率的に利用できるが、安全にスタック割り当てに置き換え可能なオブジェクトを見つけるのは難しい。よって私達は手続きをまたぐエスケープ解析(interprocedural escape analysis)を必要としない、Java VMのような動的クラスロードやリフレクション、例外処理機構を持つ環境において安全にスタック割り当てを行う手法を提案する。

既存研究

従来のエスケープ解析手法はプログラム全体の解析結果を元にスタック割り当てを行う。よって動的クラスロードなどによりプログラムが変形した場合には解析をやり直す必要があり、そういった手法を適用するには困難が伴う。

Bakerの最適化スタック割り当て手法

CONS should not CONS its arguments, or, a lazy alloc is a smart allocで提案された手法は「全てのオブジェクトは一旦スタック領域に格納し、ヒープ領域からの参照された時に参照から辿れるオブジェクトをヒープに移動する」もの。参照が書き換えられたときにオブジェクトの移動をするのでライトバリアが必要。移動したオブジェクトがあった位置にはforwarding pointerを書き込む。移動前の位置を指す参照はforwarding pointerを指す先を見るのでリードバリアも必要。

提案手法

基本的に「Bakerの手法(Schemeへの実装)を元にJavaライクな言語に対して実装する」といった内容。

リードバリアの削除

Bakerの手法ではリードバリアが必要だったが、オブジェクトの移動をした際にそのオブジェクトを指していたオブジェクトの参照も書き換えればリードバリアは必要無くなる。オブジェクトの移動はヒープから参照されたとき行われるので、その時点では他にありうる参照はスタックからの参照のみである。参照の書き換えのためにスキャンしなければいけないのはスタック領域のみなのでコストはそれほど大きくならない。

ヒープ割り当てオブジェクト

スタック割り当てを経由せず、直接ヒープにオブジェクトを割り当てられるようにする。ヒープ領域に移動されるのが確実なオブジェクトをスタックに割り当てると性能劣化があるため。

スタック割り当てオブジェクトのロック

スタックに割り当てられたオブジェクトは他のスレッドからはアクセスできないようにする。

ループベースのオブジェクトスタック領域

まず提案手法ではメソッド呼び出しや返り値の受け渡しに用いるスタック領域(コールスタック)と、スタック割り当てに用いるスタック(オブジェクトスタック)は別の領域として管理する。オブジェクトスタックはリージョン(フレーム)に分割して管理し、以下の操作が可能なものとする。

  • 新しいリージョンの開始
  • 現在のリージョンに新しいオブジェクトを割り当てる
  • 指定されたオブジェクトをヒープに移動
  • 移動したオブジェクトを指すオブジェクトの検索
  • リージョンとその中に含まれるオブジェクトの解放

新しいリージョンの開始をループ開始時、リージョンの解放をループの終了時に行う。リージョンはループの度に開始と解放を繰り返す。

深い再帰呼び出しをされるとスタックが大きくなってしまうという問題がある。これにはオブジェエクトスタックがある程度以上大きくなった場合はスタック割り当てをやめ、直接ヒープに割り当てるようにすることで対処する。また末尾再帰呼び出しの最適化を行なっている環境においては、ループと同等のフローであると見なして処理するものとする。

手続き内解析

提案手法では手続き内解析(intraprocedural escape analysis)のみを用いて、手続き内のコントロールフロー(ループ、分岐、例外処理)を解析し、コードとリージョンの対応をつける。

実験など

省略。

まとめ

実験結果は提案手法がスタックを利用することでメモリを効率的に利用し、高いキャッシュ効率を見込めることを示す。しかも我々の提案する手法はJavaのような動的クラスロードやリフレクション、例外処理機構を持つ環境において簡単かつ安全に実装可能である。

次はJikes RVMに実装して性能を計測します。

コメント

まだ実装してないようだ。「実装しやすい!」みたいなこと書いてあるけど実装されてないんだから真偽の程やいかに。

この論文の対象はJavaライクな言語というよりJava VMかな。Java VMみたいなスタック型VMで実装されてる言語においてスタック割り当てを導入することを考えるのにはかなり参考になるように思える。

またこの論文でループを基準としているのは、Java VMで動くようなプログラムがループをベースにしているという前提を元にしているんだと思うんだけど、例えばRubyなんかでは繰り返しはブロック呼び出しで書くのが普通だったりしてるし、色々考える必要がありそう。

February 18(Wed), 2009

[] 習作GCライブラリ(1) exact copying gc

習作として単純なGCライブラリを実装してみました。とりあえず面倒だったのでヒープとスタックのサイズは固定長。

githubを使って公開してみる http://github.com/hogelog/copying_gc/tree/master

こんな感じで使う。

static Memory *memory;
void test_01() {
    Object iv, fv, str, pair;
    int i;
    for (i=0;i<2000;++i) {
        fixed_memory_push(memory,
                iv = new_ivalue(memory, i));
        printf("%p: %ld\n", iv, IVALUE(iv));

        fixed_memory_push(memory,
                fv = new_fvalue(memory, (double)i));
        printf("%p: %f\n", fv, FVALUE(fv));

        fixed_memory_push(memory,
                str = new_string(memory, "hogefuga"));
        printf("%p: %s\n", str, STR_BUF(str));

        fixed_memory_push(memory,
                pair = new_pair(memory, iv, fv));
        printf("%p: (%ld . %f)\n", pair,
                IVALUE(PAIR_CAR(pair)), FVALUE(PAIR_CDR(pair)));
        fixed_memory_pop(memory);
        fixed_memory_pop(memory);
        fixed_memory_pop(memory);
        fixed_memory_pop(memory);
    }
}
void test_02() {
    Object iv_0 = new_ivalue(memory, 0);
    Object pair = push_pair(memory, iv_0, iv_0);
    Object *cdr = &PAIR_CDR(pair);
    int i;
    for (i=1;i<10;++i) {
        Object iv_i = new_ivalue(memory, i);
        (*cdr) = new_pair(memory, iv_i, iv_i);
        cdr = &PAIR_CDR(*cdr);
    }
    printf("%p:", pair);
    print_object(pair);
    putchar('\n');
}

int main(int argc, char **argv) {
    Memory mainmem;
    memory = &mainmem;
    fixed_memory_init(memory, 1024, 1024);
    test_01();
    test_02();
    fixed_memory_printinfo(memory);
    fixed_memory_sweep(memory);
    puts("# run sweep");
    fixed_memory_printinfo(memory);
    return 0;
}
0x9d73008: 0
0x9d73018: 0.000000
0x9d73028: hogefuga
0x9d73038: (0 . 0.000000)
0x9d73048: 1
0x9d73058: 1.000000
0x9d73068: hogefuga
0x9d73078: (1 . 1.000000)
...
0x9d7a390: 1998
0x9d7a3a0: 1998.000000
0x9d7a3b0: hogefuga
0x9d7a3c0: (1998 . 1998.000000)
0x9d7a3d0: 1999
0x9d7a3e0: 1999.000000
0x9d7a3f0: hogefuga
0x9d7a400: (1999 . 1999.000000)
0x9d7b018:(0 . (1 . (2 . (3 . 
(4 . (5 . (6 . (7 . (8 . (9 . 9))))))))))
heap: 851 / 1024
stack: 1 / 1024
# run sweep
heap: 19 / 1024
stack: 1 / 1024

ここではヒープ長を固定長の1024としているのにアロケーション命令を8000回以上呼んでいますが、足りなくなるたびにfixed_memory_sweepが走っているので大丈夫。mainの最後で意図的にGCを走らせた後はtest_02で作った、スタックから辿ることのできる19個のオブジェクトのみ生存しています。

特におもしろいことはしていない。まあ一度は書いておかないとなあと思って書いた。しかしGC処理部分は100行もいかない程度で書けたのがおもしろかった。

2009/2/18 14:03 追記

GC処理部分だけ切り出すとこれだけ。一般教養としてのGarbage Collection片手に「こんな感じかなー」と書きました。

/* Cheney compacting Algorithm */
#define COPY_TO(obj) do {\
    if(FORWARD(obj)==NULL) {\
        Object *forward = &FORWARD(obj);\
        obj = fixed_array_push(to, obj);\
        *forward = obj;\
    } else {\
        obj = FORWARD(obj);\
    }\
} while (0)
static void copy_space(Array *from, Array *to) {
    Object scanned = from->head;
    while(scanned!=from->current) {
        switch(TYPE(scanned)) {
            case T_PAIR:
                COPY_TO(PAIR_CAR(scanned));
                COPY_TO(PAIR_CDR(scanned));
                break;
            default:
                break;
        }
        ++scanned;
    }
}
size_t fixed_memory_sweep(Memory *mem) {
    Array *stack = mem->stack;
    Array *from = mem->heap;
    Array *to = from==&mem->h1 ? &mem->h2 : &mem->h1;
    Object scanned;
 
    to->current = to->head;

    scanned = from->head;
    while(scanned!=from->current) {
        FORWARD(scanned) = NULL;
        ++scanned;
    }
    /* copy object referenced from stack */
    copy_space(stack, to);

    copy_space(to, to);

    scanned = from->head;
    while(scanned!=from->current) {
        if(FORWARD(scanned)==NULL && TYPE(scanned)==T_STR) {
            free(STR_BUF(scanned));
        }
        ++scanned;
    }

既にfromからtoへコピーされているかチェックしている処理がなんかかなしいことになっている。結局fromスペースを走査すんのかよと。既存のcopying gcの実装をちゃんと読んだことないのだが、この辺はたぶんもっとうまい方法あるんじゃないかと思う。

2009/2/21 17:15追記

電車の中でGC論文読んでて気付いたんだけど、fowarding pointerを記録の仕方が非常に阿呆だったので修正。diffで示すにこういう変更をしました。

 enum Type {
     T_INT, T_FLOAT, T_STR,
-    T_PAIR
+    T_PAIR, T_FORWARD
 };
 union Value {
     long ivalue;
     double fvalue;
     String str;
     Pair pair;
+    Object forward;
 };
 struct Object {
     Type type;
     Value value;
-    Object forward;
 };

最初の書き方だと全てのオブジェクトの構造にforward pointerを書き込む場所があった。GCの時にしか使わないのに! そんなことせずに、移動したらT_FORWARD型にして参照先を値として記録すればいいのでした。データ構造の変更に従い、アルゴリズムも変更。

/* Cheney compacting Algorithm */
#define COPY_TO(obj) do {\
    if(TYPE(obj)==T_FORWARD) {\
        obj = FORWARD(obj);\
    } else {\
        Object new = fixed_array_push(to, obj);\
        FORWARD_SET(obj,new);\
    }\
} while (0)
static void copy_space(Array *from, Array *to) {
    Object scanned = from->head;
    while(scanned!=from->current) {
        switch(TYPE(scanned)) {
            case T_PAIR:
                COPY_TO(PAIR_CAR(scanned));
                COPY_TO(PAIR_CDR(scanned));
                break;
            default:
                break;
        }
        ++scanned;
    }
}
size_t fixed_memory_sweep(Memory *mem) {
    Array *stack = mem->stack;
    Array *from = mem->heap;
    Array *to = from==&mem->h1 ? &mem->h2 : &mem->h1;
    Object scanned;

    to->current = to->head;

    /* copy object referenced from stack */
    copy_space(stack, to);
    
    copy_space(to, to);

    scanned = from->head;
    while(scanned!=from->current) {
        if(TYPE(scanned)==T_STR) {
            free(STR_BUF(scanned));
        }
        ++scanned;
    }

    mem->heap = to;
    return (from->current-from->head) - (to->current-to->head);
}

短かくなってくれましたね、ありがたいありがたい。COPY_TOがマクロなのは、ついなんとなくなんだけど今どきこういうの関数にするでしょうとかそんな意見はありえますねううん

あいかわあいかわ 2009/02/18 16:26 >既にfromからtoへコピーされているかチェックしている処理

if(FORWARD(obj)==NULL) {\
のことですか?これはこれでいいんじゃないかなあ。
コピー済みオブジェクトobjのFORWARDをobj自身にしておくって手もありますけど、まあ同じか。

それよりfree(STR_BUF(scanned)) が気になったんですがこれでいいのでしょうか。

hogeloghogelog 2009/02/18 17:38 悲しいのはfromの走査をなんか2回もやってることです。一個目のループでは全部のforward領域に値書き込んだりもしてますし、ベタベタメモリに触るのが嫌だなあと。

STR_BUF(obj)部分は常にstrdupで生成してるのでfreeで良いかなと思いましたが。
http://github.com/hogelog/copying_gc/blob/b9ecdc72be3b2445b910fea9e74c81f3abcf1245/main.c#L17
まずそうでしょうか。

あいかわあいかわ 2009/02/18 18:16 >悲しいのはfromの走査をなんか2回もやってることです
ほんとですね。なんでだろ。
コピーGCのアルゴリズムは
1)ルートから参照されているオブジェクトをtoスペースへコピー
2)Toスペースのオブジェクトをスキャンしてポインタの書き換え(fromをさしていたらtoへコピー)
なので、うまくやれば
scanned = from->head;
while(scanned!=from->current) {
FORWARD(scanned) = NULL;
++scanned;
}
のあたりは消せるのではないでしょうか。


>STR_BUF(obj)部分は常にstrdupで生成してるのでfreeで良いかなと思いましたが。
ああつまりRubyみたいにヒープ上にはStringオブジェクトのヘッダだけがあって、文字列はstrdupで確保してるのですね。
ならいいと思います。
#記事だけを見ててgithubの方は見てませんでした。すみません。

hogeloghogelog 2009/02/19 09:05 先のループはなんか消せそうな気もしてきました。ぬぬぬ

February 02(Mon), 2009

[] 文字列の繰り返し

rubyのソースコードを眺めていたらrb_str_timesの実装がおもしろかったので、実際そういった書き方をすることでどれだけパフォーマンスに差が出てくるのか試してみました。

http://codepad.org/AQbS4Ilu

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

inline unsigned long long rdtsc() {
    unsigned long long ret;
    __asm__ volatile ("rdtsc" : "=A" (ret));
    return ret;
}

char *times_simple(char *str, size_t times) {
    size_t i, len = strlen(str);
    char *str2 = malloc(len*times + 1);
    for(i=0;i<len*times;i+=len) {
	memcpy(str2+i, str, len);
    }
    str2[len*times] = '\0';
    return str2;
}
char *times_log(char *str, size_t times) {
    size_t n, len = strlen(str);
    char *str2 = malloc(len*times + 1);
    n = len;
    memcpy(str2, str, n);
    while(n <= len*times/2) {
	memcpy(str2+n, str2, n);
	n *= 2;
    }
    memcpy(str2+n, str2, len*times-n);
    str2[len*times] = '\0';
    return str2;
}
int main(int argc, char **argv) {
    static char *str = "hoge";
    char *str2;
    size_t times = 100;
    unsigned long long start, end;

    start = rdtsc();
    str2 = times_simple(str, times);
    end= rdtsc();
    printf("%s x %d = %s\n", str, times, str2);
    printf("time stamp counter: %llu\n", end - start);

    start = rdtsc();
    str2 = times_log(str, times);
    end= rdtsc();
    printf("%s x %d = %s\n", str, times, str2);
    printf("time stamp counter: %llu\n", end - start);

    return 0;
}

memcpyを単純に100回繰り返すtimes_simpleと、memcpyの回数が8回で済むtimes_logの速度比較。時間計測はRDTSC命令で。

hoge x 100 = hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge
time stamp counter: 1871674
hoge x 100 = hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge
time stamp counter: 2430

すごく差がでました。


「アルゴリズムって大事ですね!」という締めはあちこちで見るので、ここでは「偉い人が書いたパーツを使って、なるべく自分でループとか書かないようにすると勝手に高速化されてたりしてて嬉しいですよ!」と言っておきます。

2009/2/2 2:46 追記

codepadの実行結果とかどういうものなのかいまいちわからんので手元の

% cat /proc/cpuinfo
...
model name      : AMD Athlon(tm)64 X2 Dual Core Processor  4600+
stepping        : 1
cpu MHz         : 1000.000
cache size      : 512 KB
...

みたいなマシンの結果だと

hoge x 100 = hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge
time stamp counter: 135745
hoge x 100 = hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge
time stamp counter: 2326

この程度に。

最近のコメント
Connection: close