HN 日本語サマリー

← 一覧へ戻る
プログラミング

ガーベージコレクションの迷宮にどこへ向かっているのか分からない

Not sure where I am going with this garbage collection rabbit hole (ikouchiha47.github.io)

4 pointsby argentum470 コメント

要約

この記事は、Go、Kotlin、Erlang/Elixir(BEAM上で動作)という3つの言語が、並行処理とガベージコレクション(GC)という共通の課題にどのように異なるアプローチを取っているかを比較します。各言語のタスク切り替えの制御方法と、それがGCの動作やクラッシュの封じ込め能力にどう影響するかを、制約から導き出します。

全文翻訳

並行処理とGCの概要

関連: 001_usage_of_signals_in_language_runtime.md, 006_other_reading_materials.md, 007_concurrency_comparison.md

要旨

3つの言語 — Go、Kotlin、およびErlang/Elixir(BEAM上で動作) — は、同じ問題(少ないOSスレッドで多数の論理タスクを実行する)を、1つの質問に対する3つの異なる答えで解決しています:タスク間の切り替えを誰が制御し、その制御者は安全に行うために何を知る必要があるか?

その質問への答えが、その後のすべてを決定します:モデルが協調型かプリエンプティブ型か、GCが1つのスレッドを一時停止するかプロセス全体を一時停止するか、そしてクラッシュが封じ込められるか破滅的になるかです。

このドキュメントでは、各モデルを機能のリストとして説明するのではなく、その制約から導き出します。各セクションの最後には、次のセクションに進む前に答えられるべきチェックポイントの質問があります。


背景:3つすべてが解決しようとしている問題

CPUコアは一度に1つの命令ストリームを実行します。OSスレッドは、コアを多数の命令ストリームにタイムスライスするためのカーネルの抽象化ですが、それらは高価です:

  • スレッドあたり約8MBのスタック(Linuxデフォルト)
  • コンテキストスイッチは、完全なレジスタファイルを保存/復元し、キャッシュとTLBを乱します
  • 10,000のOSスレッドは、作業が行われる前にギガバイトのスタック領域を意味します

したがって、安価な並行処理を望むすべてのランタイムは、M:Nスケジューラを構築します:M個の論理タスクをN個のOSスレッドに多重化します(通常、N ≈ コア数)。以下の3つのシステムは、3つの異なるM:Nスケジューラであり、切り替えロジックの所有者について異なる決定を下したために異なります。

チェックポイント: 続行する前に、OSスレッドがなぜスケーラブルな論理タスクあたり1つ使用するには高価すぎるのかを1文で述べてください。


パート1 — Go

このセクションで直接参照したソース(記憶からの言い換えではない):src/runtime/preempt.go, src/runtime/signal_unix.go, src/runtime/proc.go, src/runtime/mgc.go — golang/go、masterブランチ、raw.githubusercontent.comから取得。

1.1 主要概念:これはフォークジョインではなくCSPである

Goの並行処理モデルは、HoareのCommunicating Sequential Processes (CSP, 1978) の実装であることが明示されています — 独立した逐次プロセスが、ロック経由でアクセスされる共有ミュータブル状態ではなく、チャネルを介したメッセージパッシングのみで相互作用します。これは設計上の系譜であり、Go自身の資料に直接記載されています:「メモリを共有して通信するのではなく、通信してメモリを共有せよ」。

CSP自体の起源。 Tony Hoareは1978年に「Communicating Sequential Processes」をCommunications of the ACMに発表しました。彼が取り組んでいた問題は、現代のウェブサービスの意味での並行処理ではありませんでした — それは、共有変数並行処理(セマフォ、モニター)が支配的なモデルであり、形式的に推論するのが非常に難しいことが証明されていた時代の並行プログラムの正しさでした:共有ミュータブル状態では、2つのプロセスの可能なインターリーブの数が爆発し、プログラムが正しいことを証明するには、すべてのインターリーブの下で正しいことを証明する必要がありました。

Hoareの移動は、プロセス間の唯一の相互作用を、明示的で同期的な、名前付きイベントにすることでした — プロセスは送信先/受信先を名前で指定し、送信/受信ペア全体が同期プリミティブであり、個別のロックは不要です。これは実際の数学的利点があります:プロセスは何も共有しないため、各プロセスを独立して推論でき、それらの間の通信イベントを、共有メモリインターリーブの網羅的なケース分析よりもはるかに小さな問題として推論できます — 代数的アプローチに近くなります。CSPは、Hoare自身の後の作品で完全なプロセス代数としてさらに形式化され、Robin MilnerのCCS(Calculus of Communicating Systems、これも1970年代後半)と並行して独立に開発されました — 両者は通常、一般的にプロセス代数の起源として一緒に引用されます。

Goの設計者(特にNewsqueakとAlef — すでにCSPスタイルのチャネルを使用していた直接の実験的前身 — で以前に作業していたRob Pike)は、CSPの通信プリミティブ — 同期チャネルメッセージパッシング — を、Hoareの完全な形式プロセス代数や、元の同期のみの制限(Goのバッファ付きチャネルはバッファサイズまでの非同期送信を許可し、Hoareの元の計算にはありませんでした)を採用せずに取得しました。したがって、「GoはCSPを実装している」というのは、コアアイデアのレベル — ロックではなく同期の単位としてのチャネル — では正確であり、Goが完全な形式計算を実装していると見なす場合は不正確です。

これは、Goが行っていない2つの他のモデルと混同しやすいので重要です:

  • フォークジョイン(JavaのForkJoinPool、Cilk、OpenMP):タスクが明示的にサブタスクに分割され、それらすべてを待機してから結合します。並列性は単一の計算の分割統治形状を中心に構造化されています。Goにはこれに対する組み込み機能はありません — sync.WaitGroupで手動で実装する必要があります。Goroutineは暗黙的な結合なしで生成されません;go f()はすぐに返り、自分で同期を追加しない限り何もそれを待ちません。
  • ロックによる共有メモリスレッディング(生のpthreads、Java synchronized):デフォルトの調整プリミティブは、相互排他によって保護された共有アドレス空間です。Goもこれをサポートしています(sync.Mutexは存在し、ランタイム自体の中で大量に使用されています)が、言語があなたを誘導する慣用的な表面ではありません。

チャネル(chan)はCSPプリミティブです:ゴルーチンはチャネルに値を送信し、別のゴルーチンがそれを受信し、転送自体が同期ポイントです — そのハンドオフに個別のロックは必要ありません。

チェックポイント: ゴルーチンが暗黙的に結合されない場合、go f()呼び出しの副作用がmain()が返る前に可視であることが保証されるのは何ですか?(回答:デフォルトでは何もありません — これは、チャネルまたはWaitGroupを介して明示的に待機しないプログラムが、生成されたゴルーチンが完了する前に終了する可能性がある理由であり、言語保証ではなく一般的なバグの発生源です。)

1.2 GMPスケジューラ

proc.goのファイル先頭のドキュメントコメント(約24行目以降)より:

スケジューラのジョブは、実行可能なゴルーチンを実行スレッドに配布することです。G - ゴルーチン。M - ワーカー・スレッド、またはマシン。P - プロセッサ、Goコードを実行するために必要なリソースです。MはGoコードを実行するために関連付けられたPを持たなければなりませんが、関連付けられたPなしでブロックされたり、システムコール中にいたりすることがあります。設計ドキュメントは https://golang.org/s/go11sched にあります。

これはgo11sched設計(Dmitry Vyukov、2012年)です — M:N:Pモデルは、Pごとのローカル実行キューの問題を解決するために特別に存在します:Pが個別のスケジューリングリソースでない場合、作業を競合するすべてのMはグローバルキューにヒットする必要がありますが、これは数コアを超えるとスケーリングしません。各Pはローカル実行キューを所有します;MはGoコードを実行するためにPを取得する必要があります。そのため、システムコールでブロックされたゴルーチンは、コアをアイドル状態にするのではなく、別のMが拾えるようにPを解放します(proc.goのhandoffp)。

1.3 プリエンプション:進化の経緯と、GCが変更を動機付けた理由

Go ≤1.10 — 協調型、関数プロローグで。 すべての関数呼び出しは「譲ってほしい」フラグをチェックしました(preempt.goのヘッダーコメントによれば、スタック境界チェックのポイズニングによって実装されています:「同期セーフポイントは、関数プロローグでのスタック境界チェックのオーバーロードによって実装されます」)。ループ本体に関数呼び出しがないゴルーチン(for {})は、そのチェックをトリガーせず、この方法でプリエンプトされることはありませんでした。

これがなぜGCの問題であり、単なるスケジューリングの公平性の問題ではないのか: mgc.goは、マーク終了とスイープ終了の両方(gcMarkTermination、gcStart — 現在のソースのmgc.goの約835行目、約1066行目)でstopTheWorldWithSemaを呼び出します。STWは文字通り、GCフェーズが進む前に、すべてのゴルーチンがGCが安全と見なす状態に到達する必要があることを意味します — マーク/スイープ遷移は、1つのゴルーチンがまだ任意のコードを実行している状態であっても開始できません。なぜなら、GCは到達可能なもののグローバルに一貫したビューを必要とするからです。関数呼び出しのないタイトなループでスタックしているゴルーチンは、これを無期限にブロックしました。これは、一般的な「公平な」スケジューリングへの欲求ではなく、2019年の提案(golang/proposal 24543-non-cooperative-preemption.md)を動機付けた、実際の測定された本番環境の問題でした。

Go 1.14 — 非協調型、シグナルベース。 preempt.goのコメント自体が、3つのセーフポイントカテゴリを正確に区別しています:

  1. ブロックされたセーフポイント — ゴルーチンがデスケジューリングされた、同期でブロックされた、またはシステムコール中の場合。安価:ランタイムはそのスタックの完全な知識を持っています。
  2. 同期セーフポイント — 実行中のゴルーチンが、保留中のプリエンプション要求を自発的にチェックします(上記のスタック境界チェックトリック)。
  3. 非同期セーフポイント — ユーザーコード内の任意の命令で、保守的なスタック/レジスタスキャンがまだすべてのルートを見つけられる場所。ランタイムは、ゴルーチンの協力を必要とせずに、シグナルを使用してここでゴルーチンを停止できます。

signal_unix.go(344〜74行目)は、SIGURGの根拠を4つの番号付き基準として正確に述べており、シグナルはそれらを満たす必要がありました:

  1. デバッガがデフォルトで通過するシグナルであること(Linuxの場合:SIGALRM、SIGURG、SIGCHLD、SIGIO、SIGVTALRM、SIGPROF、SIGWINCH)。
  2. Go/C混合バイナリでlibcが内部的に主張しないこと(SIGCANCEL、SIGSETXIDを除く)。
  3. 偽陽性で受信しても安全であること — SIGALRM(曖昧な原因)とSIGUSR1/SIGUSR2(アプリケーションが実際の目的で一般的に使用する)を除く。
  4. リアルタイムシグナルがないプラットフォームに存在すること(macOSのRTシグナル範囲の欠落を除く)。

SIGURGが選ばれたのは、帯域外TCPデータが実際にはほとんど使用されておらず、シグナルはそのトリガーとなったソケットさえ報告しない(文字通りの目的にはほとんど役に立たない)ため、そして正しく書かれたアプリケーションはすでに偽陽性のSIGURGを許容する必要があるためです。

メカニズムは、実際のコールパスをたどると:suspendG(preempt.go)はゴルーチンをサスペンドに向かわせます — それが_Grunningの場合、gp.preemptStop/gp.preemptを設定し、preemptMを呼び出します。これは、その特定のOSスレッドにSIGURGを配信するためにsignalM(mp, sigPreempt)(signal_unix.goの約386行目)を呼び出します。シグナルハンドラ(doSigPreempt、signal_unix.goの約342行目)は、中断されたPCを検査し、認識された非同期セーフポイントに着地した場合にのみアクションを実行します。そうでない場合は、ゴルーチンを続行させてリトライさせます。受け入れられると、ハンドラは実行がasyncPreemptで再開するようにシグナルコンテキストを書き換えます。これは、スタックをGCでスキャン可能にするものです。

中間的な修正 — ループバックエッジにチェックを挿入して、関数呼び出しのないタイトなループでも同期セーフポイントにヒットするようにする — は測定され、却下されました:7.8%のスループット低下であり、このギャップを閉じるためだけにすべてのGoプログラムで無条件に支払うには高すぎると見なされました。シグナルベースの非同期プリエンプションは、実際に呼び出されるまでコストがかからないため、厳密により安価でした。

具体的な例を追跡:

func main() {
    go func() {
        for {} // 無限にスピン、関数呼び出しなし
    }()
    time.Sleep(time.Second)
    runtime.GC()
}

