8/20 (金)
[Food] 三間堂＠新横浜
2006年の前半に事業部へ出向していたが、奉公が終わり研究所に戻れることになった。
今日は私を含めた三名の歓送会が新横浜富士火災ビル店の三間堂で開催されました。
 |
 |
 |
 |
 |
 |
 |
 |
8/17 (火)
Older-first GC に関する覚え書き
異動のためにオフィスの机を整理していたら、読みかけの論文やメモ書きが出てきたのでボチボチ日記に転写する。
Older-first GC は 1999 年に Stefanović が提唱したガーベージコレクションのコンセプト。 Stefanović 自身は older-first GC の実装方式として age-based GC を開発し、その評価を行なっている。 ただ実装方式の age-based GC よりはコンセプトの方が大切。
- Darko Stefanović 他 Age-based garbage collection OOPSLA'99
- Lars T. Hansen 他 An experimental study of renewal-older-first garbage collection SIGPLAN Notices Volume 37 , Issue 9 (September 2002)
- Darko Stefanović 他Older-first garbage collection in practice: evaluation in a Java Virtual Machine ISMM 2002
従来の younger-first GC の場合
世代別 GC (Generational GC) は、「生成されてからの時間が短い(若い)オブジェクトの方が時間が長い(古い)オブジェクトよりもゴミになる確率が高い」、「若いオブジェクトの方が古いオブジェクトよりも残存寿命が短い」という仮定のもと、若い世代のオブジェクトから回収を試みる。 つまり younger-first GC だ。
実際には空間を若い世代用と古い世代用に最低2つ(必要ならもっと)に分けて、ランタイムが新しいオブジェクトを割り付ける場合は若い世代用の空間に割り付ける。 GC は若い世代用の空間を先に回収対象とするが、この GC を幾度かくぐりぬけたオブジェクトは加齢(aging または tenured)されて古い世代用の空間に割り付けられるというのが基本的な実装になる。
通常の GC では古い世代を回収対象としない(手を触れない、動かさない)ので、短時間で処理を完了することができる。
仮定への懐疑
ところが世代別 GC のオブジェクト寿命への仮定は、半分正しくて、半分間違っている。 トイプログラムやマイクロベンチマークはいざ知らず、何らかの業務用のプログラムは「トランザクション」や「セッション」と呼ばれる処理上の切れ目を持っている。 そしてトランザクションの処理のために作り出されたオブジェクトは、そのトランザクションが終わるまでは解放されないので寿命がこない。
そのためオブジェクトを寿命から考えた場合、「古いオブジェクト」、「若いオブジェクト」、「幼いオブジェクト」がある。 そのオブジェクト寿命は、普通以下のようになる。
(古いオブジェクト) > (幼いオブジェクト) > (若いオブジェクト)
世代別 GC で若い世代に copying GC などを使うとトランザクションの真ん中にある幼いオブジェクトをコピーしてしまうので実はかなり無駄をしている。
Older-first GC の場合
Older-first GC はこの幼いオブジェクトを避けて若いオブジェクトから回収しようといもの。 一部に生成順序と回収順序が逆転しているので older-first だがシステム全体でみれば younger-first になっている。
実装方法はいろいろあるが、空間を一つ付け足してメモリ割り付けを行なっている空間は直近の GC の回収対象にはせずに「寝かせ」ておけるようにする。 今日割り付けたオブジェクトは、次回の GC で回収する。 GC 間隔がトランザクションの時間よりも十分に長ければ、GC によって回収できないメモリ量が大幅に減ることになる。
実際に i386 版の Hotspot VM 1.5 に older-first GC を導入すると 20%〜40% ぐらい性能が上がる。
8/13 (金)
[Linux] Soft lockups
Linux カーネルは各 CPU 毎に 10 秒以上カーネルランドの続行が続くと、soft lookup の警告メッセージを表示する。
BUG: soft lockup - CPU#13 stuck for 14s! [hogehoge:1234]
この判定は各 CPU の tick のための割り込み(x86-64 では local APIC timer)の中で、過去に記録した jiffies と比べて値が前進しているかどうかを比較している。 jiffies は CPU#0 のタイマー割り込みの中で更新される。
そのため、CPU#0 が長時間ハード割り込みを禁止されると、正常に動いている CPU も soft lockup と判定されることがあるようだ。
まあ全 CPU 分の BUG: soft lockup のメッセージが出てくるので、違いはすぐ分かるけど…
8/2 (月)
[CPU] Intel の x86 の Local APIC Timer が TSC 指定可能に
Intel の Intel64 and IA-32 Architectures Software Developer's Manual が July 2010 で更新されている。 ぱらぱらと見ていくと Volume 3A の 10.5 に記載された Local APIC Timer の機能が追加されている。
これまで Local APIC Timer はプロセッサバスを 1、2、4、8、16、32、64、128 に分割したクロックベースを持っており、それに対して 32 ビット幅であらわせるタイマー値を指定してタイマー割り込みを発生させていた。 32 ビット幅だとあまり長い時間を指定できないし、指定したカウンタ値が APIC Timer のクロックと共に減算し 0 になったら発火するというタイマーなので、One-Shot 指定の場合には次のタイマーを設定する処理のコスト等が入って、「実時間に沿って 1 ミリ秒毎にタイマー割り込みをかける」といった処理を正確に行なうのが難しかった。
今回、TSC-Deadline 指定が可能になった。 プロセッサの持つ TSC の時刻ベースに対して、IA32_TSC_DEADLINE MSR を使い 64 ビット幅でタイマーを指定する。 これは将来の TSC の値をそのまま指定し、TSC がデッドラインに到着するとタイマー割り込みが発火する。 現在の Intel の x86 CPU の TSC は (Constant TSC や Invariant TSC があるなら) 実時間を刻んでおり、絶対時刻を指定することが可能になった。
この機能はなんとなく IA-64 の ITC (Interval Timer Counter; x86 の TSC に相当) と ITM (Interval Timer Match Register) を連想させる。 過去の仕事で IA-64/Linux にマイクロ秒精度の高精度なタイマーの実装した(2006年5月22日、2006年7月4日、2006年9月19日、2006年9月23日)。 IA-64/Linux は ITM を使って 1/1024 秒単位にスレッドスケジューリング用のタイマー割り込みを起こしているが、高精度タイマーはティックとティックの間に別の ITM を挟み込めるように修正することで実現した。
x86-64/Linux の場合は、APIC Timer をプロセッサ別のスレッドスケジューリングのために使用するが、前述のように指定し辛い方式のためティックとティックの間に別の割り込みを挟み込むということが難しかった。 そのため結局、HPET タイマーを利用している。 だが TSC-Deadline を使うと、HPET を使うよりも簡単にできそうな予感がする。