はじめに
ruby3で導入されるRactorという機構があり、そこの提案の中で
This model is similar to Racket's Place abstraction.
という記載があったのでRacketのPlaceを探してみると、Place自体はRacketの公式ドキュメント に記述を見つけることができました。
更に追ってみるとこれらの源流になっている気配がする2011年のDLS(Dynamic Languages Symposium)で Places: Adding Message-Passing Parallelism to Racket という論文が見つかったので、こちらについてかいつまんで紹介したいと思います。(RubyやRacketの話はせず、この論文の話のみを行います。RubyやRacketにある機能がこの論文と同じモデルなのか等は特に調査していません。）
自分が面白いなと思ったところだけを紹介するので、気になった人はぜひ論文を読んでみてください。
論文について
Racketにmesage passingベースの並列性サポートである Place を実装する提案です。
メッセージパッシングベースの並列性サポートというと色々あるわけですが、この提案ではsequentialな処理を前提とした巨大なランタイムシステムに、後入れで並列性を（無理なく）入れるところに工夫があるようです。*1
従来型の手法としてはUnixのforkをつかう物が上げられますが、この手法だとタスク間の通信がbyte streamに制限されてしまうため抽象化の難しさや通信効率の低下などの問題が生じることがあります。
PlaceではOSによるサポートではなくランタイムによるサポートを実現することで、上記のような問題を回避しようとしています。
Placeの概要
Racketのランタイムを起動すると、まず単一のinitial placeが作成されます。 そこから追加のplaceを作成したり、メッセージを送信したりすることで並列性を実現します。
Placeは基本的には独立したRacket virtual machineであり*2、GCなどもPlaceごとに実行されます。*3
メッセージはplace channelを経由してやりとりされます。place channelにはlistやpairなどの構造化されたデータを送ることができます。またplace channel自体を送信することもできるので、直接の親子関係にないplace同士も直接やりとりさせることができます。
place channelで送れる値は基本的にimmutable(一部atomicなデータのvectorなど例外あり）です*4が、この制約があるとthunkなども送れなくなります。*5
Thread等の場合は開始用のコードをthunkで指定したりできるのですが、Placeではそれができないので、Placeを新しく作成する場合は module pathで指定し、そこでexportされたmain関数を実行することでPlaceの開始処理を行います。*6
(このあとAPIの話とマクロを利用した抽象化がありますがカットするので気になる方は論文を読んでください)
実装について
Placeがない状態のRacket virtual machineは単一のgarbage collectorとOS threadから成り立ちます。 Racketにはthreadのサポートがありますが、これは並行性のサポートであり並列性でのサポートではないそうです。（concurrentなタスクに分割することはできるが、マルチコアで同時に実行させてパフォーマンスを上げるものではない）
PlaceありのRacketではOSのスレッドを複数使い、Racket virtual machineを稼働させます。 並列実行でのパフォーマンスを向上させるために、Placeは可能な限り独立・疎結合になっており、メモリ領域も分離させることで局所参照性を最大化させています。この分離があることで、PlaceごとにGCが可能になるといった点もあります。*7 PlaceごとのGCに加えて、全Placeで共有されているmaster GCというのもあり、こちらはグローバルで共有されているオブジェクトを管理しているようです。
global変数とthread local変数
Racketは10年半開発されてきており、コードベースにはたくさんのグローバル変数があります。 これがスレッド導入の障壁であり、Place導入のためにはこれの解決が必須になります。
残念ながらすごく手軽に解決する方法はなさそうで、grep とCIL解析を使用して、Racket 実装内の 719 個のグローバル変数を監査しタグ付けし、以下のように分類していったようです。
- READ_ONLY: 読み取り専用のシングルトン・オブジェクト(scheme_true, scheme_falseなど)
- SHARED_OK: 共有が許可されているもの
- THREAD_LOCAL_DECL: Placeごとに局所化が必要なもの
グローバル変数を局所化させるにあたって、大きく移動させるとランタイムシステムへの修正が大きくなりすぎる*8のでOSがサポートしているスレッドローカル変数を使用してplaceローカルな変数を作ったそうです。
thread local storageの操作には pthread_get_specific()より _threadlocal とか _declspec(thread) などのコンパイラが提供しているアノテーションを使ったほうが高速らしいのですが、OSによっては(macやwinなど）ではうまく動作しないようです。
windowsではコンパイラの提供するスレッドローカルのサポートがありますが、windows XPではDLL内では使えないようです*9
macはこの論文が書かれた時点では上記のようなコンパイラのサポートが提供されていないようです。
論文ではプリプロセッサを定義して、OSごとにスレッドローカル変数へのアクセス方法を切り替えるような工夫を行っています。
GC
racketの起動時にmaster GCはリードオンリーなグローバル変数やシンボルテーブル、解決済みのモジュールpathテーブルなどを割り当てます。 上記が終わったあと、initial placeはmaster GCから切り離され、自身専用のGCインスタンスを作成することになります。 このブートストラップフェーズのあとはmaster GCは通信チャンネルや共有される値の割当などごく少量のことしか行いません。
PlaceでのGCはplaceのローカルヒープを独立して回収するか、master GCと協力してglobalなオブジェクトを回収する(=グローバルコレクション)かに二分されます。 グローバルコレクションではすべてのPlaceが一時停止しますが、基本的にmaster GCからの割当はプログラムの初期化時にほぼ全てが終わるため、大体の状況ではプログラムの処理中で発生することはあまりないそうです。*10
グローバルコレクションを開始する際にはmaster GCがすべてのPlaceに対してmutationを停止し、収集を開始するようにシグナルを送ります。 すべてのPlaceがオブジェクトにマーク付けを行ったあと、master GCが不要なオブジェクトを回収します。 PlaceのローカルGCの場合はフラグメンテーションを防ぐためにオブジェクトを移動させますが、一方でmaster GCの場合は移動させません。*11
channel
前述のplaceローカルでのGCを成立させるためにチャンネルを介したメッセージングではデータをコピーして行います。 placeチャンネルはこのプロセスを新しいメモリをorphanアロケータに要求することで開始します。 orphanアロケータはすべての割当をどのGCによっても管理されていないメモリーブロックに対して行います。
次に、placeチャンネルはメッセージ全体をorphanアロケータに割り当てられたメモリーにコピーします。 コピーが完了したあと、メッセージにはオブジェクトの参照とmaster GCによって管理されている共有オブジェクトのみが含まれることになります。 その後、送信元のplaceはこの新しいメッセージとorphanアロケータによって割り当てられたメモリーを送信先のplaceへ送信します。
メッセージを受信したplaceチャンネルは、孤立したメモリーページをnursery generationとして採用し、ユーザープログラムにメッセージを返します。 nursery generationを経ても生き残ったメッセージコンテンツはplaceローカルなメモリーに再配置されます。(長さが1024byte以下の場合はnursery generationをスキップして直接ローカルアロケータにコピーするという最適化が入っているそうです。) このプロセスにより、送信側・受信側でアロケーションの調整なく非同期メッセージングが可能になります。*12
lock
上記の工夫で爆速racketが完成！と行きたいところですが、racketのGCでは mprotect() *13 がたくさん呼ばれており、これがボトルネックになることがあるようでした。
mprotectはOSのページテーブルロックを取得するため、通常のsequentialなracketで問題にならなかったmprotect()呼び出しが、placeありのracketでは並列にGCが走りlock contentionが高まり、ロック待ちでボトルネックになるという構造のようです。 この構造を回避するために、racket allocatorで大きなブロックを確保するようにすることでブロック数を削減し、結果的にmprotectの呼び出し回数を劇的に減らすようにしたそうです。
まとめ
実装には2年位かかったそうです。が、不具合などはかなり少なく実装できたそうです。 著者らが以前にランタイムシステムにconcurrencyサポートを実装した際は、数ヶ月の追加テストを行い多数のレースコンディションを発見したそう*14なので、sequentialが前提になっている巨大なランタイムに後からこのようなサポートを追加する場合はplaceのような実装方法を取ると良さそうですね。
ところでErlangはメッセージに流れるオブジェクト用のアロケーションだけ静的解析で検出して（軽量）プロセス用ヒープじゃなくて共有用ヒープにメモリ確保する。*15って書いてあったんですが、これは初耳でした。おもしろいですね。
ということで以上です。
*1:巨大なランタイムにlockを適切に入れていく作業はかなり大変なのは想像に難くない・・
*2:初期段階ではリードオンリーなコードやJITによって生成されたコードなどをplace間で共有することはないらしいですが、長期的にはやりたいとのこと
*3:こういうのがあると、全VMが止まるstop the worldとかを回避できたりするのでよいですね
*4:shared memoryなのでmutableなデータだとdata raceが発生する可能性があるので、この辺は大事ですね。
*5:thunkについては https://www.fos.kuis.kyoto-u.ac.jp/~igarashi/class/isle4-05w/text/eopl014.html などを参照
*6:なかなか豪快な作り方っぽさを感じますね。racket virtual machineの起動オーバーヘッドがどのくらいかはあまりわからないんですが、後述するmaster GCなどでの仮定などからも、起動時にまとめてplaceを作っておいて順次処理させるといった使い方が想定されていそうです。そもそもこれってconcurrentをサポートしたいと言うよりは、マルチコアなハードウェアを活かしたparallelな機構を備えたいという動機（concurrentサポート自体はすでにある）らしいので、そう考えるとplaceをたくさん動的に立てたいというシチュエーションは無いのだと思います。Erlangのようにたくさん（軽量）プロセスを立てて、たくさんメッセージを送り合うのとは思想が違うはず。
*7:（軽量）Process/ActorごとにGCというのはErlangとかPonyとかもそういう感じですね。
*8:大きな修正を入れないというのがPlace導入の最大の肝なのでここは重要
*9:vista以降なら使えるけど32bit racketはwindows xpで動作する必要があるなど歴史を感じる部分がありますね
*10:逆に言うと、そういう仕組みであることを理解して使わないとすごいことになりそう
*11:master GCが稀なのとコンパクションが不要になる程度の荒い粒度で管理されているそうなので必要なさそうですね
*12:普通に自分のplaceのGCが管理してるメモリー領域のポインタ渡すとlocal placeでGCが起きたときに死んだり、それをlockで回避しようとすると泥沼なので、それとは別などこにも所属してない領域にメモリを確保してそこでやりとりするって感じですね。
*13: mprotect()は、同一プロセス内のメモリ保護機能で、一時的にheapの特定領域をread onlyなどにすることができます。GC中にいじられないように保護してるんですかね？
*14:バグの質も異なるらしく、lockベースの実装では競合状態による見つけにくいタイミングバグ、placeのような実装では壊れた参照によるバグ（GCのタイミングでだいたい見つかる）ですぐ治るものだったそうです。
*15:The Erlang implementation employs static analysis to try to determine which allocations will eventually flow to a message send and therefore should be allocated in the shared heap.
