アカウント名:
パスワード:
ストールが問題になるにはデータ依存が存在していることが必要で、データ依存の有無はアルゴリズムによって決まります。インクリメントが後置か前置かとは別の話でしょう。前置インクリメントを使ったためにデータ依存が新たに生じることはありません。（生じるとすれば、アルゴリズムが変わっています。）
影響があるとすればコンパイラの最適化でしょうが、前置インクリメントの方が一般に処理が単純なので、これを使ったために、データ依存解析に失敗するケースというのはちょっと想像がつきませんね。
逆に、後置インクリメントを使うことによって生じるコピーコンストラクタの削除にコンパイラが失敗するケースなら十分あり得ます。一般論として、コピーコンストラクタを削除するには手続き間解析（少なくともインライン化）が必要ですが、手続き間解析はコストが大きいため、現行のコンパイラは、これを完全には行えていないからです。（そもそも、コピーコンストラクタのソースコードが提供されていない場合、リンク時最適化を利用しない限り、最適化はできません。）
この問題はアルゴリズムやコンパイラレベルの話ではなく、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%以上速いので、分岐予測絡みだとは思うけど、詳しいところは分からん。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
UNIXはただ死んだだけでなく、本当にひどい臭いを放ち始めている -- あるソフトウェアエンジニア
あきらかにおかしい (スコア:0)
ストールが問題になるにはデータ依存が存在していることが必要で、データ依存の有無はアルゴリズムによって決まります。
インクリメントが後置か前置かとは別の話でしょう。
前置インクリメントを使ったためにデータ依存が新たに生じることはありません。
（生じるとすれば、アルゴリズムが変わっています。）
影響があるとすればコンパイラの最適化でしょうが、前置インクリメントの方が一般に処理が単純なので、
これを使ったために、データ依存解析に失敗するケースというのはちょっと想像がつきませんね。
逆に、後置インクリメントを使うことによって生じるコピーコンストラクタの削除にコンパイラが失敗するケースなら十分あり得ます。
一般論として、コピーコンストラクタを削除するには手続き間解析（少なくともインライン化）が必要ですが、
手続き間解析はコストが大きいため、現行のコンパイラは、これを完全には行えていないからです。
（そもそも、コピーコンストラクタのソースコードが提供されていない場合、リンク時最適化を利用しない限り、最適化はできません。）
Re: (スコア:0)
この問題はアルゴリズムやコンパイラレベルの話ではなく、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%以上速いので、分岐予測絡みだとは思うけど、詳しいところは分からん。