カテゴリー「C言語」の6件の記事

2010年3月28日 (日)

ガベージコレクションのアルゴリズムと実装を読む(4日目+5日目)

ガベージコレクションのアルゴリズムと実装を読み始めて5日目になりました。

4日目の記事を残しておくのを忘れてしまいましたが、4日目はコピーGCを読みました。
5日目はマークコンパクトGCでした。

コピーGCには以下のメリットがあります。
(From領域からTo領域にコピーするときに領域がコンパクションされるため、
$freeがつめ直した最後に設定される。ということで、確保する時に$freeをずらせば良い)

キャッシュメモリとの相性が良い(参照関係があるオブジェクトをコピーするため)

デメリット
ヒープ領域が2分割されるため領域の使用効率が悪い。
再起関数呼び出しでスタックオーバーフローが起こる可能性がある。

など、一長一短があるようです。

マークコンパクトGCについてですが、
メリットはコピーGCと同じく、フラグメンテーションが発生しない。
ヒープ領域が有効活用できるなどがあるようです。

デメリット
コンパクションの処理にコストがかかる。(3回ヒープ領域をscanする)

デメリットを解消するために
Two-Fingerアルゴリズム、テーブルアルゴリズムがあります。
(Scan回数が2回で済む)

ImmixGCというのもあるそうですが、難解そうだったのとSoftbankのUstを見ていたので
今回はSkipしました。

個人的にはマークコンパクトGCは難しいイメージがありますね。

| | コメント (0) | トラックバック (0)

2010年3月25日 (木)

ガベージコレクションのアルゴリズムと実装を読む(3日目)

ガベージコレクションのアルゴリズムと実装を読み始めて3日目になりました。

今日は、分散して読んだのでちょっと記憶が飛んでいる部分がありますが、
今日のGCは「参照カウント法」でした。

オブジェクトにカウントフィールドを持たせて、被参照数をカウントしておく方法でした。
確かにカウント数が分かれば、ポインタをたどらなくてもカウンタが0になった瞬間に
FreeListに登録するだけで済みます。
(FreeListに登録されているものを回収すれば良い)

ただ、参照カウントを持つとメモリを食うという状況がでてしまうので、
(1オブジェクトに4バイト)
カウントの容量を押さえたSticky参照カウント法とか、1ビット参照カウント法なんてものも
あるようです。(カウントオーバーフロー時は無視するというのには、「仕様として割り切る」ってのも
大事だと再認識しました。)

最大の弱点が「循環参照を回収できない」という点があるみたいですが、
部分マークスイープ法と組み合わせて弱点を補う事ができるなど、
GCも奥が深いですね。

| | コメント (0) | トラックバック (0)

2010年3月24日 (水)

ガベージコレクションのアルゴリズムと実装を読む(2日目)

ガベージコレクションのアルゴリズムと実装を読み始めて2日目になりました。

今日は、2章の「マークスイープGC」を読みました。

マークスイープGCは「マークフェイズ」と「スイープフェイズ」がある。

生きているオブジェクトに対してマークビットを立てる。
マークビットが立っていないオブジェクトをスイープフェイズで回収する。

分かりやすいアルゴリズムでした。疑似コードもマークして、スイープといった
ロジックになっていました。

メリット
実装が簡単(疑似コードから大体わかりました)
保守的GCと相性がいい
(オブジェクトの移動がないため。。だそうです。以降の保守的GCを読めば分かるはず)

デメリット
フラグメンテーションが発生しやすい
アロケーション速度の問題(FreeListをたどって行く必要がある。最悪、毎回最後まで)
コピーオンライトと相性が悪い(マークビットを立てるとコピーが頻発する)

で、デメリットを解消するために考えられた方法が
複数フリーリストを用意する
BiBOP法
ビットマップマーキング

ビットマップマーキングの例(リスト9)で私が詰まってしまったので、
筆者にTwitterで質問してみました。
詰まった内容:
2行目の
obj_num = (obj - $heap_start) / WORD_LENGTH

3行目の
index = obj_num / WORD_LENGTH
に具体的な数値を当てはめると、以降の配列のアクセスがおかしくならないか?

具体例)
obj_num = (3 * 32 - 1 * 32) / WORD_LENGTH(=32) = 2
index = 2 / WORD_LENGTH(=32) = 1/16

(実際、リストの次の段にobj_num = 8の例がありますが)

これは私のミスでした。C言語の整数の扱いのように小数を切り捨てるということを
しなければいけませんでした。
ということで、実際には

obj_num = (3 * 32 - 1 * 32) / WORD_LENGTH(=32) = 2
index = 2 / WORD_LENGTH(=32) = 0(切り捨てる)

となります。

これで、すっきりしました。(作者と簡単に連絡が取れるのは良いなぁ。)

| | コメント (0) | トラックバック (0)

2010年3月23日 (火)

ガベージコレクションのアルゴリズムと実装を読む(1日目)

ガベージコレクションのアルゴリズムと実装という本を昨日購入しました。

ということで、早速今日から読み進めようと思います。

今日読んだのは序章と1章です。
内容としては、GCが行う事、GCがある場合とない場合の違い、
「なぜGCなのか?」という疑問に対する記述など、
GC本を読むにあたり、最初の導入部分が書かれていました。

GCを理解して行くと、メモリの使い方を意識するようになるようです。
(確かに、C言語でプログラムを書く時と、Javaで書く時とでは、意識の仕方が違う気がします。)

1章では、GCを学ぶ前に必要な内容が書かれていました。
オブジェクト、ポインタ、ミューテータ、ヒープ領域。。。

生きている/死んでいるオブジェクトの違いなど。

何となく、ミューテータがアロケータに指示して確保したメモリを
GCが先頭から見て行って死んでたらオブジェクトを解放するというのを
繰り返すのかな?という理解をしました。

と、今日は「そんな事よりGCは面白い」というのが印象に残りました。

| | コメント (0) | トラックバック (0)

2008年3月11日 (火)

Visual C++ 2008を使おうと思ったものの

Visual C++ 2008を使ってみました。

と言っても、コンソールアプリケーションで「Hello World」を表示させただけなんですが。

Express EditionはMFCとATLは作成できないわけですが、2005の時よりも心なしか
作成できるプロジェクトが増えているような気がしますね。
(ちなみに、2005の時は、SDKを入れないとWin32アプリケーションが作成できなかった。)

少し気になったのが、Windowsフォームアプリケーションが簡単に作れるようになっている事です。
VB.NETやC#のようにフォームにぺたぺたと貼り付けてイベント駆動型のアプリケーションを
作成するようです。(Microsoftのサイトにサンプルが載っています)

今の仕事柄Microsoft一色に染まっているから少しは調べた方がいいのかも知れませんね。

| | コメント (0) | トラックバック (0)

2007年9月19日 (水)

SocketプログラミングとTCP/IP

ふと思ってFINパケットが送信されるタイミングを調べていたわけですが、
send()で送るわけでは無いのですね。

これは個人的に新発見でした。

知ってしまえば、なんとなく理解はできますが、FINを送る時というのは
通信を完了して切断する時なので、関数的にはshutdown()、close()の時に
なりますね。

実際にtcpdumpなどで見たわけではないので、あくまでも資料を見ただけです。

今週末はプログラミング三昧になるかな…?

| | コメント (0) | トラックバック (0)