不幸な GC

Transcript

1. 不幸な GC ちぇん / Chen 2026/08/22 Kernel/VM 探検隊@東京 No19
2. 世 界 あやしい VM って？ 2/53
3. 世 界 あやしい VM って？ ｢配列はあるのに動的インデックスアクセスがほぼできない｣ とか･･･ 3/53
4. 世 界 あやしい VM って？ ｢配列はあるのに動的インデックスアクセスがほぼできない｣ とか･･･ ｢データの取り扱いがめちゃくちゃ下手｣ とか･･･ 4/53
5. 世 界 その VM の名は 5/53
6. 世 界 その VM の名は Minecraft ブロックでできたオープンワールドの 世界で探検したり、建築したり、モン スターと戦ったりできる VM そこそこの表現力を持つコマンド体系 が標準で搭載されている 6/53
7. 君誰？ 名前: ちぇん / Chen Twitter: @Chen__TS GitHub: @ChenCMD 本業: サーバーサイドエンジニア / 技術広報 メイン言語: Scala 人生を狂わせたもの 趣 味 : Minecraft Minecraft のコマンド体系に 9 年在住 メンバー 30 人以上を率いて Minecraft 上で ゲームを約 6 年間作っている 7/53 https://project-tsb.org
8. そんな世界で何に困っているのか？ 何を作るにしても、entity に固有の状態を持たせたくなる entity: プレイヤー / モブ / 落ちているアイテム / 放った矢 / 残留ポーションのモヤモヤ など、ワ ールド上に存在するオブジェクトだいたい全てのこと 例えば･･･ 独自のパラメータ AI の内部状態 Temporary なフラグやリスト 8/53
9. 幸運な世界ならこう書くよね entity.data = { name: "checche", age: 222.2, history: [12, 42, 51] } データの観点で言えば 配列やオブジェクトも持てる entity の観点で言えば entity ごとに独立している 好きなだけ構造化できる これくらいはほしい！ が、Minecraft にはこれらを満たす仕組みが標準では存在しない 9/53
10. 使えるもの (1/2) scoreboard Map<EntityID, i32> 相当のグローバルなデータ領域 ここが嬉しい！ entity が消滅した際に対応するレコードが それ以外はだいたい何も出来ない 自動で回収される entity が消滅した際に対応するレコードの 特定レコードに対する四則演算・剰余が 値を使ってなんやかんやするとか できる 値が N であるレコードが存在するかを確認 全レコードを対象とする、定数加算などの 算術演算 全レコードの min / max が取れる 10/53 ここが嬉しくない！ するとか bit 演算をするとか
11. 使えるもの (2/2) StorageObject JSONObject 相当のグローバルなデータ領域 ここが嬉しい！ JSONPath ライクな pathでデータへアクセ スできる 配列に対して ｢末尾から N 番目の要素｣ とい う表現を扱える 11/53 ここが嬉しくない！ 動的インデックスアクセスができない 参照を取るという操作がなく、値を peek す る以上のことをすると deep コピーになる
12. つまり？ Map<Entity, StorageObject> が欲しい！ それを実現しているライブラリがある 12/53
13. つまり？ Map<Entity, StorageObject> が欲しい！ それを実現しているライブラリがある Oh!MyDat! さっき欲しいと言ったものを、scoreboard と StorageObject だけで実現しているラ イブラリ 気持ち的にはこんなイメージ entity A -> { name: "checche", age: 222.2, history: [12, 42, 51] } entity B -> { ... } entity C -> { ... } scoreboard と StorageObject から、どうやってそんなものを･･･？ 13/53
14. まずは I/F を見てみよう Oh!MyDat! が提供するのは、実質下記の 1 つのみ please(Entity): void 呼び出す前の状態に関わらず、特定の path が引数として渡した Entity の データ領域を指すようになる魔法の関数 please(entityA) Storage.write(path = "data[-4][-4][-4][-4][-4][-4][-4][-4].x", value = "neko") please(entityB) Storage.write(path = "data[-4][-4][-4][-4][-4][-4][-4][-4].x", value = "dog") please(entityA) Storage.read(path = "data[-4][-4][-4][-4][-4][-4][-4][-4]") // => { x: "neko" } 14/53
15. Q. この data って何？ A. ただの深さ 8 の (完全とは限らない) 4 分木 ⁸ 4 = 65536 個ある末端ノードが entity のデータ領域 データ構造としても、ただのネストされた配列 [[[[[[[[{}, ...], ...], ...], ...], ...], ...], ...], ...] entity に木のパス (アドレス) を対応させる方法さえ用意す れば末端ノードと entity の紐付けができる うれしい！ 15/53
16. そろそろお忘れかも知れませんが･･･ おさらい StorageObject ここが嬉しくない！ 動的インデックスアクセスができない 参照を取るという操作がなく、値を peek する以上のことを すると deep コピーになる こ、こんな制約下でどうやって木を扱えと･･･ 16/53
17. ここで data[-4][-4]...[-4] が再登場 特定の path が引数として渡した Entity のデータ領域 を指すようになる おさらい StorageObject ここが嬉しい！ 配列に対して ｢末尾から N 番目の要素｣ という表現を扱える つまり: data を配列と仮定して、｢末尾から 4 番目を対象 にするという操作｣ を 8 回繰り返している ≒ data.get(-4).get(-4) ... .get(-4) 17/53
18. つまり•••？ 動的インデックスアクセスができないなら、 木の方を変形すれば良い path は data[-4][-4]...[-4] で固定する 末尾に 0~3 個の空ノードを追加すると、 [-4] が指す枝を変えられる これを 8 段繰り返せば、path を固定したまま 任意の末尾ノードにアクセスすることができる 18/53
19. つまり•••？ 動的インデックスアクセスができないなら、 木の方を変形すれば良い path は data[-4][-4]...[-4] で固定する 末尾に 0~3 個の空ノードを追加すると、 [-4] が指す枝を変えられる これを 8 段繰り返せば、path を固定したまま 任意の末尾ノードにアクセスすることができる つまり？ 深さ 8 の 4 分木 深さ 8 の 4 ~ 7 分木 19/53
20. please 完全に理解した 20/53
21. 大事なことを忘れていませんか•••？
22. 不幸な GC ちぇん / Chen 2026/08/22 Kernel/VM 探検隊@東京 No19
23. あ゛！！！！！ 確かに entity に紐付く固有のデータ領域は出来た が、今のままでは entity が消滅しても紐付くデータ領域が消えない 23/53
24. あ゛！！！！！ 確かに entity に紐付く固有のデータ領域は出来た が、今のままでは entity が消滅しても紐付くデータ領域が消えない Q. entity が消滅した時に消せば良いだけでは？ 24/53
25. あ゛！！！！！ 確かに entity に紐付く固有のデータ領域は出来た が、今のままでは entity が消滅しても紐付くデータ領域が消えない Q. entity が消滅した時に消せば良いだけでは？ A. そんな幸福な世界だったらよかったですね (笑) この世界において、イベントハンドラみたいな幸福なものはほぼ存在しない^1 当然、entity の消滅を元になんやかんやするなどできるはずもなく••• やりたきゃこちら側でその仕組みを工夫して実現する必要がある 25/53
26. では逆に何があれば GC ができるのか？ 消滅した entity に割り当てられていた address が分かれば、 対応する末端ノードを空に戻せる でも entity が消滅した時点で、その対応関係も失われてしまう → 直接どうにかするのは難しそう••• 26/53
27. こんな時は一般の世界のありがたい言葉を参照しよう Fundamental theorem of software engineering ソフトウェア工学の基本定理 「コンピュータ科学のあらゆる問題は、間接参照 (indirection) のレイヤーを 1 つ追加することで解決できる」 — David Wheeler こんな世界でももちろんソフトウェア工学の基本定理は適用できるはずだ please(Entity) が外向きに保証しているのは entity から個別データ領域への 対応だけ 木のどの末端を使うかや、その対応をどう管理するかは実装側で自由に決められる ということで、entity と 木の間に entity が消滅したことがわかるような中間層を挟 んで、解決しよう 27/53
28. Q. どこに中間層を生やすって？ A. ここ 28/53
29. 中間層を用意する 我々が勝手に割り当てる 16 bit address の保存先を 2 カ所に用意する scoreboard Map<Entity, address> StorageObject: addresses SomethingCollection<address> レコードのライフタイムが entity と同期 entity のライフタイムとは無関係に する address を保持する A B C 29/53 → 0xC000 → 0x8000 → 0x4000 0xC000 0x8000 0x4000
30. このように保存して entity が消滅すると何が起きるか 消滅前 entity B が消滅した後 scoreboard StorageObject scoreboard StorageObject A → 0xC000 0xC000 A → 0xC000 0xC000 B → 0x8000 0x8000 C → 0x4000 0x4000 0x8000 C → 0x4000 0x4000 scoreboard 側だけが entity と一緒に変化するので、2 つの状態に差が生じる entity の消滅そのものは観測できないが、この差分を根拠にすれば、 消滅した entity に割り当てていた address を特定できるという言えるだろう じゃあその状態の差分取れば GC も実装終わりだね！楽勝ですね！ 30/53
31. ちょっと待って•••？ 31/53
32. ちょっと待って•••？ おさらい scoreboard ここが嬉しくない！ それ以外はだいたい何も出来ない 値が N であるレコードが存在するかを確認するとか 32/53
33. ちょっと待って•••？ おさらい scoreboard ここが嬉しくない！ それ以外はだいたい何も出来ない 値が N であるレコードが存在するかを確認するとか 差分が取れないじゃん 33/53
34. では、GC は実装できないのか？ 全 address と全 entity を突き合わせるような全精査は不可能 34/53
35. では、GC は実装できないのか？ 全 address と全 entity を突き合わせるような全精査は不可能 なら、差分の一部だけを検証する形なら、あるいは•••？ 35/53
36. これをやるのに極めて都合がいい構造がある StorageObject 側の address collection を少し頑張る 具体的には••• 0〜65535 の address を保持する ある位置から見ると、円環状に降順になる 「次に掃除する場所」を 1 箇所だけ持つ この位置を head と呼ぶ この構造を addressRing と呼ぶ 36/53
37. この ring をどう使う？ 例えば、 0xC000 、 0xA000 、 0x4000 が消滅しているとする この図上では、 head は 0xC000 となる 37/53
38. この ring をどう使う？ 例えば、 0xC000 、 0xA000 、 0x4000 が消滅しているとする この図上では、 head は 0xC000 となる scoreboard を用いて head 以下で生きている 最大の address が 0x8000 だと分かったとす る 38/53
39. この ring をどう使う？ 例えば、 0xC000 、 0xA000 、 0x4000 が消滅しているとする この図上では、 head は 0xC000 となる scoreboard を用いて head 以下で生きている 最大の address が 0x8000 だと分かったとす る すると、 0x9000 に到達するまでに通った address は全部消してよいことがわかる やった〜 できた〜 39/53
40. この ring をどう使う？ 例えば、 0xC000 、 0xA000 、 0x4000 が消滅しているとする この図上では、 head は 0xC000 となる scoreboard を用いて head 以下で生きている 最大の address が 0x8000 だと分かったとす る すると、 0x9000 に到達するまでに通った address は全部消してよいことがわかる やった〜 できた〜 40/53
41. そんな演算あるわけがない 41/53
42. そんな演算あるわけがない 欲しいのは雰囲気で言えばこれ scoreboard.records .filter(n => n <= head) .max() しかし使えるのはせいぜい 全レコードに同じ値を足す / 引く 全レコードの max を取る filter なんて幸福なものは存在しない 42/53
43. いったん Minecraft を忘れる 0〜65535 の範囲にある i32 値の集合 threshold を取りたい 以下の最大値 ただし使えるのは 集合全体への一括加減算 集合全体の max だけとする 43/53 から
44. こうやる (AI slop) https://claude.ai/public/artifacts/3bf1cf38-7f15-45e4-bee8-c76505a60f10 44/53
45. Minecraft に戻ってきて••• scoreboard が持っていた機能を思い出す 全レコードへの一括加減算 全レコードの max なので実際に 1. scoreboard 全体に i32_MAX - head を加算する 2. scoreboard 全体の max を取る 3. 取得した max と scoreboard 全体から i32_MAX - head を引く とすれば head 以下で生きている最大の address、即ち GC の境界 が取れることがわかる 45/53
46. ring に戻ってみよう 例えば得られた境界が 0x9000 だとする 1. addressRing の先頭を peek する 2. 境界値以下であるなら pop し、その address の領域を空にする 3. このループ^2を 2 の条件が満たされる限り回し続ける 4. 最後に、次回の GC で別の区間を見るために head を一つ進める できた！！！！！！ 46/53
47. まとめ (1/4) 動的 index がない → path を動かさず、木の方を変形する 47/53
48. まとめ (2/4) 動的 index がない → path を動かさず、木の方を 変形する entity の消滅をフックできな い → ライフタイムの異なる 2 つ の状態を用意して、そこに生 じる集合としての差分を利用 する 48/53
49. まとめ (3/4) 動的 index がない → path を動かさず、木の方を変形する entity の消滅をフックできない → ライフタイムの異なる 2 つの状態を 用意して、そこに生じる集合としての 差分を利用する 差集合も条件付き max もない → 全てのゴミを探さず境界問題に変換 し、i32 の値域を回して普通の max に する 49/53
50. まとめ (4/4) 動的 index がない → path を動かさず、木の方を変形する entity の消滅をフックできない → ライフタイムの異なる 2 つの状態を用意して、そこに生じる集合としての差分 を利用する 差集合も条件付き max もない → 全てのゴミを探さず境界問題に変換し、i32 の値域を回して普通の max にする できない操作を求める代わりに、問題の形を変える そんな形で Minecraft のコマンド体系で人々は過ごしているのでした おしまい 50/53
51. 謝辞 テストに付き合ってくださった方々 (敬称略) @yanorei32, @syugasato, あにみゃん, @Tenasub2021 登壇資料作成を手伝ってくださった方々 @Kory__3, @hsjoihs 昨日の深夜 2 時半に唐突に頼んだクリーパーのイラストを 7 分で書いてくれた方 @nukknu99 51/53
52. 不幸な GC ちぇん / Chen 2026/08/22 Kernel/VM 探検隊@東京 No19
53. おまけ: この ring はどう維持する？ 新しい entity に渡す address は実装側で自由に決められた そこで allocation のたびに GC を走らせて head を進める head と末尾の address の間に空きを作る 末尾が 0 の場合は 0x10000 として扱う その中間値を新しい address として末尾へ追加する こうして、 head から見て降順になるという条件を保ったまま address を増やせる 53/53