アカウント名:
パスワード:
ストールが問題になるにはデータ依存が存在していることが必要で、データ依存の有無はアルゴリズムによって決まります。インクリメントが後置か前置かとは別の話でしょう。前置インクリメントを使ったためにデータ依存が新たに生じることはありません。（生じるとすれば、アルゴリズムが変わっています。）
影響があるとすればコンパイラの最適化でしょうが、前置インクリメントの方が一般に処理が単純なので、これを使ったために、データ依存解析に失敗するケースというのはちょっと想像がつきませんね。
逆に、後置インクリメントを使うことによって生じるコピーコンストラクタの削除にコンパイラが失敗するケースなら十分あり得ます。一般論として、コピーコンストラクタを削除するには手続き間解析（少なくともインライン化）が必要ですが、手続き間解析はコストが大きいため、現行のコンパイラは、これを完全には行えていないからです。（そもそも、コピーコンストラクタのソースコードが提供されていない場合、リンク時最適化を利用しない限り、最適化はできません。）
うん。リンク先も、単純な場合はコンパイラが勝手に上手いことやってくれる、までは良いんだけど、そこから迷走しだしてるね。
前置/後置の差で不自然なストールを演出しようとしても、わざわざそこでソースを分割して最適化出来ないような工夫さえしてなければ、本質的にストールを考慮て最適化する必要があるかどうか、コンパイラには見抜かれる。
コンパイラの最適化の限界を知っておくのはなかなかおもしろい。ソースコードを愚直に実行するとものすごく無駄な手順を踏むことになるけど、構造化されてて書きやすく、従ってバグを入れにくいような書き方を気楽に使える。
例えば、2×2行列の掛け算みたいな、手で書くと最小限のコードに出来そうだけどどこか書き間違えてしまいそうな処理も、汎用的なn×n行列の掛け算インライン関数を呼んでおけば、何だかループがアンロールされて、必死こいて必要最小限だけ手で書いたやつと似たような結果になる。出来合いの関数が無い処理でも、こういうのは、添え字を丁寧に書き並べるより、ループを使ったほうが書き間違いをしづらいし。
このあたり理解してる人間がわざとそうやって書いててもコードレビューという名の理解してない人間への説明会で遅いから書き換えろと言われる率の高さがなぁ変わらないって説明しても聞きゃしねぇ…
もしも差があったらコンパイラっていうかプリプロセッサに問題があるって言うのが現代でしょう。コード化された時に大きな速度差が出るようなコードって、プロセッサ処理よりI/O周りの処理がボトルネックになる方が大きいと思う。実際にコード化されたイメージをしながらプログラムソースを書く時代はとっくに終わってる。
この問題はアルゴリズムやコンパイラレベルの話ではなく、CPU内部のパイプラインの話なのだが…。
ストールを気にするのなんてループの中くらいだし、それなら今時のCPUだと上手く隠してくれそうな気がするする。
ゲームエンジンの話なので対象が「今時のCPU」ではないPS3等のインオーダーのCPUも入るわけですよ。で、インオーダーのCPUのストールコストは非常に高い。そこから後置インクリメントが云々って話なわけです。
インクリメント前の変数を持つ時点でreturnする前の処理は多いと思うのだが？
同感。元ねたがコンパイラの話とCPUの話をごっちゃにしているのが間違い。常識が覆ることがあったのはCPUの進歩で動的に平行処理されるようになったから。
同じ、同じ(笑)。なんで、コンパイラの最適化ルーチンの設計なんてハッカーの極みみたいな仕事をしてる人が、「CPUのパイプラインまで考えたら、前置より後置の方が良いぞこれ」とか言うアイデアに気付かないと思ってるのよ。その方が速くなりえて、置き換えても良い場面なら、どっちで書かれてても勝手に置き換える最適化ルーチンを設計するって。
置き換えても差し支えがないかどうかはアルゴリズム次第。本当は置き換えられるけど、コンパイラが見落とすほど巧妙に一見そうは見えないコードなんて、難解Cコードコンテストぐらいでないと出て来ないんじゃない？知らんけど。
開始値は簡単に修正が効くけど、終了値が一個違うアルゴリズムに自動で置換するのは大変だと思うなぁ…if(～)a[++i]=b;みたいにして条件に合致するものを配列に詰めて終了値を使う処理とか、詰めるときのインデックス値を使う処理があったら、そこら辺まで最適化で変更するの？別の処理に渡す変数の中身を最適化で変えてしまうのは現在最適化で許される改変の範疇を超えてるでしょう。
なるほど、それは確かに何か違いが出るかも知れないですね。
大ざっぱな実験ですが、試しにやってみました。下記のように、同じ結果になるfind1とfind2を、10万回試す指向を交互にやってみたところ、clock()で計ったミリ秒は、
find1: 7550 7534 7551 7551 7550 7551 (平均: 約7548ミリ秒)find2: 7582 7598 7612 7581 7597 7612 (平均: 約7597ミリ秒)
で、find2の方が、0.67%程高速ですね。
念のため、「乱数の引きの悪さ」で負けてる可能性を排除するため、find2とfind1の順序を入れ替えたりもしてみましたが、傾向は変わらないです。
この例では、遅い方の方が不自然な記述になってますが、確かに、前置を使った自然な書き方より、後置に置き換えた不自然な書き方の方が早いという例もあるでしょうね。
これぐらい自明(手動で、ここの前置を後置に置き換えろ、といわれたら一瞬で出来る)なら最適化の餌食になってもおかしくないと期待していたんですが、なかなか奥深いです。
static const int MAX = 10000;int List[MAX];int Count;
void find1(){ Count = 0; for(int i = 0; i < MAX; i ++){ if(rand() < RAND_MAX / 2) List[Count ++] = rand(); }}
void find2(){ Count = -1; for(int i = 0; i < MAX; i ++){ if(rand() < RAND_MAX / 2) List[++ Count] = rand(); } Count += 1;}
int main(){ clock_t start;
start = clock(); for(int i = 0; i < 100000; i ++){ find1(); } std::cout << clock() - start << std::endl;
start = clock(); for(int i = 0; i < 100000; i ++){ find2(); } std::cout << clock() - start << std::endl;//以下繰り返し return 0;}
g++ 4.9.2で試してみたけど、最適化オプション無しだと、find1の方が1%弱、速い。ただ、-O2とか-O3とかだと、ほとんど誤差範囲だが、find2の方が0.1%ぐらい速い。普通に考えれば、このコードにおいては前置のほうが速そうなんだけど、意外だった。
因みに、分岐を除くと、find1の方が1%以上速いので、分岐予測絡みだとは思うけど、詳しいところは分からん。
配列に頭から詰めてく・読んでくためのインデックスとかの場合、初期値と終了値がずれるため明らかにアルゴリズムが違います。ストール直後にインクリメント演算子の戻り値を使う場合、配列へのアクセスがインクリメント結果待ちになるか、配列アクセスと並行してパイプラインに詰め込めるかは明らかに違います。
そしてその程度の用途では演算子オーバライドだのでかいクラスのコピーだのとは次元の違う、単なる1レジスタの複製であり、その程度はレジスタリネームで隠蔽されかねないコストな訳です。
複雑なイテレータオブジェクトだと前置の方が高速になりがちで、単純なイテレータオブジェクトだと後置の方がパイプライン的には好都合、と言うだけです。リンク先の引用元はおそらく後者で、リンク元は前者よりに迷走してるから話が変なだけです。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
海軍に入るくらいなら海賊になった方がいい -- Steven Paul Jobs
あきらかにおかしい (スコア:0)
ストールが問題になるにはデータ依存が存在していることが必要で、データ依存の有無はアルゴリズムによって決まります。
インクリメントが後置か前置かとは別の話でしょう。
前置インクリメントを使ったためにデータ依存が新たに生じることはありません。
（生じるとすれば、アルゴリズムが変わっています。）
影響があるとすればコンパイラの最適化でしょうが、前置インクリメントの方が一般に処理が単純なので、
これを使ったために、データ依存解析に失敗するケースというのはちょっと想像がつきませんね。
逆に、後置インクリメントを使うことによって生じるコピーコンストラクタの削除にコンパイラが失敗するケースなら十分あり得ます。
一般論として、コピーコンストラクタを削除するには手続き間解析（少なくともインライン化）が必要ですが、
手続き間解析はコストが大きいため、現行のコンパイラは、これを完全には行えていないからです。
（そもそも、コピーコンストラクタのソースコードが提供されていない場合、リンク時最適化を利用しない限り、最適化はできません。）
Re:あきらかにおかしい (スコア:1)
うん。リンク先も、単純な場合はコンパイラが勝手に上手いことやってくれる、までは良いんだけど、そこから迷走しだしてるね。
前置/後置の差で不自然なストールを演出しようとしても、
わざわざそこでソースを分割して最適化出来ないような工夫さえしてなければ、
本質的にストールを考慮て最適化する必要があるかどうか、コンパイラには見抜かれる。
コンパイラの最適化の限界を知っておくのはなかなかおもしろい。
ソースコードを愚直に実行するとものすごく無駄な手順を踏むことになるけど、
構造化されてて書きやすく、従ってバグを入れにくいような書き方を気楽に使える。
例えば、2×2行列の掛け算みたいな、手で書くと最小限のコードに出来そうだけどどこか書き間違えてしまいそうな処理も、
汎用的なn×n行列の掛け算インライン関数を呼んでおけば、
何だかループがアンロールされて、必死こいて必要最小限だけ手で書いたやつと似たような結果になる。
出来合いの関数が無い処理でも、こういうのは、添え字を丁寧に書き並べるより、ループを使ったほうが書き間違いをしづらいし。
Re: (スコア:0)
このあたり理解してる人間がわざとそうやって書いててもコードレビューという名の理解してない人間への説明会で
遅いから書き換えろと言われる率の高さがなぁ
変わらないって説明しても聞きゃしねぇ…
Re: (スコア:0)
もしも差があったらコンパイラっていうかプリプロセッサに問題があるって言うのが現代でしょう。
コード化された時に大きな速度差が出るようなコードって、プロセッサ処理よりI/O周りの処理がボトルネックになる方が大きいと思う。
実際にコード化されたイメージをしながらプログラムソースを書く時代はとっくに終わってる。
Re: (スコア:0)
この問題はアルゴリズムやコンパイラレベルの話ではなく、CPU内部のパイプラインの話なのだが…。
Re:あきらかにおかしい (スコア:2)
ストールを気にするのなんてループの中くらいだし、それなら今時のCPUだと上手く隠してくれそうな気がするする。
Re: (スコア:0)
ゲームエンジンの話なので対象が「今時のCPU」ではないPS3等のインオーダーのCPUも入るわけですよ。
で、インオーダーのCPUのストールコストは非常に高い。
そこから後置インクリメントが云々って話なわけです。
Re:あきらかにおかしい (スコア:2)
インクリメント前の変数を持つ時点でreturnする前の処理は多いと思うのだが？
Re:あきらかにおかしい (スコア:1)
同感。元ねたがコンパイラの話とCPUの話をごっちゃにしているのが間違い。常識が覆ることがあったのはCPUの進歩で動的に平行処理されるようになったから。
Re: (スコア:0)
同じ、同じ(笑)。
なんで、コンパイラの最適化ルーチンの設計なんてハッカーの極みみたいな仕事をしてる人が、
「CPUのパイプラインまで考えたら、前置より後置の方が良いぞこれ」とか言う
アイデアに気付かないと思ってるのよ。
その方が速くなりえて、置き換えても良い場面なら、どっちで書かれてても勝手に置き換える最適化ルーチンを設計するって。
置き換えても差し支えがないかどうかはアルゴリズム次第。
本当は置き換えられるけど、コンパイラが見落とすほど巧妙に一見そうは見えないコードなんて、
難解Cコードコンテストぐらいでないと出て来ないんじゃない？知らんけど。
Re: (スコア:0)
開始値は簡単に修正が効くけど、終了値が一個違うアルゴリズムに自動で置換するのは大変だと思うなぁ…
if(～)a[++i]=b;
みたいにして条件に合致するものを配列に詰めて終了値を使う処理とか、
詰めるときのインデックス値を使う処理があったら、そこら辺まで最適化で変更するの？
別の処理に渡す変数の中身を最適化で変えてしまうのは現在最適化で許される改変の範疇を超えてるでしょう。
Re:あきらかにおかしい (スコア:1)
なるほど、それは確かに何か違いが出るかも知れないですね。
大ざっぱな実験ですが、試しにやってみました。
下記のように、同じ結果になるfind1とfind2を、10万回試す指向を交互にやってみたところ、clock()で計ったミリ秒は、
find1: 7550 7534 7551 7551 7550 7551 (平均: 約7548ミリ秒)
find2: 7582 7598 7612 7581 7597 7612 (平均: 約7597ミリ秒)
で、find2の方が、0.67%程高速ですね。
念のため、「乱数の引きの悪さ」で負けてる可能性を排除するため、
find2とfind1の順序を入れ替えたりもしてみましたが、傾向は変わらないです。
この例では、遅い方の方が不自然な記述になってますが、
確かに、前置を使った自然な書き方より、後置に置き換えた不自然な書き方の方が早いという例もあるでしょうね。
これぐらい自明(手動で、ここの前置を後置に置き換えろ、といわれたら一瞬で出来る)なら
最適化の餌食になってもおかしくないと期待していたんですが、なかなか奥深いです。
static const int MAX = 10000;
int List[MAX];
int Count;
void find1(){
Count = 0;
for(int i = 0; i < MAX; i ++){
if(rand() < RAND_MAX / 2) List[Count ++] = rand();
}
}
void find2(){
Count = -1;
for(int i = 0; i < MAX; i ++){
if(rand() < RAND_MAX / 2) List[++ Count] = rand();
}
Count += 1;
}
int main(){
clock_t start;
start = clock();
for(int i = 0; i < 100000; i ++){
find1();
}
std::cout << clock() - start << std::endl;
start = clock();
for(int i = 0; i < 100000; i ++){
find2();
}
std::cout << clock() - start << std::endl;
//以下繰り返し
return 0;
}
Re: (スコア:0)
g++ 4.9.2で試してみたけど、最適化オプション無しだと、find1の方が1%弱、速い。ただ、-O2とか-O3とかだと、ほとんど誤差範囲だが、find2の方が0.1%ぐらい速い。普通に考えれば、このコードにおいては前置のほうが速そうなんだけど、意外だった。
因みに、分岐を除くと、find1の方が1%以上速いので、分岐予測絡みだとは思うけど、詳しいところは分からん。
Re: (スコア:0)
配列に頭から詰めてく・読んでくためのインデックスとかの場合、初期値と終了値がずれるため明らかにアルゴリズムが違います。
ストール直後にインクリメント演算子の戻り値を使う場合、配列へのアクセスがインクリメント結果待ちになるか、配列アクセスと並行してパイプラインに詰め込めるかは明らかに違います。
そしてその程度の用途では演算子オーバライドだのでかいクラスのコピーだのとは次元の違う、単なる1レジスタの複製であり、その程度はレジスタリネームで隠蔽されかねないコストな訳です。
複雑なイテレータオブジェクトだと前置の方が高速になりがちで、単純なイテレータオブジェクトだと後置の方がパイプライン的には好都合、と言うだけです。
リンク先の引用元はおそらく後者で、リンク元は前者よりに迷走してるから話が変なだけです。