Go ≤1.10では、runtime.GC()はここで決して返りませんでした。runtime.GC()はストップ・ザ・ワールドGCサイクルを強制し、これはstopTheWorldWithSemaを呼び出します — スピンしているゴルーチンを含むすべてのゴルーチンは、最初にセーフポイントに到達する必要があります。スピンしているゴルーチンは関数を呼び出さないため、古い同期メカニズムが依存していたスタック境界チェックをトリガーしません。それは無限にスピンし、GCは無限に待ち、プログラムはハングします。

Go ≥1.14では、同じプログラムのGC呼び出しは成功します。stopTheWorldWithSemaはスピンしているゴルーチンに対してsuspendGを呼び出します。それは保留中のサスペンドがなく_Grunningであるため、suspendGはpreemptMを呼び出し、それはそれを実行しているOSスレッドにSIGURGを送信します。シグナルはfor {}ループを飛行中に中断します — ループ本体のゼロ関数呼び出しであっても、コンパイラのスタックマップがすべての非同期セーフポイントをカバーしているため、文字通り任意の命令で中断します。シグナルハンドラは実行をasyncPreemptで再開するように書き換え、レジスタをスタックにスピルし、ゴルーチンはパークします。GCは続行します。この正確なシナリオ — 関数呼び出しのない無限ループ — は、2019年の提案が修正するために書かれた教科書的なケースです。

1.3a 実際のGCアルゴリズム:ハイブリッド書き込みバリアを使用するトリコロールマークスイープ

上記のすべて(1.3)は、ゴルーチンがGCのためにいつ停止するかをカバーしています。このサブセクションは、GCが実際に行っていることをカバーしています — src/runtime/mgc.go(ファイル先頭のドキュメントコメント)とsrc/runtime/mbarrier.go(ファイル先頭のドキュメントコメント)から直接読み取り、記憶からの要約ではありません。

mgc.goが直接述べていること、行ごと:

// GCはミュータター・スレッドと並行して実行され、型精度(または正確)であり、複数の
// GCスレッドが並列で実行されることを許可します。これは書き込みバリアを使用する並行マーク・アンド・スイープです。これは
// 非世代別であり、非コンパクション型です。

テイクアウェイ:

  • 「並行マーク・アンド・スイープ」 — マークフェーズ(ライブオブジェクトの検出)とスイープフェーズ(デッドオブジェクトの回収)の両方が、プログラム自身のゴルーチンと並行して実行されます。単に互いに並行して実行されるわけではありません。
  • 「非世代別」 — GoのGCは、ほとんどのJVM/V8 GCが使用する若い/古い世代の分割とは異なり、若い/古いオブジェクトを異なるヒープに分離して異なるレートでスイープしません。各GCサイクルは、ライブセット全体をスキャンします。これは明示的な設計上のトレードオフであり、見落としではありません。ソースはその選択の根拠を示していません。
  • 「非コンパクション型」 — デッドオブジェクトはインプレースで解放されます。Goは、コンパクションコレクタ(ZGCなど)が行うように、ヒープをデフラグするためにライブオブジェクトを移動しません。これは、Goのスタックマップ/ポインタ追跡メカニズム(パート1.3)が、オブジェクトが飛行中に移動するのを処理する必要がない理由でもあります — 移動するコレクタ(ZGCなど)よりも複雑さが1つ減ります。

3色抽象化、マークフェーズのウォークスルー(mgc.go、ステップ2b–2d)と、同じファイルにある明示的な不変条件コメントから:

// この時点で、すべてのPは書き込み
// バリアを有効にしており、それによって
// 白から黒への不変条件を維持しています。

オブジェクトは概念的に白(まだ訪問されていない — ゴミと推定される)、灰色(訪問済みだが、それ自身のポインタはまだスキャンされていない)、または黒(訪問済みかつそれ自身のポインタはすべてスキャン済み)です。マークフェーズのジョブは、灰色オブジェクトをスキャンして、それらがなくなるまで歩くことです — その時点で、到達可能なすべてが黒になり、まだ白いすべてがゴミになります。保護されている不変条件 — 「白から黒へのものはない」 — は、黒いオブジェクト(すでに完全にスキャンされた)が、白いオブジェクトが最初にシェードされることなく、直接白いオブジェクトへのポインタを決して獲得してはならないということです。その不変条件が違反された場合、GCはマークを完了しても、まだ白いオブジェクトを見ている可能性があり、ミュータター(実行中のプログラム)がまだライブ参照を持っているものを解放してしまう可能性があります。これは、以下の書き込みバリアメカニズムが存在する理由である正確な正しさのプロパティです。

書き込みバリア自体、mbarrier.goの疑似コードより:

// Goは、上書きされる参照を持つオブジェクトをシェードするYuasaスタイルの削除
// バリアと、参照が書き込まれるオブジェクトをシェードするDijkstra挿入バリアを組み合わせたハイブリッドバリアを使用します。
//
//     writePointer(slot, ptr):
//         shade(*slot)
//         if current stack is grey:
//             shade(ptr)
//         *slot = ptr

そして、なぜ両方の部分が必要なのかという理由が、ソースに3つの番号付きケースとして記載されています:

// 1. shade(*slot) は、ミュータターがオブジェクトへの唯一のポインタを
// ヒープからスタックに移動することによって、オブジェクトを隠すのを防ぎます。
// 2. shade(ptr) は、ミュータターがオブジェクトへの唯一のポインタを
// スタックからヒープ内の黒いオブジェクトに移動することによって、オブジェクトを隠すのを防ぎます。
// 3. ゴルーチンのスタックが黒になったら、shade(ptr) は不要になります。

それはファイルドキュメントコメントからの疑似コードです。それを実行する実際のコード — typedmemmove、Goのポインタを含むすべての構造体コピーが通過する関数 — は、単なる意図されたドキュメントではなく、実際のランタイムチェックによってゲートされた同じ考え方を示しています:

//go:linkname typedmemmove
//go:nosplit
func typedmemmove(typ *abi.Type, dst, src unsafe.Pointer) {
	if dst == src {
		return
	}
	if writeBarrier.enabled && typ.Pointers() {
		// これは常に型typの完全な値をコピーするため、
		// typを最適化として渡しても安全です。bulkBarrierPreWriteのコメントを参照してください。
		bulkBarrierPreWrite(uintptr(dst), uintptr(src), typ.PtrBytes, typ)
	}
	// ここに競合状態があります:他のゴルーチンが
	// srcに書き込むことができる場合、書き込みバリアを実行した後、
	// メモリコピーを実行する前にsrc内のポインタを変更する可能性があります。
	// これは、その
	// 他のゴルーチンによる書き込みも書き込みバリアを伴う必要があるため安全です。
	// 最悪の場合、srcにあった古いポインタを不必要にグレーにしただけです。
	memmove(dst, src, typ.Size_)
}

疑似コードだけでは示せない2つの点:チェックはwriteBarrier.enabled && typ.Pointers()です — コピーされている型が実際にポインタを含んでいる場合にのみバリアが実行されます。したがって、プレーンな整数の構造体をコピーしてもコストはかかりません。そして、バリア呼び出し(疑似コードのshade(*slot)/shade(ptr)作業を行うbulkBarrierPreWrite)は、実際のコピーを実行するmemmoveの直前に行われます — その直下のコメントは、バリアとコピーの間のsrcの競合状態がなぜ安全なのかを説明しています:他のゴルーチンのsrcへの書き込みは、すでに独自のバリアを通過しているため、最悪の場合、オブジェクトが不必要にグレーになるだけで、決して見逃されることはありません。

テイクアウェイ: 書き込みバリアは、並行マークフェーズ中のすべてのポインタ書き込みの周りにコンパイラが挿入するコードです — JVMのポールページ(パート3.5.2)のようなハードウェアメカニズムではなく、ソフトウェアインストルメンテーションコストであり、gcphase == _GCmark(マーク開始時にgcBlackenEnabledを有効にし、スイープ開始時に無効にするmgc.goのフェーズ遷移コードで確認済み)の間のみ支払われます。2つの部分は、オブジェクトが「失われる」可能性のある2つの方向を保護します:すでにスキャンされた(黒い)ヒープ部分からオブジェクトへの唯一のポインタを削除すること(ケース1、Yuasaスタイル)、またはGCがそれを見る前にミュータター自体が自身のスキャンされていないスタックから黒いオブジェクトへのポインタを移動すること(ケース2、Dijkstraスタイル)。ケース3は、ソースが自身の最適化を説明している部分です — あるゴルーチンのスタック全体がスキャンされると(黒くなる)、そのスタック上の何もシェードされていないポインタを隠すことができないため、挿入部分は冗長になります。

未解決の質問: gcMarkDone(上記では言及されているが示されていない)のマークワーク・スティーリング/分散終了アルゴリズム、および並行スイープの各スパンのロッキングスキーム — これら2つのファイルではカバーされていません。

1.4 チェックポイント

これが修正した実際の失敗を追跡してください:1.14より前、関数呼び出しが内部にないfor {}。何が具体的にブロックされ、どれくらいの時間ブロックされましたか?(回答:mgc.go内の任意のstopTheWorldWithSema呼び出し — つまり、すべてのGCマークまたはスイープ終了フェーズ — は無期限にブロックされました。なぜなら、ゴルーチンは同期プリエンプションが依存するスタック境界チェックに決して到達しなかったからです。これはレイテンシの不便さではなく、無制限の停止でした。)


パート2 — Kotlin

このセクションで直接参照したソース:kotlin.coroutines.Continuation および kotlin.coroutines.intrinsics(JetBrains/kotlin、stdlib — この部分は言語レベル)、および kotlinx.coroutines.CoroutineDispatcher / kotlinx.coroutines.scheduling.CoroutineScheduler(Kotlin/kotlinx.coroutines — この部分はライブラリであり、コンパイラや言語仕様ではありません)。

この分割は、以前のドラフトからの修正です:suspendとCPS変換はコンパイラ+stdlibです。Dispatchers、Job、CoroutineScope、構造化並行処理、および実際のスレッドプールスケジューラはkotlinx.coroutines、JetBrainsが公開したライブラリですが、Kotlin自体の一部ではありません — 依存関係なしでsuspend関数を記述できます。それは、ディスパッチャ、構造化キャンセル、async/awaitスタイルのビルダー、またはFlowが必要になるまで必要ありません。

2.1 コンパイラ+stdlibレイヤー:suspendの実際の意味

Kotlinは主にJVM上で実行されます。JVMのスレッドモデルを変更することはできません — JVMスレッドはOSスレッドです。利用可能なレバーは、それらの使用数を減らすことです。つまり、サスペンドされた計算がスレッドのスタックを保持しないようにすることです。

メカニズムはCPS(Continuation-Passing Style)であり、実際のコンパイル対象インターフェースはkotlin.coroutines.Continuationで、stdlibで定義されています:

public interface Continuation<in T> {
    public val context: CoroutineContext
    public fun resumeWith(result: Result<T>)
}

それが完全なプリミティブです。ABIレベルでは、suspend関数は、追加の末尾のContinuationパラメータを取り、Any?を返す通常のJVMメソッドです — 結果、またはサスペンドした場合はセンチネルCOROUTINE_SUSPENDED(kotlin.coroutines.intrinsics、stdlibで定義)です。suspendCoroutineUninterceptedOrReturnは、生の継続を上にサスペンションプリミティブを構築するライブラリ作成者に公開するstdlibの組み込み関数です。

コンパイラは、Continuationを実装するステートマシンオブジェクトをフィールドに持つsuspend関数の本体を変換します。labelフィールドは進行状況を追跡し、ローカル変数はフィールドにリフトされます。大まかに言うと:

suspend fun fetchAndProcess() {
    val data = fetch()
    val result = process(data)
    save(result)
}
class FetchAndProcessContinuation(val completion: Continuation<Unit>) : Continuation<Any?> {
    var label = 0
    var data: Data? = null

    override fun resumeWith(result: Result<Any?>) {
        when (label) {
            0 -> { label = 1; fetch(this) }
            1 -> { data = result.getOrThrow() as Data; label = 2; process(data, this) }
            2 -> { save(result.getOrThrow() as Result); completion.resumeWith(Result.success(Unit)) }
        }
    }
}

関数はブロックするのではなく(スレッドを解放して)返ります。ヒープ上の継続オブジェクトは、再開に必要な状態を保持します。これらすべて — Continuation、CPS変換、suspendキーワード — はKotlin言語とコンパイラの一部であり、任意の並行処理ライブラリに依存しません。これは、例えば、kotlinx.coroutines依存関係がまったくない最小限の環境でもsuspend関数が正常に機能する理由です。それらが機能するためには、それらを駆動するContinuationを実装するものが何らかの形で必要です。

launchを追跡すると、チェックポイント2.4のDispatchedContinuationがどこで構築されるかという未解決の質問が解決されます:

