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 |

May 24(Sat), 2008

[] GC分野では動的割り当て量(allocate bytes)を時間の単位として使う

「400キロバイト未満の時間で終了する小規模なプログラムはここでは対象外とする」みたいな文章を読んだら普通首を傾げることでしょう。400キロバイト未満の時間? しかし、GC分野ではよくこんな言い回しをします。ここで言っている「400キロバイト」とは、時間としての値です。この「400キロバイト」とは「動的割り当て量が述べで400キロバイトに至る時間」という意味です。

例えば、以下のプログラムのようなプログラムを考えてみます。

#include <stdio.h>
#include <stdlib.h>
int main() {
  int i;
  for(i=0;i<10;++i) {
    printf("%p\n", malloc(8));
  }
  return 0;
}

このプログラムが開始から終了までにかかる時間はどのくらいでしょう。秒という単位であらわすと、私のローカル環境では約0.016秒になりました。動的割り当て量(allocate bytes)を単位とすると、80バイトです。

プログラムの実時間というと環境によってまちまちであることは用意に想像がつきます。というわけでGCのポリシーを考える際に「時間」というものとして実時間を用いるのは不適切である場合が多いです。その点動的割り当て量というものはプログラム言語や実行環境などによらず、「時間」の単位として適している、とされています。

そういうわけで、GCの論文を読んでいたりすると「40 kb old」とか「after 10mb」みたいな言い回しが普通に出てきます。もちろん、元々のサイズという意味でもバイトという単位は使われますから、文脈で時間について言ってるのかサイズについて言ってるのか読みとく必要があります。とっぺんぱらりのぷう。

h_sakuraih_sakurai 2008/05/29 06:42 どかっと、10Mと10バイトx1M回と、同じなんでしょうか?10MByteなんでしょか?
なんか違う気がする。10バイトx1Mのほうが管理が大変だもの。管理する側のことを考えた時間ってどうなのかなと。
容量xノード数^2とかっていうほうが現実的な気もする。10Mx1=10M bn2 10x1kx1k=10M bn2 みたいなの。
10バイトを1000個と10Mが1個が同じくらいなのか、どうかはわかりませんけど。
どっちかというと、メモリのアロケーション、リアロケーションの回数を時間としたほうがいい気がするなぁ。
この例だとアロケーション回数は10回。それに動的割当量を掛けて800mb回。動的割当量を回数で割ると平均割り当てバイト数が出る。(8byte/回)
とかと、勝手に概念を考えてみました。

hogeloghogelog 2008/07/06 17:01 管理の大変さ、プログラムの複雑さはたしかに回数多い方が大変ですよね。
ここで表現したいのはプログラムの規模というかプログラムがどれだけ仕事してるかみたいな感じなので、一理はあるかもしんないです。でもたぶんシンプルさが勝って「割り当て量」で考えるのだと思います。
あと嫌らしい話(嫌らしいか?)過去のデータの単位がこれですからねえ。

May 20(Tue), 2008

[] ひどいな。何も書いてない。

なんかしばらくGCについて調べたり調べなかったり調べたりtwitterでだらだら変なことをつぶやいたりしてた。なんか日記を全然書いてない。調べて得たGCの知識とかアウトプットせな。忘れる前に。

まあとりあえず今はゼミ資料をつくる。

トラックバック - http://d.hatena.ne.jp/hogelog/20080520

May 03(Sat), 2008

[] Whitespace処理系つくったの忘れてた。

かんたん言語Whitespaceの処理系つくったの忘れてた。

http://konbu.s13.xrea.com/lib/lang/c/ws_20080503.tar.bz2

Whitespaceっていう言語はForthライク(といって良いと思うたぶん)な小さなスタック型言語。パーサとかもとても簡単に書けるし、brainf*ckなどの処理系をつくるのに飽きた人なんかにおすすめですね。

makeすれば普通に動くんじゃないかな。strndupの無い環境だとそこ変えんと駄目。

% make
perl parsegen.pl wsparse.def >gencode.c
gcc -Wall   -c -o parse.o parse.c
parse.c: In function ‘read_String’:
parse.c:80: warning: implicit declaration of function ‘strndup’
parse.c:80: warning: incompatible implicit declaration of built-in function ‘strndup’
gcc -Wall   -c -o vm.o vm.c
gcc -Wall   -c -o wspace.o wspace.c
gcc parse.o vm.o wspace.o -Wall -o wspace

警告でてるけど気にしない。よくわからんけどstrndupの警告がまったくとれない。string.hもちゃんと読んでるというのに。 id:masa_edwさんの指摘でわかりましたけど、strndupはGNU拡張なのでstring.hをインクルードするときにマクロ_GNU_SOURCEが有効になってないといけませんね。具体的には#include <string.h>の前に#define _GNU_SOURCEするか、コンパイル時に-D_GNU_SOURCEとする。

% ./wspace examples/hworld.ws
Hello, world of spaces!

なんかまあ実行できる。

[][] GCの評価方法

がんばって定式化して、ふんふんこのアルゴリズムはよさそーだなー、とこじつける。それの次どうするかというと、がんばって実装してベンチマークとるしかなさげ。


「がんばって実装してベンチマーク」は色々やりようがあるでしょうけど、Jikes RVMに独自GCを実装し、jvm98jbb2000DaCapo Benchmarksみたいなベンチマークするといった手法は広く使われてるみたいだ。GCの論文とか適当に眺めた感じ。多さでいうと、Jikes RVM + jvm98はすごく多い印象。


http://www.mm-net.org.uk/resources/benchmarks.html

にいくつかのメモリ管理研究分野で用いられてるベンチマークの紹介とかあり。


関連ツールとしてはJVMのヒープ操作の可視化フレームワークGCspyとかJVMの吐くGC情報を視覚化するGCViewerとか気になりますね。


なんか関数型方面の情報が欠けてる感じ。MLとかのGCとかの研究とかもさかんな印象あるんだけど、全然補足してない。Java勢強い。金とってきやすかったりするんか。

masa_edwmasa_edw 2008/05/03 04:45 man によると strndup は GNU 拡張なので、 swpace.h の先頭で #define _GNU_SOURCE と書くか、 Makefile で CFLAGS = -Wall -D_GNU_SOURCE 等とすると警告が無くなるはず。

hogeloghogelog 2008/05/03 22:22 あー、ちゃんと読めばたしかにそういうこと書いてありますね。ありがたや! string.hも読んでたのにstrndup宣言の前の行にある
#if defined __USE_GNU
を読み飛ばしてた自分に絶望ですね。

May 01(Thu), 2008

[][] 「生きてるオブジェクト」を示す式

下手な自然言語で説明するよりわかりやすいかもしれないのでメモ

live = ¥{N ¥in Nodes | (¥exists r ¥in Roots.r ¥to N) ¥bigvee (¥exists M ¥in live.M ¥to N)¥}

2008/05/03 追記

書き忘れてましたけどこの式Garbage Collection p4からの引用です。


Nodesは変数として割り当てることのできる全ての領域の集合。a → bはaからbへの参照があること。Rootsとは静的割り当て領域、レジスタ、スタック領域といった集合の和集合。liveとは生きてるノードの集合。

k.inabaさんにツッコミもらいました。最初のつっつきの通りであり、原文では

the least set live where

live = ¥{N ¥in Nodes | (¥exists r ¥in Roots.r ¥to N) ¥bigvee (¥exists M ¥in live.M ¥to N)¥}

だったのでしたという。

トラックバック - http://d.hatena.ne.jp/hogelog/20080501
最近のコメント