$B%$%s%i%$%sE83+$H%-%c%C%7%e%R%C%HN((B?
Yasushi Shinjo
In article <dc95c98e.03102...@posting.google.com>
ki...@s05.itscom.net (Kiwi) writes:
> よく、「インライン展開を行うと、プログラム領域が膨らむが実行速度が上がる」
> と聞きますが、プログラム領域が膨らむことによって命令キャッシュのヒット率が
> 下がって実行速度も下がる、ということは無いのでしょうか?
「あるかないか？」と問われると、もちろん答えは「ある」です。
インライン展開した方が得かしない方が得か、なにか予測できるん
ですかね。全部のコードが一様に実行されるということなら、まあ
なんとかなりそうな気もしますけど。コードの実行回数の予測が難
しいですよね。
キャッシュのラインがぶつかるという話もあるので、あえてコード
を大きくした方が、全体的には得という話もあるんでしょうね。
実際にインライン展開をオンにしたりオフにしたりして走らせてみ
て実行時間を図ってみたことはあるんですが、CPU とかレジスタ数
とかによっても違うでしょうし。前に試したのは、SPARC のレジス
タ・ウインドウの効果を調べるというものです。答えはローカル変
数がウインドウに入るくらいの展開した方がいいということだった
と思いました。レジスタ・ウインドウがあると手続き呼出しが苦に
はならないはずなんだけれど、割込みがあったりスレッドのコンテ
キスト切替えがなどの外乱があると、フラッシュされるし。
> なお、インライン展開してもプログラム領域が小さく場合があることは知っています。
インライン展開どころか、if 文とか関数呼出しを「増」やした方
が速いということもあるから、困るんですよね。一生懸命、新しい
方式を考えて１０％速くしたつもりが、この手の変動に阻まれてう
まく効果が図れないということがあります。
元の記事は、fj.comp.lang.c++ に投稿されたもですが、C++言語と
は独立した話も多いので、 Followup-To: fj.comp.arch としてお
きます。
＼＼ 新城 靖 （しんじょう やすし） ＼＼
＼＼ 筑波大学 電子・情報 ＼＼
Shinji KONO
In article <YAS.03Oc...@kirk.is.tsukuba.ac.jp>, y...@is.tsukuba.ac.jp (Yasushi Shinjo) writes
> インライン展開した方が得かしない方が得か、なにか予測できるん
> ですかね。全部のコードが一様に実行されるということなら、まあ
> なんとかなりそうな気もしますけど。コードの実行回数の予測が難
> しいですよね。
たぶん、こういう話は、inline ってのを知ると「全部にinlineを
付ける」って言う学生のためにあるんだと思う。
本当に早くなったかどうか実測しろっていう良い機会にはなる
んだけど。
>前に試したのは、SPARC のレジス
> タ・ウインドウの効果を調べるというものです。答えはローカル変
> 数がウインドウに入るくらいの展開した方がいいということだった
> と思いました。レジスタ・ウインドウがあると手続き呼出しが苦に
> はならないはずなんだけれど、割込みがあったりスレッドのコンテ
> キスト切替えがなどの外乱があると、フラッシュされるし。
レジスタウィンドは「必ずシフトする」ので、いつかウィンドの
フラッシュルーチンを呼ばないといけない。レジスタウィンドは
スパースな構造を持っているのでフラッシュが遅い。
なのでサブルーチンコールを減らすinlineは効果があります。
inline で欲しいのは、本来はプログラム変換でのspecialization
であって、サブルーチンオーバヘッドではないはず。Specialiation
は通常のサブルーチンコールでも出来るので、inlineは、
なにか間違った選択だったと思います。
---
Shinji KONO @ Information Engineering, University of the Ryukyus,
河野真治 @ 琉球大学工学部情報工学科,
Masamichi Takatsu
私がちょっと前にx86で試した時は、inline 展開によるサブルーチンコールの
オーバーヘッド削減はほとんどありませんでした。
というか、最近のCPUは賢いので、引数がレジスタ渡しにさえなっていれば
サブルーチンコールのオーバーヘッドはほとんど無いって感じです。
かといって inline 展開に意味が無かったわけではなく、関数を跨ったピープ
ホール最適化が出来るという点では効果的でした。
似たような処理がある inline 関数の呼び出しが連続しているところで、
まとめて共通部分式の削除とか、そういうことができると、数倍とか、
そういうオーダーで目に見えて高速化できてしまいます。
記事 <3989148...@insigna.ie.u-ryukyu.ac.jp> で
Shinji KONOさんは書きました
> レジスタウィンドは「必ずシフトする」ので、いつかウィンドの
> フラッシュルーチンを呼ばないといけない。レジスタウィンドは
> スパースな構造を持っているのでフラッシュが遅い。
> なのでサブルーチンコールを減らすinlineは効果があります。
inline 展開での性能向上を期待するような小さな関数では、その中に
サブルーチンコールなどはあまり無いでしょう。とすると、呼び出しの
深さが1段増えるだけで、それも末端の部分ですから、1度フラッシュして
ウィンドウが確保できれば、あとはレジスタウィンドウが溢れることは
ほとんど無いんじゃないでしょうか。
PROJECT TEAM ＤｏＧＡ 高津正道 ta...@doga.jp
TBD0...@nifty.ne.jp
PROJECT TEAM DoGAのホームページ → http://doga.jp/
10月24日(金) 今日のマーフィーの法則 [ピーターの予言]
実際に必要かどうかを時間をかけて確認しているうちに、不必要になる。
Takuya KUDO
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> なのでサブルーチンコールを減らすinlineは効果があります。
いや、それがですね。実際、速度計測してみたんですけど
レジスタウィンドウに入りきる量ならば inline 展開より
関数コールの方が速かったです。
==
E-mail: ku...@astec.co.jp
Takuya KUDO ASTEC, Inc.
Shinji KONO
In article <bna4dl$1gob$1...@maha2.doga.co.jp>, Masamichi Takatsu <ta...@doga.jp> writes
> というか、最近のCPUは賢いので、引数がレジスタ渡しにさえなっていれば
> サブルーチンコールのオーバーヘッドはほとんど無いって感じです。
In article <seznfrxn...@astec.co.jp>,Takuya KUDO <ku...@astec.co.jp> writes
> いや、それがですね。実際、速度計測してみたんですけど
> レジスタウィンドウに入りきる量ならば inline 展開より
> 関数コールの方が速かったです。
この辺りの仮定が結構怪しいんだよな。その末端の関数だけじゃなくてそこまでの
過程で呼ばれた関数の履歴が関係するんだよね。
浮動小数点とかはレジスタとかウインドに乗らないし、使っているレジスタの
待避とかもあるし。引き数渡しに使ったレジスタは必ず待避が必要ですよね。
単純にinlineにしたから速くなるってことは、もちろんないんだけど。
関数呼び出しのオーバヘッドがないってわけでもないです。
Takuya KUDO
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> 浮動小数点とかはレジスタとかウインドに乗らないし、使っているレジスタの
> 待避とかもあるし。引き数渡しに使ったレジスタは必ず待避が必要ですよね。
>
> 単純にinlineにしたから速くなるってことは、もちろんないんだけど。
> 関数呼び出しのオーバヘッドがないってわけでもないです。
視点をあわせるために背景を説明します。
私が携わった Sparc プロセッサは随分昔の話で組み込み用途
浮動小数点演算なし（当時はソフトウェアエミュレーションを
使いました）のアーキテクチャです。
具体的に言うと富士通 Sparc Lite です。
Yasushi Shinjo
In article <3989148...@insigna.ie.u-ryukyu.ac.jp>
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> 河野真治 @ 琉球大学情報工学です。
> inline で欲しいのは、本来はプログラム変換でのspecialization
> であって、サブルーチンオーバヘッドではないはず。Specialiation
> は通常のサブルーチンコールでも出来るので、inlineは、
> なにか間違った選択だったと思います。
inline も、時代がたつと間違いに見えるようになるのでしょうね。
変数の register 宣言みたいに。ただ、register も inline もま
だまだ可愛いものです。プログラムの可読性は、そんなに下げない
し、普通は無視しても全然平気だから。#define よりは、inline
の方が見やすいし。
この間、ふと Linux のソースを見ていて辛かったのは、likely()
です。
include/linux/compiler.h:
------------------------------------------------------------
/* Somewhere in the middle of the GCC 2.96 development cycle, we implemented
a mechanism by which the user can annotate likely branch directions and
expect the blocks to be reordered appropriately. Define __builtin_expect
to nothing for earlier compilers. */
#if __GNUC__ == 2 && __GNUC_MINOR__ < 96
#define __builtin_expect(x, expected_value) (x)
#endif
#define likely(x) __builtin_expect(!!(x), 1)
#define unlikely(x) __builtin_expect(!!(x), 0)
------------------------------------------------------------
これを、if 文の中にかかれると、可読性の下がること下がること。
こんな感じ。
for( ... )
{
....
if (unlikely(dentry->d_bucket != head))
break;
....
if (likely(move_count == dentry->d_move_count)) {
if (!d_unhashed(dentry)) {
atomic_inc(&dentry->d_count);
found = dentry;
}
}
}
lilely() と unlikely() は、やめてくれって、というよりは、
「何間考えているんだ、このボケ」って感じ。こんなの人間がやる
ことじゃないです。
まあ、likely(), unlikely() も、まあ inline とか register と
同じで、まったく無視してもいいんだけど、無視するのは、辛いわ
けです。英語nativeなら平気なんですかね。
そもそも、コンパイル時の静的な分岐予測って、効くんですかね。
最近のプロセッサは、動的な分岐予測はしているわけですよね。
Yasushi Shinjo
In article <sek76vkx...@astec.co.jp>
Takuya KUDO <ku...@astec.co.jp> writes:
> 私が携わった Sparc プロセッサは随分昔の話で組み込み用途
> 浮動小数点演算なし（当時はソフトウェアエミュレーションを
> 使いました）のアーキテクチャです。
> 具体的に言うと富士通 Sparc Lite です。
私がインライン展開の効果を調べたのも、そのくらいの時代です。
SPARCstation 1 くらい。具体的には、inline ではなくて、
#define を使ったのですけれど。その当時の gcc は、inline がな
かったと思います。
同じ仕事をする関数を #defineで書いたのと普通の関数で書いたも
のを用意します。これを単純にループで回すのではなくて、関数を
ネストさせます。こんな感じ。
f1()
{
int x0,x1,x2,x3,x4,x5;
f2();
}
f2()
{
int x0,x1,x2,x3,x4,x5;
f3();
}
それで、インラインにすると速くなるのですが、ある程度増やして
いくと逆に遅くなります。５段か６段くらいだったかなあ。
これは、昔の話。SPARC で話。キャッシュとはあんまり関係ないか。
In article <bna4dl$1gob$1...@maha2.doga.co.jp>
Masamichi Takatsu <ta...@doga.jp> writes:
> 高津@ドーガです。
> 私がちょっと前にx86で試した時は、inline 展開によるサブルーチンコールの
> オーバーヘッド削減はほとんどありませんでした。
> というか、最近のCPUは賢いので、引数がレジスタ渡しにさえなっていれば
> サブルーチンコールのオーバーヘッドはほとんど無いって感じです。
最近、Pentium III での話ですが、Tempo という specializer で
インライン展開を調整すると効くことがあります。というか、イン
ラインにしないとspecialization の効果が全然出てこないことが
ありました。関数呼出しで、スタックに引数を積む所を削除するの
が効いているように思います。
> かといって inline 展開に意味が無かったわけではなく、関数を跨ったピープ
> ホール最適化が出来るという点では効果的でした。
> 似たような処理がある inline 関数の呼び出しが連続しているところで、
> まとめて共通部分式の削除とか、そういうことができると、数倍とか、
> そういうオーダーで目に見えて高速化できてしまいます。
手続きを越えて、共通式削除の最適化はやってもいいわけですよね。
> inline 展開での性能向上を期待するような小さな関数では、その中に
> サブルーチンコールなどはあまり無いでしょう。
別に小さい関数にしか inline を付けてはいけないという規則はな
いので、ぼこぼこ付ける人が出てくるわけです。
Shinji KONO
In article <YAS.03Oc...@kirk.is.tsukuba.ac.jp>, y...@is.tsukuba.ac.jp (Yasushi Shinjo) writes
> > inline 展開での性能向上を期待するような小さな関数では、その中に
> > サブルーチンコールなどはあまり無いでしょう。
> 別に小さい関数にしか inline を付けてはいけないという規則はな
> いので、ぼこぼこ付ける人が出てくるわけです。
たぶん、putchar みたいに、
if (buffer_full()) call_flush()
else buffer_op()
みたいなのが多いんじゃないかな。データ構造に対するアクセサ
もinlineにしたくなるかも知れない。オブジェクト指向的な観点
からだとinlineではだめで、ちゃんとmethod callしないといけ
ないわけですけどね。
関数呼び出しのオーバヘッドは末端にはないんだけど、中間には
あります。段数を減らすと言う意味で有効なんだよね。
最近発見したのは、PowerPCなんかのlink register (戻り番地を覚
えておくための専用のレジスタ(そういや、なんで専用なんだろう?)
が結構有効だってことです。スタックと言うメモリへのアクセスが
減るので高速ですね。ただ専用レジスタなので、それをいじるため
には専用の命令が必要だってのがダサイ。
MAEDA Atusi
> In article <3989148...@insigna.ie.u-ryukyu.ac.jp>
> ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> > 河野真治 @ 琉球大学情報工学です。
> > inline で欲しいのは、本来はプログラム変換でのspecialization
> > であって、サブルーチンオーバヘッドではないはず。Specialiation
> > は通常のサブルーチンコールでも出来るので、inlineは、
> > なにか間違った選択だったと思います。
inlineしないspecializationって，specializeした色んなバージョンのサブルー
チンを作るってことでしょうか．だったらinliningしても良いような．
昔，MIPSのコンパイラはオブジェクトを中間コード(uコード)で出力しておい
て，リンク時に手続き間最適化やをしていましたが，あれは廃れたんですか
ね．
> /* Somewhere in the middle of the GCC 2.96 development cycle, we implemented
> a mechanism by which the user can annotate likely branch directions and
> expect the blocks to be reordered appropriately. Define __builtin_expect
> to nothing for earlier compilers. */
分岐予測というより，どちらかのパスを優先して分岐以外の命令をスケジュー
ルするんでしょうかね．trace schedulingみたいに．
> lilely() と unlikely() は、やめてくれって、というよりは、
> 「何間考えているんだ、このボケ」って感じ。こんなの人間がやる
> ことじゃないです。
if_likelyとif_unlikelyだと少しはましですかね(大差ないか)．
商用のコンパイラだと，プロファイラのフィードバックが使えたりしますから，
人間が手でannotateするより楽ですね．
> そもそも、コンパイル時の静的な分岐予測って、効くんですかね。
ループに関してはある程度効くんじゃないですか．
> 最近のプロセッサは、動的な分岐予測はしているわけですよね。
今や，動的分岐予測なしでは話にならないです．分岐の結果が分かるまで待っ
ていたらフェッチが全然間に合いません．
最近のプロセッサの命令フェッチステージはたいてい，
while (1) {
fetch_block(pc); // 複数の命令をフェッチ
pc = predict(pc); // 次のフェッチ番地を予測
}
みたいな作りになっていると思います．(分岐命令が含まれていないブロック
なら，予測器は次のブロックの番地を返す．)
前田敦司
MAEDA Atusi
> 最近発見したのは、PowerPCなんかのlink register (戻り番地を覚
> えておくための専用のレジスタ(そういや、なんで専用なんだろう?)
> が結構有効だってことです。スタックと言うメモリへのアクセスが
> 減るので高速ですね。ただ専用レジスタなので、それをいじるため
> には専用の命令が必要だってのがダサイ。
他のRISC(SPARC, Alpha, PA-RISC, MIPS)は汎用レジスタをcallのlinkageに使
いますね．Pentium4やAthlonは，オンチップにreturn address stackをそれぞ
れ16, 12エントリー持っていて，RET命令の分岐先を予測するのに使います．
link registerが専用レジスタだと，整数演算とcall/returnの間に依存関係が
なくなります．また，PowerPCは条件call(すべての分岐命令はlink bit が1だ
とPC を保存), 条件return(branch conditional link register命令)があると
いう意味では，普通のアーキテクチャより汎用性があります．
前田敦司
Shinji KONO
In article <m3brs47...@maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <ma...@cc.tsukuba.ac.jp> writes
> inlineしないspecializationって，specializeした色んなバージョンのサブルー
> チンを作るってことでしょうか．だったらinliningしても良いような．
実はおんなじ引数で呼ぶってのがたくさんあるからinlineにしたい
わけなので、それらが共用される可能性があるからspecialization
の方が優れていると思います。(subroutine のoverhead が小さければ...)
> 昔，MIPSのコンパイラはオブジェクトを中間コード(uコード)で出力しておい
> て，リンク時に手続き間最適化やをしていましたが，あれは廃れたんですか
> ね．
オブジェクト指向に起因するindirect callや、shared library 用
のdynamick linkがしこたまある現状ではあんまり意味無いんでし
ょうね。これも、時代の流れか。
> > そもそも、コンパイル時の静的な分岐予測って、効くんですかね。
> ループに関してはある程度効くんじゃないですか．
動的分岐予測がある状況ではループで静的予測ほとんど意味無いと
思う。ループでない部分(櫛形の一回の分岐)みたいなものの方が静
的分岐予測は有効だと思います。
In article <m37k2s7...@maedapc.cc.tsukuba.ac.jp>,MAEDA Atusi <ma...@cc.tsukuba.ac.jp> writes
> 他のRISC(SPARC, Alpha, PA-RISC, MIPS)は汎用レジスタをcallのlinkageに使
> いますね．Pentium4やAthlonは，オンチップにreturn address stackをそれぞ
> れ16, 12エントリー持っていて，RET命令の分岐先を予測するのに使います．
スタックトップが大域メモリにあるとそこを書き換える可能性を否
定できないので限界はあると思います。結局、スタックマシンは、
階層型メモリに対応できてないってのが僕の考えなんだけど。
一方で、return とか分岐判断用の専用のレジスタがあった方がい
いかというと、それも少し疑問に思ってます。VAX みたいに、PC
が汎用レジスタって方がやっぱりいいんじゃないかな。昔は、予測
や依存関係の解消にハードウェアを割けなかったから、だめだった
んだけど...
> link registerが専用レジスタだと，整数演算とcall/returnの間に依存関係が
> なくなります．また，PowerPCは条件call(すべての分岐命令はlink bit が1だ
> とPC を保存), 条件return(branch conditional link register命令)があると
> いう意味では，普通のアーキテクチャより汎用性があります．
整数演算とcall/return/branchには、結局、依存関係はあります。
if (i+3===hoge) do_process();
みたいな感じですよね。むしろ積極的に依存関係を使って動作を予
測して良く方が良い。逆に、ハードウェア量に制限があるなら、命
令の種類を増やすのはまずい選択だと思う。
r10 = 0x234234234+r11
pc = r10
みたいなのと、switch (i) みたいなのって、あんまり変わりません
よね。
条件callや条件returnが使えないのは、コンパイラを書いてみると
わかるんだけど、
call する前にしなければならないこと
return する時にしなければならないこと
が山程あるからです。
引数の準備
使ったレジスタの後始末 (値を元に戻したり)
フレームポインタがあれば、その操作
C++ などあれば、stack 上のオブジェクトの破壊
もちろん、そんなことしないですむ短いサブルーチンには有効なん
ですけど。どうも短いサブルーチンってのはあんまりないみたい。
プログラマの性がそうさせるのか?
さらにPowerPCの複数あるフラグとかで分岐予測しやすいようにし
てやると、早めの分岐という意味では逆に遅くなります。また、C
のような言語だと計算と分岐の順序をいじるのは危険すぎる。なの
で、結局、フラグは一つしか使わないってことになりがち。
たぶん、PowerPC には「速くしたい特定のアプリケーション」
ってのがあったので、ああいう命令になったんだと思います。
しかし裏目に出てるような気がするな。
MAEDA Atusi
> 河野真治 @ 琉球大学情報工学です。
>
> In article <m3brs47...@maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <ma...@cc.tsukuba.ac.jp> writes
> > inlineしないspecializationって，specializeした色んなバージョンのサブルー
> > チンを作るってことでしょうか．だったらinliningしても良いような．
>
> 実はおんなじ引数で呼ぶってのがたくさんあるからinlineにしたい
> わけなので、それらが共用される可能性があるからspecialization
> の方が優れていると思います。(subroutine のoverhead が小さければ...)
「おんなじ引数で呼ぶってのがたくさんある」というのは良く分からないなあ．
それも静的にですよね．そんなことがそれほどあるのかしらん．
「polymorphicな関数を型についてspecializeする」とかなら価値はあると思
うけど．
> In article <m37k2s7...@maedapc.cc.tsukuba.ac.jp>,MAEDA Atusi <ma...@cc.tsukuba.ac.jp> writes
> > 他のRISC(SPARC, Alpha, PA-RISC, MIPS)は汎用レジスタをcallのlinkageに使
> > いますね．Pentium4やAthlonは，オンチップにreturn address stackをそれぞ
> > れ16, 12エントリー持っていて，RET命令の分岐先を予測するのに使います．
>
> スタックトップが大域メモリにあるとそこを書き換える可能性を否
> 定できないので限界はあると思います。結局、スタックマシンは、
> 階層型メモリに対応できてないってのが僕の考えなんだけど。
分岐予測は，外れても遅くなるだけなので，「可能性が否定できない」程度の
頻度しか外れないなら，やる利益の方が大きいのです．(メモリの参照を減ら
すための仕組みではないです．)
> 一方で、return とか分岐判断用の専用のレジスタがあった方がい
> いかというと、それも少し疑問に思ってます。VAX みたいに、PC
> が汎用レジスタって方がやっぱりいいんじゃないかな。昔は、予測
> や依存関係の解消にハードウェアを割けなかったから、だめだった
> んだけど...
データパスを考えると分かりますが，PCは特別扱いした方がほとんどの場合有
利だと思います．
> > link registerが専用レジスタだと，整数演算とcall/returnの間に依存関係が
> > なくなります．また，PowerPCは条件call(すべての分岐命令はlink bit が1だ
> > とPC を保存), 条件return(branch conditional link register命令)があると
> > いう意味では，普通のアーキテクチャより汎用性があります．
>
> 整数演算とcall/return/branchには、結局、依存関係はあります。
> if (i+3===hoge) do_process();
> みたいな感じですよね。むしろ積極的に依存関係を使って動作を予
> 測して良く方が良い。逆に、ハードウェア量に制限があるなら、命
> 令の種類を増やすのはまずい選択だと思う。
そういう間接的な依存関係はもちろんありますが，例えば100^2よりも
50^2 + 50^2が小さくなるように，命令の種類を分ける意味はあります．
例えば最初のPowerPC601は機能ユニットごとに別々のリザベーションステーショ
ンを持ち，命令の種類でまずそれぞれのリザベーションステーションにディス
パッチしています．分岐ユニットのリザベーションステーションには整数演算
が入ってこず，link registerと条件コードに関してのみの依存関係を調べま
す．
条件コードを書き換える整数演算の後に，それに依存した条件分岐がある場合，
フラグビットにinterlockがかかった状態で分岐がディスパッチされます．フ
ラグの値が十分早く確定しなかった場合は，(601では静的)分岐予測を用いて
処理を進めます．
また，逆に，分岐がlink registerやcount registerを書き換え，先行する整
数演算命令がそれらに依存している場合は，renamingで依存を取り除きます．
> r10 = 0x234234234+r11
> pc = r10
> みたいなのと、switch (i) みたいなのって、あんまり変わりません
> よね。
そういう計算型gotoみたいなのばっかり実際のアプリで使われるならそうでしょ
うね．
> 条件callや条件returnが使えないのは、コンパイラを書いてみると
> わかるんだけど、
> call する前にしなければならないこと
> return する時にしなければならないこと
> が山程あるからです。
さあ，specializeしたsubroutineなんかは，使う絶好のチャンスに見えますが…
いずれにせよ，PowerやARMがこれらの命令セットを決める際には統計的な根拠
に基づいて決めたはずです．定量的な値なしでは何とも私には言えません．
> さらにPowerPCの複数あるフラグとかで分岐予測しやすいようにし
> てやると、早めの分岐という意味では逆に遅くなります。また、C
> のような言語だと計算と分岐の順序をいじるのは危険すぎる。なの
> で、結局、フラグは一つしか使わないってことになりがち。
これは，分岐予測じゃなくて資源競合による偽の依存を避けるためでは? 効
けん過ぎると言うのは何のことか良く分かりませんが，最新のプロセッサはど
れも分岐を越えて投機的な計算を行なっています．
> たぶん、PowerPC には「速くしたい特定のアプリケーション」
> ってのがあったので、ああいう命令になったんだと思います。
> しかし裏目に出てるような気がするな。
兄貴分のPowerは常にIPCではトップクラスの値を誇っており(懐かしい言葉で
言えばbrainiac approach)，性能的にもトップグループにいます．その後を追
うPowerPCも，特に今度の970はクロックも上げてきてなかなか頑張っていると
思いますが．
# いわゆる「アセンブリ言語プログラマから見たきれいさ」は，あまり性能に
# 結び付かないように思います．
前田敦司
Takuya KUDO
y...@is.tsukuba.ac.jp (Yasushi Shinjo) さん writes:
> この間、ふと Linux のソースを見ていて辛かったのは、likely()
...
> lilely() と unlikely() は、やめてくれって、というよりは、
> 「何間考えているんだ、このボケ」って感じ。こんなの人間がやる
> ことじゃないです。
同感。
> まあ、likely(), unlikely() も、まあ inline とか register と
> 同じで、まったく無視してもいいんだけど、無視するのは、辛いわ
> けです。英語nativeなら平気なんですかね。
ソースコードの可読性を下げますよね。
まぁ Linux は所詮混沌のなんでもありのしろものなのでまともに相手に
するのはどうかと・・・。
ついでにそもそも Unix 自体も大型汎用機系の人達に言わせると無茶苦茶
だそうです。
Shinji KONO
予測と実際の計算の話がごっちゃになるのでわかりずらいですね。
In article <m3oew45...@maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <ma...@cc.tsukuba.ac.jp> writes
> 分岐予測は，外れても遅くなるだけなので，「可能性が否定できない」程度の
> 頻度しか外れないなら，やる利益の方が大きいのです．(メモリの参照を減ら
> すための仕組みではないです．)
分岐予測に関してはそうですね。でも、サブルーチン・コールの爲
に外部メモリに触るってのは限界があるだろうってことです。
PowerPC の link register は、優れていると思う。けど、SPARCの
方式は外れ。いつかは外部メモリに触れるとしても、それをコンパ
イラなりハードウェアなりが「隠れてこそこそ」やりたい。
> データパスを考えると分かりますが，PCは特別扱いした方がほとんどの場合有
> 利だと思います．
予測に関しては、命令部で予測するかオペランドで予測するかの違
いだけだと思うんだけど...
なんていうのかな、
a = b?3:4
cmp b
jz _2
move r10,3
j _1
_2: move r10,4
_1: st a,r10
より分岐を計算に書き換える
a = b*3+(!b)*4
ld r11,b
move r10,3
mul r10,r11
not r11
move r12,4
mul r11,r12
add r11,r10
st r11,a
の方が速いってのは、分岐に演算が関わってないからであって、本
来は前者の方が速いべきなんじゃないかなと思います。述語修飾み
たいな手法は、前者を、
a = b?3:4
ld r11,b
move r10,3 if r11
move r10,4 if r11
_1: st r10,a
に書き換えるわけだけど、分岐予測があるなら、おんなじことで
あって欲しい。Predication は、実行時にやるべきことをコンパイル時
に押しつけている気がする。
データパス的には「PCにかけ算する」なんてのは確かに出て来ない
ので、無駄なのかも知れない。でも、Shard Library とかの
PIC (Position Independent Code) とか、オブジェクト指向的な
間接コールが多量に出て来る状況では、結構、汎用的に使われてます。
> 兄貴分のPowerは常にIPCではトップクラスの値を誇っており(懐かしい言葉で
> 言えばbrainiac approach)，性能的にもトップグループにいます．その後を追
> うPowerPCも，特に今度の970はクロックも上げてきてなかなか頑張っていると
> 思いますが．
PowerPC は良くできてます。ただ、
cmp flag1
cmp flag2
cmp flag3
jcond flag1,_1
jcond flag2,_2
jcond flag3,_3
みたいなのって、いかにもIPCのためであって、実性能とは関係ない
って感じがしませんか?
cmp
jcond _1
cmp
jcond _2
cmp
jcond _3
でできるはずだってわけです。
> # いわゆる「アセンブリ言語プログラマから見たきれいさ」は，あまり性能に
> # 結び付かないように思います．
コンパイラは静的予測を行ない、CPUは動的予測を行なう。その間
の橋渡しがアセンブラ言語の予測に対する機能ですね。
予測と動作記述を分ける方が良いってことなのかな。
Yasushi Shinjo
In article <m3oew45...@maedapc.cc.tsukuba.ac.jp>
MAEDA Atusi <ma...@cc.tsukuba.ac.jp> writes:
> > 実はおんなじ引数で呼ぶってのがたくさんあるからinlineにしたい
> > わけなので、それらが共用される可能性があるからspecialization
> > の方が優れていると思います。(subroutine のoverhead が小さければ...)
> 「おんなじ引数で呼ぶってのがたくさんある」というのは良く分からないなあ．
> それも静的にですよね．そんなことがそれほどあるのかしらん．
私の感じだと、(静的に) specialization かけられるプログラムと
いうのは、ゴロゴロしていると思っています。たとえば、こんな感
じのプログラムは、よく見ませんか。
------------------------------------------------------------
f()
{
for( x=0; x<10; x++ )
{
g( x,y,10 );
}
}
g( x,y,z )
{
if( z >= 10 )
{
h( x, y );
}
else
{
i( x, y );
}
}
------------------------------------------------------------
ループの中で変らない変数を引数で渡したりします。10 などの定
数があからさまに出てくることもあるだろうし、x とか y と書い
てあっても、実は定数というのもあるでしょう。10 で
specialization かけるとこうなります。
------------------------------------------------------------
f()
{
for(...)
{
g_10( x,y );
}
}
g_10( x,y )
{
h( x, y );
}
------------------------------------------------------------
こうすると、インライン展開は別にやらなくても、g_10() の中で
if文外したり、計算を進めたりできるわけです。まあ、関数呼出し
のインライン展開も、分類上は、specialization の一種ではある
んですけれど。
さらに、x でループの展開もできます。
> 「polymorphicな関数を型についてspecializeする」とかなら価値はあると思
> うけど．
Ｃ＋＋のテンプレートの展開以外にも、上のようなコードは、けっ
こうあります。あと、実行時にしか型がわからなくても、実行時
specialization というのもあります。実行時にコード生成します。
型ごとと言わず、オブジェクトごとにコード生成してもいい場合も
あるでしょう。
たぶん、今までは人間が specialization をしていたんだと思いま
す。これからは、コンパイラに任せる部分を増やしていこうという
方向でいいんだと思います。
MAEDA Atusi
> > 「おんなじ引数で呼ぶってのがたくさんある」というのは良く分からないなあ．
> > それも静的にですよね．そんなことがそれほどあるのかしらん．
> こうすると、インライン展開は別にやらなくても、g_10() の中で
> if文外したり、計算を進めたりできるわけです。まあ、関数呼出し
> のインライン展開も、分類上は、specialization の一種ではある
> んですけれど。
これは分かるんですけれど，g_10(), g_20(), g_4()とかがたくさんできるん
じゃないか(だったらインライン展開の方が良いんじゃないか)ということです．
あちこちからg(10, x, y)のように特定の引数だけで呼ばれるということが，
そんなにあるものかどうか．あとは，specialize結果をちゃんと(同じインス
タンスを呼ぶように)共有するのがそんなに簡単なのかどうか(色んなファイル
から呼ばれてたり，とか)．
前田敦司
Shinji KONO
In article <m3znfl5...@maedapc.cc.tsukuba.ac.jp>, MAEDA Atusi <ma...@cc.tsukuba.ac.jp> writes
> これは分かるんですけれど，g_10(), g_20(), g_4()とかがたくさんできるん
> じゃないか(だったらインライン展開の方が良いんじゃないか)ということです．
まぁ、呼び出し側で展開するか呼び出され側で展開するかの差なわけですけどね。
> あちこちからg(10, x, y)のように特定の引数だけで呼ばれるということが，
> そんなにあるものかどうか．
自明な例だと、
inline fd(struct handle hd) { return hd.hoge->hage->fugo->fd; }
みたいな奴。で、これが、
fd(hd0) = fd(hd0) + 3;
みたいな形で呼ばれるわけだな。(おっと左側には置けないが...)
この場合は、inline が有効なわけですが... だめな例をを考える
のは結構面白いかも。
specialize した関数を手で複数書くのは人間には危なすぎます。
変更したときに、他方を変更することを忘れることが多いので。
# define で工夫した例をみたこともあるけど... どれだかは
忘れました。
Lisp では良く使われる技術なんですけどね。
(defmacro hoge (a b c) ....)
して、
(defun hoge1 (b c) (hoge 1 b c))
(defun hoge2 (b c) (hoge 2 b c))
みたいな...
> あとは，specialize結果をちゃんと(同じインス
> タンスを呼ぶように)共有するのがそんなに簡単なのかどうか(色んなファイル
> から呼ばれてたり，とか)．
そのあたりは色んな技術があるわけなんだけど... 何故、inline
だけが使われているのかと言うと、呼び出し側だけ見れば良いから
なんだろうな。でも、最適化という観点から見れば、全体を見なけ
ればだめなのは当然なんですけどね。
inline でcodeが大きくなる欠点が実は無視できないのと、末端の
call の手間は実は小さいのとで、inline は、あまり有効でない
ってことなんでしょうね。
その一方で、nested function call とか indirect function call
ってのは、パフォーマンスに対する影響は結構あるんじゃないかっ
てのが僕の意見です。stack top を register にキャッシュするの
は有効な技術なので、単純に、必ずstackに触るcall/return する
のではだめなんじゃなかろうかってわけですね。
MAEDA Atusi
> 分岐予測に関してはそうですね。でも、サブルーチン・コールの爲
> に外部メモリに触るってのは限界があるだろうってことです。
>
> PowerPC の link register は、優れていると思う。けど、SPARCの
> 方式は外れ。いつかは外部メモリに触れるとしても、それをコンパ
> イラなりハードウェアなりが「隠れてこそこそ」やりたい。
えっと，leaf procedure以外では必ずlink registerをスタックにセーブする
んじゃないでしょうか? それはPowerPCもMIPSもAlphaも同じでは．
CISCだと，leafへのcallでもメモリへの参照が起きる．
SPARCだと，leaf以外でもメモリに書かないこともある．
戻りPCに関するメモリへの参照の回数だけで言ったら，
CISC > PowerPC = MIPS = Alpha = ... >= SPARC
では?
(もっとも，引数や局所変数も考えると 他のRISC >= SPARCとは必ずしも言え
ないけど．)
> > データパスを考えると分かりますが，PCは特別扱いした方がほとんどの場合有
> > 利だと思います．
>
> 予測に関しては、命令部で予測するかオペランドで予測するかの違
> いだけだと思うんだけど...
>
> なんていうのかな、
> a = b?3:4
> cmp b
> jz _2
> move r10,3
> j _1
> _2: move r10,4
> _1: st a,r10
> より分岐を計算に書き換える
> a = b*3+(!b)*4
...
> の方が速いってのは、分岐に演算が関わってないからであって、本
> 来は前者の方が速いべきなんじゃないかなと思います。...
偏りがあるなら分岐予測が効いて，分岐でやった方が速くなるんじゃないです
か．
同じくらいの確率だとすると，分岐だけで頑張るには，分岐の両方向について
投機的に命令の実行を始めないといけないと思うのですが，そのアプローチだ
と無駄な(投機に失敗する)命令が指数関数的に増えてしまって，プロセッサ資
源の無駄使いになります．
> データパス的には「PCにかけ算する」なんてのは確かに出て来ない
> ので、無駄なのかも知れない。でも、Shard Library とかの
> PIC (Position Independent Code) とか、オブジェクト指向的な
> 間接コールが多量に出て来る状況では、結構、汎用的に使われてます。
問題は頻度ですね．そういう使い方が(SPEC INTのベンチマークで高い頻度に
なるくらい)良く出てくるなら，プロセッサもそれに対応すると思います．
> PowerPC は良くできてます。ただ、
> cmp flag1
> cmp flag2
> cmp flag3
> jcond flag1,_1
> jcond flag2,_2
> jcond flag3,_3
> みたいなのって、いかにもIPCのためであって、実性能とは関係ない
> って感じがしませんか?
> cmp
> jcond _1
> cmp
> jcond _2
> cmp
> jcond _3
> でできるはずだってわけです。
むしろ，下のコードで3つのcmp ... jcond ペアの間の依存性を無くそうとい
うのが狙いでしょう．flagが1つだと逆依存(や出力依存)が出てきてしまいま
す．renaming すれば良いという話もありますが，ここはscoreboarding風な集
中制御にしてあります．この辺はdesign decisionでしょう．
> > # いわゆる「アセンブリ言語プログラマから見たきれいさ」は，あまり性能に
> > # 結び付かないように思います．
>
> コンパイラは静的予測を行ない、CPUは動的予測を行なう。その間
> の橋渡しがアセンブラ言語の予測に対する機能ですね。
>
> 予測と動作記述を分ける方が良いってことなのかな。
いや，そのー「link registerを汎用レジスタにする」とか「PCを汎用レジス
タにする」とか，「直交したアドレッシングモード」とかは，別に速くならな
いことが多いということです．あとは「OOの効率良い実装のための命令」とか
も．
前田敦司
Takuya KUDO
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> inline でcodeが大きくなる欠点が実は無視できないのと、末端の
> call の手間は実は小さいのとで、inline は、あまり有効でない
> ってことなんでしょうね。
組み込み向けだとコードサイズが無視できなくてキャッシュに入る
きるかどうかでパフォーマンスに大きな影響がでます。
Yasushi Shinjo
In article <m3znfl5...@maedapc.cc.tsukuba.ac.jp>
MAEDA Atusi <ma...@cc.tsukuba.ac.jp> writes:
> これは分かるんですけれど，g_10(), g_20(), g_4()とかがたくさんできるん
> じゃないか(だったらインライン展開の方が良いんじゃないか)ということです．
> あちこちからg(10, x, y)のように特定の引数だけで呼ばれるということが，
> そんなにあるものかどうか．あとは，specialize結果をちゃんと(同じインス
> タンスを呼ぶように)共有するのがそんなに簡単なのかどうか(色んなファイル
> から呼ばれてたり，とか)．
specialization の結果のコードの共有をするような、specializer
は、見たことがないですね。研究レベルでは、誰かがやっていそう
な気もするんだけれど。specialization は、高速化が目的なので、
「やりすぎて遅くなったらやらない」というスタンスです。そすい
う意味では、必ずうまく行くことになっているんだけど、うまくいっ
たかどうか誰が確かめるかという問題が残る、ということですかね。
逆に、コードの共有が本当に得なら、specialization の逆をすれ
ばいいんですよね。仮に generalization と呼ぶことにします。
（←正式の用語があれば、教えてください。） 簡単にできる
generalization は、inline の逆に outline というか、わざと関
数呼出しにするものです。
前に、Tempo の開発元の一人に、inline の逆をしてみたらとは言っ
てはみたんだけど、そんなことを specializer に求められても、、、
みたいな反応でした。それはそうです。
In article <3989159...@insigna.ie.u-ryukyu.ac.jp>
ko...@ie.u-ryukyu.ac.jp (Shinji KONO) writes:
> 河野真治 @ 琉球大学情報工学です。
> 自明な例だと、
> inline fd(struct handle hd) { return hd.hoge->hage->fugo->fd; }
> みたいな奴。で、これが、
> fd(hd0) = fd(hd0) + 3;
> みたいな形で呼ばれるわけだな。(おっと左側には置けないが...)
Ｃ＋＋の参照型を使えば、置けるんでしたっけ。Ｃ＋＋の参照型は、
ソースが読めなくなるから一般的には使いたくはないんだけど。
ＯＳの特権モードのような所なら許してもいいかな。
> そのあたりは色んな技術があるわけなんだけど... 何故、inline
> だけが使われているのかと言うと、呼び出し側だけ見れば良いから
> なんだろうな。でも、最適化という観点から見れば、全体を見なけ
> ればだめなのは当然なんですけどね。
Ｃ言語だと inline は、マクロよりははるかに見やすいので、そう
いう意味では許すかなあ。register と同じように、そのうちコン
パイラが無視するんじゃないかなあ。
inline で意味的に違うのは、オブジェクトにシンボルが残らない
ことです。昔の Linux (2.2) なんか、この機能に頼っていて、
inline を外す、つまり、コンパイル・オプション -O2 を取ると、
リンク時にエラーになります。デバッグしたいだけなのに。今でも
そうなんでかかね。
In article <septgh9...@astec.co.jp>
Takuya KUDO <ku...@astec.co.jp> writes:
> 組み込み向けだとコードサイズが無視できなくてキャッシュに入る
> きるかどうかでパフォーマンスに大きな影響がでます。
メモリ使用量を減らすなら、インタプリタにするといいんですよね。
昔は２段階のインタプリタもあった思いました。でも、全部インタ
プリタというわけにもいかなくて、展開というかコンパイルという
か specialize すべき所もあるのでしょうけれど、誰がどうやって
判断するんでしょうね。