fun main() = runBlocking {
    launch {
        println("A")
        delay(1000)   // サスペンドポイント
        println("B")
    }
}

launch(kotlinx.coroutinesビルダー、ライブラリレイヤー)はラムダを受け取ります。コンパイラはすでにそれをステートマシンに変換しています。大まかに言うと:

class LambdaContinuation : Continuation<Unit> {
    var label = 0
    override fun resumeWith(result: Result<Unit>) {
        when (label) {
            0 -> { println("A"); label = 1; delay(1000, this) } // ここで返る
            1 -> { println("B") }
        }
    }
}

launchは、それを呼び出す前に、そのステートマシンをDispatchedContinuation(パート2.4a)でラップします。実行がdelay(1000)に達すると、関数はすぐに返ります — スレッドはブロックされず、タイマーがセットされます。1000ms後にタイマーが発火すると、何かが同じDispatchedContinuationオブジェクトのresumeWithを呼び出します。そのresumeWithオーバーライド(パート2.4a)はdispatcher.safeIsDispatchNeededをチェックし、必要であればディスパッチャのスレッドプール経由で再開をルーティングします。これにより、ラップされた継続のresumeWithが呼び出され、label = 1に戻って「B」を出力します — 「A」を出力したスレッドとは完全に異なるスレッドである可能性があります。

協調的な部分:コンパイラはdelayがsuspend呼び出しであるため、再開可能なポイントをdelayでのみ挿入しました。ループ内にサスペンド呼び出しがないlaunch { while (true) {} }には、ループ本体内にステートマシントランジションがありません — Goのfor {}例とは異なり、外部から割り込むことができるものはありません。これは、ループ本体が何を行うかに関係なく、外部から割り込むことができるものです。

2.2 なぜこれがサスペンションを協調的にするのか

コンパイラは、コンパイル時に実行がサスペンドする可能性のあるすべてのポイントを知っている必要があります — suspendがキーワードである理由であり、ランタイムアノテーションではない理由です。コルーチンの本体がループ内でサスペンド関数を呼び出さない場合、コンパイラはその場所にステートマシントランジションを挿入しないため、強制するリターン/譲渡ポイントがありません。外部からそれを割り込むことができる、GoのSIGURGに類似したメカニズムはありません — コルーチンオブジェクトの外部にあるものは、割り込むためのものとして作成されていません — コンパイラ生成のステートマシン、生のネイティブスレッドレジスタ状態ではなく、サスペンションの単位であり、ソースコードが実際にサスペンド可能とマークしたポイントにのみ存在します。

2.3 ライブラリレイヤー:kotlinx.coroutinesとそれが追加するもの

継続だけではサスペンションが得られますが、コードがどこで再開するか、キャンセル、または構造化されたライフタイムについては何も得られません。それがkotlinx.coroutinesの目的です:

  • CoroutineDispatcher はContinuationInterceptorを実装します — これは、継続がどのスレッドで再開するかを決定するものです。Dispatchers.DefaultとDispatchers.IOが一般的なものです。
  • CoroutineScheduler(kotlinx-coroutines-core/jvm/.../scheduling/)は、Dispatchers.Default/IOの背後にある実際の(スレッドプール)です。そのドキュメントコメントは、設計上の系譜について明確です:

「単一スロットLIFOバッファの元のアイデアは、D. VyukovによるGolangランタイムスケジューラに由来します。それは『十分に公平』で、パフォーマンスが高く、一般的に受け入れられていることが証明されており、当初はコルーチンスケジューラにとって重要なインスピレーションソースでした。」

具体的には:ワーカーごとのローカル実行キュー、ワーカーのキューが空になったときのワークスティーリング、およびプール外から送信されたタスク用のグローバルキュー — GoのPごとのローカル実行キューとワークスティーリング(proc.goのfindRunnable)と同じ形状です。これは直接の告白による収束進化であり、独立した設計ではありません — Kotlinの著者はGoのスケジューラを読み、完全に異なる基盤(GoroutineではなくJVMスレッド)のためにその形状を再利用しました。

実際のdispatch関数、それを説明するドキュメントコメントだけでなく:

fun dispatch(block: Runnable, taskContext: TaskContext = NonBlockingContext, fair: Boolean = false) {
    trackTask() // これは仮想時間サポートのために必要です
    val task = createTask(block, taskContext)
    val isBlockingTask = task.isBlocking
    val stateSnapshot = if (isBlockingTask) incrementBlockingTasks() else 0
    // タスクをローカルキューにサブミットし、結果に応じて動作を試みます
    val currentWorker = currentWorker()
    val notAdded = currentWorker.submitToLocalQueue(task, fair)
    if (notAdded != null) {
        if (!addToGlobalQueue(notAdded)) {
            throw RejectedExecutionException("$schedulerName was terminated")
        }
    }
    if (isBlockingTask) {
        signalBlockingWork(stateSnapshot)
    } else {
        signalCpuWork()
    }
}

これは、ドキュメントコメントが説明するローカルキュー優先、グローバルキューをオーバーフローとして扱うポリシーを具体化したものです:submitToLocalQueueは呼び出し元のワーカー自身のキューを最初に試みます(安価で競合のないパス)。それが失敗した場合(notAdded != null — ローカルキューがいっぱい)、タスクは共有され、競合するキューであるaddToGlobalQueueにフォールバックします。これは、すべてのアイドルワーカーもチェックするキューです。ブロッキング対CPUの区別(signalBlockingWork/signalCpuWork)はKotlin固有です — GoのGMPモデルには同等の分割がありません。なぜなら、システムコールでブロックされたゴルーチンは、事前にスケジューラによって分類されるのではなく、Pを解放するだけだからです(パート1.2)。

  • Job、CoroutineScope、構造化並行処理 — スコープが子プロセスがまだ実行中に完了できないこと、および親をキャンセルするとすべての子がキャンセルされることを保証する、親/子のキャンセルツリー。これはKotlinがフォークジョインセマンティクスに最も近いものですが、それはコンパイラレベルの機能ではなく、継続の上にレイヤー化されたオプトインライブラリの動作です。
2.4 GCの結果

Kotlin/JVMのGCは、基盤となるJVM GC(G1、ZGCなど)のいずれかです。コルーチンはGCアルゴリズムを変更しません — それらは、特定のOSスレッドで特定の瞬間に実行されるものを変更し、ヒープに継続オブジェクトを追加します(呼び出しごとにサスペンドポイントごとに1つの割り当てですが、JVM JITは短命のものを削除できる場合があります)。サスペンションは、Goのスタックマップ(パート1.3)やHotSpotのポールページ(パート3.5)のようなGCセーフポイント問題を作成しません。なぜなら、JVMセーフポイントは、コルーチンサスペンションとは完全に直交する、別のJIT挿入ポーリングメカニズムだからです — このスタック上の実際のGC関連メカニズムであるHotSpotのセーフポイントポーリングがどのように機能するかについてはパート4を参照してください。コルーチンメカニズム自体ではありません。

2.4a ContinuationとDispatchedContinuation、ソースより

直接読み取り:kotlin/libraries/stdlib/src/kotlin/coroutines/Continuation.kt、kotlin/libraries/stdlib/src/kotlin/coroutines/intrinsics/Intrinsics.kt、kotlinx.coroutines/kotlinx-coroutines-core/common/src/internal/DispatchedContinuation.kt。

Continuation.kt、インターフェース全体、情報が失われるため短いためそのまま引用:

public interface Continuation<in T> {
    public val context: CoroutineContext
    public fun resumeWith(result: Result<T>)
}

テイクアウェイ: stdlibの「サスペンドされた計算」の契約は正確に2つです — コンテキストバッグ、および結果が準備できたときに呼び出すメソッド。ここにはスレッド、ディスパッチャ、またはスケジューリングに関する言及はありません:スレッド配置はコンパイラレベルの懸念事項ではありません。なぜなら、コンパイラが生成するインターフェースにはそれ用のスロットがないからです。

Intrinsics.kt、実際のサスペンションプリミティブ:

public suspend inline fun <T> suspendCoroutineUninterceptedOrReturn(
    crossinline block: (Continuation<T>) -> Any?
): T {
    contract { callsInPlace(block, InvocationKind.EXACTLY_ONCE) }
    throw NotImplementedError("Implementation of suspendCoroutineUninterceptedOrReturn is intrinsic")
}

テイクアウェイ: 本体はthrowです — この関数はKotlinソースに実際の実際の実装がまったくありません。ファイル内のその上のコメント(上記には再現されていません)は、実装が組み込みであると述べています:コンパイラはこの特定の関数を名前で認識し、呼び出しを生成されたバイトコードに直接置き換えます。CPS変換は、通常の言語機能の上に構築されたライブラリトリックではありません — コンパイラはこの関数を特別にケース処理しています。

未解決の質問: 組み込み自体のコンパイラのコード生成は、このファイルからは見えません — シグネチャと、特別なケース処理が発生するというドキュメントコメントのみです。

DispatchedContinuation.kt、パート2.1のラップ主張を確認:

