前置インクリメント(++x) よりも後置インクリメント(x++) のほうが高速? 129
ストーリー by headless
演算 部門より
演算 部門より
insiderman 曰く、
C/C++には「++x」(前置インクリメント) や「x++」(後置インクリメント) のようなインクリメント演算子がある。前者はxをインクリメントしてからその値を返すのに対し、後者はxの値をコピーしてからxをインクリメントし、コピーした値を返す。後置インクリメントは値をコピーする分遅いと言われていたそうなのだが、これとは逆の主張が話題になっているそうだ(闇夜のC++)。
これによると、前置インクリメントはインクリメント処理が終わるまで値を返せないのに対し、後置インクリメントはインクリメント処理が終わる前に値を返すことができる。そのため並列処理が可能になるなどのメリットがあるという。ただし、オブジェクトをコピーするコストについては議論されていないとのことなので、コピーに必要なコストが大きい場合は逆に処理が遅くなる可能性もある。
そもそもタレコミ子は前置インクリメントと後置インクリメントの処理の違いについては把握していたが、処理コストの違いについては知らなかったので非常に勉強になった(言われれば確かにそうだと理解できるのだが)。
記事で話題となっている書籍の英語版「Game Engine Architecture, Second Edition」は、該当部分をGoogleブックスで閲覧できるので、参照してほしい。
そもそもPDP-11のアセンブラにもとづく、 (スコア:2, 参考になる)
都市伝説が形を変えて流風しているじゃないかな。(ただし、PDP-11のことは、かつては「常識」だった)。
このあたりのそこそこ説得力のある話は、
http://ja.wikipedia.org/wiki/PDP-11#.E5.91.BD.E4.BB.A4.E3.82.BB.E3.83.... [wikipedia.org]
に書いてある。
Re:そもそもPDP-11のアセンブラにもとづく、 (スコア:2, 興味深い)
時代とともにハードウェアも変われば「常識」も変わるというだけの話だな。似たような例として、「floatのほうが速い」→「コプロセッサがあるからfloatもdoubleも変わらない、むしろいちいち型変換が入る分floatのほうが遅い」→「floatのほうがSIMD命令で並列処理できる分速い」という変遷があった。
ところで2番めを有名にした記事はこれ [pro.or.jp]なんだが、
としっかり書かれているのに、この一番肝心な部分は無視されて新しい迷信を作り出しちゃったというのがもうね。
こういうこと? (スコア:2)
b = a[i++] みたいな場合、
まず a[i] の中身を取りに行く
もう i は参照しちゃったので、i は変更可
a[i] の中身を取りに行きながら、並行して i もインクリメント => 速い
だけど、b = a[++] だと
まず i をインクリメント
インクリメントが終わらなきゃ、どこにアクセスしていいか分からない
並行不可 => 遅い
for( ほげ; ふが; i++) とか for( ほげ; ふが; ++i) の場合
コンパイラが最適化しちゃうので、どっちも同じ
結論: 習慣化する (≒考えずにやる) なら、後置で。
Re:こういうこと? (スコア:2)
だけど、b = a[++] だと
これでは、意味不明ではないか orz
正しくは当然
b = a[++i]
です。
Re:こういうこと? (スコア:1)
Re:こういうこと? (スコア:2)
ループとかだと初期値を増減するだけで本質的に同じ動作にできますよ。
高レベルな低レベル話 (スコア:2)
業務アプリケーション開発してる自分の周りでは・・・
i++って書いたら、これ何?(トリッキーな書き方してんじゃねーよという雰囲気)
「++」が使える言語で、VBの癖なのかiKingaku = iKingaku + 1とかstrSql += strSql のようなシステムハンガリアンを未だに普通に見かける
とかそんなレベルよ。
どっちが速いとかなんとか!?業務アプリのレベルでは全く関係ない。
組み込み系か、ゲームのAPI開発くらいでないの?
馬鹿馬鹿しい (スコア:1)
動作の違うものを比較しても意味がない
Re:馬鹿馬鹿しい (スコア:2)
いやほんとにその通りだ。
for (int i = 0; i num; ++i)
for (int i = 0; i num; i++)
でどちらが高速かという話ならまだしも、無意味な比較にしか思えない。
Re:馬鹿馬鹿しい (スコア:1)
プログラムの意味について議論しているのであれば仰るとおりですが、
議論されている内容はプログラムの意味ではありません。
少なくともそれだけを議論しているわけではありません。
なので比較する意味はあります。
Re: (スコア:0)
用途も違いますからな。ただどちらかが軽いなら軽い方をつかうべきではある。
個人的にはよほどリソースが逼迫しているか顧客からの要求が厳しくない限りはパフォーマンス上有利な方よりも処理に適した方を使いたい。
議論や考察だけでなく計測結果は? (スコア:1)
この手の話はよく出るけど、最終的には計測結果だよね。
タレこみにあるリンク先でもマシンコードで一致する例などそこそこのことはしているが、ちゃんと意味を持たせるなら現実的な処理での計測結果がないとね。
GAMEを作るような場合はぎりぎりの性能を目指すからそうでもないのかな?
Re:議論や考察だけでなく計測結果は? (スコア:2)
PS3,PS4,XBox 360,XBox Oneなどで計測できて,その結果を公表できる人を待ち望んでいます.
ベンチマーク結果って秘密保持契約に引っかかるのだろうか…?
Re: (スコア:0)
並列化を考慮する必要があるんだし、ケースバイケースになるんで
単に計測したからといって結論が出るもんじゃ
ないんだよ
Re:議論や考察だけでなく計測結果は? (スコア:1)
ケースバイケースだから実測が重要なのだが...
Re: (スコア:0)
分かってないな
結果に影響を及ぼしうる因子なんて無数に考えられるわけで
単に、やってみた、で結論が出るもんじゃないんだよ
Re: (スコア:0)
実測って一種類の結果しか出ないものと思ってない?
Re: (スコア:0)
無数の因子の組み合わせを全て実測することは不可能なわけで
Re: (スコア:0)
因子のパターンが多すぎて結果出すのもしんどすぎるって話じゃないの
Re: (スコア:0)
> 結果に影響を及ぼしうる因子なんて無数に考えられるわけで
そういう場合は「ほとんど影響なし」という単純な結論になるな
Re: (スコア:0)
ゲーム機もそれなりに複雑なOSがのっていたいたりで今回の例のインクリメント記法の違いは無視できる誤差かと。
これを気にするくらいならゲームロジック全体を見直して無駄を省く方が精神衛生上よろしいと思います。
ネトゲにいたってはそんなチューニングも無意味なくらい全体的に非同期で動かすことが前提ですし…
ただシェーダーまわりはまだギリギリを狙うメリットが大きいかな。
Re:議論や考察だけでなく計測結果は? (スコア:1)
今の開発環境なら++が前か後か無視できるだろという意見には同意。
ただ、昔は最適化が下手なコンパイラやちょっとしたテクニックで性能改善があった経験があるので、無下に否定する気はない。
ぎりぎり狙うならコンパイラーの癖を考慮したコーディング規約くらい作るかもしれないとは思っている。一般化できないことだし、根拠薄い思いだけど。
現場の人の意見が聞きたいな。
Re:議論や考察だけでなく計測結果は? (スコア:1)
プロファイルをとって結果が有意であれば規約化というのはありだと思いますが、今回の前置後置の話レベルはやはり誤差かなあと。
整数の割り算だとキャストしてでも逆数をかけた方が速いとかはあるかな。
どちらかというとコードキャッシュ、データキャッシュを生かす実行単位を維持することの方が効果高いと思っています。
ループ処理とか余計なif文をなくす設計とか。
今時の規模だとデータキャッシュはようわからんというところでしょうが、コードをコンパクトにすることはまだコントロールできると思います。
ここまでくるとゲームとか関係なくて、なんとなくでコード書いちゃ駄目だよねーってだけの話ではないかと。
Re: (スコア:0)
ブログ記事の方の感想も、どちらかと言うと効果に疑問を投げかける姿勢ですね。
というコメントが象徴的かなと思います。
オペレータオーバーライド (スコア:1)
C++としてできるのはいいけど、オブジェクトに++/--を適用したくないor適用するなら(そこそこ)アトミックである特性を維持してほしかった...感が。
# +=1の処理になる、ではない、んだよね?
M-FalconSky (暑いか寒い)
Re:オペレータオーバーライド (スコア:1)
C++じゃ保証してないしC++で保証するのは現実的ではないから必要ならインラインアセンブラでアトミックナンバークラスでも書けばよろし。
Cはかわらない (スコア:0)
Cは速度変わらないけど
C++ はオーバーロードの関係で余計な処理が入ってた覚えがある
えーと (スコア:0)
騒ぐほど拘るとこかね?
Re:えーと (スコア:1)
耳が痛い。
オフトピですがついでに愚痴る。
自分は森を見るよう努めていましたが、周りは木…部分最適ダイスキーだらけで衝突すること多し。
システムなりサービス全体でバランスをとりたく管理側に軸足移していろいろ頑張ってましたが疲れてしまい結局ゲーム開発の本流からは身を引いてしまいました。
ライブラリ使えば済むところを余計なこだわりwを持つせいで実装が遅れているのに良いモノは時間がかかるとか勘違いも甚だしい。
給料がどこから出ているのか、と小一時間(ry。
まずは世に出さないといかんだろ。
あきらかにおかしい (スコア:0)
ストールが問題になるにはデータ依存が存在していることが必要で、データ依存の有無はアルゴリズムによって決まります。
インクリメントが後置か前置かとは別の話でしょう。
前置インクリメントを使ったためにデータ依存が新たに生じることはありません。
(生じるとすれば、アルゴリズムが変わっています。)
影響があるとすればコンパイラの最適化でしょうが、前置インクリメントの方が一般に処理が単純なので、
これを使ったために、データ依存解析に失敗するケースというのはちょっと想像がつきませんね。
逆に、後置インクリメントを使うことによって生じるコピーコンストラクタの削除にコンパイラが失敗するケースなら十分あり得ます。
一般論として、コピーコンストラクタを削除するには手続き間解析(少なくともインライン化)が必要ですが、
手続き間解析はコストが大きいため、現行のコンパイラは、これを完全には行えていないからです。
(そもそも、コピーコンストラクタのソースコードが提供されていない場合、リンク時最適化を利用しない限り、最適化はできません。)
Re:あきらかにおかしい (スコア:1)
うん。リンク先も、単純な場合はコンパイラが勝手に上手いことやってくれる、までは良いんだけど、そこから迷走しだしてるね。
前置/後置の差で不自然なストールを演出しようとしても、
わざわざそこでソースを分割して最適化出来ないような工夫さえしてなければ、
本質的にストールを考慮て最適化する必要があるかどうか、コンパイラには見抜かれる。
コンパイラの最適化の限界を知っておくのはなかなかおもしろい。
ソースコードを愚直に実行するとものすごく無駄な手順を踏むことになるけど、
構造化されてて書きやすく、従ってバグを入れにくいような書き方を気楽に使える。
例えば、2×2行列の掛け算みたいな、手で書くと最小限のコードに出来そうだけどどこか書き間違えてしまいそうな処理も、
汎用的なn×n行列の掛け算インライン関数を呼んでおけば、
何だかループがアンロールされて、必死こいて必要最小限だけ手で書いたやつと似たような結果になる。
出来合いの関数が無い処理でも、こういうのは、添え字を丁寧に書き並べるより、ループを使ったほうが書き間違いをしづらいし。
Re: (スコア:0)
この問題はアルゴリズムやコンパイラレベルの話ではなく、CPU内部のパイプラインの話なのだが…。
Re:あきらかにおかしい (スコア:2)
ストールを気にするのなんてループの中くらいだし、それなら今時のCPUだと上手く隠してくれそうな気がするする。
Re:あきらかにおかしい (スコア:2)
インクリメント前の変数を持つ時点でreturnする前の処理は多いと思うのだが?
Re:あきらかにおかしい (スコア:1)
同感。元ねたがコンパイラの話とCPUの話をごっちゃにしているのが間違い。常識が覆ることがあったのはCPUの進歩で動的に平行処理されるようになったから。
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;
}
intel者 (スコア:0)
286時代は前置の方が早いと聞いていたので、前置が習慣になった。
今時パソコン向けならどっちでもいいと思うけどね。
motorola者 (スコア:1)
68000使いだと、
デクリメントは前置、
インクリメントは後置、
ですね。
スタックの処理は通常、
push時: スタックポインタをデクリメントしてから、スタックポインタの指すメモリに書き込み
pop時: スタックポインタの指すメモリを読み込んでから、スタックポインタをインクリメント
という処理になります。
で、スタック処理を高速化するために、68000ではこれらの処理は一命令で処理できるようになっていました。
でもって、68000はスタックポインタも汎用レジスタの一つ、という直交性の高い設計なので、汎用レジスタに対しても前置デクリメントと後置インクリメントは一命令で処理できるからちょっと速い。
#正確に言えば、アドレスレジスタについての話なので、「*--p」「*p++」が一命令処理。
Re:intel者 (スコア:1)
無駄は無駄なのだが、今でもそういう無駄な作業を一度は経験してみるのは無駄ではない
プロセッサの性能が上がって今はインタプリタ言語で結構大掛かりな処理をする機会も多いが、そういうインタプリタのコードを人手で最適化をする時にその無駄な経験が役に立つ
#インタプリタは遅いからと言って簡単に放り投げてしまう人もいるが、ほんのちょっとしたオプティマイズで劇的に速度が改善されることもあるのよ
こんなタレコミがあると・・・ (スコア:0)
宗教チックになって、コードを書く人間によって
記載方法が変わったりしない?
品質面を考えそっちのほうが不安なんだが、、、
もうしゅこし、まともなタレコミがほしい。
-- は前置、++ は後置 (スコア:0)
対象 CPU が何だったのか記憶にありませんが、x86系でないのは確か。
と、ここまで書いて、逆だったかと思い始めた。。。
Re:-- は前置、++ は後置 (スコア:1)
たぶんMC680x0系
ただし単なる--,++ではなく、
*--p 、*p++のようにポインタを増減して指す値を使う場合。
前者がpush、後者がpopに相当するので、スタックポインタ用に高速な命令が存在する。
そしてスタックポインタとして汎用レジスタの一つを使うCPUでは、他の汎用レジスタでも使える。
H8やSHもこのアドレッシングモードを踏襲してたと思う。
Re: (スコア:0)
mips fujituu1600 IBM 分からないテープが動いていた
日立わからない1++しかなかった方打ち間違い起きたとこ。
COBOL85しか知らない1++を使っていた、パソコン使って書いてる、最新のoSX今はIMEつていうのキーボードばかり汎用機ばかりで慣れない
済まない
は僕の癖(クセ)
Re: (スコア:0)
正解だよ。PDP-11 のアセンブラのアドレッシングモード(わかる?)だと、--iとi++しかないからね。でも、これは都市伝説の類。
よく分かった! (スコア:0)
で、そこ並列化されてる言語って?
Re:どのコンパイラではどういうコードに落ちてどのプロセッサではどう実行されるみたいな話がないと無意 (スコア:1)
「ふーん、ちなみに ++x と x++ の比較と、*++x と *x++ の比較では事情が違うよね?」
と振って、相手が反応するかどうかで話を聞く価値があるかどうか値踏みできそうな気がする。
でも、組み込みとかデバドラとかのレイヤのコーディングしてる人とか、HPCの人とか以外は、パフォーマンスのボトルネックのありかがよそにあるので、こんな些細な話はそもそもあまり気にしないのではないのかな。
Re:どのコンパイラではどういうコードに落ちてどのプロセッサではどう実行されるみたいな話がないと無意 (スコア:1)
> いきなり3を代入するんじゃなくて、*xを徐々に0~3まで増やして貰わないと困る、
困るような使い方をしてる時はvolatile を付けましょう。
「volatile int* x」なら大丈夫。INC1は毎回加算後にメモリ書き込みされます。
#組み込み系のコードで、割り込みルーチンと本ルーチンで同じ変数を参照するのはよくある話。
#で、「正常動作しないので最適化はオフにしておいてください」とかいう説明してるのもたまに見かけたりして…
#ちゃんとvolatile付けろよとツッコミを入れたくなります。
Re:可読性 (スコア:1)
「!」もわからない奴がいるとか言われたことがある。
# もうね、そいつを教育するほうが先だろうと(ry
Re:可読性 (スコア:1)
> ++C言語ではどうだか知らんが。
コレを見てようやくわかった。C++って加算前の言語が返ってきてるから、微妙にいろいろ失敗した設計なんですね。
(20年かけて改善されてきてはいるものの…)
Re:可読性 (スコア:1)
日常使ってる言語がSVO型かSOV型かで、、
アレゲはハナゲ以上のなにものでもなさげ