Optimizing direct threaded code by selective inlining
|
2007/11/21(水) 14:43:31
|
東大さんで今，mini-python のインタプリタを作るという演習をやっているそうな．
んで，今 twitter の柱の hayamizu 氏を筆頭に，空前の VM (仮想マシン) ブームが起きている感じ．
ちなみに，仮想マシンの本で僕が読んで良かったのは，Java 仮想マシン仕様の第二版と，コンパイラとバーチャルマシンって本かなぁ (そんなに詳しくない）．
ところで，仮想マシンの構造ってのは，ナイーブには単純で，ひたすら switch 文で命令を引いて実行するだけ．
なので，switch 文をテーブルに展開して，直接命令のコードの場所に goto したりする最適化が非常に効く．というのがこの論文．
Optimizing direct threaded code by selective inlining (PDF)
# 追記 : あ，ACM ポータルの論文は，北大ドメインからじゃないとダウンロードできないのか… いつも普通に落としてたので，気がつかなかった．
毎朝 5 時から朝 hack しているらしい hayamizu 氏も，GCC が switch をジャンプに展開するのを期待していたようですが，僕が寝ている間にいろいろ一悶着あったみたいです （twitter のログをテキトーに加工して tac で逆順にしたもの）．GCC の最適化はそんなにがんばってないので有名ですが，馬鹿の子呼ばわりはひどい！
hayamizu switchのアセンブリコードをみて驚いているところ
yuki_neko_nyan あ、素人な私はswitchのasmすら知らない
hayamizu 驚いたというより, こうするしかないのかぁ, と思った.
yuki_neko_nyan いまの作業が済んだら見てみる。
natsutan 上手くジャンプのテーブル乗ってますか？ ＞ switch文
hayamizu switch分は cmpl, je, cmpl, je, cmpl, je, cmpl, je, cmpl, je, ....
yuki_neko_nyan テーブル表現がどうなるのかを知らないのじゃよぉ。いや、本当にテー ブルつくってlogic計算なのかな、とか ...
natsutan caseが、 0,1,2,3,4とか、等差数列になっていれば、テーブルで一発飛んでく れますよ。
hayamizu なるほど。0, 1, 100 でやってみたところです。enumでやってみよう。
yuki_neko_nyan gcc compiler hack入門編[Switch]ただいま開催中
yuki_neko_nyan でもcmpl,jmpだとifと全然かわらない気がする
hayamizu あれ、enumでも cmpl, jp, cmpl, jp, cmpl, jp, cmpl, jp になるぞ。もしか してgccってバカの子なんじゃ、、、
yuki_neko_nyan -O2とかは効く？
natsutan -mno-tablejump があるくらいなので、テーブルにしてくれそうなのですが、条件がたりないのかな。
natsutan @hayamizu 最適化おぷしょんが入ってないとか
yuki_neko_nyan つけないと最適化しないとするなら、私の常識が崩壊か。
hayamizu 0, 1, 2, 3 とそのまま書いても cmpl, je, cmpl, je （°∀°） cmpl, je, cmpl, je
hayamizu jpってなんだよjpって。
hayamizu なるほど、 最適化オプション
natsutan @alohakunの光臨を待つか・・
hayamizu 最適化オプションをつけると、 -O2からコードの形はかわるものの、 cmplが1 回減ったくらいでテーブルを作っている気配がない。
yuki_neko_nyan -O2してもcmpl jeだねぇ
yuki_neko_nyan なぞ。というか騙されてきたのでなければ、どういう条件でよばれるの だろうか
natsutan @hayamizu default:ラベルを抜いてみるとか
natsutan @hayamizu 今、長門プロンプト立ち上げた。長門に聞いてみる
hayamizu .@natsutanの長門キター / ちなみにdefaultは書いてないです
yuki_neko_nyan 長門キターー。彼女ならなんとかしてくれる。というかなんでもしてく れる
yuki_neko_nyan わたしはdefaultを書いた組でしたが同じだたーよ
yuki_neko_nyan 朝からgcc -Sまつり
natsutan できたよ
natsutan natsutan http://homepage3.nifty.com/~Natsutan/tmp/t.c
YUKI.N>gcc -c -O3 -S t.c でこれ。http://homepage3.nifty.com/~Natsutan/tmp/t.s
yuki_neko_nyan ひょっとしてcaseの数によって最適化がちがう？？
hayamizu うおお、見事に最適化されているっぽい。
natsutan 2のべきじょうじゃないと、テーブルがややこしくなる。
hayamizu それだ！ > caseの数
hayamizu おー最適化された。caseの数がすくないとそのままなのか。
yuki_neko_nyan とりあえずcaseを8個にしたら手元のでもTableになった
yuki_neko_nyan -Oつけなくてもtableになりそう
yuki_neko_nyan defaultありcaseが5つ最適化なしでtableになった
hayamizu 今Gaucheのvm.o を逆アセンブルしてcmplの数を数えたら、メインループの鬼のようなcase祭り(case 183個)もcmplが28個しかなかった。 ...
yuki_neko_nyan うひゃ、それすげーvm.c
hayamizu お騒がせしました。おかげさまで飯田橋6時半着なのに授業に遅刻できそうです(・∀・) 朝ハックはたのしい。 ...
yuki_neko_nyan caseが4まではtableにならない。jmp2回ってのがコストになるのかな
@hayamizu @natsutan 凄い勉強になった。感謝
yuki_neko_nyan 早起きするといいことあるねぇ〜
yuki_neko_nyan defaultラベルの存在は関係なさそう。純粋にcaseが5つ以上で最適化 。
natsutan 全ては長門のおかげです
hayamizu 授業にまにあったのも長門のおかげ。感謝感謝
hayamizu しかし、テーブルを作るならgaucheのvm.cはもっと効率よく最適化されそうな 気もする
yuki_neko_nyan caseのnestもあるし、fall throughもあるからvm.cは意外とすごいこと になってる。
yuki_neko_nyan gccの最適化に@hayamizuがその名を刻むのはこれからしばらくたって のことであった。
gcc の optimizer のどこで最適化されてるのかってのは，また後で (光臨しても結局役たたずの alohakun)
linux kernel とか device driver が，default 文を一番上に書く書き方をしてるのって，もしかしてここらへん関係なのかな ? 今は default あっても関係無いみたいだけど，昔の gcc では意味があったとか，古い gcc に対する対策とかの慣習なのかもしれないし．関数の引数を fast call するために 3 つ以内にするとかと同様に，switch の case 文の数まで考えてコードが書かれているのかもしれない．gcc が吐くコードを見ながら，kernel のコードの書き方を修正しているような GNU の変態どもなら有り得る．ハードウェア/コンパイラ/オペレーティングシステムは三位一体で，お互いがお互いにフィードバックをあたえる MAGI SYSTEM．全部知らないと理由がわからないことが多く，奥が深い世界である．
追記
masa_edw 丁度落ちてる時間に発言して更新されてないぽいな
masa_edw もう一度→gaucheのvm.cはgccの場合labels as valueを使ったgotoに展開されるということを見落としてない？
hayamizu @masa_edw dispatch_tableってやつ？
hayamizu @masa_edw なるほど. GCCじゃないとただのswitchになるのか.
hayamizu わざわざSWITCHとCASEのマクロがあるのはこのせいだったのか
本筋とは関係無いけど，これが論文や記事でも触れられていた，移植性と可搬性のトレードオフの例ですな．
他にも，例えば関数論理型言語マーキュリーのコンパイラが生成するCコードは，gcc の場合は labels as values 使った threaded code に展開されて，それ以外のCコンパイラの場合は普通のCコードに展開されるようなコードを，ifdef 使って吐いている．
natsutan さんにせっかく光臨を期待されたので，論文書きつつ必死で gcc のコード追ってたのに，先に書かれてしまいましたよ ＼(＾o＾)／
はじめてのにき 2007-11-21 _ switchの展開
素晴らしすぎて全俺が泣いた．natsutan さんは，これからは shinh さんの光臨を期待した方が良いと思います．わいはいらんこやなぁ．
あと，このネタはよくまとまってますし，表に書かれた方が良いのではないですかね．とか．いや，兼雑記見てる人のほとんどはにきもも見てるとは思いますけど．
|
C 言語/コンパイラ/BinaryHacks｜TB：1｜CM：8｜
 |
 
 
▲
|
|
|
コメント
|
サーセンｗｗｗ > 馬鹿の子
バカの子は自分だったようです。 |
|
hayamiz #6YFKLgoA｜2007/11/21(水) 07:04 [ 編集 ]
|
いえいえ www GCC は遅いですが，わりとできる子です．末永く見守ってあげてください．
ujihisa 無き後，twitter の柱に成り得る人材は hayamiz しかいない… っ ！ わしの case 文は 108 まであるぞ |
|
あろは #wNX6xxGw｜2007/11/21(水) 10:53 [ 編集 ]
|
>gcc が吐くコードを見ながら，kernel のコードの書き方を修正しているような GNU の変態どもなら有り得る
GNUの連中はカーネル書いてないだろう。
あ、Hurdがあるか。
|
|
きむら（K） #grGQ8zlQ｜2007/11/21(水) 11:29 [ 編集 ]
|
う〜ん，もはや GNU (Free Software Foundation 陣営) も Linus (Open Source 陣営) も同じような (とかうかつに言うと小1時間説教されそうだけど ｗ)
linux が gcc に合わせてコード書かれてるって話は，どこで見たんだっけなぁ… わりと衝撃的だった記憶があります． |
|
あろは #wNX6xxGw｜2007/11/21(水) 14:44 [ 編集 ]
|
rmsに半日説教喰らってこい(笑)
んで、Linuxの開発チームがgccの癖にあわせているってのはわしも読んだ覚えがある。
で結論は外から見ると些細に思える違いが当事者にとってはそうではない
場合もあるよ。と。
|
|
きむら(K) #grGQ8zlQ｜2007/11/21(水) 23:28 [ 編集 ]
|
みんなすごいなぁ
俺も生駒最速のHaskell作らないと。
生駒在住じゃないけど |
|
ujihisa #ja.2fmMI｜2007/11/22(木) 01:12 [ 編集 ]
|
一見似ている自由なソフトウェア陣営と，オープンなソフトウェア陣営ですが，その間には本質的な壁がありますよね．
僕はどちらかというと，オープン派ですが，RMS の思想には共感する部分も多いです． |
|
あろは #wNX6xxGw｜2007/11/22(木) 01:25 [ 編集 ]
|
きみは… なんだかとてもなつかしいような気がするけど，思いだそうとすると… 頭が… うぅ
http://www.atlus.co.jp/cs/game/pstation/per2_b/index.htm |
|
あろは #wNX6xxGw｜2007/11/22(木) 01:31 [ 編集 ]
|
|
|
コメントの投稿
|
|
|
トラックバック
|
『[朝ハック] switchの最適化』
昨日の朝の話をまとめようとしたら、すでにまとめられた上にお役立ち情報まで付加されていて俺歓喜。 東大さんで今，mini-python のインタプリタを作るという演習をやっているそうな． んで，今 twitter の柱の hayamizu 氏を筆頭に，空前の VM (仮想マシン) ブームが起き� |
|
日記を書く[・ _ゝ・]はやみずさん｜2007/11/21(水) 07:37 |
トラックバックURLはこちら
http://alohakun.blog7.fc2.com/tb.php/878-56f14e42
|
|
|