internal class DispatchedContinuation<in T>(
    @JvmField internal val dispatcher: CoroutineDispatcher,
    @JvmField val continuation: Continuation<T>
) : DispatchedTask<T>(MODE_UNINITIALIZED), CoroutineStackFrame, Continuation<T> by continuation {

テイクアウェイ: DispatchedContinuationは、dispatcherフィールドと元のコンパイラ生成のcontinuationの両方をデリゲート(Continuation<T> by continuation)として保持します。それはコンパイラの継続を置き換えるのではなくラップします — コンパイラはプレーンなContinuationを生成します。kotlinx.coroutinesは、resumeWithが呼び出される前に、それをディスパッチャ対応クラスでラップします。

実際のディスパッチ決定 — 上記のフィールド宣言が暗示するスレッドホップが実際に発生する場所 — は、DispatchedContinuation自身のresumeWithオーバーライドです:

override fun resumeWith(result: Result<T>) {
    val state = result.toState()
    if (dispatcher.safeIsDispatchNeeded(context)) {
        _state = state
        resumeMode = MODE_ATOMIC
        dispatcher.safeDispatch(context, this)
    } else {
        executeUnconfined(state, MODE_ATOMIC) {
            withCoroutineContext(context, countOrElement) {
                continuation.resumeWith(result)
            }
        }
    }
}

ラップされた操作が完了するたびに、これが実際に実行されるものです(stdlibのプレーンなContinuation.resumeWithインターフェースメソッドではなく、パート2.4a)。それはディスパッチャにsafeIsDispatchNeeded(context)を尋ねます — 現在のスレッドがすでに正しい場合(例えば、アンコンファインドディスパッチャ、またはすでに正しいスレッドでの再開)、それはラップされたcontinuation.resumeWith(result)に直接呼び出され、スレッドホップはありません。それ以外の場合は、結果を_stateに保存し、dispatcher.safeDispatch(context, this)を呼び出します。これは、ディスパッチャのスレッドプール(パート2.3のCoroutineScheduler)にこの同じオブジェクトをスケジュールしてそこで再開させるための具体的なメカニズムです。これは「ディスパッチャが再開するスレッドを決定する」という背後にある具体的なメカニズムです(チェックポイント2.5の回答) — resumeWith内のランタイムブランチであり、ステートマシンのコンパイラは何も知りません。

未解決の質問: kotlinx.coroutinesのlaunch/async実装内のDispatchedContinuationが構築される実際のソース行 — パート2.1のlaunch/delayウォークスルーはメカニズムを概念的に追跡しますが(何がラップされ、いつ再開し、どのスレッドで)、実際のビルダーソースファイルは建設呼び出しサイトをラインフォーラインで確認するためにまだ読まれていません。

2.5 チェックポイント

サスペンドするコルーチン呼び出しには2つの継続が存在します:コンパイラは1つを自動生成します。ディスパッチャは、Continuation.resumeWithの内部で、またはkotlinx.coroutinesがそれをラップするどこかで、再開するスレッドを決定しますか?(回答:kotlinx.coroutinesは、コンパイラ生成の継続をContinuationInterceptor.interceptContinuationでラップし、実際のresumeWith呼び出しをディスパッチャのスレッドプールにルーティングするDispatchedContinuationを生成します。コンパイラのステートマシンは独自の Сレッド親和性ロジックを持っていません — それは完全にライブラリレイヤーです。)


パート3 — BEAM

このセクションで直接参照したソース:erts/emulator/beam/erl_process.c、erts/emulator/beam/erl_vm.h、erts/emulator/beam/emu/beam_emu.c、erts/emulator/beam/erl_gc.c — erlang/otp、masterブランチ。

3.1 制約

Erlangの元の設計質問(Joe Armstrong)はパフォーマンスについてではありませんでした — それは:システムをダウンせずに実質的に永遠に実行できるようにするにはどうすればよいか?答えは:障害は封じ込められなければならず、それには分離が必要であり、それには何も共有しないことが必要です。

3.2 設計:プロセスごとのヒープ、共有メモリなし

BEAMプロセス(VM管理、OSプロセスではない)はメモリを共有しません。それぞれが独自のヒープと独自のGCを持っています。beam_emu.cのprocess_mainはこれを具体化します — インタプリターループのレジスタは、JVMヒープやGoヒープがスレッド/ゴルーチン間で共有される方法とは異なり、OSスレッドごとではなく、文字通りプロセスごとの状態です:

/* Pointer to X registers: x(0)..x(N). */
register Eterm* reg REG_xregs = NULL;

/* Top of heap (next free location); grows upwards. */
register Eterm* HTOP REG_htop = NULL;

/* Stack pointer. Grows downwards; points
 * to last item pushed (normally a saved
 * continuation pointer). */
register Eterm* E REG_stop = NULL;

スケジューラスレッドにスワップされる各プロセスは、独自のヒープポインタ(HTOP)、独自のスタックポインタ(E)、および独自のレジスタファイル(reg)を持ちます — ここにあるものは、JVMヒープやGoヒープがスレッド/ゴルーチン間で共有される方法とは異なり、プロセス間で共有されません。別のプロセスにメッセージを送信すると、データがターゲットのヒープにコピーされます(大きなバイナリは例外 — コピーを避けるために共有バイナリヒープで参照カウントされます)。

プロセスは他のプロセスのスタックやヒープを見ることができないため、共有セーフポイントの問題はありません:スケジューラは、1つのプロセスをプリエンプトするために他のプロセスのメモリ内のポインタの有効性を推論する必要がありません。これは、Goのスタックマップ(パート1.3)とHotSpotのポールページ(パート3.5)の両方が存在し、BEAMが構造的に必要としない正確な制約です。

3.3 主要概念:リダクションとは何か

メカニズムの前に、用語自体。「リダクション」は、スケジューリングのために発明されたBEAM固有の専門用語ではありません — それは項書き換え/リダクションセマンティクスに由来します。プログラミング言語理論では、式の評価は「リダクションステップ」のシーケンスであり、各ステップは項を最終値に近づけるように書き換えます(ラムダ計算の「ベータリダクション」と同じ根源的な意味 — Erlangのインタプリタは、構造的には項書き換えマシンであり、BEAMは文字通り「Bogdan/Björn’s Erlang Abstract Machine」の略で、その書き換えを実行する抽象マシンです)。BEAMリダクションは、その考え方のスケジューリング射影です:インタプリタの作業単位ごとに課金される1つの会計単位 — プロセスの予算から、インタプリタが1つディスパッチするたびに差し引かれる、ほぼ1つの関数呼び出し、1つのBIF(組み込み関数)呼び出し、または同等のプリミティブ操作です。

それは意図的に固定された壁時計単位ではありません。それは、スケジューラがハードウェアタイマー割り込みを必要とせずに、「このプロセスはどれだけの作業を行ったか」をプロセス間で比較できるようにする抽象化です(パート0のOSタイマー割り込みプリエンプションと比較)。 — インタプリタ自体が、作業を行っている最中に、インラインでカウントしているものです。それが安価な理由です:個別のポーリング命令(HotSpotのポールページ、パート3.5.2と比較)や外部割り込み(GoのSIGURG、パート1.3と比較)はありません — デクリメントは、すでに発生していた命令ディスパッチに折り込まれています。

これが単なるスケジューリング専用の概念ではないことを確認するために、erl_process.hもリダクションを実際の測定単位として使用し、経過壁時計時間を同等のリダクションカウントに変換します(これは、スケジューラの会計を整合させるために、ブロックされた時間に対してプロセスに課金するために使用されます):

ErtsMonotonicTime time = end - start;
...
time = ERTS_MONOTONIC_TO_USEC(time);
if (time == 0)
    return (Sint64) 1; /* At least one reduction */
/* Currently two reductions per micro second */
time *= (CONTEXT_REDS-1)/1000 + 1;
return (Sint64) time;

そして、プロセス構造体自体(erl_process.h)は、fcallsをライブ予算として正確に文書化しています:

Sint32 fcalls;   /* Number of reductions left to execute.
                  * Only valid for the current process while it
                  * is executing. */

したがって:リダクションは、項書き換え理論から名前を受け継いだ、BEAMの「完了した作業」の単位であり、インタプリタでほぼ1つの関数/BIF呼び出しとして具体化され、プリエンプションのタイミングを決定するため(3.3以下)と、実際の経過時間を比較可能なスケジューリング会計に変換するために使用されます。

3.3a リダクション対セーフポイント

それらは異なる質問に答えます。その違いが比較を有用にする正確な理由です:

  • セーフポイント(Go、パート1.3;JVM、パート3.5)は、「コードのどこでこのスレッドの状態を検査/一時停止するのが有効か?」 という質問に答えます — 空間的な質問です。ほとんどの命令はセーフポイントではありません。コンパイラ/ランタイムは、共有ヒープ、レジスタベースの実行モデルではほとんどの命令の中間点が完全に既知でGCで検査可能なマシン状態を持っていないため、それらが少ないものを特別にマークまたは検出する必要があります。
  • リダクションは、「このプロセスは譲渡されるべきほど多くの作業を行ったか?」 という質問に答えます — 予算の質問であり、場所の質問ではありません。

リダクションが個別のセーフポイント概念を必要としない理由は、BEAMのインタプリタでは、すべてのリダクション境界がすでに有効なセーフポイントであることです — プロセス状態(ヒープポインタ、スタックポインタ、レジスタ)は、インタプリタループ(process_main、3.2)が実行を部分的に更新された状態でディスパッチ間で残すことがないため、命令間では常に完全に既知で一貫しています。ポインタが一時的に生の整数として格納されるような「命令の中間、ポインタが一時的に生の整数として格納される」という危険はありません(Goのunsafe.Pointer→uintptrケース、パート1.3)。なぜなら、コンパイル済みマシンコードにあるような、同等の安全でない低レベルのエスケープハッチは、通常のBEAMバイトコード実行にはないからです。

したがって、正確な関係は次のようになります:GoとJVMでは、セーフポイントは実行ポイントの疎なサブセットであり、ほとんどのポイントが安全ではないため特別に構築されます。BEAMでは、命令間のすべてのポイントはすでに安全です。したがって、残りの唯一の質問はスケジューリングポリシーです — どれくらいの頻度で実際にその安全性に基づいてアクションを実行するか — そして、それがリダクションカウンターが答えるものです。 リダクションカウントは、もともと問題ではなかった実行モデルの上にレイヤー化された「いつ行動するか」のポリシーです — これは、パート3.2の分離制約の直接の結果です:共有、GC管理メモリは、「どこで行動するのが安全か」をそもそも難しくしているものであり、BEAMはそれをメモリモデルレベルでオプトアウトしたのであって、スケジューリングレベルではありません。

3.3.1 プリエンプション:リダクションカウント、実際の定数付き

erl_vm.hは予算を直接定義しています:

#define CONTEXT_REDS 4000            /* Swap process out after this number */

(注:これは現在のソース値です。古いErlangのドキュメントやブログ記事は一般的に約2000リダクションを引用しています — その数字は古いです。ターゲットとするバージョンの定数を確認してください。このドキュメントが1年後であっても、記憶された数字を信頼するのではなく。)

デクリメントメカニズムは、インタプリタ自身の削減カウンターFCALLSであり、その宣言で直接文書化されていますprocess_main:

/* Number of reductions left.  This function
 * returns to the scheduler when FCALLS reaches zero. */
register Sint FCALLS REG_fcalls = 0;

各BEAM命令(ほぼ:1つの関数呼び出し、1つの同等の作業単位)はFCALLSをデクリメントします。ゼロになると、process_mainはスケジューラに制御を返し、消費されたリダクションカウントをerts_scheduleに渡します:

reds_used = REDS_IN(c_p) - FCALLS;
...
c_p = erts_schedule(NULL, c_p, reds_used);

erl_process.cは、CONTEXT_REDSから直接いくつかのスケジューラチューニング定数も導き出します — 例えば、実行キュー間の負荷分散の頻度のためのERTS_RUNQ_CHECK_BALANCE_REDS_PER_SCHED (2000*CONTEXT_REDS)、およびERTS_PROC_MIN_CONTEXT_SWITCH_REDS_COST (CONTEXT_REDS/10) — リダクションが「どれだけの作業が行われたか」のスケジューラの普遍的な単位であることを確認します。単なるプリエンプショントリガーではありません。

シグナル、スタックマップ、ポールページはありません:ここでのプリエンプションは、各命令ディスパッチの一部としてチェックされるプレーンな整数カウンターであり、ホットループにすでにインライン化されているため安価であり、外部のボルトオンメカニズムではありません。

具体的な例を追跡:

loop() -> loop().

main() ->
    spawn(fun loop/0),
    spawn(fun() -> io:format("still runs fine~n") end).

spawn(fun loop/0)は決して返らないプロセスを開始します — Goのfor {}に相当するBEAMバージョンです。Go 1.14より前とは異なり、これはシステムをハングさせません:process_mainのインタプリターループは、loop/0の呼び出しを自身への1つのリダクションとしてディスパッチし、そのたびにFCALLS(パート3.3.1)をデクリメントします。FCALLSがゼロになると — CONTEXT_REDS(デフォルトで4000)回のディスパッチされた呼び出しの後 — process_mainはerts_schedule(パート3.5a)に制御を返し、ループしているプロセスをランキューに戻し、次の準備完了プロセスを選択します。「still runs fine」を出力する2番目のspawnは、無限ループを待つことなく、同じコアでスケジュールされ、完了まで実行されます。loop/0を中断するためにシグナルは送信されませんでした。それは決して長すぎる間実行されなかったため、それを必要としませんでした — ゼロに達したカウンターが中断そのものであり、ループが行うすべての呼び出しにすでに組み込まれています。

各プロセスがヒープを排他的に所有しているため、erl_gc.cはプロセスごとにGCを実行します — 1つのプロセスのGC一時停止は、他のコアで並行して実行されている他のすべてのプロセスには見えません。GoのstopTheWorldWithSema(パート1.3)やHotSpotのグローバルセーフポイント同期(パート3.5.1)のような、VM全体のストップ・ザ・ワールドに相当するものは存在しません:BEAMは、それを必要とする共有GC関連のものが決してないため、VM全体を一度に停止する必要がありません。

3.5 障害モデルは哲学ではなく結果である

プロセスは分離されているため、クラッシュは単にプロセスが終了することです — 構築上、他のプロセスの状態を破損させることはできません。これが「クラッシュさせる」ことが実行可能である理由です:スーパーバイザは失敗したプロセスを再起動し、残りのシステムは証明可能に影響を受けません。なぜなら、分離が、他のすべて(プロセスごとのGC、リダクションカウントされたプリエンプション、コピーオンセンドメッセージング)がそれに従う最初の制約だったからです。後付けではありません。

3.5a erts_schedule:デスケジューリング/リスケジューリングハンドオフ

直接読み取り:erts/emulator/beam/erl_process.c、Process *erts_schedule(...)。

Process *erts_schedule(ErtsSchedulerData *esdp, Process *p, int calls)
{
    ...
    if (ERTS_USE_MODIFIED_TIMING()) {
        context_reds = ERTS_MODIFIED_TIMING_CONTEXT_REDS;
    }
    else {
        context_reds = CONTEXT_REDS;
    }
    ...
    /*
     * Clean up after the process being scheduled out.
     */
    if (!p) {  /* NULL in the very first schedule() call */
        is_normal_sched = !esdp;
        ...
        rq = erts_get_runq_current(esdp);
        actual_reds = reds = 0;
        erts_runq_lock(rq);
    }
    else {

テイクアウェイ: これはprocess_main(3.3.1)がFCALLSがゼロになると呼び出す関数です — erts_scheduleは、デスケジューリングされるプロセスのクリーンアップと、次のプロセスの選択と返却の両方を1つの関数で行います(if (!p)ブランチは、前のプロセスがないブートストラップケースです)。ERTS_USE_MODIFIED_TIMING()ブランチは、CONTEXT_REDS(4000)が常にリテラルな数値ではないことを意味します — 異なる定数を持つ「変更されたタイミング」モードがあります。3.3.1の4000という数字はデフォルトであり、無条件の定数ではありません。

未解決の質問: ERTS_USE_MODIFIED_TIMING()が何をゲートするか、および上記で示されたクリーンアップセクション(優先度レベル、実行キューの移行)以降のerts_schedule内の次のプロセス選択ロジック — 関数の開始部分のみがここでカバーされています。

3.6 チェックポイント

CONTEXT_REDS = 4000で、1リダクション ≈ 1関数呼び出しと仮定すると、Goの1.14より前のゴルーチンがスケジューラをスターブさせることができたように、単一のBEAMプロセスはまだスケジューラをスターブさせることができますか?チェックがトリガーされるものを調べてください。(回答:同じ方法ではできません — チェックはprocess_mainのインタプリターループ内のすべての命令ディスパッチに組み込まれており、Goの古いスタック境界チェックのように関数呼び出し境界に到達することによってゲートされるわけではありません。命令がディスパッチされてFCALLSをデクリメントする文字通りのゼロの無限ループの本体がないため、BEAMにfor {}に相当するものはありません。まだスケジューラースレッドをブロックできる1つのことは、制御をVMに戻さない真にブロックするNIF/ネイティブ呼び出しです — Pを解放せずにブロックするシステムコール中のゴルーチンに相当します。)


パート3.5 — JVMセーフポイント(Kotlinがその上に座っているメカニズムであり、Goのアプローチとの真の対比)

このセクションは、パート2.4が言及したメカニズムであり、Goのアプローチとの正しい対比点です — オプションの脇道ではありません。以前のドラフトでは完全に欠落していました。

3.5.1 HotSpotにおけるセーフポイントの正確な意味

safepoint.hppのヘッダーコメント:

// VMThreadは、SafepointSynchronize::begin/endメソッドを使用して、セーフポイント領域に入り/終了します。beginメソッドは、すべてのJavaThreadをセーフポイントまでロールフォワードします。
//
// JavaThreadは、ThreadSafepointState抽象化(thread.hppで定義)を使用して、セーフポイントにいることを示す必要があります。
//
// Mutex/Condition変数およびObjectLockerクラスは、スレッドがブロック/再開されるときに、enter/exitセーフポイントメソッドを呼び出します。したがって、すべてのmutex enter/exitポイントはセーフポイントでなければなりません。

そして、メカニズム全体を駆動する3状態列挙:

enum SynchronizeState {
    _not_synchronized = 0,   // スレッドはセーフポイントで同期されていません。この値は0のままにしてください。
    _synchronizing    = 1,   // 同期処理中
    _synchronized     = 2    // すべてのJavaスレッドはネイティブで実行中、OSでブロックされている、
                              // またはセーフポイントで停止しています。VMスレッドおよび任意のNonJavaThread
                              // は実行されている可能性があります。
};

これは、GCに隣接するフレームワークを直接確認します:セーフポイントはHotSpotではGC固有のものではありません — それはVMがすべてのJavaスレッドを既知の状態(GC、非最適化、バイアスロック取り消し、スレッドダンプ、クラス再定義)で凍結する必要があるときに使用する一般的なメカニズムです。GCは最も頻繁な消費者であり、唯一のものではありません。

3.5.2 ポーリングページメカニズム — スレッドが停止する必要があることに気づく方法

Goの同期セーフポイント(スタック境界チェックのポイズニング)や非同期セーフポイント(シグナル配信)とは異なり、HotSpotの古典的なメカニズムはメモリポーリングです。safepointMechanism.hppより:

class SafepointMechanism : public AllStatic {
  ...
  static uintptr_t _poll_page_armed_value;
  static uintptr_t _poll_page_disarmed_value;
  static address   _polling_page;
  ...
  struct ThreadData {
    volatile uintptr_t _polling_word;
    volatile uintptr_t _polling_page;
    ...
  };

  // このスレッドがセーフポイントまたはハンドシェイクを処理する必要があるかどうかを確認するために、このメソッドを呼び出します。
  static inline bool should_process(JavaThread* thread, bool allow_suspend = true);

JITコンパイラは、メソッドエントリとループバックエッジで、_polling_pageからのメモリ読み込みを発行します。通常、このページは読み取り専用だがアーム可能としてマッピングされており、読み込みはほぼ無料です(CPUがパイプライン化できる単一のロード)。セーフポイントを要求するために、VMスレッドはポーリングページをアンマップまたは保護します(「アームされた」状態)。そのポーリング命令を実行する最初のエントリ・スレッドは、トラップ — OSがシグナル/例外として配信する実際のページフォルト — をトリガーし、HotSpotのフォルトハンドラがそれをインターセプトしてセーフポイント処理にリダイレクトします。

これはGoとの重要な対比です:HotSpotのメカニズムはメカニズム的には協調的です(スレッドが自身のポーリング命令を実行して気づく必要がある)が、ハードウェアトラップを結びつけることで安価で実質的に非自発的になります — スレッドがポーリングを実行すると、それをスキップすることはできません。しかし、ポーリングポイントにまったく到達しないスレッド(Goのプリ1.14タイトーループ問題に類似)は、まだ停止できません。これは、リンクされたMedium記事が本番環境で測定する「セーフポイントまでの時間」(TTSP)レイテンシです — VMスレッドがページをアームしてから、最後の遅延スレッドがポーリングにヒットしてブロックするまでのギャップです。JITコンパイルコードは、ループバックエッジとメソッドリターン/コールにポーリングポイントを持ちます(コンパイラはループ構造に基づいてメソッドごとに配置を決定します)。インタプリタフレームは、すべてのバイトコードディスパッチでフラグをチェックします。そのため、インタプリタコードはセーフポイントに早く到達しますが、一般的に実行は遅くなります。

3.5.2a 正確なポーリング配置と、セーフポイント/ブロックの区別

このサブセクションの追加ソース(二次的だが正確で帰属表示あり):Gil Teneのmechanical-sympathyメーリングリストでの説明、Nitsan Wakart、「Safepoints: Meaning, Side Effects and Overheads」で再現されています。また、chriskirk.blogspot.com、「What is a Java Safepoint?」およびjpbempel.blogspot.com、「Safety First: Safepoints」も関連しています。

HotSpotは無条件にあらゆる場所にポーリングするわけではありません — ポーリング配置は意図的なトレードオフです。「フラグチェック自体のコストに加えて、'既知の状態'を維持することは、特定の最適化の実装にかなりの複雑さを加える」ため、セーフポイントをより離して配置することは最適化の範囲を広げます。実際のポーリング場所:

  • インタプリタで実行中の2つのバイトコード間のほぼすべての場所
  • C1/C2コンパイルコードの非カウントループバックエッジ(「カウント」ループ — コンパイル時に境界が既知 — はポーリングをスキップできます。なぜなら、JITはそれが終了することを証明できるからです)。
  • コンパイルコードのメソッドエントリ/エグジット(Zingではエントリ、OpenJDKではエグジット) — そしてコンパイラはメソッドがインライン化されるときにこれらのポーリングを完全に削除します。なぜなら、呼び出し元のポーリングがそれをカバーするからです。

-XX:+PrintAssembly出力で、命令コメントの{poll}または{poll return}を検索することで、実際のポーリング命令を見つけることができます — これはブログからの主張だけでなく、実行中のJVMで直接確認できます。

もう1つの正確に述べる価値のある修正:「セーフポイントで」は「ブロックされている」ことを意味しません。 例えばJNIコードは、ブロックされることなくセーフポイントで実行されます(そのJava状態表現は凍結されており、検査可能です)。「ブロックされていることは常にセーフポイントで発生しますが、セーフポイントにいることはブロックされていることを必要としません」 — これは、Goの「ブロックされたセーフポイント」と、ゴルーチンがシステムコール中にいる状態(パート1.3、カテゴリ1)との区別と正確に類似しています:状態はGCで検査可能であり、スレッドが外部から一時停止される必要はありません。

さらに2つのポイントがモデルを正しく一般化します:

  • グローバル対スレッドごとのセーフポイント。 ページ保護トリック(3.5.2)はグローバルメカニズムです — OpenJDKはSTW作業のためにすべてのスレッドを一緒にセーフポイントに連れて行きます。一部のJVM(AzulのZing、いわゆる「チェックポイント」経由)は、グローバル一時停止なしで個々のスレッドをセーフポイントのような状態に連れて行くことができます。これは、GoとBEAMが反対側にいるのと同じ軸です:GoのSTW GCフェーズは必要に応じてグローバルです(パート1.3)、BEAMのプロセスごとのGCはすでに本質的にスレッドごとです(パート3) — Zingのチェックポイントは、共有ヒープランタイム上でHotSpotがBEAM形状のアイデアを借用したものです。
  • 安全でないコードとセーフポイント密度。 セーフポイントはデフォルトで2つのバイトコード間に発生する可能性があるため、GCセーフポイントなしで長時間の実行をしたいJNI/Unsafeコード(例:大きなUnsafe.copyMemory)は、それ自体で定期的なセーフポイント機会にオプトインする必要があります — そうしないと、長いネイティブ呼び出しが、STW作業を開始する前にVMスレッドが待機する「セーフポイントまでの時間」を膨張させる可能性があります。これは、リンクされた「Java Peak Safepoints」記事が本番環境で測定するTTSPレイテンシと正確に同じです。
3.5.2b safepoint.cppのbegin()関数

直接読み取り:src/hotspot/share/runtime/safepoint.cpp、SafepointSynchronize::begin()。

void SafepointSynchronize::begin() {
  assert(Thread::current()->is_VM_thread(), "Only VM thread may execute a safepoint");
  ...
  log_trace(safepoint)("Blocking threads from starting/exiting");
  Threads_lock->lock();
  ...
  _waiting_to_block = nof_threads;
  ...
  log_trace(safepoint)("Arming safepoint using %s wait barrier", _wait_barrier->description());
  arm_safepoint();
  ...
  if (SafepointTimeout) {
    safepoint_limit_time = SafepointTracing::start_of_safepoint()
        + (jlong)(SafepointTimeoutDelay * NANOSECS_PER_MILLISEC);
  }

そしてさらに下に、スレッドがポーリングに間に合わなかった場合に何が起こるか:

  if (AbortVMOnSafepointTimeout && (os::elapsedTime() * MILLIUNITS > AbortVMOnSafepointTimeoutDelay)) {
    for (JavaThreadIteratorWithHandle jtiwh; JavaThread *cur_thread = jtiwh.next(); ) {
      if (cur_thread->safepoint_state()->is_running()) {
        VMError::set_safepoint_timed_out_thread(cur_thread);
        if (!os::signal_thread(cur_thread, SIGILL, "blocking a safepoint")) {
          break;
        }

テイクアウェイ: begin()はThreads_lockを取得するため、アーム中にスレッドが開始または終了できません。次にarm_safepoint()(3.5.2のページ保護操作)を呼び出し、_waiting_to_blockで追跡しながら待機します。HotSpotは、設定可能な遅延を超えた場合に、ポーリングポイントに到達しなかったスレッドに強制的にSIGILLを送信する組み込みの監視タイマー(SafepointTimeout/AbortVMOnSafepointTimeoutDelay)も出荷しています — 本番環境では、スレッドが合理的な時間内にセーフポイントに到達できない可能性があり、VMの答えはハングするのではなく、そのスレッドを意図的にクラッシュさせることです。これは、Goのプリ1.14障害モード(パート1.3)の最も直接的なJVM類似体です:HotSpotにはそれに対する明示的な、ソースから見えるフェイルセーフがありますが、Goの答えは、プリエンプションメカニズムを変更して、スタックしたケースが発生しないようにすることでした。

未解決の質問: arm_safepoint()の待機バリア実装がOSレベルで何をするか(_wait_barrier->description()として言及されているが、ここでは読まれていない) — 「STW要求」から「すべてのスレッドが確認済みパーク」までのメカニズムの次のステップ。

3.5.3 Goがこのアプローチを再利用しなかった理由

Goのランタイムには、HotSpotのC1/C2コンパイラのように、ループごとにポーリング命令を発行するJITはありません — Goは事前にコンパイルされ、プロジェクト自身の試行され却下されたループバックエッジチェック(パート1.3)は、HotSpotのメカニズムのインタプリタスタイルバージョンに機能的に似ています(ページフォルトトリックなし):すべてのループイテレーションで明示的な条件分岐であり、新しいチェックを追加するのではなく、既存の境界チェックをトラップにするようにランタイムがstackguard0を書き換える「パッチング」に近いです。7.8%の低下は、コンパイル済みレベルのコードであるべきものにインタプリタレベルのオーバーヘッドを支払うことと一致しています — HotSpotは、ポーリングをCPUがほとんど隠せるロードにし、それを要求された瞬間にのみ実際のトラップに武器化することで、このコストを回避します。Goのシグナルベースの非同期セーフポイントは、問題を異なる方法で回避します:ゴルーチン自体が実行するポーリングではなく、OSが外部からスレッドを中断し、ゼロの定常コストで、ランタイムはプリエンプションが実際に要求された場合にのみスタックマップルックアップのコストを支払います。

3.5.4 チェックポイント

HotSpotのポーリングとGoのプリ1.14バックエッジチェックの両方で、すべてのループイテレーションに定常コストがかかります。それらがコストを課す方法と、なぜ一方がリリースされ、もう一方が7.8%で測定され却下されたのかという点で、質的な違いは何ですか?(回答:HotSpotのポーリングは、CPUが通常予測/キャッシュできるページに対する単一のメモリロードです — 無条件に支払っても安価であり、JITコンパイルされているため、ホットループごとに選択的に配置されます。Goのバックエッジチェックは、AOTコンパイラによってすべてのループに均一に挿入されたスタックガード変数に対する比較と分岐であり、HotSpotのランタイムプロファイリングによる選択的な配置なしで行われました。)


パート4 — 比較:セーフポイント問題、並べて

GoKotlin (JVM)BEAM
並行処理単位Goroutine (ランタイム管理スタック)Coroutine (コンパイラ変換継続)Process (VM管理、分離ヒープ)
切り替え制御者Goランタイムスケジューラ (GMP)コンパイラ生成ステートマシン + ディスパッチャBEAMスケジューラ (コアごと)
プリエンプションスタイル非協調型 (シグナル, SIGURG) セーフポイントで制約協調型 (サスペンドポイントのみ)非協調型 (リダクションカウント)
メモリモデルゴルーチン間の共有ヒープコルーチン間の共有ヒープ (同じJVMヒープ)プロセスごとの分離ヒープ
GCスコーププロセス全体;STWフェーズはすべてのゴルーチンがセーフポイントにいる必要あり実行中のJVM GCによる;セーフポイントはコルーチンとは無関係な別のJITポーリングメカニズムプロセスごと;1つのプロセスのGC一時停止は他のプロセスに影響しない
不正確なプリエンプションで起こりうることGCが古い/無効なポインタを見る、ライブオブジェクトを収集するN/A — 何も強制的にプリエンプトされないN/A — 破損する共有状態がない
障害封じ込め1つのゴルーチンでのパニックは、回復しない限りプロセスをクラッシュさせる可能性がある構造化並行処理スコープに従って、1つのコルーチンでの例外が伝播する可能性がある構築上、クラッシュは1つのプロセスに分離される

1文での統一: セーフポイント問題は、プリエンプションが非協調的かつメモリが共有されている場合に正確に発生します — Goは両方を持っており、スタックマップとシグナル処理でそれを支払います。BEAMは非協調的なプリエンプションを持ちますが、共有メモリがないため、セーフポイント問題は存在しません。Kotlinは共有メモリを持ちますが、コルーチンの非協調的なプリエンプションがないため、これも問題を回避します。ただし、コルーチンが暴走ループから自身をプリエンプトできないというコストがかかります。


パート5 — GraalVM:そのセーフポイントメカニズムはHotSpotと実際に異なるのか?

直接読み取り:oracle/graal → substratevm/src/com.oracle.svm.core/.../thread/Safepoint.java。

GraalVM Native Image(SubstrateVM)は、JVMバイトコードをネイティブバイナリに事前にコンパイルし、HotSpotを完全に置き換えます。起動時間とメモリフットプリントを大幅に変更し、JIT再コンパイルトリガーのセーフポイント(実行中のJITなし)を削除します。これはKotlinコルーチンサスペンションモデルを変更しません — CPS変換は、GraalVMがバイトコードを見る前にKotlinコンパイラで行われます(パート2)。しかし、セーフポイントメカニズム自体 — パート3.5でHotSpotについてカバーしたものです — SubstrateVMでは実際に異なります。単なる同じアイデアの実装ではなく、単に「まだJVMなので、まだポールページがある」と仮定するのは簡単なので、正確に述べる価値があります。

Safepoint.java自身のクラスレベルドキュメントコメント、それが説明するメカニズム全体が発見のすべてなので引用:

/**
 * Manages the initiation of safepoints. A safepoint is a global state where all Java threads, 
 * except one, are paused so that invasive operations (such as a garbage collection) can execute 
 * without interferences.
 *
 * When a safepoint is requested, one Java thread (the master) acquires the
 * {@link VMThreads#SAFEPOINT_MUTEX}. The master notifies all other threads about the pending
 * safepoint by modifying each thread's {@link SafepointCheckCounter} thread-local.
 *
 * Each Java threads periodically checks the value of its {@link SafepointCheckCounter}. If a
 * safepoint is pending, the thread enters the safepoint slowpath and blocks on the mutex that
 * the master is holding.
 */

そして実際のアーミング操作は、ページ保護ではなく否定を行います:

value = SafepointCheckCounter.getVolatile(thread);
} while (!SafepointCheckCounter.compareAndSet(thread, value, -value));

テイクアウェイ: HotSpotは共有メモリページ(パート3.5.2)を保護することでセーフポイントをアームします — すべてのスレッドのポーリングは同じアドレスに対するロードであり、トラップはハードウェアページフォルトです。SubstrateVMは、CASを使用して各スレッドのカウンター値自体を否定することでセーフポイントをアームします — 共有ページ、ページフォルト、一般的なパスでのシグナルは関与しません。各コンパイル済みメソッドは、定期的にスレッドローカルSafepointCheckCounterをデクリメントします(パート3.5.2aのHotSpotのループバックエッジ/メソッドエントリポーリングの配置を反映していますが、保護されたページを読むのではなく、カウンターが負になるのをチェックします)。スレッドが自身のカウンターが負になったことに気づくと、スローパスを取り、SAFEPOINT_MUTEXでブロックします。これは、構造的にはBEAMのリダクションカウント(パート3.3)よりもHotSpot自身のポールページトラップよりも、スレッドごとのソフトウェアカウンターであり、共有トラップトリガーメモリ領域ではないため、アーキテクチャ的には近いです。ただし、SubstrateVMは依然として根本的にはJVMセマンティクスランタイムであり、プロセス分離ランタイムではありません。それは、同じ「セーフポイント」という名前の下での実際のメカニズムの交換です、化粧的な違いではありません。

未解決の質問: OracleのSubstrateVMエンジニアがHotSpotのポールページアプローチを再利用するのではなく、スレッドごとのカウンターを選択した理由 — ファイルには根拠が記載されていません。可能性のある候補(アーム/デアームサイクルごとにmprotectシステムコールを回避する、アイソレート/マルチテナントネイティブイメージ下でのより良い動作)はソースで確認されていません。

チェックポイント: コルーチンスケジューリングレイテンシがボトルネックの場合、GraalVMは役立ちますか?(回答:いいえ — それはKotlinコルーチン変換のコンパイル時プロパティであり、結果のバイトコードを実行するVMとは無関係です。)別途:GraalVMのセーフポイントメカニズムは、BEAMのセーフポイントメカニズムと同じ理由で、HotSpotと比較して「セーフポイントまでの時間」を削減しますか?(回答:同じ理由ではありません — BEAMの利点は構造的であり、保護すべき共有メモリがまったくありません。SubstrateVMは依然として共有ヒープを持っており、グローバル停止が必要ですが、それはすべてのスレッドが最終的に一緒に停止する必要があるという事実ではなく、各スレッドが要求に気づく方法を変更しただけです。)


パート6 — フラグの背後にあるGCアルゴリズム

~/Documents/Books_on_vm/にあるThe Garbage Collection Handbookのコピーは2023年の第2版であり、専用セクションでG1、ZGC、およびShenandoahを名前でカバーしています。以下は、そのPDF(ページ番号は各ページヘッダーに印刷されている本のページ番号です — PDFファイル自体のページインデックスは、これらの番号から固定で+37オフセットされており、前書きで差が説明されています)から直接読み取られたものです。

6.1 トリコロール抽象化:形式的な不変条件の前の基本アルゴリズム

ソース:Robert Nystrom、Crafting Interpreters、「Garbage Collection」(このリサーチスレッドでも読みました — このディレクトリの003_research.mdを参照)。Nystromの章は、以下のGCハンドブックの形式的な正しさの定理の前に、基本的なマークスイープトリコロールアルゴリズムを直感的な言葉で提供しています:

1. すべてのオブジェクトを白として開始します。
2. すべてのルートを見つけて、それらを灰色にマークします。
3. 灰色のオブジェクトがまだある限り繰り返します:
    a. 灰色のオブジェクトを1つ選択します。オブジェクトが言及する白いオブジェクトをすべて灰色に変更します。
    b. 元の灰色のオブジェクトを黒にマークします。

「灰色の波面」画像:ルートは灰色になり、各灰色のオブジェクトの隣人は灰色になり、オブジェクト自体は黒くなり、波面は到達した(黒い)オブジェクトを後ろに残して進み、灰色のオブジェクトがなくなると白い未接触のオブジェクトをゴミとして集めます。

[画像: tricolor mark-sweep wavefront]

画像:Robert Nystrom、Crafting Interpreters、「Garbage Collection」(craftinginterpreters.com/garbage-collection.html)、教育参照のためにサイトの条件に従ってここで使用されています。

6.1a 同じ不変条件の形式的なバージョン

Goランタイム自身のこの不変条件のバージョン、src/runtime/mgc.goから、gcStartのSTWからマークフェーズへの遷移 — 完全なシーケンスであり、単一行だけではありません:

	// Enter concurrent mark phase and enable
	// write barriers.
	//
	// Because the world is stopped, all Ps will
	// observe that write barriers are enabled by
	// the time we start the world and begin
	// scanning.
	//
	// Write barriers must be enabled before assists are
	// enabled because they must be enabled before
	// any non-leaf heap objects are marked. Since
	// allocations are blocked until assists can
	// happen, we want to enable assists as early as
	// possible.
	setGCPhase(_GCmark)

	gcBgMarkPrepare() // Must happen before assists are enabled.
	gcPrepareMarkRoots()

	// Mark all active tinyalloc blocks. Since we're
	// allocating from these, they need to be black like
	// other allocations. The alternative is to blacken
	// the tiny block on every allocation from it, which
	// would slow down the tiny allocator.
	gcMarkTinyAllocs()

	// At this point all Ps have enabled the write
	// barrier, thus maintaining the no white to
	// black invariant. Enable mutator assists to
	// put back-pressure on fast allocating
	// mutators.
	atomic.Store(&gcBlackenEnabled, 1)

上から下へ読むと、これはマークフェーズ開始時の実際の操作順序です:(1) setGCPhase(_GCmark)は世界がまだ停止している間にグローバルフェーズを切り替えるため、すべてのPは世界が再開した瞬間に新しいフェーズを認識します。(2) gcBgMarkPrepare()とgcPrepareMarkRoots()は、マークが許可される前に、バックグラウンドマークワーカーとルートスキャンジョブキューをセットアップします。コメントの順序制約(アシストが有効になる前に書き込みバリアを有効にする、マークする前にアシストを有効にする)に従います。(3) gcMarkTinyAllocs()は、すでにタイニーアロケータから切り出された小さな割り当てを事後的に黒くするため、個別のバリアカバーを必要としません。(4) その後初めて、atomic.Store(&gcBlackenEnabled, 1)が実際にパート1.3aのmbarrier.goがチェックする書き込みバリアをアームします — コメントの「白から黒への不変条件なし」という主張は、それより前ではなく、この正確なストアから始まります。この行より上のすべては、不変条件がバリアがルートが準備される前にアームされた場合に違反される可能性があるため、最初に完了する必要があるセットアップです。

§15.1、「The tricolour abstraction, revisited」(p.331)は、Wilson [1994]に帰属する、この正確なコメントを2つの条件の正しさの定理として再定式化しています:

Condition 1: the mutator stores a pointer to a white object into a black object, and
Condition 2: all paths from any grey objects to that white object are destroyed.

テイクアウェイ: オブジェクトが誤って収集されるのは、両方の条件が同時に満たされた場合のみです — 黒いオブジェクトが隠された白いポインタを獲得し、かつ、コレクタがその白いオブジェクトを独立して再発見できたすべてのパスが破壊された場合です。どちらかの条件を破ると、コレクタは正しく動作しなくなります。これはすぐに2つの名前付き不変条件に一般化されます:

The weak tricolour invariant: All white objects pointed to by a black
object are grey protected (that is, reachable from some grey object, 
whether directly or through a chain of white objects).

The strong tricolour invariant: There are no pointers from black
objects to white objects.

テイクアウェイ: Goのハイブリッドバリア(Yuasa削除+Dijkstra挿入)は、これら2つの間の何かを強制するバリアの例です — Goのコメントは「白から黒へのものはない」と言っており、これはGoの特定の非移動コレクタに対して述べられた強い不変条件です。Goのような非移動コレクタは、弱い不変条件(「黒いオブジェクト内の白いポインタは問題ない。なぜなら、それらが灰色保護された白いターゲットは最終的にシェードされるから」)のみで済ませることができます。一方、並行コピーコレクタは強い不変条件を維持する必要があります。なぜなら、移動コレクタはサイクル終了時にfromspaceの白いコピーを完全に破棄するからです — tospaceの黒いオブジェクトが破棄されたfromspaceアドレスを指しているのは、単なる遅延マークではなく、ぶら下がったポインタです。これは、ZGC/Shenandoah(両方とも移動型)とGo(非移動型)が構造的に異なるバリア強度を必要とする正確な理由です。

6.2 §11.6 — パート3.5のベンダー非依存バージョン

§11.6、「GC safe-points and mutator suspension」(p.198)は、パート3.5が名前を持っていなかった区別を設けています:GCセーフポイント対GCチェックポイント。

Many systems make the opposite choice and only allow garbage collection
at certain restricted safe-points, and only produce maps for those
points. The minimal set of safe-points needed for correctness includes
each allocation ... and each call of a routine in which there may be
allocation or which may cause the thread to suspend in a wait.
Since these additional safe-points do not do anything that actually can
trigger a garbage collection, they need to have an added check for
whether garbage collection is needed/requested, so we call them GC
check-points.

テイクアウェイ: セーフポイントは、マシン状態がGCで検査可能な任意のポイントです。チェックポイントは、ランタイムが「今すぐ停止すべきか」を実際にテストするコードを挿入した(はるかに小さい)サブセットです。HotSpotのポールページ命令(パート3.5.2)は、この語彙におけるチェックポイントです — それらはループバックエッジとメソッドエントリに配置され、本は独立してそれを正しい最小配置として特定します(「各ループにセーフポイントが必要である。簡単なルールは、関数内の各後方分岐にセーフポイントを配置することである…さらに、各関数エントリまたは各リターンにセーフポイントが必要である」)。これは、Gil Teneの説明(パート3.5.2a)がHotSpotに正確に与えた配置ルールと同じです — 本は、HotSpot(およびGoの古いバックエッジチェック、およびSubstrateVMのカウンター)がすべて独立したインスタンスである一般的な原則として述べています。

本はまた、2つの異なるランタイムで見つかった正確な2つのメカニズムを名前で挙げ、それらを1つの一般的な二分法として扱っています。Agesen [1998]に帰属します:

Agesen [1998] compared two ways of causing a thread to suspend at a
GC-point. One is polling ... The other technique is patching, which
involves modifying the code at the next GC-point(s) of the thread.

テイクアウェイ: HotSpotのポールページ(パート3.5.2)は「ポーリング」です。Goのプリ1.14スタック境界チェックポイズニング(パート1.3)は、「パッチング」の精神に近い — ランタイムは、新しいチェックを追加するのではなく、既存の境界チェックをトラップにするようにstackguard0を書き換えます。Goのポスト1.14 SIGURGメカニズムは、Agesenの元の2方向分割のどちらでもありません — それは3番目の戦略(非同期外部割り込み)であり、1998年の分類法はそれを予期していませんでした。これは正確に知っておくべき有用なことです:SIGURGはポーリングやパッチングのバリアントではなく、真に後のデザインスペースへの追加です。

6.3 G1 — 地域アイデアだけでなく、実際のフェーズリスト

§16.5、「Garbage-First: collecting young and old regions」(p.354)は、OpenJDK 20の実際の混合コレクションフェーズシーケンスを提供します。パート6の元のバージョンが説明した地域優先順位付けのアイデアだけではありません。直接引用(短縮):

Start: This stop-the-world phase is piggy-backed on a 'young only'
collection that seeds the roots for concurrent marking. ... G1 sets a
Top At Mark Start (TAMS) variable for each region; any objects allocated
at addresses above the TAMS for a region will be considered implicitly
live/marked.

Concurrent Mark From Roots: ... using a snapshot-at-the-beginning
algorithm, with mutators using a deletion barrier ... G1 marking threads
... Each thread first claims a region to mark by atomically advancing a
global 'finger' to the right.

テイクアウェイ: TAMSは、G1が新しい割り当てオブジェクトをマークするのを避けることを可能にするメカニズムです — 地域でマーク開始後に割り当てられたものはすべて、アドレス比較だけでライブと見なされます。バリアやスキャンは必要ありません。これはGoのアプローチ(パート1.3)とはまったく異なる戦略です。そこでは、新しい割り当てはgcBlackenEnabledでゲートされた動作を通じてすぐに黒くマークされます — G1のTAMSしきい値は、同様の目標(新しいオブジェクトに無駄な作業をしない)を異なるメカニズム(地域ごとのアドレス比較、グローバルな割り当て色フラグではない)で達成します。本はまた、G1のバリアを削除バリアとして具体的に名前を付けています(スナップショット・アット・ザ・ビギニング)。これはYuasaの半分だけであり、GoのハイブリッドYuasa+Dijkstraの組み合わせではありません — 両コレクタのバリア間の実際のアルゴリズムの違いであり、JEPだけでは見えません。

6.4 ZGC — 色付きポインタ、実際のビットレイアウトで確認済み

§17.5はZGC [Lidén, 2018]を説明し、単に「色付きポインタ」という概念を名前で呼ぶのではなく、実際のポインタビットレイアウト(図17.4)を提供します:

ZGC uses tagged pointers and self-healing load barriers. ... A group of
four higher-order bits determine a colour. The four bits are named F
(finalisable), R (relocated), M1 and M0 (marked). A given pointer will
have only one of R, M0 and M1 set ... At any given time, only one of R,
M0 or M1 is the good colour; loading pointers of other colours forces a
load barrier slow path.

テイクアウェイ: 「色付きポインタ」は比喩ではありません — それは64ビットポインタの未使用の高位ビットにある4つの特定のビット(F/R/M0/M1)です。アドレスは実際には47ビットしか必要としません(アドレスビットは約ビット46から0までをカバーし、タグビットのために上にスペースを残します)。自己修復:スレッドが古い色のポインタをロードすると、ロードバリアはそのバリアのスローパスを通じて、その場所の色をインプレースで修正します。そのため、同じ場所に対する後続のロードは、スローパスを再トリガーしません。これは、Goの書き込みバリア(書き込み時に発火し、読み取り時には発火しない)やG1の削除バリア(これも書き込み側)とは、材料的に異なるメカニズムです — ZGCのバリアは読み取り時に発火します。

6.5 Shenandoah

§17.5、「Shenandoah」(p.401)はアルゴリズムと、特に、引用された著者が自身の以前の設計議論に疑問を呈する一文を提供します:

In 2016 Flood et al. argued that programs such as web caches hold onto
objects just long enough to defeat generational collectors so, instead,
Shenandoah focuses its effort on regions with fewer live objects... 
They also argued that generational collection requires some kind of
remembered set... However, it is not clear that these concerns still
hold and implementation of a generational version of Shenandoah is in
progress.

テイクアウェイ: 2023年現在、Shenandoah自身の基礎となる2016年の設計議論(なぜ世代別でないのかという議論)は、その著者自身によって積極的に再検討されており、世代別バリアントが進行中です — 静的な「Shenandoahは非世代別、ZGCは非世代別」という事実が与えるものとは異なる絵です。この分野は静止しているのではなく、改訂の途上にあります。

自己修復ロードバリア自体は、実際の疑似コード(アルゴリズム17.12)として提供されており、ZGCのものと行ごとに比較する価値があります:

Read(src, i):
    addr ← &src[i]
    obj ← *addr
    if not isGCactive()             /* fast path: accesses thread-local flag */
        return obj
    if not isInCollectionSet(obj)
        return obj
    fwd = resolveForwardee(obj)     /* access forwarding pointer, if one */
    if obj ≠ fwd
        CAS(addr, fwd, obj)         /* self-heal */
        return fwd

テイクアウェイ: Shenandoahの自己修復は、発見された転送ポインタを元のスロットにCASすることによって機能します — ZGCの色のポインタリマップとは異なる自己修復メカニズムですが、同じ目標です(バリアコストを場所ごとに1回支払う、アクセスごとに1回ではない)。isGCactive()の高速パスチェックは、G1のgcBlackenEnabledとGoのgcphase == _GCmarkゲーティング(パート1.3a)の形状と機能的に同じです — 3つのコレクタすべてが、それぞれのバリア機構のコストをアクティブなサイクル中にのみ支払います。これは、3つの異なるコードベースとこの1つの教科書の説明で独立して確認されています。

6.6 CompressorとPauseless/C4:ページ保護対タグ付きポインタ

§17.5、「Compressor」(p.386)および「Pauseless and C4」(p.387–388)。

Compressorのメカニズム、本の自身のカテゴリリストより:

Live: pages containing (mostly) live objects
Condemned: pages containing some live objects, but mostly dead ones
Free: pages currently free but available for allocation
New Live: pages in which copied live objects have been allocated but not yet copied
Dead: unmapped pages that can be recycled once there are no pointers to them

テイクアウェイ: Compressorは、ページ保護を介してコンパクションを完全に駆動します — tospaceページをmprotectして、ミュータターアクセスがトラップするようにします。トラップハンドラはオンデマンドで転送/コピーを実行します。これはHotSpotのセーフポイントポールページ(パート3.5.2)と同じスタイルのメカニズムです — ハードウェアトラップが有用な作業を実行し、単なる停止信号ではありません。これは、セーフポイント到着ではなく、コピー中のGC不変条件を強制するために適用されます。同じトリックが、ミュータターサスペンションの同期だけでなく、コピーの正しさにも一般化されます。

対照的に、Pauseless/C4のメカニズムは、ページ保護をほとんど完全に回避し、タグ付きポインタを使用します — 図17.2(p.388)の実際のビットレイアウトで確認済み:

Pauseless steals one address bit from the 64-bit address space to use as
a pointer tag. This Not-Marked-Through (NMT) bit is used by the LVB
during the concurrent marking phase of the collector to decide whether
the reference has previously been scanned by the collector.

テイクアウェイ: C4/PauselessのLVB(「Loaded Value Barrier」)は、ZGCの自己修復色付きポインタロードバリア(パート6.4)と同じ考え方です — 両方ともアドレスビットを盗み、両方ともロード時に自己修復します。ZGCのデザイン(2018年)は、AzulのPauseless/C4(2005/2011)の後に出てきて、それを基盤としており、独立した発明ではありません。C4の世代別拡張は、ポインタごとに追加のタグビットを盗んで、参照が属する世代を追跡できるようにします。これにより、若い世代と古い世代のコレクションが、単一のグローバルNMT値を相互チェックすることなく独立して進行できます。

未解決の質問: ZGCの世代別バリアント(図17.4b)が、C4のビット予算トレードオフに類似したものを持っているかどうか — ZGCの世代別タグ付きポインタの図と直接比較されていません。

6.7 Staccato

§19.7、「Staccato: best-effort compaction with mutator wait-freedom」(p.455) — このリサーチディレクトリの006_other_reading_materials.mdでも参照されているMcCloskey et al.の論文。

Staccato [McCloskey et al., 2008] permits concurrent compaction without
requiring the mutators to use locks or atomic operations like
compare-and-swap in the common case, even on multiprocessors with weak
memory ordering.

メカニズムは、本の自身の疑似コード(アルゴリズム19.8)で確認済み:

copyObjects(candidates):
    for each p in candidates
        CompareAndSet(&forwardingAddress(p), p, p | COPYING)
        waitForRaggedSynch(writeFence; readFence)
        ...

テイクアウェイ: 「ラグド同期」は、Collieの「プリコンパクションラグドハンドシェイク」(パート6.6)および§15.3の「ラグドフェーズ変更」で触れたパターンに似ています。単一のグローバルストップ・ザ・ワールドのランデブーの代わりに、各ミュータターは独立してメモリフェンスを「定期的な間隔(GCセーフポイントなど)で」実行し、コレクタはすべてのミュータターが個別に、自分のペースでそのフェンスを越えるのを待ちます — 同期バリアではなく分散ハンドシェイクです。これは、HotSpotの単一グローバルThreads_lockベースのランデブー(パート3.5.2b)とは異なるSTW回避戦略です。

6.8 スコープノートとさらなる読書

上記ではカバーされていません:第14章(並列GCの内部 — マーク、コピー、コンパクションアルゴリズム)、Tax-and-Spend(§19.6)。Sapphire、Transactional Sapphire、Platinum、Metronome、Stopless、Chicken、Cloverは、以下の付録(§19.5–19.7)でカバーされており、上記の番号付きセクションではありません。

ベンダー/JEPレベルのポインタ、アルゴリズムビューではなく本番フラグビュー用:

6.9 Sapphire, Platinum, Metronome, Stopless, Chicken, Clover

SapphireとTransactional Sapphire(§17.4、p.376–379) — 共有メモリマルチプロセッサ向けの並行コピーアルゴリズム。これにより、すべてのスレッドを停止して一度にフリップするのではなく、1つのミュータタースレッドが一度にfromspaceの読み取りからtospaceの読み取りに切り替えることができます。Transactional Sapphireは、これを並列コレクタスレッドとオブジェクトコピーのためのハードウェア/ソフトウェアトランザクションで拡張し、4つのフェーズグループ(Mark、Copy、Flip、Reclaim — アルゴリズム17.4)を各フェーズに異なる書き込みバリアで通過します。

Flip: In this group, the collector forwards pointers in global variables
and thread stacks and registers, flipping them one at a time into
tospace. Unflipped mutator threads may hold references to both fromspace
and tospace copies (even of the same object).

テイクアウェイ: インクリメンタルフリッピング(一度に1つのスレッド、全体の一時停止ではなく)がメカニズムのポイントです — より複雑なバリア(ミュータターは同じオブジェクトのコピーの両方に同時に参照を持つ可能性がある)と引き換えに、いずれかのスレッドがブロックする必要があるウィンドウを短縮します。

Platinum(§17.4、p.383–384) — ほとんど並行、世代別、レプリケーション型で、ロングテールレイテンシを対象としています。コア数よりも少ないコレクタスレッドを使用し、各スレッドを特定のコアにバインドします。また、Intelのメモリ保護キー(システムコールが多いmprotectではなく、高速なスレッドごとのレジスタ)を使用して、フルページテーブル変更なしでコレクタとミュータタースレッドに同じページへの異なるアクセス権を与えます。

Platinum sets up two protection keys. During collection, one is
associated with pages to which only the collector threads should have
write access, and Platinum arranges that the mutators set their
protection keys to disallow writes to these pages.

Metronome(§19.5、p.439–441) — Java向けのタイムベースのリアルタイムコレクタ:インクリメンタルマークスイープコレクタで、部分的なオンデマンドコンパクションを備え、固定時間クォータ(10msウィンドウで500µsコレクタスライス)でスケジュールされ、最小ミュータター利用率(MMU)ターゲット(一般的に70%)を保証します。

Stopless(§19.7、p.454–455) — ロックフリーの並行コンパクタ。Sapphire(ミュータターがfromspaceとtospaceのオブジェクトコピーの両方を更新する必要がある)とは異なり、Stoplessは、各フィールドのステータスワードを持つ「ワイド」中間コピーに対するダブルワード比較・交換を使用して、常に1つのコピーのみが最終的なコピーであることを保証します(inOriginal/inWide/inCopy)。

Chicken(§19.7、p.458) — アーキテクチャ的にはStaccato(パート6.7)に近く、独立して開発され、特にx86/x86-64のより強力なメモリモデルを対象としています。そのアーキテクチャは読み取りをアトミックと比較して順序付けるため、書き込みのみが進行中のコピーを中止する必要があり、Staccatoが依存するラグド同期は読み取りフェンス部分を必要としません。

Clover(§19.7、p.458–459) — コレクタがコピーされたフィールドを予約済みセンチネル値α(現代のx86-64での128ビット比較・交換を使用して、実際のプログラム値との衝突が天文学的にありそうもないように選択)でマークすることにより、一般的なケースでロックフリーのミュータターアクセスによるコンパクションを保証します。αを読み取ったミュータターは、代わりに転送ポインタを介してフィールドを再ロードすることを知っています。


パート7 — この資料を線形ではなく、パスで読む

以下のフレームワークは、すべてのソースに均一にチェックリストとして適用されるのではなく、選択的に適用されます — これらの資料のいくつかは5つのプロパティすべてを持っていません(却下された代替案セクション、認められた弱点)、そしてフレームワークをその構造を持たないソースに強制すると、正直なものではなく、偽のパターンが生成されます。テクニックが特定のソースに適合しない場合、それはパディングされるのではなく、そのソースのために省略されます。

1つの支配的な制約は、Go(GCはポインタマップを必要とする→プリエンプションを制約する、パート1.3)、BEAM(共有なし→セーフポイント問題なし、パート3.2–3.3a)、およびKotlin(JVMを変更できない→CPS変換が唯一のレバー、パート2.1)にきれいに適用されます。それはGCアルゴリズム(パート6)にはそれほどきれいに適用されません — G1、ZGC、およびShenandoahはすべて同じ制約(ヒープサイズに依存しないバウンドされた一時停止時間)を異なるメカニズムで解決しています。したがって、そのクラスターでは、有用な移動は、各コレクタに対して異なる制約を見つけるのではなく、メカニズムを共有制約に対して比較することです。

認められた弱点/却下されたパスは、具体的に3つの場所で、すでにこのドキュメントで表面化しています。仮説ではなく:Goの提案が、測定された7.8%の低下によりループバックエッジチェックを却下したこと(パート1.3)、HotSpot自身のAbortVMOnSafepointTimeout監視タイマーがスレッドが本番環境でセーフポイントに到達できないことを認めていること(パート3.5.2b)、およびShenandoahの著者が2016年の非世代別議論に疑問を呈していること(パート6.5)。これら3つは、ドキュメント全体で最も価値のある再読です。もしあなたが3つだけを再訪する時間があるなら。

7.1 コンセプトマインドマップ — 事実リストではなく、テンションマップ
mindmap
  root((Preempt a running<br/>task safely))
    Who initiates preemption
      OS timer interrupt
        No cooperation needed
        Thread has no say
      Go: SIGURG signal
        Async, external
        Still gated by safe-point check
      HotSpot: poll page
        Thread checks itself
        Trap turns it involuntary
      SubstrateVM: counter CAS
        Per-thread, no shared page
      BEAM: reduction counter
        Every instruction dispatch
        No separate check needed
    What makes a point unsafe
      Shared GC-managed heap
        Pointer vs raw int ambiguity
        Go stack maps
        HotSpot stack maps
      No shared heap at all
        BEAM sidesteps the question
        Every point is already safe
    GC correctness invariant
      Weak tricolour
        Non-moving OK
        Go hybrid barrier
      Strong tricolour
        Required for moving GC
        ZGC load barrier
        Shenandoah load barrier
        G1 deletion barrier
    Concurrency unit
      Go: goroutine, CSP channels
      Kotlin: continuation, CPS
        compiler layer
        kotlinx.coroutines layer
      BEAM: process, shared nothing

この図が主張していること、1文あたり: プリエンプションメカニズムは、誰がタスクを停止するかを決定する点で異なります。安全メカニズムは、共有GC管理メモリがほとんどのポイントを停止するには安全でないかどうかという点で異なります。GCの正しさは、コレクタがどれだけ弱く強制できるかに還元されます。これは、コレクタがオブジェクトを移動するかどうかによってさらに下流になります。3つのトップレベルのブランチは独立していません — 「誰が開始するか」という答えは、メモリモデルがすでにコミットした「どこで安全でないか」という答えによって制約されました。

7.2 リーディングロードマップ — このドキュメントの実際のソースリストを横断する4つのパス
flowchart TD
    subgraph P1["パス1 — オリエンテーション:解決されている問題"]
        direction LR
        A1["Go proposal 24543<br/>abstract + problem statement"]
        A2["mgc.go header comment<br/>(algorithm summary, lines 1-20)"]
        A3["Safepoint.java class doc<br/>(GraalVM)"]
        A4["GC Handbook §1.3<br/>Comparing GC algorithms"]
    end

    subgraph P2["パス2 — 1つの制約を見つける"]
        direction LR
        B1["preempt.go safe-point<br/>categories comment"]
        B2["signal_unix.go SIGURG<br/>4-criteria rationale"]
        B3["Continuation.kt<br/>+ why suspend is compiler-level"]
        B4["erl_process.h fcalls comment<br/>+ Part 3.2 shared-nothing"]
        B5["GC Handbook §11.6<br/>safe-point vs check-point"]
    end

    subgraph P3["パス3 — 却下されたパスと緊張関係をマッピングする"]
        direction LR
        C1["Go: loop back-edge check,<br/>7.8% regression, rejected"]
        C2["HotSpot: SafepointTimeout<br/>watchdog admits failure mode"]
        C3["Shenandoah §17.5: authors<br/>question own 2016 argument"]
        C4["Agesen 1998: polling vs<br/>patching vs SIGURG (3rd path)"]
    end

    subgraph P4["パス4 — システムごとに1文に圧縮する"]
        direction LR
        D1["Go: non-cooperative,<br/>gated by pointer safety"]
        D2["Kotlin: cooperative by<br/>construction, no interrupt exists"]
        D3["BEAM: no unsafe points<br/>exist, only a budget"]
        D4["JVM family: same constraint<br/>(bounded pause), different<br/>mechanism per collector"]
    end

    P1 --> P2 --> P3 --> P4

    A1 -.reread after.-> C1
    B2 -.reread after.-> C4
    B5 -.reread after.-> C2

このロードマップを実際に使用する方法: 各ボックスを一度に順番に読むのではなく — まず4つのソースすべてを横断するパス1(それぞれがどのような問題を解決しているかを知るのに十分なだけ)を読み、次に4つすべてを横断するパス2(各システムでの負荷のかかる制約を見つける)、次にパス3は、却下されたパスまたは認められたギャップがあるソースのみ(すべてがそうではない — Continuation.kt、例えば、Goの提案やShenandoahの回顧録のように「Xを試したが却下した」という瞬間がない)を読み、最後にパス4は各システムに対して1文の圧縮を書くことを強制します。これは、最初の3つのパスが機能したかどうかをテストします。システムに対してパス4の文を書けない場合、それはそのシステムに対してパス2に具体的に戻るための信号であり、すべてを再読するためではありません。


深く掘り下げるためのソース参照(チェックポイントがあなたを立ち往生させた場合のみ)

このドキュメントのために直接取得・読み取られたプライマリソースファイル

Go(golang/go、master):

Kotlin/kotlinx.coroutines:

OpenJDK/HotSpot(openjdk/jdk、master):

GraalVM/SubstrateVM(oracle/graal、master):

The Garbage Collection Handbook, 2nd ed. (2023) — 直接読み取り、ローカルPDF

~/Documents/Books_on_vm/Jones, Richard - The Garbage Collection Handbook...pdf(Jones, Hosking, Moss; Chapman and Hall/CRC, 2023)。パート6のために直接読まれたセクション:§11.6「GC safe-points and mutator suspension」(p.198)、§15.1「Correctness of concurrent collection」/ tricolour invariants(p.331–334)、§16.5「Garbage-First: collecting young and old regions」(p.354)、§17.4「Replication copying」— Sapphire、Transactional Sapphire、Platinum(p.376–384)、§17.5「Concurrent compaction」— Compressor(p.386)、Pauseless/C4(p.387–388)、Collie(p.395)、ZGC(p.396)、Shenandoah(p.401)、§19.5「Metronome」(p.439–441)、§19.7「Controlling fragmentation」— Staccato、Stopless、Chicken、Clover(p.453–459)。まだ直接読んでいないもの:第14章(並列GCの内部)、§19.6「Tax-and-Spend」(p.448)。

GCアルゴリズム(パート6) — ソースとしては読まず、後で読むためのポインタとして引用

Erlang/OTP(erlang/otp、master):

Crafting Interpreters — 直接読み取り(003_research.md、このディレクトリ経由)

Robert Nystrom、Crafting Interpreters, “Garbage Collection” — 基本マークスイープとトリコロール抽象化(パート6.1);パート6.1で使用されているトリコロール波面画像はこの章からソースされています。

二次ソース(貼り付け/引用、このドキュメントのために独立して取得されていません)

ありがとう。共有しますか?


ルール

  • 技術用語は適切にカタカナ表記または原語のまま残し、それ以外の英単語は日本語に訳してください
  • 数値と単位は原文の意味を正確に保って訳してください(例: trillion は「兆」)
  • 本文は Markdown で与えられます。translatedBody も Markdown で書き、原文の構造(見出し・段落・箇条書き・番号付きリスト・引用・表・強調・取り消し線)をそのまま保ってください。段落の間には空行を入れ、全文を1つの塊にまとめないでください
  • コードブロックとインラインコードは翻訳せずそのまま残してください
  • リンク テキスト はテキストだけを翻訳し、URL は一字も変えずに残してください
  • [画像: …][動画: …][音声: …][図: …]は原文に画像・動画・音声・図があった位置を示す印です。印の形と位置はそのまま残し、「…」の説明文だけを翻訳してください
  • 原文にない見出しや装飾を追加しないでください
  • タイトル先頭の「Ask HN:」「Show HN:」「Tell HN:」「Launch HN:」は翻訳せず、そのまま titleJa の先頭に残してください
  • titleJa と summary は Markdown を使わないプレーンテキストで書いてください(太字、箇条書きの記号、# 見出し、テキスト のリンクなどの記法は使わない)
  • 本文が取得できない場合は、タイトルから推測した簡潔な説明のみを記述し、「本文が取得できません」等の取得状況には一切言及しないでください
  • 記事の順番を維持してください