I'm struck with an idea to implement CPU emulation using JIT like technique on JavaScript. Basically, the emulator generates JavaScript function which emulate a target binary sequence by the basic block, then cache it in hash. The code could be like 'cache[pc] = eval(jit()); cache[pc]();'.
Since I'd like to know how this technique could be effective, I just make a tiny pseudo emulator and estimate its performance. The result show the JavaScript CPU interpretor will be x100 slower than a native code. Modern JavaScript engines become faster and faster. But it seems to be still slow. On the other hand, qemu-arm seems to be quite fast. It's just several times slower than the native one. So how about my emulation using JIT on JavaScript? It's slower than qemu. But not so bad. It might be pretty fast than native CPU interpreter.
As supplements, I must say that this benchmark treats just one simple case and the result will be changed by loop size, count, and JIT overheads in various situations.
2011年9月19日月曜日
2011年9月14日水曜日
g++ bit-fieldsの謎
C++でbit field使ってるコードでハマった。
擬似的に書くと以下のようなクラス。
class A {
signed a: 15;
signed b: 15;
bool c: 1;
bool d: 1;
void *e;
};
んで、Vector<A>を比較するのに、性能を気にしてsizeof(A)*lengthでmemcmp。
x86やARMでは問題ないんだけど、x86_64になると問題発生。
実質12Bのペイロードに対して、sizeof(A)が16。
全フィールドを初期化しても未初期化領域が必ず残ってしまうという罠。
ポインタがいるから8Bに揃えてるんだろな、と思ってポインタを頭に持って行っても結果はかわらず。
x86_64 ABI的には構造体は8Bアライメントなのか。。。
ということで、memcmpでは不一致が発生してしまう。
ちなみに32bit環境ではsizeof(A)は8でびっしり詰まってる感じ。
その後、色々試しているうちに気づいたんだけど、
bit-fieldが15,15,1,1の組み合わせだと詰め込んで32bitに納めてくれるんだけど、
31,31,1,1の組み合わせだと64bitに詰め込んでくれない。
けど、31,1,31,1の順に並び替えれば64bitに納めてくれる。。。どんな規約なんだ？
・・・と、そうこうしてたら@nminoru氏のABI仕様の指摘。
出てきた順にLSBから32bit単位で詰めてく模様。
はみ出そうになったらパディングして次のアライメントから。
なので、15,15,1,1の組み合わせは(15+1)x2になってるわけじゃなく、
[14:0], [29:15], [30] [31]というマップになるようだ。
だから、31,31,1,1の場合は、31,31+1,1となって、31,1,31,1の場合は(31+1)x2。
うん、納得だ。__attribute__((packed))がbit-fieldに対しても効果があることも、
32bit単位のアライメントを無効化してくれると思えば納得なのであった。
という事で、もっと仕様をちゃんと読め的な、いつもどおりの教訓を胸に抱きつつ、次号にコンティニュー。
参考）
IA-32 ABI : http://www.sco.com/developers/devspecs/abi386-4.pdf#page=33
x86_64 ABI: http://www.x86-64.org/documentation/abi.pdf#page=14
擬似的に書くと以下のようなクラス。
class A {
signed a: 15;
signed b: 15;
bool c: 1;
bool d: 1;
void *e;
};
んで、Vector<A>を比較するのに、性能を気にしてsizeof(A)*lengthでmemcmp。
x86やARMでは問題ないんだけど、x86_64になると問題発生。
実質12Bのペイロードに対して、sizeof(A)が16。
全フィールドを初期化しても未初期化領域が必ず残ってしまうという罠。
ポインタがいるから8Bに揃えてるんだろな、と思ってポインタを頭に持って行っても結果はかわらず。
x86_64 ABI的には構造体は8Bアライメントなのか。。。
ということで、memcmpでは不一致が発生してしまう。
ちなみに32bit環境ではsizeof(A)は8でびっしり詰まってる感じ。
その後、色々試しているうちに気づいたんだけど、
bit-fieldが15,15,1,1の組み合わせだと詰め込んで32bitに納めてくれるんだけど、
31,31,1,1の組み合わせだと64bitに詰め込んでくれない。
けど、31,1,31,1の順に並び替えれば64bitに納めてくれる。。。どんな規約なんだ？
・・・と、そうこうしてたら@nminoru氏のABI仕様の指摘。
出てきた順にLSBから32bit単位で詰めてく模様。
はみ出そうになったらパディングして次のアライメントから。
なので、15,15,1,1の組み合わせは(15+1)x2になってるわけじゃなく、
[14:0], [29:15], [30] [31]というマップになるようだ。
だから、31,31,1,1の場合は、31,31+1,1となって、31,1,31,1の場合は(31+1)x2。
うん、納得だ。__attribute__((packed))がbit-fieldに対しても効果があることも、
32bit単位のアライメントを無効化してくれると思えば納得なのであった。
という事で、もっと仕様をちゃんと読め的な、いつもどおりの教訓を胸に抱きつつ、次号にコンティニュー。
参考）
IA-32 ABI : http://www.sco.com/developers/devspecs/abi386-4.pdf#page=33
x86_64 ABI: http://www.x86-64.org/documentation/abi.pdf#page=14
2010年8月28日土曜日
The Singularity System
ここのところ、まったく時間がなかったのですが、出張帰りの飛行機で時間があったので、Communications of the ACMに寄稿されていたSingularityの記事を読んでみました。
SingularityとはMicrosoft Researchによる研究段階のOperating Systemです。micro kernelを採用しており、コストの高いプロセス間通信を解決する方法としてSIPと呼ばれる機構と、高位言語による記述を採用している点が特徴かと思います。
大雑把な説明はWikipediaの解説が手っ取り早いでしょうか。
Singularityでは、OSを含めて高位言語で記述するのが基本です。kernel本体はSing#と呼ばれるC#の拡張言語で記述され、他にはC#、F#、Visual Basicあたりがサポートされています。
Wikipediaを見るとSIPはmicro kernelと各サーバ群との通信を最適化するための仕組みのようにも見えますが、記事によるともっと一般的なプロセス分離の仕組みのようです。
Singularityにおけるプロセス保護は多層で実現（multiple layers of protection）され、基本的な方式がSIP、二次的な方式が仮想メモリ空間による分離（近代的なOSが一般的に採用している方法）になります。
SIPによる分離では、同一メモリ空間内にページ単位で複数プロセスを貼り付け、仮想メモリ空間切り替えによるプロセス切り替えコストを除去する事が目的となっています。ページ保護は利用しているようなので、SIPで分離されたプロセス間の切り替えでは、ページのアクセス権限だけ書き換えるのかな？この辺は詳しく書かれていないので想像です。このへんの保護は言語レベルでのサポートや形式検証なども使えるみたいです。
一般的にプロセス単位で仮想メモリ空間を切り替えるメリットは、メモリ保護だけでなくメモリ管理にもあります。プロセスにつきヒープとスタックという二種類の可変長作業域が必要となります。一般的にはヒープは下位アドレスからプラス方向に、スタックは上位アドレスからマイナス方向に伸びていくことで実現していますが、同じアドレス空間に複数のプロセスを配置するとなると、ヒープを拡張しようとしたら、別のプロセス空間が邪魔で・・・なんて状況が起き得ます。
680x0時代のMac OSでは、MMUが使えなかったため、ハンドルとコンパクションという考え方で対応してきました。メモリはハンドルで管理し、必要なときだけロックをかけてハンドルからポインタに変換します。使い終わったメモリはすぐにアンロックすることで、ポインタは無効になります。このお約束を守ることで、連続したメモリ領域がなくなった時、コンパクションによってロックされていないメモリを移動し、メモリ再配置による最適化を行うことができるようになります。
Singularityでこの辺りをどう対処しているのかは読み取れませんでした。Garbage Collectionによるメモリ管理をOS含めて導入しており、runtimeによるポインタチェックも行っているようなので、その気になればコンパクションもできるのかもしれません。今時のメモリサイズであれば、コンパクションがなくて実用上問題にならないのかなぁ。
あるいは、記事の例を見ると、そうは言ってもSIPによる分離は共有ライブラリやコンポーネント、Plug-insなどのレベルでメモリ保護を実現するための機構として利用しているようにも見え、実際には仮想メモリ空間による分離もかなり積極的に使っているのかもしれません。
SIPを導入するためには、Javaのような実行時のポインタチェック、配列領域チェックなどが必要になります。この記事の結論では、これらのruntimeのコストは5%程度の効率低下に留まり、仮想メモリ分離をやめたことによるパフォーマンスゲインが38%もあるため、総じて安い、という事のようです。
SIPを使うとプログラムはリロケータブルにする必要があるので、元々共有ライブラリで実装されていたような物は差がないんでしょうが、プロセス分離に適用しちゃうとローダがリロケートするコストが馬鹿にならないような気はしました。
SIP間通信の仕組みとしては、強く型付けされたパイプを使っているようです。実データは同一メモリ空間内のExchange Heapと呼ばれるところに格納され、ゼロコピーでデータ交換しているように読めます。このあたりが効いて、low latency、high bandwidthなプロセス間通信が実現できる、という事のようです。また、通信には"contract"と呼ばれる仕組みが使われており、この辺も突っ込んで調べてみると面白そう。通信データを入出力としてステートマシンを記述して制御しているようなので、形式検証を使ってプロトコルチェックとかできるのかも。
最後の方では、kernelにGarbage Collectionを適用する事の是非について触れられています。kernel objectの多くはlifetimeが非常に長く、プロセスの開始から終了まで張り付いています。この種のobjectを大量にGCで管理したところで、メモリ回収のwalkingにかかるコストが大きくなるだけで、あまり旨みがないのでは、といった議論があるようです。
という事で、最近は懐古趣味ばかりでしたが、めずらしく先端研究についても調べてみました。
SingularityとはMicrosoft Researchによる研究段階のOperating Systemです。micro kernelを採用しており、コストの高いプロセス間通信を解決する方法としてSIPと呼ばれる機構と、高位言語による記述を採用している点が特徴かと思います。
大雑把な説明はWikipediaの解説が手っ取り早いでしょうか。
Singularityでは、OSを含めて高位言語で記述するのが基本です。kernel本体はSing#と呼ばれるC#の拡張言語で記述され、他にはC#、F#、Visual Basicあたりがサポートされています。
Wikipediaを見るとSIPはmicro kernelと各サーバ群との通信を最適化するための仕組みのようにも見えますが、記事によるともっと一般的なプロセス分離の仕組みのようです。
Singularityにおけるプロセス保護は多層で実現（multiple layers of protection）され、基本的な方式がSIP、二次的な方式が仮想メモリ空間による分離（近代的なOSが一般的に採用している方法）になります。
SIPによる分離では、同一メモリ空間内にページ単位で複数プロセスを貼り付け、仮想メモリ空間切り替えによるプロセス切り替えコストを除去する事が目的となっています。ページ保護は利用しているようなので、SIPで分離されたプロセス間の切り替えでは、ページのアクセス権限だけ書き換えるのかな？この辺は詳しく書かれていないので想像です。このへんの保護は言語レベルでのサポートや形式検証なども使えるみたいです。
一般的にプロセス単位で仮想メモリ空間を切り替えるメリットは、メモリ保護だけでなくメモリ管理にもあります。プロセスにつきヒープとスタックという二種類の可変長作業域が必要となります。一般的にはヒープは下位アドレスからプラス方向に、スタックは上位アドレスからマイナス方向に伸びていくことで実現していますが、同じアドレス空間に複数のプロセスを配置するとなると、ヒープを拡張しようとしたら、別のプロセス空間が邪魔で・・・なんて状況が起き得ます。
680x0時代のMac OSでは、MMUが使えなかったため、ハンドルとコンパクションという考え方で対応してきました。メモリはハンドルで管理し、必要なときだけロックをかけてハンドルからポインタに変換します。使い終わったメモリはすぐにアンロックすることで、ポインタは無効になります。このお約束を守ることで、連続したメモリ領域がなくなった時、コンパクションによってロックされていないメモリを移動し、メモリ再配置による最適化を行うことができるようになります。
Singularityでこの辺りをどう対処しているのかは読み取れませんでした。Garbage Collectionによるメモリ管理をOS含めて導入しており、runtimeによるポインタチェックも行っているようなので、その気になればコンパクションもできるのかもしれません。今時のメモリサイズであれば、コンパクションがなくて実用上問題にならないのかなぁ。
あるいは、記事の例を見ると、そうは言ってもSIPによる分離は共有ライブラリやコンポーネント、Plug-insなどのレベルでメモリ保護を実現するための機構として利用しているようにも見え、実際には仮想メモリ空間による分離もかなり積極的に使っているのかもしれません。
SIPを導入するためには、Javaのような実行時のポインタチェック、配列領域チェックなどが必要になります。この記事の結論では、これらのruntimeのコストは5%程度の効率低下に留まり、仮想メモリ分離をやめたことによるパフォーマンスゲインが38%もあるため、総じて安い、という事のようです。
SIPを使うとプログラムはリロケータブルにする必要があるので、元々共有ライブラリで実装されていたような物は差がないんでしょうが、プロセス分離に適用しちゃうとローダがリロケートするコストが馬鹿にならないような気はしました。
SIP間通信の仕組みとしては、強く型付けされたパイプを使っているようです。実データは同一メモリ空間内のExchange Heapと呼ばれるところに格納され、ゼロコピーでデータ交換しているように読めます。このあたりが効いて、low latency、high bandwidthなプロセス間通信が実現できる、という事のようです。また、通信には"contract"と呼ばれる仕組みが使われており、この辺も突っ込んで調べてみると面白そう。通信データを入出力としてステートマシンを記述して制御しているようなので、形式検証を使ってプロトコルチェックとかできるのかも。
最後の方では、kernelにGarbage Collectionを適用する事の是非について触れられています。kernel objectの多くはlifetimeが非常に長く、プロセスの開始から終了まで張り付いています。この種のobjectを大量にGCで管理したところで、メモリ回収のwalkingにかかるコストが大きくなるだけで、あまり旨みがないのでは、といった議論があるようです。
という事で、最近は懐古趣味ばかりでしたが、めずらしく先端研究についても調べてみました。
2010年2月24日水曜日
カーネル／VM探検隊
同じ会社にしばらくいると、少し外の空気を吸わないと・・・という気分になります。
Lionsもその一環なのですが、しばらく前にngcomで「最近は勉強会が流行っている」
という話を聞いたので、なにか面白そうなものがあれば参加したいな・・・と思い
目をつけていたのがカーネル／VM探検隊。ちょうど仕事にも余裕が出てきたところなので、
平日開催という敷居の高さを乗り越えて（午後からエスケープしたとも言う）参加して
きました。
まったく知った顔がいない、という状況は凄く久しぶりで、言葉通じるのにまるで
海外出張みたいにドキドキしてしまいました（笑。そうは言っても、実は大学の同期も
いたのですが、すいません人を覚えるのがトコトン苦手な私。。。うっすらと記憶に
あるものの、よく覚えていませんでした（汗。一応、だんだんと記憶は戻ってきて
最後にはなんとなく思い出してたんですよ。。。とフォローはしておきます（笑。
本業の面では畑違いなんですが、Plan 9とか、SheevaPlugとか、プライベートな嗜好では
思いっきりストライクゾーンで、人見知りとは別の意味でドキドキワクワクな時間でした。
LTのタイマー割り込みの話とか妙に盛り上がって（一部の？）参加者のハイレベルっぷりに
ときめいたりしてました。自分はv6のclock.c callouts近辺のコードしか頭になくて、
どこまで話についていけてたかわかりませんが。。。
先日の社内でのsignal話もそうなんですが、今まで身近にkernel hackerがいるって状況に
なかなか巡り会えなかったので、最近のこの体験はちょっとした感動です。
そのうちLTネタくらいは出したいなぁ。
P.S.
スライドがド派手な人が多くて驚いた。最近はこれが普通なのか。。。あと、OS Xを
使って長いくせに、画面の一部を拡大したり・・・って機能をまったく知らなかったorz
Lionsもその一環なのですが、しばらく前にngcomで「最近は勉強会が流行っている」
という話を聞いたので、なにか面白そうなものがあれば参加したいな・・・と思い
目をつけていたのがカーネル／VM探検隊。ちょうど仕事にも余裕が出てきたところなので、
平日開催という敷居の高さを乗り越えて（午後からエスケープしたとも言う）参加して
きました。
まったく知った顔がいない、という状況は凄く久しぶりで、言葉通じるのにまるで
海外出張みたいにドキドキしてしまいました（笑。そうは言っても、実は大学の同期も
いたのですが、すいません人を覚えるのがトコトン苦手な私。。。うっすらと記憶に
あるものの、よく覚えていませんでした（汗。一応、だんだんと記憶は戻ってきて
最後にはなんとなく思い出してたんですよ。。。とフォローはしておきます（笑。
本業の面では畑違いなんですが、Plan 9とか、SheevaPlugとか、プライベートな嗜好では
思いっきりストライクゾーンで、人見知りとは別の意味でドキドキワクワクな時間でした。
LTのタイマー割り込みの話とか妙に盛り上がって（一部の？）参加者のハイレベルっぷりに
ときめいたりしてました。自分はv6のclock.c callouts近辺のコードしか頭になくて、
どこまで話についていけてたかわかりませんが。。。
先日の社内でのsignal話もそうなんですが、今まで身近にkernel hackerがいるって状況に
なかなか巡り会えなかったので、最近のこの体験はちょっとした感動です。
そのうちLTネタくらいは出したいなぁ。
P.S.
スライドがド派手な人が多くて驚いた。最近はこれが普通なのか。。。あと、OS Xを
使って長いくせに、画面の一部を拡大したり・・・って機能をまったく知らなかったorz
2009年11月15日日曜日
Go
Google発の新言語、というトピックには興味がなかったんだけど、なにやら別の面で気になる存在に。
という事で、ベル研からGoogleへ移籍したUNIXチームの面々が開発者なんですね。どうりで変なキャラがマスコットなわけだ。6版読んでる関係からPlan 9周辺もそれなりに調べてまして「間違えて“Inferno Programming with Limbo”を二冊買っちまったー」とか、こんなコレクターアイテム重複させてどうすんだろ・・・と思ってた矢先でした。
（VM絡みも別件で調べてて、Disもちょっとしたマイブームなんですw）
新言語習得という意味では、今はOCamlで苦戦してるので、すぐに手を出すつもりはないんですが・・・とりあえず処理系だけでもインストール、という事で非gcc版をインストールしてみました。
GNUなconfigureの作法に従わないあたり、らしいな〜と思いましたが（笑）。Plan9portとかInfernoと似たようなbuild方法ですね。ターゲットでDisもサポートしないかな〜。Infernoの裾野が広ければひと月もまてば誰かがportするんだろうけど。。。
次にGoogleが戦略的に出してくるとしたらVMですかね。個人プレイ中心ってイメージなので、企業としてのポートレートみたいなのがあるのか知りませんが。まぁ、悩みどころですね、うん。。。
という事で、ベル研からGoogleへ移籍したUNIXチームの面々が開発者なんですね。どうりで変なキャラがマスコットなわけだ。6版読んでる関係からPlan 9周辺もそれなりに調べてまして「間違えて“Inferno Programming with Limbo”を二冊買っちまったー」とか、こんなコレクターアイテム重複させてどうすんだろ・・・と思ってた矢先でした。
（VM絡みも別件で調べてて、Disもちょっとしたマイブームなんですw）
新言語習得という意味では、今はOCamlで苦戦してるので、すぐに手を出すつもりはないんですが・・・とりあえず処理系だけでもインストール、という事で非gcc版をインストールしてみました。
GNUなconfigureの作法に従わないあたり、らしいな〜と思いましたが（笑）。Plan9portとかInfernoと似たようなbuild方法ですね。ターゲットでDisもサポートしないかな〜。Infernoの裾野が広ければひと月もまてば誰かがportするんだろうけど。。。
次にGoogleが戦略的に出してくるとしたらVMですかね。個人プレイ中心ってイメージなので、企業としてのポートレートみたいなのがあるのか知りませんが。まぁ、悩みどころですね、うん。。。
登録:
投稿 (Atom)