マイコン向け処理系の実装戦略を調べる会

nmosh

追記: mruby/c 1.1にはGCが有るらしい http://www.s-itoc.jp/news/notice/726
C向けにヒープ実装を用意するにあたって、まぁ富豪的にガツンとやってしまえば良いんじゃないかと適当に考えていたけど、営業上どうしても32KiBヒープで動くアプリを用意する必要が出てきたので比較的真面目にROM化やポインタの圧縮等を考える必要が出てきた。というわけでいくつか処理系を見てまわることにする。

PICOBIT (R4RS Scheme)

Gambitの一派としてPICOBITが有り、Schemeで書かれたTCP/IPスタック(https://github.com/stamourv/s3 , http://users.eecs.northwestern.edu/~stamourv/slides/s3-sw08.pdf )のようなアプリケーションも抱えている。
興味深いのは、わざわざ自身のVMをコンパイルするためのCコンパイラまで用意していて(SIXPIC)、当時の純正コンパイラを超えたパフォーマンスを出している点。これはwhole program optimizationや関数ポインタのfold等を実装しているためとしている。(amalgamationする等しないとフェアな比較でない気もするけど)
オブジェクト表現等は標準的な実装。32bitワードにcar/cdrを収めてcellとしている。

mruby, mruby/c (Ruby)

意外にmrubyはこの領域に何も提供していない。mrubyはかなり真面目なヒープ実装を持っているがメモリ消費量も400KiB程度(mruby/cサイトの公称)でマイコン向けには厳しいものがある。
mruby/cはmrubyのバイトコードを実行するコンパクトな処理系で今回のターゲットにより近いが、そもそもGCをしない(追記: 1.1には有るらしい)。オブジェクトも単なるunionで、逆にここまで単純化して良いのかというところ。"グルーロジックをRubyで書ける"というポイントをどの程度評価するのか。下のmJSも同じような立ち位置のインタプリタと言えるが、mJSはGCも実装している。
(追記: mruby/c 1.1以降には有るというリファレンスカウント式のGC https://github.com/mrubyc/mrubyc/blob/814725908305f380cd761057dd97fd616b8bec07/src/value.c#L154 )

MicroPython (Python3)

MicroPythonはこの手の言語として考えうる殆どの機能を備えている。ROM化、マルチスレッド、インラインアセンブラ、バイトコードコンパイル、マシンネィティブワードの使用(Viper)、補完付きのREPL、...。
ワード中のオブジェクト表現は4種用意されていて、コンパイル時に選択される。

  1. MICROPY_OBJ_REPR_A: ポインタを4バイトアラインで表現する
  2. MICROPY_OBJ_REPR_B: ポインタを2バイトアラインで表現する(fixnumを犠牲にしたコンパクト表現、デフォルトで使用されるのはPIC16のみ)
  3. MICROPY_OBJ_REPR_C: 32bitマシン向けのNaN boxing
  4. MICROPY_OBJ_REPR_D: 64bitマシン向けのNaN boxing(ポインタは32bit範囲)

特徴的なのはinternされた文字列として"qstr"を持っていることで、これにより文字列オブジェクトをinternしてROM上に配置することで省メモリを実現できる。

eLua (Lua)

eLuaは通常のLua5.1にいくつかパッチを当てて組込み動作に向くようにしたもので、uIPのバインディングやXMODEMのサポート、I/O等ライブラリサポートの方がどちらかというと力点になっているように見える。オブジェクト表現等も通常のLuaと同等ということになる。
LTR(Lua Tiny RAM)はC APIを想定した専用のクロージャであるlightfunctionとROM化されたtableであるrotableを実装する。どちらもLuaコードから直接定義することはできない。つまり、純粋にアプリケーション統合のための機能ということになる。

JerryScript (JavaScript)

元Samsung、現JS Foundation( https://github.com/jerryscript-project/jerryscript/pull/1446 )のJerryScriptは、16bitの圧縮ポインタを採用し、512KiBヒープを表現する。オブジェクトの各プロパティは線型リストに接続され、さらに参照のキャッシュとして"LCache"と呼ぶハッシュテーブルを持っている。このレベルの考察を持っている組込みJavaScriptは意外と珍しい。
ワードは8バイトアラインポインタで、fixnumは29bits。
また、JerryScriptはASTを構築せず直接バイトコードをemitする。MicroPythonはASTを構築してconstant folding等の最適化を実装しているのと比べると対称的と言える。

Espruino (JavaScript)

EspruinoはJerryScriptのようにバイトコードを出力するのではなく、パーサが直接コードを実行する。歴史的にはこちらのデザインの方が一般的だった気がするが、mrubyやLuaのようなバイトコード型の実装が組込み言語として一般化したので比較的珍しい構成と言える。
ヒープは16bytesまたは12bytesの"block"単位で処理される(32bitポインタ環境では32bytes)。特にオブジェクトを1024個以下を想定して12bytesで済ませるモードは強烈な割り切りと言える。stringやバッファは複数のblockを占有してポインタ用のフィールドに実データを埋め込んでいる(1ブロックあたり4〜5バイト)。これはオブジェクト管理方法を相当に単純にできるが当然オーバーヘッド面では不利になる。
Espruinoの置いているデザインゴールがすごくて:

Espruino is designed to run on devices with very small amounts of RAM available (down to 8kB) while still keeping a copy of the source code it is executing so you can edit it on the device. As such, it makes some compromises that affect the performance in ways you may not expect.

Forthでもこんなのやらないと思う。

mjs (JavaScript)

組込みHTTPサーバのmongooseで知られるCesantaの組込みJavaScriptエンジンmjsは、旧v7( https://github.com/cesanta/v7 )を受けついでいるもので、RAM footprintは脅威の1KiBとしている。もっとも、RegExpのような標準ライブラリを欠いている他、言語的には相当な制約を設けている。Schemeで言うと:

  • lambdaなし。letのみ。
  • eqv? なし。 eq? のみ。
  • stringはbytevectorのsyntax sugar。

ただしJSON parser等は備えている。GCやオブジェクト表現にはコレといった特徴はない。
mjsは自社のMongooseOS用のJavaScriptインタプリタ( https://mongoose-os.com/docs/quickstart/using-javascript.html )として使用されていて、そこでは "One of which is an mJS library that adds JavaScript prototyping ability." と明確にプロトタイプ用の環境であることを打ち出している。
実装はバイトコードベースのインタプリタでヒープ実装も普通。ASTを持たず、直接バイトコードをemitする。