Scheme:組込み・リアルタイム用処理系
組込み and/or リアルタイム処理を目指したScheme/Lisp処理系を語ってみる。 (「組込み」と「リアルタイム」は直交する概念だろうけど、 なんとなく共通部分が多そうなのでまとめてみた。)
実装
「組込み」and/or「リアルタイム」を掲げてる処理系
BIT
Danny Dube氏の組込み用 実装。 size-optimizeなので速度はそれほど出ない。8bit CPU 68HC11等が ターゲット。memory efficientなGC実装が特徴。
L
Rodney Brooksらがロボットの制御に使っているLisp。 リアルタイムかつ細かいプロセスを大量に作って並行に処理できるらしい。 http://citeseer.nj.nec.com/32508.html
Lego/Scheme Compiler
snow:Lego MindStormsを制御するコードを作成するコンパイラです。 http://www.cs.indiana.edu/~mtwagner/legoscheme/
GOOL/GOAL
Naughty Dogがゲーム用に開発したLisp。 GOOLはPSの「クラッシュバンディクー」でイベント、アニメーションを 記述するために使われた。 GOALはPS2の「Jak and Daxter」の開発に使われた。 確かGOOLはイベントエンジンの解釈するバイトコードにコンパイルされるんだが、 GOALの方はPS2のネイティブコードへとコンパイルされ、ゲームエンジンそのものが GOALで記述されている、と聞いた。メモリアクセスのクロック単位でのタイミング 合わせなど非常にシビアな調整にもGOALは役に立ったとか。 (でも多分、ランタイムのメモリアロケーションとかはGCではなくプログラマが 緻密に管理してると思う。PS2でGCにバスを取られると痛いから)
- http://www.franz.com/success/customer_apps/animation_graphics/naughtydog.lhtml
- http://www.gamasutra.com/features/20020710/white_02.htm
要素技術
関連資料
- http://practical-scheme.net/docs/ILC2002.pdf STkの改造版をSCEのPS2とかGSCubeとかでリアルタイムレンダリングに 使ってみた話。リアルタイム部分ではSchemeは走ってないので ちとずれるけど、一応。
- A Real-Time Garbage Collector Based on the Lifetimes of Objects - HENRY
LIEBERMAN AND CARL HEWITT, MIT Artificial Intelligence Laboratory
http://lieber.www.media.mit.edu/people/lieber/Lieberary/GC/Realtime/Realtime.html
snow:少し古いですが概要をつかむのに良いと思います。
- Real-Time Replication Garbage Collection - Scott Nettles and James
O’Toole
http://citeseer.nj.nec.com/nettles93realtime.html
snow:コレクターがコンカレント実行可、ポータビリティーの良さに特徴。でも良い話ばかりでは....(笑
議論、コメント
- snow:リアルタイム用(non-stop)を考えると、やはりGC。それも最悪時が問題となります
- トータルのGCコストを下げるには「GCを起こす頻度を下げる」も有効と思われます。例えば一時的に利用されるセルはコンパイラーの助けを借りてスタックにアロケートするなど色々考えられます。しかし、それでは最悪時の助けにはなりません。メモリーを使い切ったところが最悪時なのですから.....
例えば128Kを使い切るのに5分しか持たないのを20分持つように出来たとしても、止まる時間が同じならば程度の問題で根本的な解決にはならないと思います。その意味で世代別GCも助けにはならないでしょう。これがリアルタイムシステムの問題を難しくしていると思います。
- 一方でGCのストップ時間を減少させるには、現状ではIncremental GCということになると思います。そして恐らく一番問題となるのは初期化コストではないでしょうか。そこでトータルのGCコストが多少悪くなっても初期化コストが激減するようなGCは無いものかと探索を始めています。
いいの知ってたら教えてください m(_ _)m
- でも本当は目から鱗のおちるような解決法がないかと夢を見ています。ロマンです(笑
- Shiro: Ikuo Takeuchi, Kenichi Yamazaki, Yoshiji Amagai, Masaharu Yoshida, Lisp can be "Hard" Real Time, in Proceedings of JLUGM 2000. では、 mark&sweep incremental GC w/ write barrierを使ってます。 TAO/SILENTマシンで、33MHzのCPUで割込みに対するGCによるディレイが 平均10〜20usec, 最悪120usecとか。 ポイントはGCの不可分な処理をなるべく細かく分けてる、ってとこでしょうか。 ハードを自前で持っているのでwrite barrierがマイクロコードで書けるという 利点もありますが。 (JLUGMのproceedingsは入手困難かもしれませんが、探せばWebに出ていそうな気が します)。
- ねるWiki:ねる: 横から失礼します。'Lisp can be "Hard" Real Time' の PDF、これでしょうか。
- Shiro: ああそうだ。本家にあったのをすっかり忘れていました。thx.
- snow: 早速拝見いたします! 感謝 感謝
- snow: まだザクッと眺めてみただけなのですが、なるほど〜と思いました。これまでルートセットのスキャンをインクリメンタル化するには、write barrierをルートセットにもかける必要があり、その場合にCスタックやコントロールスタックもそれに含まれてしまうので、例えOSやハードウエアの機能を使っても厳しいなと考えていました。でも書き換えのあった部分(dirty page)だけを検出してそこを繰り返し対象がなくなるまでスキャンしつづける手があったんですね....仮想記憶の使えるCPUと環境が必要となるけど、これはとても参考になりました。どうもありがとう ^_^/