19. Gauche Schemeのスタックとヒープのハンドリング (川合史朗)

Turing Complete FM

川合史朗さんが作っているScheme処理系Gaucheの実装について、特にメモリ管理やクロージャ、継続の実装などに焦点を当てて話をしました。最近のCPUでは単純にJITしても速くならない理由などについても話をしています。

出演者: 川合史朗 (@anohana)、Rui Ueyama (@rui314)

https://turingcomplete.fm/19

ハッシュタグは#tcfmです。

TCFMはサポーターの投げ銭によって収益を上げています。このコンテンツに課金してもいいよという方はぜひクリエイター支援サイトPatreonから登録してご協力ください。

• イントロ (0:00)
• Schemeのストレージモデルではすべてが無限エクステント (1:06)
• 関数呼び出しのモデルとアクティベーションレコードのアロケーション (4:34)
• SPARCのレジスタウィンドウ (9:20)
• Alphaの速さの秘密 (12:41)
• 大コケしたIntel Itaniumプロセッサ (14:11)
• GoのGC停止時間の劇的な改善 (16:55)
• ページテーブルのダーティービットをユーザプログラムから使う話 (20:14)
• Goの分割スタック機能 (23:07)
• クロージャを作ったときに使ってない変数を不必要に掴んでしまう問題 (25:54)
• 32ビットハッシュ値を大量に作ると32ビットマシンで偽ポインタがたくさんできてしまう問題 (27:44)
• 決してreturnしないCプログラムにコンパイルするScheme処理系 (33:00)
• タグ付きポインタ (41:23)
• C言語の仕様を満たすためのBoehm GCの機能と、それを使いたくない理由 (46:10)
• 64ビット浮動小数点数をなるべくヒープにアロケートせずに扱いたい (50:30)
• 16ビット"Brain"浮動小数点フォーマット (55:27)
• Gaucheの正規表現エンジン (56:44)
• Scheme→C→Schemeという呼び出しをした先で継続を取得すると限定継続になる (1:00:19)
• Schemeスタックからヒープへのコピー (1:04:44)
• 末尾呼び出しはスタックを消費しないように手続きを呼び出す (1:05:50)
• Chez Schemeでは多値ありと多値なしの2つの継続を渡す (1:10:29)
• 最近のCPUの分岐予測の賢さとMeltdown & Spectre (1:13:16)
• Gaucheを単純にJIT化してもCPUの分岐予測が賢いのでそれだけでは速くならない (1:20:08)
• 社会的や経済的理由で速くなる言語 (1:25:05)
• リテラルで書けるオブジェクト (1:27:29)
• 正規表現リテラル (1:28:32)
• マップのリテラル (1:30:55)
• Gaucheのハッシュテーブルとハッシュ衝突攻撃 (1:36:41)
• TCFMの難易度 (1:39:24)

• Gauche Scheme
• ハッカーと画家（川合さんが翻訳した本）
• SISC Scheme
• メモリのローカリティ
• SPARC
• DEC Alpha
• Itanium (IA-64)
• VLIW命令セット
• HamajiさんによるGCフレンドリーなスタック塗りつぶしの話
• Clojure（JVMで動くLisp）
• Chicken Scheme
• Azul Systems（並列Javaマシンを作っていた会社）
• Hans Boehmによる保守的GC安全なデータ構造についての論文 (PDF)
• Cheney on the M.T.A.
• History of T
• タグ付きポインタ
• 16ビット"Brain"浮動小数点フォーマット
• Russ CoxによるThompson NFAの解説
• Anton Ertlらによるmemcpyを使ったJITの手法の論文 (PDF)
• 末尾呼び出し最適化
• セキュアで速いハッシュとしてデザインされたHighwayHash

追記

• CPythonはリファレンスカウンタを使っていますが、Pythonの言語仕様自体では必須とはされていません。