C、C++の最適化について語るスレ 3

コンパイラ性能、コンパイルオプション、コードの最適化などについて語りましょう。
主に速度面の最適化を中心としますが、サイズなどの最適化もどうぞ。
なお、OS、CPU、コンパイラなどは限定しません。

前スレ

C、C++の最適化について語るスレ
http://pc11.2ch.net/test/read.cgi/tech/1084676298/ (過去ログ化前)

C、C++の最適化について語るスレ 2
http://pc11.2ch.net/test/read.cgi/tech/1177808054/

スレが荒れるので団子は書き込み禁止です

>前スレ1000
読めてないよ

>>2
まったくだよな。
前スレの後半読み飛ばしまくったけど、それでもむかついた。

むしろ組み込みしか頭にないおっさん連中全員うぜぇ

最適化の具体例を出して議論して欲しいな。

前スレの後半は組み込み関連の話だけになってたな。

ダンゴの名言が面白かった。

組み込みCPU限定の話題はスレ違いっていうか板違い

>なお、OS、CPU、コンパイラなどは限定しません。

かってにシキるなよ。クソを流さないダンゴ。

お前ら組み込みの大変さを理解してないだろ。
これだから組み込みを知らない奴らは・・・

>>11
大変なのはいいからC++でリソース潤沢な環境の最適化の需要を想定できない人は電子板に行ってください。

ここのカテゴリは「PC等」なんで。
俺はPPCマカーでもあるから非x86には寛容な方だけど

家電 UIのうんこ加減(ry

>>12
前スレの807-813の再レスというかネタだろ

マカーきめえｗ

>>15
うるしぁiPodぶつけんぞ

>>16
前スレの948に答えてあげよう、ROMは割と余る、RAMは意外と足りない。
あと16ビット系は多品種少量でめちゃ現役。
ARMやMIPSみたいな豪華なCPUが使えない場所はけっこうあるよ。

ヨッシーの鳴き声

団子さん薬飲みすぎじゃね？
テンション高すぎｗ

そろそろ具体的な最適化の話にもどらないか？

最適化の需要が少ないって絡まれるのは、やだなあ。

ここは団子さんを最適化するスレ

早く右辺値参照が使いたい・・・

具体的なの書くと、マイノリティって言われるしな〜。

マカーか。納得。

飛ばしすぎなダンゴさんがちょっと心配になってきたな

前スレのこれってダンゴさんの自演なの？

905 ：デフォルトの名無しさん：2008/07/04(金) 00:07:09
>>899
憶測だけど多分25前後。

>>903-904
いや、シャシャリ出てこないだけで話を理解出来る奴もいるよ。
奴は持論、空論、論理のすり替えは多いがCPUのアーキテクチャは人一倍理解している。たまに勘違いしてるが、突っ込みどころは少ない。

それよりファミリーカーの話題にスポーツカーとか農機とか平気で語り出して、それで結論づけて話を終わらせるのが問題なんだよ。

ほとんどがダンゴさんの自演だよ

>>24
どうせならHDみたいな本に載せてもいいような、
機種によらずほとんどのCPUで有効な最適化手段用意しようよ。

ちなみに前スレのは俺の使う石だとかえって遅くなるぞ。
そういう特定のCPUに依存したコードをことわりもなく書くのが傲慢なんだよ

俺がどれだけSSEとかVMXの話題遠慮してると思ってるんだ


もっとも、この板に専門スレがあるがな

そのまま色々遠慮しててください。

ダンゴさんの心遣いがとうとう語られてしまったな

団子に構って欲しい人だらけのようだけど、気にせず書くよ。

ヒープ確保よりスタック確保の方が早いけど、
スタックだとコンパイル時にサイズ決まってしまうのが残念だ。
allocaが安心して使えたら良いのに。

リンク時だろ

C++はもちろん当たり前だがC99準拠の処理系では
void foo(int n)
{
　double a[n];
　…
}

こんな風に整数の変数でスタック上配列を確保できる。
もちろん関数の途中でも{}で囲んでやりさえすればいつでも使える。

なんにせよC99準拠の処理系ならほぼ例外なく
何らかの形でallocaみたいな関数も実装されてると思ってるが。

しかし機械語レベルで見るとなんのことはない、x86でいうespを変数値ぶんだけ操作してるだけ。

何のことは無いって言うけど、
配列のアドレスを別に保存しておかないといけないし、
サイズも sizeof 用に保存しておかないといけないんだぜ。

その昔 x68k 用の gcc で

void foo(const char *p)
{
　char a[strlen(p) + 1];
　...
}

で上手くコンパイルできないバグがあった。

esp を操作するだけなんて言う奴は考え浅すぎ。

>>34
>C++はもちろん当たり前だがC99準拠の処理系では
C++でも出来るように読めてしまう

>>35,36 そんなのコンパイラ屋ならできて当たり前のレベルだろｗ

>>34
allocaと同じく、関数頭辺りでスタックのページ拡張コードも入るよ。
espをいじるだけだと例外が発生する。

C++にも可変長配列欲しいな・・・

>>38
だから、>>34 はそんなレベルじゃないって言ってるだけだが。

>>39
それは、環境による。

全ての環境にページングシステムがついてるわけじゃないし、
スタック例外処理ハンドラで拡張するシステムもあるし。

>>40
std::vect(ry

そんなnew/deleteのただのラッパーじゃ嫌です＞＜

手元にint32_t変数があるとして、このビットを逆順にする高速なコードをください

i = ~i;

>>45
それ反転

鏡を2つ用意します

ビット逆順ってどんなときに必要になるんだ？

>>29

>そういう特定のCPUに依存したコードをことわりもなく書くのが傲慢なんだよ

すげぇ
お薬効きまくってますネ！

47みたいなのを天才というんだな

前スレがdat落ちしていない間は良いけど、
前スレ見てない人には、団子の人格批判だけのレスは
アホっぽく見えるから、止めた方が良いと思うぞ。

団子が居る限り
このスレも
同じレベルだろ

正直、団子だけでなく双方同レベルです・・・

>>43
ヒープに確保で駄目な理由ってなに？
逆にスタックを使うデメリットは認識してる？
多くのCランタイムはアプリケーションヒープはプールしてmallocの度に未使用領域を再利用する実装が多いよ

Cellのspu-gccだとは単にLS上の空いたとこ割り当てるだけだし

>>29
>そういう特定のCPUに依存したコードをことわりもなく書くのが傲慢なんだよ
勝手に決めんな。このスレはOS、CPU、コンパイラは限定しないんだから、
古くても新しくても、機種依存でも、あきらかにそれとわかれば問題ねーんだよ。

>>34
高速なメモリプールを動的に確保したいってだけでしょ？
最適化は直接関係ないじゃん。

>>48
他システムとのエンディアン変換で使わんか？フーリエ変換でもあると便利でしょ。
SIMDにそんな命令があるCPUもあるから、どうしても速度が気になるなら直書でやったら？
ダンゴが固定しているCPUに依存しない最適化じゃ無理。

スタックに確保するとか決まってたっけ？　別にヒープで実装してもいいんじゃないの

>>56
ダンゴの使っていない処理系の話題は板違いです

>>44
じゃ古典的な実装のひとつでも覚えようか。
ちなみに4〜5行目はBSWAPがあれば一発だね。
i = ((i&0x55555555)<<1) | ((i>>1)&0x55555555);
i = ((i&0x33333333)<<2) | ((i>>2)&0x33333333);
i = ((i&0x0F0F0F0F)<<4) | ((i>>4)&0x0F0F0F0F);
i = ((i&0x00FF00FF)<<8) | ((i>>8)&0x00FF00FF);
i = i>>16 | i<<16;
ま、これが最善とは限らないがね。
ちなみに他に、ビットスワップにXORを使う実装があるが
スーパースカラと相性よくない気がするので俺はこっちが好き

＃組み込み爺さんは放置推奨。かまうあなたも組み込みです。

>>55
Radix-SRT dividerは組み込みには関係ないからと噛みついたのが組み込み爺さん
ダブスタもいいところだな

くみ取り系は基本的に自己チューですので

>>58
用意してたの？

>>58
で？最適化は？

すまんが、組み込み＝じいさんってどういう発想なの？
俺、組み込みやってるんだけど、このスレじゃダンゴ氏に
肯定的でないと発言出来ないって事？
あと、結局このスレはCPU依存な話題はNGって事でOK？

>>54
いや、駄目ってことではなくて、違うじゃんってこと。
そりゃヒープ気分ででかいの確保したらすぐ死ぬけどさ。

>>56
可変長配列のこと？
だとするとC言語用の単なる構文糖衣みたいなものか・・・。

>>55
バイト列じゃなく、ビット列まで逆になるエンディアンがあるってこと？

エンディアンってバイト順のことじゃないのか？
最近はビット順もエンディアンって言うのか？

シリアルでLSBから送ってくる機器を相手にした事はあるけど

7セグLEDの表示ﾋﾞｯﾄ列が逆で手持ちのﾋﾞｯﾄ列を逆順にしたいことはあったな。
まぁ手でやったけど。

780 名前：デフォルトの名無しさん[] 投稿日：2008/06/17(火) 08:53:09
ビット演算だけで、剰余を求める方法を教えてください

788 名前：,,・´∀｀・,,）っ-○◎●[sage] 投稿日：2008/06/28(土) 13:17:18
というか、除算・剰余にビット演算を使うような厨テクなんて
最近のCPUじゃマイクロコードレベルで同等かそれよりエレガントなことやってるだろうから
よっぽどガチガチのRISCでも使わない限り覚えても意味ないよ

795 名前：デフォルトの名無しさん[sage] 投稿日：2008/06/29(日) 06:48:48
古いCPUと枯れたコンパイラの仕事はもう無いっておもってるのか？
それとも、ダンゴがアホなのか？
--
これで荒れはじめたんでしょ。
よっぽどツボついたのか、ダンゴが組込み＝悪って事にして散々罵倒しだした。
それで、なんだか、ココは最新のベクトル系の最適化の話以外は禁止なふんいき。

>>61
こういうのは基本的に何パターンか丸暗記してる。HDにも載ってるし。
ちなみにこれは比較的命令の並列度が高めのCPU向け。

>>62
逆に、これより速いのあるならやってみてよ。
ちなみにAltiVecやSSE4を使っていいなら攪拌命令を使って各バイト4ビットずつ
同時にビットオーダーを反転する手もある。

ごめん。エンディアンとFFTのビット順の逆は別の話だった。混同しちゃってた。

>>65
汲み取り系君はビット順とバイト順が区別できないほど頭がアレなんで。

>>68
お前みたいなスレが荒れる原因を
わざわさ持ち出してくる奴も同じくらい迷惑なんだが

リア房んときCASL&COMETでビットシフトと加減算で除算やったことあるが、
普通はCではコンパイラの仕事だろ。

ダンゴさんよっぽど悔しいんだな。

>>74
くやしいのうｗｗｗくやしいのうｗｗｗ

こうですかわかりません＞＜

>>74-75
vipでやれカス共

>>75
ところで、モトローラのマイコンの件はどうなりましたか？

ム板でも特筆すべき勢いのスレ

>>77
あの会社の収益は組み込みPPCが大半だと思ってたよ

で、R8Cとどっちが売れてるの？

だいぶ前にフリースケールに売ったけどな。

> 大半
だからマジョリティしか発言権無いのかと。

一々単語に噛み付くなようぜぇ

>>80
売ったんじゃなくてスピンアウトだろ
どっちかというと分社化

MacのIntel移行は痛かったようだな

ダンゴさんは前スレから勝ちっぱなしだな

なんでそこでR8Cなんだろう？

すっかり雑談スレだな。ダンゴの自演が面白いけど。
モトローラは通信事業の収益の方が大きかったから辞めたがってた。
アポは五月蝿いくせに数捌かない客だったし。
アポが消えたら、厄払いが済んだかのように、各ゲーム機が一斉にPPC系になって
フリスケとIBM大勝利って感じ。
>>63
別にダンゴスレじゃないから、ココで組込みの話題でもオッケー。
最適化関係ならね。

>>86
は？
Freescaleはゲーム3機種に絡んでないよ。Wiiのは750CLカスタムだし。

Appleこそ脱PPC以降米国市場で1000ドル以上のPCの売上でダントツトップになったり
大躍進じゃないか


でもclassic見捨てるなﾎﾞｹﾞ

>>87
どーでも良い事にいちいち噛み付くなよ。ウゼェ。

>>87
最適化された結果消えたんだから文句言うな

ダンゴ的にアップルはマイノリティじゃないの？
PPCマックのプログラムなんて、爺の野良仕事みたいなもんだと思うけど。

お前ら、今日もム板最速スレ伝説を築く気か。
ダンゴもいい加減からかわれてるって気づけ！
良い天気なんだから、外に出て体動かせ。ビタミンDでも補給しろ！

>>87
で、モトローラのマイコンはどうなんだ？
市場規模とかｗ

>>92
まあウンコじゃね？
ハードの売上とそれに群がるソフト市場、ともにIntelが圧倒的に首位なのは言うまでもないし。

>91
たまのフレーミングが終われば過疎スレに戻るんだから、いまはこのイベントを楽しめ

>87
> Freescaleはゲーム3機種に絡んでないよ。Wiiのは750CLカスタムだし。
言いたいことは否定しないが、CodeWarrior を供給してる関係で、"ゲーム開発に絡んでいる" という言い方は出来る。

つうか、前スレ831 にアンカー付けてくれないかな。
824には同意なんだが。

ダンゴさんが順位で市場規模を語り始めたぞ。

そーいやメトロワークスってFreescaleに買われたんだww
しかしCodeWarriorねぇ・・・

Wii向けならまだ使ってるとこあんのかね？
PS3はSCE謹製のSDKがあるし360はもちろんVisualStudioだし。

むしろIDEとしてはMSVSとEclipseに蹴散らされてるのがCWの現状

団子って組み込み屋にクビでも切られた？
ツボをつく書き込みがあった？

団子はしばしば発狂してるけどトリガが知りたいな

CodeWarriorのIDE部分がEclipseに移行するという発表は先月だったな。
なかなかの蹴散らされっぷりだなｗ

GPL関係でもFUDを書き飛ばしていたよな団子は。

「甘味所 THE 団子」ってスレだな。ほぼ雑談
店主を完全に拘束しといてくれ、頼んだよ

>>99
要するに独自IDEを維持できないほどにヤバいんだよ。
地味にMac用C/C++として独占的な需要あったのにXcodeに完全に食われたしね。

フリースケールにとってIDE部分はお荷物だったからな。

>>98
低リソースでやりくりの文化が生理的に嫌いなだけよ
さらに組み込みのローカルルールを持ち込んで吠える奴が嫌い。


ま、Sunのみたいにいちいちアラインメント例外吐くCPUも嫌いだが
（下位ビットを無視してでもメモリアクセスの方が好き）
まあどうでもいいこと

ARMやSHの変態プロセッサのことか

変態といえばPICだろ。

ローカルルールｗ
ソフトウエア市場規模TOP以外はローカルなのか。

壊れたラジオ全開だな
要するにボクちゃん以外は
ローカルなんだよ

さすが自称社長の息子ｗｗｗ

[1] 授業単元： Cプログラミング基礎
[2] 問題文(含コード&リンク)：
キーボードから4桁の10進数の入力を2回受付ける．
但し，4桁の各位の数は必ず互いに異なるものが入力されるとする．
A：二つの数字を同じ位ごとに比較した時，何ヶ所の位について一致しているかを表す．
B：二つの数字を異なる位同士で比較した時，一致している組み合わせの数を表す．
AとBの数値を最後に表示させる。
[3] 環境
　[3.1] OS：Windows
　[3.2] コンパイラ名とバージョン：borland c++ 5.5
　[3.3] 言語：C
[4] 期限： 今日中でお願いします。

[1] 授業単元： Cプログラミング基礎
[2] 問題文(含コード&リンク)：
キーボードから4桁の10進数の入力を2回受付ける．
但し，4桁の各位の数は必ず互いに異なるものが入力されるとする．
A：二つの数字を同じ位ごとに比較した時，何ヶ所の位について一致しているかを表す．
B：二つの数字を異なる位同士で比較した時，一致している組み合わせの数を表す．
AとBの数値を最後に表示させる。
[3] 環境
　[3.1] OS：Windows
　[3.2] コンパイラ名とバージョン：borland c++ 5.5
　[3.3] 言語：C
[4] 期限： 今日中でお願いします。

> さすが自称社長の息子ｗｗｗ

え？ダンゴってそんな面白設定あったんだ。
なんでPGなんてやってんの？マゾ？

ひんと:「自称」社長

やべえ。ツボった（ｗ
さすがに、それは誹謗中傷すぎるだろ。
ダンゴ、早く否定してくれ。笑い死ぬ。

社長って言葉に過剰に反応する奴は、大会社のサラリーマンなのかな？
その辺の八百屋のおっちゃんだって社長だぞ。定食屋のおっさんも社長だよ。
俺の小学校なんて、同じクラスの1/3くらいは社長の息子だったぞ。

なんだっけな、前に、俺チャンは社長の息子で
帝王学ばかり学んでたので、おまえらリーマンのことなんて
知るかボケみたいな発狂をしてた
細かい言い回しは違うだろうけど

こういうのを見てると、団子の技術は刃物としか思えん

他にもゲームの開発してた自慢なんて面白発言もあったかな

なんだと！おれもゲーム開発してたわ

いや、他人に一々「私は社長の息子です」なんていってたら滑稽だろ（ｗ
まあ、こっちは別に下賎よばわりされても結構だが（ｗ
みんなドラえもんとか思い出しちゃうよ。「スネ夫か！」って（ｗ

「社長の息子」なんて社会的地位にトラウマある人間以外には意味無い単語だよな。
今の自分の仕事に社会的な意味をみいだせてないんじゃないの？
組込みの人は、社会的に説得力のある仕事が多いから、
組込み＝爺とかマイノリティってレッテル貼って自我を保ってるように思える。

そんなの気にしなくて良いのに。誰もダンゴを下賎だとか思ってないって。
面白キャラだとは思うけど。

なんていうか学生ポイんだよねー
就労経験はあるんだろうけど（バイトとか）、職場の人を見ながら小学生の妄想
「皆ボクチンの考えどおり動けばギガイオナズンなのに」って感じで

ん、学生を馬鹿にしてる訳じゃないけど、なんか一人よがりって意味で

アプリ開発に古い組込み屋が混ざるとウゼーのは同意。
だけど、組込みでアプリ屋の戯言ホザク奴もアホだろ。
自分の領分と異なる世界なら、黙って学んでけば良いだけで。
PICで開発やってるのに除算連発して「コンパイラを信じろ」なんて言ってたら基地外だよ。
同様に、アプリ開発でいまさら除算をいちいちシフトに直してたら、そんなカスはクビだろ。

いい加減いがみ合うなって。

団子のよくないところは
技術があれば何をしてもいいんだって所なんだよ
わざわざ自作PCみたいなところで
素人相手に技術自慢というか
技術をふりかざしたイジメをしてみたり

せっかく愛嬌もあるし面白キャラなんだから
もう少しなんとかならんものか

本当に学生だったり
もっと飛び抜けてればそれもありだと思うけど

いや、あれば何してもいいよ
あればね

>>122
ム板でそれが通用すると思ってるあたりが痛いんだよな。
まあ、ココはイイ隔離スレになってるよ。
出来れば、社長の息子はずっとここに閉じ込めといてくれ。

>>121
組込みでアプリ屋の戯言ホザク奴とかこの場に存在しない人を持ち出されても困る

まぁ、アプリ屋とか組み込み屋とか言ってないで、両方やるといいんじゃね？

団子って、やねうらおに性格ちょっと似てる気がする。

8080とか6800まで戻れば、それほど違いなんか無かったわけだし。

>>125
つ鏡

>>125
小規模開発でいろいろ気を使うのは事実だし、
それをマイノリティとか爺の仕事とかいってるアホがいるじゃん。

>>125おまえダンゴか？ダンゴが言ってんだろ。

大規模な数値演算も組み込みも限りあるリソースを最大限活用するために最適化する点は共通だと思うんだな。

最適化自体が不要って言ってる人は居ないと思う。

ダンゴはそれを超えてソフトが不要って言ってたしな。

ペンション経営ばかにすんなよ
プンプン


つか、ちなみに俺いまアマグラミンガーで本職営業だけど
職業マが負け犬って自覚はあるのか。良いことだ

どこの大手SIerでもコンサル＞SE・PGだもんな。

客に仕様を提案したり、自分たちで作ったソフトを売り込む人間は偉いんだよ。
与えられたハードと仕様の通りにソフトを作る人間はただの駒でしかない。
本質的な話、組み込みには負け組しかいないってことな。

>>132
世の中トレードオフと言うものがあって、全ての項目を良く
するなんてできない事も多い。

例えばコンパイラオプションで速度優先とかサイズ優先の
最適化とかあるだろ。

最適化によって速度もサイズも良くなる場合はいいけど、
背反する場合もあるからな。

それはファーム屋だろ。
組み込み屋って回路図引くところから、つか、デバイスの選定からやるもんだぜ。

しかし、今回は思った通り過ぎてつまらないな・・・

アホか。
勝ち組とか駒とか負け組みとか偉いとか、アホくさい発言すんなよ恥ずかしい。
兼業農家と専業農家はどっちは偉いかとか、近海漁業は遠洋漁業に比べて偉いとか
イチイチ職業や役職にランク付けして、自分の地位を確認してんのか？
寂しい奴だな。

よっぽど自分の社会的地位が高いってことになってないと不安なんだな・・・。
ペンション屋の息子か・・・。別に悪かないが、他人様の職業バカに出来るほどかぁ？

俺は会社の金で高価なロジアナ使いたい放題だから、組込みが自分に向いてるって
思ってるけど、自分が負け組みなんて考えたこと無かった。
偉いってなに？定量的に言ってほしい。

幸福感の多様性が認められない価値観の人が、管理職を技術職より偉いってよく言うけど。そんな感じ？
それとも、生涯年俸の話？
もしかして、社長＞社員って価値観？

おまいら釣られ過ぎ

だ
ん
ごは転職を二度ほどしてなかったか？なぜペンション屋の息子などと主張するの？

>>100
ｋｗｓｋ

>>137
最近は論理層と物理層で分ける所も多いよな。ソフトとハードって呼んでだけで。
FPGAやらCPLDのソースも普通に使うし。ターゲット用のデバドラをCで組む事もあるし。

もちろん
社員(株主)＞社長(従業員筆頭)だな。

ちなみに俺は某生命保険相互会社の【社員】でもあるが

>>144
団子専用スレで団子に理解できない話を振って脱線させるのはどうかと

アマグラミンガーってなに？初めて聞いた。
ようするに、職業では組んでないって事？アマグラマーみたいな造語？
別に、このスレとしてプロかどうかなんてどうでも良い事だと思うんだけど。
別に学生でも社会人でも職業でやってても趣味でやってても良いと思うよ。

ただ、俺は職業プログラマーが負け犬とか思わないけどな。
自分が職業プログラマやってて自虐ギャグでやってるんなら構わないけど、
そうじゃないなら、他人の職業を貶めるのは貧しい発想だし、傲慢なアホウのする事だよ。

なんか、ダンゴの貧しい人間性を暴くスレになって来たな。

んなもん自作板の過去ログ漁れば腐るほど出てくるし

団子は刃物を持っちゃった無敵君なんだよ

これでもまだ団子と会話が成り立つと思ってる?
残念だけどまともな対処はできないと思うよ

さて想定通り荒らしに占拠されたのでスレの流れ戻すか

【問】
uint32型の整数nが2のべき乗もしくは0ならtrue,それ以外ならfalseを返す関数を作れ。

＃しかし簡単すぎるなこれ。

みんな、釣られるなお。

やべえ。つっこみてぇ。鏡って概念もってないんだな。

いや〜。俺、組込み屋だからわかんねーや（ｗ

俺はペンション屋の息子だからわからん。しかし、社長の息子でもあり、保険屋の社員でもある。

このスレは皆でうまいことを言い合うスレですかｗ

もうこのスレ駄目だな
目糞と鼻糞が罵り合ってる

>>151
保険屋の宿題か？自分で考えろよ、それ位。

>>152
釣れた結果がム板最速スレじゃん

正解は、「整数nが2のべき乗もしくは0ならtrue,それ以外ならfalseを返す処理」
なんざありふれてるのでライブラリを検索する。
わざわざ車輪の再発明する必要はない。

なんだ
相互会社における【社員】の意味も知らないのか

やめろよ、夜なのに爆笑してしまっただろ

>>160
え？
こんなものまでライブラリ化するの？

多倍長でもない整数の足し算や引き算を関数にするようなもんだな

正解はコンパイラを信じてループをまわす、だろ。後は最適化のスイッチを探す。コレよ。

おまえら、明日も仕事なんだから、ほどほどにしとけよ。

32個のcaseでいいんじゃね？

switch (n) {
case 0:
case 0x00000001: case 0x00000002: case 0x00000004: case 0x00000008: case 0x00000010: case 0x00000020: case 0x00000040: case 0x00000080:
case 0x00000100: case 0x00000200: case 0x00000400: case 0x00000800: case 0x00001000: case 0x00002000: case 0x00004000: case 0x00008000:
case 0x00010000: case 0x00020000: case 0x00040000: case 0x00080000: case 0x00100000: case 0x00200000: case 0x00400000: case 0x00800000:
case 0x01000000: case 0x02000000: case 0x04000000: case 0x08000000: case 0x10000000: case 0x20000000: case 0x40000000: case 0x80000000:
　　return true;
default:
　　return false;
}

（￣ー￣）

それはひょっとして
ギャグで言ってるのか？

>>167

ギャグでいってるのか？
あと、関数とかいってるクズはどうしようもないな
そのまま氏んでくれ

33個だった・・・

配列引いても良いと思うけどな。
まあ、組込み屋的発想で申し訳ないが。

やべー、おれダンゴとかぶってるｗｗｗ

どうみてもみんなダンゴをからかってるだけなんだが。

>>170
関数っていってるのってダンゴさまだけだぞ！あやまれ！

4億-33個のcaseでいいだろ

>>155
言い方が聖書の一説っぽいな。

正解は、職業プログラマ(特に組込み)は負け組みなので、みんな提案型になる。

↓SystemCで書いちゃったというネタきぼう

もう、命令追加だな。コレは。

じゃあ、ここは勝ち組団子さんのスレにして
プログラマ組は次スレに移動しましょう

>>172
どんな配列だよｗ
一瞬想像しちゃっただろ。

>>181
ペンション屋の息子スレに移動でいいんじゃね？

ダンゴに対するみんなの回答が滅茶苦茶おもしろいんだが。
このスレの面白さは、プログラマにしかわからんだろうな。

マジレスしとくと>>151に対する良回答は
「発明」できなくても恥じることはないような式を使うことになる。
答えつーか元ネタを知ってる連中は今頃アイタタタ・・・と思ってるだろう。
つか俺俺

ついでに言うとスレチ。

まあ欲しいのは真偽値だけなんで
ビット配列にすればたった512MBですむな。

みんなが、引っかからずにボケに徹するところが面白いんだけどね。

あやまれ！全力で釣られている俺にあやまれ！！！

全力で釣られた人は2のべき乗となる32通りを全て2進数で書いてみると
ある法則に気付くだろう。

未だにこのスレに張り付いている奴って
よっぽどダンゴ先生が気になっているんだなｗ

単純に面白い見世物だからだよ。

>>188
何言ってんだこいつ？ダンゴ先生がそんなつまんない回答するわけないだろ。
すっげー最適化スレにふさわしい目から鱗の超回答に決まってんだろ！偽者！

> アマグラミンガー に一致する情報は見つかりませんでした。

この辺の単語に回答が隠れてると思うな。俺は。
google先生も知らない単語だし、こいつは怪しいぜ。

今日だけで200レス消化ってどんなだよ。

前スレのあんな状況でビットの入れ替えアルゴリズムの質問とか、すっげえジャストタイミングでキタよな

あの質問自体は、はあ？って感じでどうてもよかったんだけどな〜。その後の展開が笑えた。

>>44だけじゃなくて前スレにもビット演算あったのか
へぇ

糞スレage

で、ダンゴ先生、((n-1) & n)==0 あたりがなんだって？

それは、今のこのスレの流れ的に不正解。
ここでは、どんなボケでダンゴをからかうかでみんな足並みそろえてる。

44も含めてがいしゅつネタもいいところ

>>199
ダンゴ先生に失礼だな、君は！！
何言ってんだよ。ダンゴ先生がこんな常識的なコードで満足しているわけないだろ！！
あのダンゴ先生だぜ！！俺達が想像もできないような方法をあと一時間もしないうちに書いてくれるはずだ！！
そうじゃなかったらダンゴ先生のことだから恥ずかしくて二度とム板に来れるわけないだろうが！！

ささ、先生どうぞ↓

このインターネットは自分がダンゴ先生よりマシなことを実感出来るな

実はダンゴ先生褒め○○しカキコを見るたびに和む

直後にダンゴがムキになって
あぼ〜んを主張するのを見ると顔がにやけてしまわないか？
　>>203

組み込み(笑)もトイレ掃除のおばちゃん並みには必要な仕事だからまあ頑張れや

組み込み屋にコテンパンにのされたことがあるのか
想像だけど団子が悪いだろ！

現在進行形。
身から出た錆。
懲りない奴。

>>205
さて、残り三十分ってところか！！
ダンゴ先生、>>206とか>>207とか見返すような鮮烈な最適化コードをよろしくお願いしますよ！！

期待age

簡単すぎるって出題時に断っておいたのに
あるわけねーだろ文盲、カス、インキンタムシ

>>210
あなたは偽物ですね、わかります。
ダンゴ先生ならちゃんと書けますから。書けないわけがありませんから。
ダンゴ先生を侮辱する偽物は失せろよ！！

ささ、ダンゴ先生、どうぞどうぞ↓

レス勢いに釣られて1からレス読んでみたら
テラおっさん臭いクソスレでﾜﾛﾀ

逆に、本職PGが営業なんざにPGスキル負けたらどうしようもないだろ

>>213
だから、偽物はとっととしっぽ巻いてママのおっぱいでも吸いに行きなって。
ダンゴ先生の実力に嫉妬すんなよ、凡人が。

その組み込み屋が作ったHDDやキーボードやマウスを使ってるなんてことは、ないですよねダンゴ先生。

トイレ掃除ののおばちゃん程度には感謝してるよ。

キーボード・・・たしかにPFUなんてソフト屋としちゃあれだな
HHKBは愛用してるけど。

肉屋を賎業とののしる奴がもりもり牛丼をかっ食らう。
馬鹿とはそういうもんだ。

団子先生、まさか家電使ってませんよね？

ダンゴ先生まさか、車や電車や飛行機は利用しませんよね？

トイレ掃除のおばちゃん程度には感謝してるよ

でも金払ってサービス受けてるんだからそれ以上の感情などないな

はい、テープレコーダ入りましたー

俺が言うトイレのおばちゃん程度ってのは褒め言葉だと思えよ。

外食行ってトイレが汚かったらその店もう二度と行きたくないだろ？
ようするに店の本質が問われるわけ。

だから誇りに思って便器磨くがごとく働けよ。

>>222
で、お前は一体何ができんの？

団子脳は幸せ回路全開ですネ

だんご先生にとって世の中の人は二種類
１、トイレ掃除のおばちゃん程度の人
２、俺様

こんな社長の息子っぷり全開じゃ
まともな営業もできないだろうよ

不思議なのはトイレ掃除のおばちゃんたちに
「ボク様のこと誉めて誉めてー」って
わざわざ書き込みしに来ることなんだよ

しかも一部から来るなって言われてるのにｗｗｗ

>>227
しかし、ダンゴ先生の能力不足でトイレ掃除のおばちゃんも誉めようもないｗｗｗ
チャンスくれてやったのに、結局無能を曝け出して終わりか……

ご愁傷様。

便所の落書きでリアルでの身の振り方推し量れると思ってる奴なんなの
ひろゆきの言うところの「掲示板を使うのは難しい」人の多いインターネットですね




君らに謝らないといけないことがある。
我が家も投資ファンドにわずかながらも協力して原油高の高騰に貢献してます。

>>229
で？

パズーの中の人は
「僕は海賊にはならないよ」って言ったけど最近では

「俺は海賊王になる」って言ってるだろ
簡単に人を信用してはいけない。

それすら遠い過去の様な気がする

>>231
だまれ和スィーツ(笑)

団子ちゃんも最近スレてきたね

自分のページにソニー的なアドレスから
アクセスがあっただけで
ボクのプログラムがソニーから注目されてる！
ＰＳ３のＳＤＫにのっちゃうかも！
みたいなことを喜気として２ｃｈに書き込んじゃう
ピュアな心はどこにいっちゃったの？

あいつは言うことはまともで突っ込みどころはほとんどないんだが
その言い方を気に入らないかつ粘着な人がいるので見ていてもったいなく思う

社長の息子だ

リアルはさぞかし立派なお方なのだろう。
しかし、ブラウザ閉じればだんごの事なんてどうでもよくなるわけだ。

>>229
「家ではおとなしくて家の仕事もよく手伝ってくれるイイコなんですよ」
こうですね、よくある話です。

>>234
悪いが一切無いよ。
でもゲトキパさん方が来るときのGoogleのキーワード見たら笑えるんだよマジで。
最近はFlashに飛ばすトラップ仕掛けてるけどね。

関係ないコードだけど別のサイトで学生んときに暇つぶしに作った某DLL公開してて、
ソースよこせって言ってきた業者に丸ごと売りつけたのならある。
ちなみに実名でやってるサイトだから詳細は言わん。

そそ、リアルGKさんなんだけど
ホントならゲハ板にfusianasan付きでカキコさせるトラップでも用意したいんだけど
cookieが必要だからブラウザで2chにカキコしたことある奴にしか通用しないし。

つーか、用心深いのかJavaScript無効にしてるケースが多い。

2chにおける団子としての存在が恥ずかしいという自覚はあるのか。

>>241
つい思いつきで、○るみさんのソフトのコミットにこっちの名前つかった。
名前が載ればそれでいいと思った。

今は反省していない。

またボク凄い誉めて誉めてーカキコか

そのネタいつまで使うつもりだよｗ
へる○さんも迷惑じゃね？

２ｃｈとかへる○さんとか使わないで
自分のｂｌｏｇでやれｗ

そのへるたんの同僚が社内ブログで俺が思いつきでム板に書いたレス
引用してたりするしそういう文化の会社だってあるんでね？

意図しないポストの開陳ってまずくねえ･･･悪さ自慢？

このスレ機能しすぎｗ

あのぉすみません
任意に子ウィンドウを破壊するには
どうすればいいでしょうか

ハンマーでモニターを全力で叩き割れば良いと思うよ。

任意に子ウィンドウを破壊するウイルスの作成だな。

俺の脳内OSとAPIならこれでいけるぜ。

do(window, "子ウィンドウを破壊");

いや重いソフトがあって
その子ウィンドウがＣＰＵ使用率が高くて

なんだ、問題はCPUの方か、
それならPC本体に対戦車ミサイルを撃ち込めばOK

普通にコンセント抜けばいいじゃん。

子ウィンドウが悪いんじゃない！　その親を破壊しろ！

対戦車ミサイルって誘導のためコンピュータを内蔵してるんだな
どういうプロセッサ使ってるんだろ

それWin32なの？

ウインドウタイトルかクラス名がユニークで一意に決まるならFindWindowでウインドウハンドル拾って、

さらにPostMessageで、
あとはわかるな？

そもそも消せないのか？
それ以前にそのウインドウ消しても問題ないのか？
つかソフト名教えろカス

つーか、どう見てもスレ違いのネタに喰い付くなよ。悪食だなぁ、団子は。

> つーか、どう見てもスレ違いのネタに喰い付くなよ。

え？スレ違いじゃないレスどれだけあったっけ？
このスレ

>>255
50MHzの8085とかじゃね？

>>258
だから、少しでも軌道修正しろってこった。

>>255
> 対戦車ミサイルって誘導のためコンピュータを内蔵してるんだな

ミサイル系は知らないけど、戦闘機のアビオニクスは
ミニコン(IBMの奴だったと思う) -> z8000 -> mips -> 今どこだかしらん
ってな, 発展をしたってなことを聞いた覚えがある

>>244
ダンゴさんスゴス

ちなみにここだけどな
p://labs.cybozu.co.jp/blog/takesako/


ちなみに引用レス中のコードはミスってたんでトラックバックしておいたんだが。

なんでそこで、ミサイルの中でも一番誘導装置がショボい対戦車ミサイルが
出てくるんだ。
対戦車ミサイルの多くは有線式の誘導方式で、射手がラジコンみたいに
操縦するんだよ。

ジャベリン知らない子が来た

有線だとセキュリティも安全だよな

むしろ射手がミサイル持って突っ込めばいいじゃん

こういうの防げるもんね
ttp://jp.youtube.com/watch?v=Z22x4JzYVsQ

防げるというか、射手がミサイル持って転ぶのは防げないというか・・・

スレもミサイルも軌道修正し辛そうだな

ミサイル持って転んでる奴がいるからな

スレタイの「C++」の文字も読めずに組み込みの話で荒らす奴がいるからだろ。

と、スレタイの「C」の文字が読めないやつが言っております。

非組み込みでもCは当たり前に使うが
C++で組み込みは絶望的に頻度低いな

前スレから見てるが「Cは組み込み専用だろ」なんていうのは思い上がりだな。
ミッションクリティカルなところで使われてるのが枯れたCPUだけなんてこともない。
俺は水力発電向けでia64 HP-UXターゲット、Cで組まれたコードの保守なんて仕事もこなした。
むしろ多数決型冗長系組めるのはエンプラ用に設計されたアーキでこそのもの。

LockStepですね。わかります。

私の周辺のプロジェクトでCが使われている理由:
・従来のコードがCで、C++にする積極的な理由がないから
・客先が(理由は兎も角)C++は使うなと指示してきたから
・作業者にスキルがないから
・管理者にスキルがないから

で、最近真面目にvtune使い始めたんだけど、流石に便利だな。
これでEclipseじゃなければもっといいんだが。
むぅ、これでもまだスレ違いか。

やねう企画代表者やねうらお（本名・磯崎元洋）が
・ソフトウェアの不正コピーを行っていた
・労働契約上の違反をしていた
・他は不正コピーしていないことを証明しようとしてエロゲーのパッケージを発見し、
　写真に撮ってアップロードしようとした。
http://d.hatena.ne.jp/pmoky/19000106
やねう企画の裏側（競馬の詐欺ソフトの製作現場）
http://d.hatena.ne.jp/pmoky/20060510
http://d.hatena.ne.jp/pmoky/20060511
http://d.hatena.ne.jp/pmoky/20060512
有限会社やねう企画（所在地・大阪府八尾市末広町２−１−２）が計画倒産
http://www.sia.go.jp/~osaka/zenso/19.09.pdf

やねうらおプロフィール
性格：友達から「チンピラ」「ヤクザ」と呼ばれている。前世で殺人鬼だった宿業を背負っているという妄想（自覚）あり。
最終学歴：専門学校卒
主な職歴：有限会社センキ（凌辱系アダルトゲームの製作会社）を経て独立、有限会社やねう企画を設立、２００６年に計画倒産
代表作：『夜這いマニア』『盗撮マニア』『お楽しみＣＤシリーズ』『競馬詐欺ソフト』『ＢＭ９８』

やねうらお語録
>「ワシのほうが潔癖やと思うんやけどな。
>絶対に違法コピーのソフトしか使わんし。
>たとえば強盗に入ったときに、ちょっとかわいそうになって
>十万円だけ残してったら、おかしいやろ？
>自分の『強盗する』という意思に対して矛盾やろ？
>だからワシは、一個も買ったソフトを使ったことがない！！」

キチガイ警報

>>279
ダンゴさんはまだキチガってないぞ

で、やねうらおって誰？

C++を日本に紹介した最初の人物

>>278
今世紀最大の正真正銘のキチガイ弓月城太郎にやねうらおは絡まれている。




弓月城太郎は正真正銘のキチガイ

【自作自演】弓月城太郎氏に関するまとめ【神秘体験】
http://d.hatena.ne.jp/yaneurao/20080619

int型の配列に

a[b[x]c[y]]って感じでアクセスしてる奴
もっと効率よくアクセスできんのかね
プンプン

ポインタ使って自前で効率よくアクセスしようと頑張るより、
読みやすいコードを書いてコンパイラの最適化に任せたほうがいいって、
じっちゃんが言ってた。

>>285
じじいのいうことなんてきかねーよぼけ

>>285
じじいたちの世代はコンパイラがバカだから
スピードのためなら読み難くてもトリッキーな
コード書いてたわな

コピーと参照は絶対的な差がある

>>287 言ってることと逆じゃねーか

＞a[ b[x] c[y] ]

これコンパイル通るのか

通らねーよボケ

見て和姦ねーのかボケ

でももしb[x]が関数だったら？

通らなねーよボケ

普通にコンパイルできるけど...

#define c +d

int a[10];
int b[10];
int d[10];
int x;
int y;

int z = a[b[x] c[y]];

普通じゃないね。

多次元配列をクラスじゃなくてコンパイラ内蔵にして欲しくならない？

for(y) { for(x){
a[x+y*size1] = ...;
}}

みたいなことやってもコンパイラはちゃんとyの項を外に出して最適化してくれるのは分かってるんだけれど、精神衛生上気持ち悪い。

それにa(x, y)みたいにアクセスできるクラスがあっても添え字の計算がクラスの奥深くになると外に出せなくなるし。

>>296
ならない
せっかく多次元配列でさえも自分でカスタマイズできるのがC++の便利なところなのにね。言語仕様に含めて自由を放棄するなんてことはできない。

そうだけどさ、コンパイラが解釈しにくくなるじゃん。
yの項を外に出すだけじゃなくて自動ベクトル化とかもやりづらくなるし。

それに二次元配列を言語が持ってても邪魔しないと思う。
必要ならオーバーライドすればいいだけ。

int a[10][10];でだめ？
C99だと要素数に変数使えてますます便利。C99使えないけど。

int a[1024][1024];

あたりでキャッシュライン縛りｱﾋｬﾋｬﾋｬ

おまえらダンゴさんのレスに一ヶ月も無反応とかどういうつもりだよ

最大の賛辞のつもり。

大惨事。

今は自作PCの方が大惨事

ペンションの経営に忙しかったんだよ。

gcc でサイズはとにかく増えてもいいのでインライン展開をさせたいんですが
-O3以上のオプションはなし？

>>306
もっと具体的に。インライン展開したからと言って、必ずしもサイズが増えるわけじゃないよ。
つーか、O2でもstaticな関数は勝手にインライン展開したと思うのだけど。

>>307
関数ポインタを使ったスイッチを多用したソースなんですが
予定してるよりも速度でないのでインライン展開で高速化できれば
と思ったんですが・・・

関数ポインタ経由で呼んでる関数をインライン展開しろと?
またそんな御無体なw

仮想関数経由なら出来るよな

>>309
あ、そういのは無理ですかｗｗ

代わりのチューニングって何かありますかね・・・

速いマシンを買う/買わせる

まずはプロファイリングしてどこで時間食ってるか確認するところから始めては？

そもそもターゲットが何かも書かずに最適かもへったくれも無いだろよ。
エスパー希望なら鼬害だ。

>>313が正解。

ダンゴさんならピシっと答えてくれるところなんだがな。

なんでそこまでして荒らしたいわけ？

お前みたいにほいほい餌やる奴がいるからだろ。

キャッシュについて教えください。

インテルアーキで、Ｃｏｒｅ２とかはキャッシュラインが64バイトだと思います。
例えば、16バイトにアライメントされた配列

float Ａ[10]［1024］ __attribute__(((aligned(16)));
float Ｂ[10]［1024］ __attribute__(((aligned(16)));
float C[10]［1024］ __attribute__(((aligned(16)));

があった場合、

for(i = 0; i < 10; i++){
for(j = 0; j < 1024; j++){
C[i][j] = A[i][j] * B[i][j];
}
}

といった計算では、［i］［0］,[i]［16］,が呼ばれるたびに、
64バイト毎にキャッシュされるのでしょうか？
最近のCPUは数Mのキャッシュがあるので、
最初にA,B,Cのデータを全部キャッシュに送ってしまえばパフォーマンスが
かなりあがるような気がするのですが。

適当に送られるから気にしなくていい

>>319
スレ違い。

>>319
場合による。
プリフェッチというのを調べてみるといい。

>>322
じゃあ、キャッシュのロックも。

>>320
配列のサイズが小さければ、特に気にすることはないと思うのですが、
配列のサイズがキャッシュラインよりも大きい場合、キャッシュライン毎に転送されるというのであれば、DDR系のメモリはデータが送られてくるまでに数百サイクルのレイテンシが
あるので、例えば64バイト単位でしか送られないのであれば、メモリ転送が非常にボトルネックになるのかと思っています。

>>322
プリフェッチも調べてみて、SSEを使ってやってみましたが、結局変わりませんでした。プリフェッチでもサイズが指定できないようで、
どこまでキャッシュされているのかが分かりません。最近のCPUはハードウェアが勝手やるみたいなので、プログラマが考慮しても余り効果がないのかもしれません。

他にスタックの変数はほとんどキャッシュされると思われるので、
関数毎にmemcpyでコピーしてみたところ、PowerPC（Cell PPU）では効果がありましたが、Core2では逆に遅くなってしまいました。
スレ違いみたいですのでこの辺で終わりにします。
void func(){
float a[256];
float b[256];
float c[256];

for(i = 0; i < 10; i++){
for(j = 0; j < 1024; i+=256){
memcpy(a,&A[i][j],256*sizeof(float));
memcpy(b,&B[i][j],256*sizeof(float));
memcpy(c,&C[i][j],256*sizeof(float));
for(k = 0; k < 256 ; k++){
c[k] = a[k] * b[k];
}
memcpy(&C[i][j],c,256*sizeof(float));
}
}
}

キャッシュは魔法ではない。
アセンブリリストを出力させて、（手でやったりツール使ったりして）どの命令でどれだけ
ストールするか調べ、ソースコードをどう変えたらどう代わるのかを比べないと意味がない。

http://perfsuite.ncsa.uiuc.edu/publications/LJ135/t1.html
とか参考になるんじゃないか。

パイプラインの動作を理解すること、実際に計測すること、が重要。
パイプライン解析するツールとかあると理解しやすいんだけど。
フリーのは知らないけど探してみたら？

unsigned hoge;

if(0 == (hoge % 60))
{
　// なになに
}

これを高速化する方法はないですか？

unsigned hoge;
↓
const unsigned hoge;

>>326
無理。

自己解決しました。
bool isHogeZero = (hoge % 60) == 0;
をループの外に追加して
if(isHogeZero)
{
// なになに
}
にしたら1%速くなりました。

0== ((hoge >> 64) & 0x0001)

>>330
その64はどこから出てきた数字なの

64ビットシフトしたら、何もかもなくなるか、何も起きないかのどちらかだな。

ほいさっさ

http://soudan1.biglobe.ne.jp/qa992559.html

32ビット範囲の X / Dなら、R = ((1 << 64) - 1) / D として、
X / D の値は (R * X + (1 << 32)) >> 64となる。

ダメだこりゃ。このスレ腐ってる。

自動焼人 ★　＝　自動保守 ◆KAWORUKOFI　＝　自動保守#K9K?_D[L

名言集　その３
『いつもサボってばかりのキャップがウゼえ』

http://yutori7.2ch.net/test/read.cgi/news4vip/1249830540/　ID:PVAf+dux0　＝　自動焼人 ★
> 71 ：以下、名無しにかわりましてVIPがお送りします [sage] ：2009/08/10(月) 00:58:57.28 ID:PVAf+dux0
> >>69
> 大変って言うか
> 毎日、報告されたのを見て、判断して、処理して、完了報告して、以下ループ。
> ちょっとでもミスすると、普段は作業もしてないキャップさんたちがさんざん文句言ってきて
> その言いわけを考えないと、キャップはく奪されたりアカウント凍結されたりするから
>
> 登録されてから一年以上経って、やっといいたいこと言えるようになってきたよ。



----------------------------------------------
この自動焼人 ★メールマガジンの配信停止をご希望される方は
http://qb5.2ch.net/test/read.cgi/sec2chd/1250169591/
にて自動焼人 ★までご連絡ください

キャッシュに入っているか入っていないかをプログラム側から知ることはできないでしょうか？

知ろうとするとキャッシュが変化するので原理的に無理
というか知る事ができないからキャッシュは高速なんだろ
知る事ができる回路にすると遅くなる

>>337
何のために？

どうせキャッシュにあるデータを優先的にアクセスするためだろ
そんなふざけた事してないで普通に良く使うデータだけ良く使ってればいいんだよ！

>>337
x86ならVTune

近い将来使うから、必要ならキャッシュにリフィルしたい、ということならターゲットにプリフェッチがあるか調べてみたら。

Core 2 Duoとかi7とかのL2キャッシュ4MB〜6MBというのは強烈に
効果があるな

キャッシュにあるか調べて条件分岐なんかする間に、
さっさとアクセスしてキャッシュに入れた方が速そうだけど。
実際どうなん？

銅じゃないよ

>>344
Itanium2の分岐プレディケーションはかなり効果があったみたいだが
悲しいかな全く新しい命令体系なのでx86に取り入れられない
しかも爆熱で設計がまずい

今の所大容量L2キャッシュに分岐予測って組み合わせがベストだろうな

＞キャッシュに入っているか入っていないか

そんなことはどうでもいい。そのデータを使いたいか使いたくないかだ。
使いたいなら事前にprefetch命令を発行しとけばいい

g++でSSEをつかうようにするオプションを教えな

http://www.fan.gr.jp/~ring/doc/gcc_i386_option.html

http://d.hatena.ne.jp/futsu-9/20070513/p1

これもか
あんまし効果ねーな
やっぱりasmでバリバリ書いた方がいいだろ

動画像処理のプログラムなんだけど

inline int hoge(const int* array, const int type){
　 if(type == 1) {
　 　 return *cPtr(array[0], array[2] , array[3], array[5]); //本当の計算は内挿を呼び出す
　 } else if(type == 2) {
　 　 return *cPtr(array[2], array[3] , array[3], array[4]);
　 } else {
　 　 return *cPtr(array[0], array[2] , array[3], array[5]);
　 }
}

という関数があって、1ピクセル毎に呼び出される。
typeは奇数ラインや呼び出しフレームで変わる。

だから、分解して関数ポインタにしてみたけど、速度変わらなかった。
もしかして、関数ポインタを呼び出すのもオーバーヘッド大きい？

関数ポインタがわりと非効率的なのは確実。
関数呼び出し自体にオーバーヘッドあるし分岐予測しにくいし。

どうすればいいかという話になるとそれだけの情報だとなんとも言えんが、
ラインやフレーム単位では処理が固定できるなら、なるべくそこでまとめるべきだろう

typeの分布にCPUの種類によって違う認識可能なパターンに一致するなら分岐が有利かもしれない
typeの分布に連続性があるなら関数テーブルが有利かもしれない
その例のようにtypeとの対応が固定なら分岐しないという手もある
return *cPtr(array[idxtbl[type][0]], array[idxtbl[type][1]] , array[idxtbl[type][2]], array[idxtbl[type][3]]);

関数ポインタだと効率が悪いなら、自己書換えをすれば良い(ぉ

>>352
コードキャッシュ的にも困るだろうな。

返信ありがとうございます。

関数ポインタ使用していた所を決め打ちで関数呼び出し & inlineしてみたんですけど
これまた微妙に…。
720x480の画像を 0.03fpsしか変化しませんでした。

ICCじゃなくて、MSVCでも実験してみます。

>>353
まあ、cPtr関数がどんなサイズでどんな処理をしているかわからんけど、
関数引っ張ってくる位だから、関数ポインタを使って分岐なくしてもそんな変わらん様な気がするな。
見る限り分岐のケースって3個しかないからな。

他の人が言ってることの言い換えだけど、ピクセル単位の分岐を
ライン単位の分岐にしよう。
そして、ループのアンロールをしよう（またはコンパイラがアンロール
できるようなコードを書こう）。

ループのアンロールは分岐予測が効いていればそんなに効果がないだ
ろうと思いがちだが、どっこい実測してみると随分と違う

8回のループをアンロールするだけでも格段に違うぞ

>>357-359さん、ありがとうございます。

ソースうｐしてみます。
http://uproda.2ch-library.com/lib222858.zip.shtml
DLキー : 1

GetFrameが、外部から１フレームずつ呼び出される部分です。
EDI.cpp内のnEDI_8x8が足引っ張ってるんですよ。

多分、for文よりif文のコストがかかってる気がしますが、どうでしょうか。

これ、元のソースが配列をプロパティで保持して、何度も使い回してたり
GetFrameメソッドにベタ打ちしてあって、300行超えてたり…。
俺なりにリファクタリングして、今のコンパイラでビルドしただけで
速度が2倍近く出るようになったという…。

>>360
その関数内の配列CtCi、自動変数だから毎回コピーされてないか?
constつけるかstaticつけるかしたらコピーが抑制される希ガス。

まずはループアンロール

--
if (final > 255) { return 0xFF;
} else if (final < 0) { return 0;
}

return (BYTE) final;
--
このキモチワルイコードを何とかしてくれw

--
inline int FastEDIUpsizer::getFinal(const BYTE p[64], const BYTE n[64][4], const double CtCi[4][4]){
double a[4] = { 0,0,0,0 };
double r[4] = { 0,0,0,0 };

for(int i = 0; i < 4; i++){ for(int k = 0; k < 64; k++){ r[i] += n[k][i] * p[k]; }}
for(int i = 0; i < 4; i++){ for(int j = 0; j < 4; j++){ a[i] += CtCi[i][j] * r[j]; }}

return (int)(p[15] * a[0] + p[26] * a[1] + p[37] * a[2] + p[48] * a[3] + 0.5f);
}
--
後者のループは手でアンロールしてもいいかも。
あー、配列rはdoubleにしたら勿体無いな、整数でいいよ。
つーか、rの制御変数はjに固定しろよ。ややこしい。
それから、0.5fじゃなくて0.5だな。doubleと足す定数はfloatじゃ拙い。
0.5ならどうでもいいけど、0.1と0.1fでは精度が違ってしまう。

>>363
＞このキモチワルイコードを何とかしてくれw
if (final > 255) return 0xff;
if (final < 0) return 0;
return BYTE(final);

＞あー、配列rはdoubleにしたら勿体無いな、整数でいいよ。
＞つーか、rの制御変数はjに固定しろよ。ややこしい。
#if 0 // どっちが早いだろ
int r[4];
for (int j = 0; j < 4; ++j) {
int r = 0;
for (int k = 0; k < 64; ++k) r += n[k][j] * p[k];
r[j] = r;
}
#else
int r[] = {0, 0, 0, 0};
for (int k = 0; k < 64; ++k) {
for (int j = 0; j < 4; ++j) r[j] += n[k][j] * p[k];
}
#endif
double a[4];
for (int i = 0; i < 4; ++i) {
double a = 0;
for (int j = 0; j < 4; ++j) a += CtCi[i][j] * r[j];
a[i] = a;
}

＞後者のループは手でアンロールしてもいいかも。
double a0 = CtCi[0][0] * r[0] + CtCi[0][1] * r[1] + CtCi[0][2] * r[2] + CtCi[0][3] * r[3];
double a1 = CtCi[1][0] * r[0] + CtCi[1][1] * r[1] + CtCi[1][2] * r[2] + CtCi[1][3] * r[3];
double a2 = CtCi[2][0] * r[0] + CtCi[2][1] * r[1] + CtCi[2][2] * r[2] + CtCi[2][3] * r[3];
double a3 = CtCi[3][0] * r[0] + CtCi[3][1] * r[1] + CtCi[3][2] * r[2] + CtCi[3][3] * r[3];
return int(p[15] * a0 + p[26] * a1 + p[37] * a2 + p[48] * a3 + 0.5);
警告出るならr[0]などはdouble(r[0])などに。

うーむ、CtCiは呼び出し先で変更するのか。作りが判り難い。
そういうことなら自動変数でもしょうがないけど、配列の初期化の警告は無視しているのかな?
double CtCi[4][4] = {{1, 0, 0, 0}, {0, 1, 0, 0}, {0, 0, 1, 0}, {0, 0, 0, 1}};
のように二重にしないとダメだし、0.fと1.0fのようにバランス悪い書き方するくらいなら初期化値くらい整数でいいよ。

stepXXのdouble CtCも計算途中はintでいいよな

>>361,366さん、ありがとうございます。
ICC・MSVC共にW3では、何故か警告出ませんでした。
何か意図があるのかと思って放置してました。

>>364さん、ありがとうございます。
前者、後者を試してみました。
iccのRelease Buildでは、デフォルトでループアンロールされるみたいで
iccでは10.93fps 〜　10.92fpsの間で、あまり変化ありませんでした。
msvcでは、手動アンロールで8.43から8.48へ変化しました。

>>363さん、ありがとうございます。修正しました。

>>367さん、ええ。この際、doubleをlongにしてしまおうかと。

何か気になる点があったら教えて欲しいです。

>>360
分岐をループの外に出してみた。コンパイルは通る。
http://www1.axfc.net/uploader/File/so/40327.zip
変更点は TEMPLATE_FALLBACK で検索。

他にも外に出せる条件がある。
でも正直、割合的には小さいと思う。

358 での、ライン単位のループにというのは、ループ中の不変条件を
抽出しやすくという意図もあったのだけれども、面倒になって説明する
のをやめた。

関係ないけど memset() の単位が違う。

unsigned char* c[n];
int count = 0;

if(*c++ == 0xFF) count++;
if(*c++ == 0xFF) count++;
if(*c++ == 0xFF) count++;

のif文を
count += if_ff(*c++);

inline int if_FF(const int c){
　 　return (c + 1) >> 2;
}

に変形してみたけど遅くなった。
キャストで足引っ張ってるのかな。

0xffの時countに64が足されるが等価なのか?

上でも比較の時に汎整数拡張されるだろ
一般的に比較のコストは減算、それに対して加算とシフトになっているので
だが、分岐が無いだけ若干有利か

アセンブリ吐かせて比較した方が早いよ

>>371
すみません、間違えました。

>>372
ヘッダファイルに、inline付け忘れていただけというオチでした。

if文を無くすだけで、それなりになりますね。

検索エンジンてどうしてあんなに速く結果を探せるのですか？
肝となるアルゴリズムを教えてください

Google レベルとなると一筋縄ではいかない。
基本は N-gram と サフィックス・アレイ で検索。

Googleは形態素解析使ってる

＞このキモチワルイコードを何とかしてくれw
ざっくっと考えてみたが・・・益々キモチワルイな orz
※final が32bitの場合
int x = ~(final >> 31);
int y = ((final - 0xFF) >> 31);
return (x & y & final) | (~y & 0xFF);

>>377
こんな感じでいいんじゃね？　キモチワルさでは負けるけどｗ

return(BYTE)((unsigned)final>255?final>255?255:0:final);

377は分岐を無くしてるんだと思うよ

空いた時間にいろいろやってみたけど、あまりいい案は浮かばなかった。

とりあえずテストコード。
ttp://codepad.org/qgKt5Lqu

signedに対する~や>>や&は処理系依存

>>371
普通に間違ってねえか

わり370へのレスだった

intel compilerでSSEを使ったベクトル化をしているのですが
FLOW dependenceというエラーが出て、ベクトル化されません。
ループ前には
#pragma ivdep
#pragma vector always
をつけています
コンパイルオプションは
-ansi_alias -O3
です。
よろしくお願いします

flowは「流れ」、dependenceは「依存」て意味です。
並列化できないコードなのでしょう。

配列の添え字ごとに完全に独立した常微分方程式なので、並列化できるはずなのですが、
依存関係がないことを指示する方法はないのでしょうか？

>>377
なぜ間違えたし。それをするなら
int x = ((255 - final) >> 31) | final;
int y = ~(final >> 31);
return x & y & 255;
でしょう

>>380
シフト演算は意外と遅いので改良案2のように連続させたら負けだと思う

シフトって何で遅いのかね
レイテンシ４だっけ？

>>386
並列化？ベクトル化じゃないの？
どっちにしろ出来るとわかっているなら、
はじめからSSEで書いてみたら？
要素数を2か4で割るだけだから。
GCCだとSIMDをあまり意識しないで書けるけど、
ICCだと組込関数を使わないとだめだな。

>>386
インテルC++コンパイラ9.0発表！
http://pc12.2ch.net/test/read.cgi/tech/1118850896/l50

現象が再現する最小限のコード無しで質問しても、望む答えは得られないと思うけどね。

とっくに規制解除されてた...orz。

>>387
さすがです。速いです。 (ただし、VC2008だと改造の余地有りでした。gccやiccならOKなのかも)

というわけでまとめコードです。
ttp://codepad.org/soXj03pM

ageちゃった。スミマセン＞＜

うーん、Windowsに依存してないコードならすぐ追試するんだけどなぁ。

BYTEをunsigned charにして
時間を計測する__rdtsc()を実装すればいいだけじゃないか
負数が2の補数表現のCPUであればほぼそのまま動く

>>394
THX! 試してみる。
処で、rdtscってナノ秒くらい?

プロセッサ・OSによっておそろしく遅かったりする。
OSでトラップしてエミュしてたり。
まあ、やってみれ。

環境によっては実行の間にコンテキスト切り替えによりコアが変わってしまい
変なカウンタ値が得られてしまうこともあるので、どうしてもそれを避けたかったら
Affinity 指定とかで逃げるのがよい。

iccでの結果 (最適化無し - DebugBuild)

全部範囲内 　 　 　 　 　- オリジナル : 860,274
全部範囲内 　 　 　 　 　- cmov参考値 : 1,352,259
全部範囲内 　 　 　 　 　- レス387(分岐無) : 1,426,005
全部範囲内 　 　 　 　 　- レス387(を改造) : 1,364,436

全部範囲外(+方向) 　 　- オリジナル : 761,985
全部範囲外(+方向) 　 　- cmov参考値 : 1,327,752
全部範囲外(+方向) 　 　- レス387(分岐無) : 1,425,996
全部範囲外(+方向) 　- レス387(を改造) : 1,363,995

全部範囲外(-方向) 　 　- オリジナル : 786,555
全部範囲外(-方向) 　 　- cmov参考値 : 1,327,743
全部範囲外(-方向) 　 　- レス387(分岐無) : 1,425,996
全部範囲外(-方向) 　 　- レス387(を改造) : 1,364,418

全部範囲外(+-交互) 　 　- オリジナル : 774,261
全部範囲外(+-交互) 　 　- cmov参考値 : 1,327,743
全部範囲外(+-交互) 　 　- レス387(分岐無) : 1,426,005
全部範囲外(+-交互) 　 　- レス387(を改造) : 1,364,436

時々外れる(分岐卵ｪ) 　 　- オリジナル : 1,295,001
時々外れる(分岐卵ｪ) 　 　- cmov参考値 : 1,605,672
時々外れる(分岐卵ｪ) 　 　- レス387(分岐無) : 1,426,005
時々外れる(分岐卵ｪ) 　- レス387(を改造) : 1,364,400

かなり外れる(分岐卵ｪ) - オリジナル : 1,236,168
かなり外れる(分岐卵ｪ) - cmov参考値 : 1,613,412
かなり外れる(分岐卵ｪ) - レス387(分岐無) : 1,426,059
かなり外れる(分岐卵ｪ) - レス387(を改造) : 1,364,409

結果Corei7 965 ( on Fedora 12) / gcc -O3
--------------------------------------------------
全部範囲内 - オリジナル : 18711
全部範囲内 - cmov参考値 : 11985
全部範囲内 - レス387(分岐無) : 20967
全部範囲内 - レス387(を改造) : 19800

全部範囲外(+方向) - オリジナル : 11988
全部範囲外(+方向) - cmov参考値 : 14310
全部範囲外(+方向) - レス387(分岐無) : 18762
全部範囲外(+方向) - レス387(を改造) : 20217

全部範囲外(-方向) - オリジナル : 26226
全部範囲外(-方向) - cmov参考値 : 19713
全部範囲外(-方向) - レス387(分岐無) : 27261
全部範囲外(-方向) - レス387(を改造) : 26136

全部範囲外(+-交互) - オリジナル : 25260
全部範囲外(+-交互) - cmov参考値 : 19704
全部範囲外(+-交互) - レス387(分岐無) : 27198
全部範囲外(+-交互) - レス387(を改造) : 26199

時々外れる(分岐予測) - オリジナル : 30450
時々外れる(分岐予測) - cmov参考値 : 23619
時々外れる(分岐予測) - レス387(分岐無) : 27279
時々外れる(分岐予測) - レス387(を改造) : 26217

かなり外れる(分岐予測) - オリジナル : 30639
かなり外れる(分岐予測) - cmov参考値 : 35454
かなり外れる(分岐予測) - レス387(分岐無) : 27270
かなり外れる(分岐予測) - レス387(を改造) : 26172

icc で簡単に書くのが一番か…

iccのテストデータ64Kです。
最適化掛けてreleaseビルドしてみたけど、殆ど変わらなかった。
プロファイルで最適化したら遅くなったり…。

結果Corei7 965 ( on Fedora 12) / icpc -O3
--------------------------------------------------
全部範囲内 - オリジナル : 32816
全部範囲内 - cmov参考値 : 32872
全部範囲内 - レス387(分岐無) : 41032
全部範囲内 - レス387(を改造) : 32848

全部範囲外(+方向) - オリジナル : 24664
全部範囲外(+方向) - cmov参考値 : 15774
全部範囲外(+方向) - レス387(分岐無) : 19692
全部範囲外(+方向) - レス387(を改造) : 15762

全部範囲外(-方向) - オリジナル : 15150
全部範囲外(-方向) - cmov参考値 : 15177
全部範囲外(-方向) - レス387(分岐無) : 18933
全部範囲外(-方向) - レス387(を改造) : 15156

全部範囲外(+-交互) - オリジナル : 11448
全部範囲外(+-交互) - cmov参考値 : 15171
全部範囲外(+-交互) - レス387(分岐無) : 18933
全部範囲外(+-交互) - レス387(を改造) : 15153

時々外れる(分岐予測) - オリジナル : 15138
時々外れる(分岐予測) - cmov参考値 : 15171
時々外れる(分岐予測) - レス387(分岐無) : 18933
時々外れる(分岐予測) - レス387(を改造) : 15153

かなり外れる(分岐予測) - オリジナル : 15249
かなり外れる(分岐予測) - cmov参考値 : 15177
かなり外れる(分岐予測) - レス387(分岐無) : 18933
かなり外れる(分岐予測) - レス387(を改造) : 15762

final = max(final, 0);
final = min(final, 255);
return final;

読みやすさ重視。どうだろ。

　 　 　 　 　 　 　 　 　 MSVC　:　ICC 9
全部範囲内 - オリジナル : 983,151 : 404,208
全部範囲内 - cmov参考値 : 690,516 : 426,708
全部範囲内 - レス387(分岐無) : 747,666 : 431,892
全部範囲内 - レス387(を改造) : 691,830 : 396,126
全部範囲内 - レス402 : 884,844 : 404,226
全部範囲外(+方向) - オリジナル : 688,230 : 404,226
全部範囲外(+方向) - cmov参考値 : 884,835 : 426,771
全部範囲外(+方向) - レス387(分岐無) : 747,819 : 431,334
全部範囲外(+方向) - レス387(を改造) : 691,866 : 396,045
全部範囲外(+方向) - レス402 : 787,851 : 404,226
全部範囲外(-方向) - オリジナル : 983,142 : 404,199
全部範囲外(-方向) - cmov参考値 : 884,844 : 426,735
全部範囲外(-方向) - レス387(分岐無) : 747,765 : 432,594
全部範囲外(-方向) - レス387(を改造) : 691,767 : 396,324
全部範囲外(-方向) - レス402 : 884,844 : 404,271
全部範囲外(+-交互) 　- オリジナル : 835,686 : 404,226
全部範囲外(+-交互) 　- cmov参考値 : 884,835 : 426,717
全部範囲外(+-交互) 　- レス387(分岐無) : 747,819 : 431,604
全部範囲外(+-交互) 　- レス387(を改造) : 691,974 : 396,45
全部範囲外(+-交互) 　- レス402 : 787,779 : 404,235
時々外れる(分岐予測) - オリジナル :　1,394,181 : 404,298
時々外れる(分岐予測) - cmov参考値 :　1,311,543 : 426,096
時々外れる(分岐予測) - レス387(分岐無) :　　747,855 : 431,739
時々外れる(分岐予測) - レス387(を改造) : 691,947 : 396,054
時々外れる(分岐予測) - レス402 :　1,436,544 : 404,253
かなり外れる(分岐予測) - オリジナル :　1,334,898 : 404,208
かなり外れる(分岐予測) - cmov参考値 :　2,007,639 : 426,105
かなり外れる(分岐予測) - レス387(分岐無) :　　498,465 : 431,883
かなり外れる(分岐予測) - レス387(を改造) :　　461,142 : 396,459
かなり外れる(分岐予測) - レス402 :　　864,846 : 404,226

ICC 9 じゃなくて 11だた。

?ってifよりもcmovの最適化が期待できるのかな？

テストコードがいろいろ間違っていたので、修正しました。
LinuxのGCCにも対応しました。ICCは分かりません。

ttp://codepad.org/4YzZa9oq

>>405
書き方次第でcmovになるか分岐になるかだと思いますよ。

配列の数が4の倍数じゃなくてもSSEを使える、合計を求めるコードをおしえてちょ

>>407
そんなもん知らなくても大丈夫。コンパイラがまともなら、勝手にループを3つに分けることさえしてくれるから。

配列がアライメントされていれば、int(n/4)回のループとmod(n/4)回のループの二つだろ。

Duff's deviceの考え方は色々応用利くと思うんだ

・ギー太抱き枕
・エリザベス抱き枕
・むったん抱き枕
　……とか作ったら売れるんだろうか。

ぎゃあ誤爆ｗ

> 411
売れるか分からんけど,
使い込めば最適化されると思うよ

inline X func(・・・)
{
・・・
return X(v);
}

これって
値を捨ててしまう場合に最後のコンストラクタ、コピーコンストラクタなどカットしてくれますかね？

Xの中身次第で意味論が変わるのに削除されたら困るだろうに

では組み込み型や参照、ポインタだとどうなんでしょうか？

RVOで調べろ

コンストラクタ次第では、その関数の全てが消えてなくなるかもしれない。
要は、情報が少なすぎ。

そもそも値を捨てなくてもコピーコンストラクタカットされたりしない？

C99のinline関数にできてC++のinline関数にできない最適化ってどんなのがあるの？

>>420 は http://hibari.2ch.net/test/read.cgi/tech/1302588918/778 より

呼び出し規約をfastcallにする

>>422
それ C++ でもできるんじゃないの？

>>423
inlineに対する最適化ならNo

>>424 なんで？

C99 なら何回も同じ関数を呼ぶ箇所があったら、
その箇所と extern 付きの inline 関数定義を同じ翻訳単位に置いて
他の場所は別の翻訳単位に置くことで、
何回も呼ばれるところだけインライン展開し
他の場所は普通に外部定義された関数を呼ぶことができる
こうすることで、コードサイズの増加を押さえながら
必要な箇所だけインライン展開できる
C++ では同じことはできない

最適化は難しい話。そして、苦労の割には報われない。
もう、コンピュータの性能が上がったからでごまかしたら？


もちろん、数値計算の分野ではコンピュータの性能が上がったら
より大きな問題を解くという循環で、きりがないのはわかっているが。


でも、そういう問題はパソコンで解いちゃだめなの。
スーパーコンピュータで解け！

>>426
（元のスレからはじまって）最後に出てきたこれが、言語機能としての
違いを利用した唯一まともな答えだね。

ありがとう。

ただ、分けた翻訳単位でインライン展開されないとも限らないし
別の翻訳単位でインライン展開されないとも限らないし、翻訳単位を
分けることのデメリットと秤にかけないといけないなど、実用性を考えると
甚だ疑問なんだけれども。

inline展開されるかどうかは状況次第なんだから、それについて気にしてもどうにもならないのはc++も一緒じゃない？
必要なところだけinline展開される(かもしれない)メリットと、翻訳単位が分かれることのデメリットのトレードオフになるかと。

> 別の翻訳単位でインライン展開されないとも限らないし

翻訳単位ごとにコンパイルしてオブジェクトファイル作って
リンクする手法を取ってる間はそんなことは起こらないんじゃないかなぁ

>>430
それはそうだが、すでにリンク時にインライン展開する実装だってあるんだぜ。

VC++のLTCG、GCCのLTO

iccのipo

最適化は極論すればコンパイラが頑張ればなんでもあり。
言語が最適化のヒントを詳しく出せるようになってても時代とともに無効になる場合もある。
逆に言えば無効になるまで他言語より優れてれば良い。Fortranのように。

>>426にはどうも納得いかないな
C++でもヘッダでinline関数を定義すれば少なくともOBJファイル単位では
inlineになったりならなかったりするでしょ
コンパイラの裁量に任せるならヘッダでstatic関数を定義して
PGOでもかけときゃ善きにはからってくれるし
そもそもC++ではtemplateを頻繁に使うのでヘッダに載ってる
コードの量がC99より多いのでリンク前の最適化の機会も多いはず
C99の方がいいバイナリ吐くとか眉唾だよね

>>435
OBJファイルとはなんぞや？

狭義のコンパイルの結果では？
リンカが扱う単位。

template の特殊化で細かいチューニングもできるしなあ。

inlineの使い方を誤解してるような

C99のinlineはgccの static inline/extern inline/inline が
標準に制限付きで取り込まれたんだと解釈してたわ。
だから >>426 みたいな使い方は当たり前だと思ってたけど
そうでもないんだね。

C++は出力されるバイナリサイズに対しては富豪的立場だから
バイナリサイズを押さえながら最適化なんてコンセプトが
理解されるはずも無い

>>441
> C++は出力されるバイナリサイズに対しては富豪的立場だから

そんなことないよ。
C++ のターゲットには ROM のサイズがごく小さい組み込み機器も入ってる。

EC++のことを言っているならC++とは別物と考えろ

EC++なんて、無かったことにするに決まってんだろ。

>>441
ハッアァァアァァァァァァアァァアァアァアアァァァァ？？？？？？？？？？？？
ゴミが散らかってる
死ね

↓どう思う? プロの意見を求む。

> 750 名前：774ワット発電中さん[sage] 投稿日：2011/08/08(月) 23:45:00.43 ID:X717yz94 [4/4]
> >>739
> 所詮はその程度の知識よのぅ。まんまと釣り針にかかるとは。
>
> もう何年もアセンブラは書いてないが、当時他のコンパイラに比べて最適化された
> コードを吐くと言われたx86のMSCあたりでさえ、MSCの出したアセンブラソースを
> 雛形に手で直していくと、自己書き換えとかトリッキーな手段を使わなくとも、
> 生成されるバイナリ比較で1/2〜1/3以下になった。
>
> アセンブラならCフラグの状態でエラーの有無を返せるが、Cでは実装により決ま
> ったレジスタで返さなければならない。　汎用レジスタは関数内で破壊される可能
> 性があるので、上位関数では関数の前後で変数の保持に使えない。
>
> 例えば、x86系の多くのコンパイラは、16bit値ならAXレジスタ、32bit値ならDX:AX
> レジスタで値を返すが、戻り値がvoid型の関数として定義しても、コンパイラは
> これらのレジスタは破壊される前提でコードを吐く。
>
> したがって、register宣言を付けてレジスタ渡にしても、実際は関数の呼び出し
> 前に、スタック上のローカル変数ないしグローバル変数から汎用レジスタへの
> コピーが行われるため速くはならない。おまけに、レジスタ渡しにしたところで、
> その関数内から別の関数を呼ぶと、変数渡しに割り当てられたレジスタが破壊
> される想定が必要なので、結局、コンパイラは関数内でスタック領域へ変数の
> コピーを置く領域を割り当て、ストアしなければならない。
>
> さらに、レジスタ渡しの関数をあちこちで呼び出すと、上記の関数呼び出し
> の際のレジスタ代入コードがばら撒かれ、コード量も増える。
>
> アセンブラでは関数ごとに、呼び出し前後のレジスタ保持ルールや、同じint型
> の値でも返すレジスタを任意に選択するなど、一歩間違うとバグるリスクと引き
> 換えに、最大限の最適化ができるが、Cコンパイラはそこまで賢くはなれない。

知識がその時代で停まっちゃった老害

>>446
過去の事実を語ってくれているだけなら害はなさそうだけど、
それを根拠に一般的な話としてアセンブリで書くことが効率的だと言っているのなら、 >>447

>>447
そうれはそう思うけど、上から順番に行くと

> アセンブラならCフラグの状態でエラーの有無を返せるが、Cでは実装により決ま
> ったレジスタで返さなければならない。　
現在なら、戻り値をフラグで返すコンパイラって無いの?

> 汎用レジスタは関数内で破壊される可能
> 性があるので、上位関数では関数の前後で変数の保持に使えない。
現在、関数内で破壊されないレジスタは保存しないグローバル最適化してくれないの?

あるいは、現在のｘ86系はレジスタリネーミングされている筈。
だけどコンパイラは昔ながらの保存をしているの?

現在のコンパイラの最適化が、そんなにアホとは思えないんだけど…

見た感じアセンブラ信者の老害、に俺も +1

人力で書いたらコンパイラのコードの数分の1になるのなんて、すげートリビアルな
コードとかそんなのだよ。あらゆる状態変化を人間の頭が完全に追える範囲、
せいぜい数KB。逆に言えば中間コードインタプリタとかでは、それをやる価値が
あることもある。

前後の文脈わからんけど、register宣言はもはや付ける意味は基本的にほとんどない、
というのはコンパイラの常識ではあるが。

プロセッサ自体もスーパスカラとかで色々ややこしい動作をするようになってるから、
その老害オヤジが実際に現代のプロセッサで大口叩いてるような最適のコードを
書けるとはとても思えない。

> 現在なら、戻り値をフラグで返すコンパイラって無いの?

呼び出し規約という奴があるから基本的には無理。

> 現在、関数内で破壊されないレジスタは保存しないグローバル最適化してくれないの?

保存しない、というのは呼び出される側のすることであって、呼び出し側では、
呼び出し規約で破壊されることがありうることになってるレジスタを、呼び出しに
またがって生存を仮定することは通常できない。これは規約が有効な限り無理。

が、返り値がフラグ一丁で済むような関数であるとかそういうのはインライン展開
しちまうのが多分一番効率的という気がする。

規約上の破壊レジスタを保存しないって最適化は一部のコンパイラではLink Time Optimizationを有効にすればやってるな

確かに、MS-Cの時代ならアセンブリ出力から作り替えることもやったけどねぇ。
今のコンパイラは当時とはまるで次元が違うことを認識できていないようでは、不勉強の謗りは免れないな。

それでも当時のMSCはMS-DOSマシンの普通手に入るコンパイラとしては
総合的な出来は一番よかったとは思うけど。

>>446
今来たけどもその時代からのプログラマだが
＞一歩間違うとバグるリスクと引き換えに
アセンブラでガリガリ書き換えてバグるんじゃコスト的には大幅ダウンなわけで
趣味で最速プログラム作りたいならいいけど仕事ならNGだわな。
確かにフラグで返すとか不使用レジスタを自己ルールで決めてレジスタ渡しするとかすれば速くはなるが
クロック8MHzとかの時代の話だからねえ。
今なら手間の方が大きすぎてお勧めできん。

>>450-451
なるほど、勉強になる。ありがと。
特に
> プロセッサ自体もスーパスカラとかで色々ややこしい動作をするようになってるから、
> その老害オヤジが実際に現代のプロセッサで大口叩いてるような最適のコードを
> 書けるとはとても思えない。
聞かせてやりたいと思った。

> 前後の文脈わからんけど、
おっと失礼した。ドヤ顔の書き込みがあったのはここ。
http://kamome.2ch.net/test/read.cgi/denki/1309466648/750

ちょっと見てみたが。

組み込み（制御系）とかリアルタイムゲーム（リフレッシュ間隔時間内での処理が要求される）とか、
確かにそういう職人芸が成否を決めることもあるんだけどね。

あとどうでもいい知識だが8086のコンパイラではLSI-C 86は非標準的なレジスタ渡しで、うまくやると
末尾再帰最適化も効いてほんとにアセンブラ手書きみたいなコードができることもあった。階乗とか
かなり単純なコードの場合だけど。

どうでもいくない知識としては、x86 64の呼び出し規約はUnix系もWindows（Microsoft）もレジスタ渡し、
ってのは今時アセンブラ信者をやるなら必須の知識かな。

ゲームでもよほどクリティカルじゃないとやらん。
RISC ならまだいいけど 86 のアセンブラを昔風に最適化なんてできる気がしねえ。
SIMD まわりは、また別だけど。

おれアホだからLSI C試食版のレジスタ渡しがよく分からんかった
あれって当然レジスタの順番ってのがあるんだよね？
第一引数から順番に

見てみた。

> 関数パラメタの受け渡しには、レジスタAX, BX, CX, DXとスタックが使われま
> す。パラメタがどのレジスタにはいるかは、左から順に各パラメタに次の規則を
> 適用することによって決定されます。
（以下箇条書きでルールが4個）

そんな面倒なもんでもないね。

>>458
説明が糞だから、仕方がない。
例えば、引数が一つでint型の場合、どのレジスタに割り当てるか不明。

箇条書きの2個目に、

> + パラメタの型がint, unsigned int, short, unsigned short, near pointer
> または2バイトの構造体か共用体ならば、AX, BX, CX, DXのうち未使用のも
> のに割り当て、どれも空いていなければ、スタック上に1ワード取ります。

と書いてあるが、どう不明なんだ？

>>461
・『未使用』の意味が不明
・どの順に使うか不明

「未使用」は、まだ割り当てられていない、という意として、
順番は確かに書いてないなw

>>462
思い出した
まさにその辺が曖昧で分からなかったんだよ

試せばいいのにこれだからジジイと厨房ゎ

実装の一例だけ見て正しいと思い込む行為

アセンブラを出力してそれを読んで修正して、インラインアセンブラにして使ってたなあ。

ドキュメントには、そのあとに例が付いてるから、それでなんとなくわかると思うけど。

真の64ビットプログラムを作る方法を教えてください

お前にはまだ早い
まずは64ビット級からはじめろ

>>469
スレ違いだからくだ質へ。
で、何がわからないのかさっぱりだから、整理して。
ハンドアセンブルでもCコンパイラでも、32bitと変わらない手順で作れるはずなんだけど。

double gweights = 0.0f;　 　 　 　 　 //　0.020s

for (int j = yT; j <= yB; ++j) {
　 　 　 //　0.666s
　 for (int k = xL; k <= xR; ++k) {　 //　2.347s
　 　 const double gwTt = gwT[k];
　 //　1.048s

　 　 const int di = s1[k] - s2[k];
　 //　2.282s
　 　 const int di2 = di * di;
　 　 　 　//　2.530s
　 　 const double di3 = di2 * gwTt;
// 10.685s

　 　 gweights += gwTt;
　 　 　 　 　 　// 1.146s
　 　 diff += di3;
　 　 　 　 　 　 　 　 // 7.087s
　 }

}

ICCでも速度出ない…。

int * doubleって遅い？

改行コード隠されてた...
orz

>>472
＞int * doubleって遅い？
遅い。つーか、キャストが遅い。
それはさて、ベクタ化しないでしょ。gweightsとdiffを別のループで計算するようにしたらベクタ化しないかな。
それと、定数だから大丈夫だと思うが0.0fはfloat値だから0.0にすべきかと。

gweights += gwTt;
// 1.146s
diff += di3;
// 7.087s

むしろこの辺に疑問を。diffの型ってintじゃないのか

誘導されて来ました、
プログラムでこの部分がかなりの時間をとっているので改善したいと考えています。

#define M 300000
#define N 50000

int XY[M], b[N];
double x[N], y[N], z[N];

for(int i = 0; i < 40000; i++)
{
　for( int j = i+1; j < 40000; j++)
　{
　　r = sqrt((x[i]-x[j])*(x[i]-x[j]) +
　　　(y[i]-y[j])*(y[i]-y[j]) +
　　　(z[i]-z[j])*(z[i]-z[j]))+0.5;
　　XY[r] += b[i]*b[j];
　}
}

・x,y,zの有効数字は整数桁まで
・rの最大値は200000程度
・インラインアセンブラやMMXを使用せずに速度を上げたい

インデックスへのアクセスとsqrtの計算の部分がボトルネックのようです。
よろしくお願いします

>>477
１秒かからないんだが、データが違うのかな？
http://ideone.com/bGwRs

>>477,478
ちょっと修正。結果変わらず。
http://ideone.com/EpARv

プロファイラだと、　　XY[r] += b[i]*b[j];がボドルネック。

>479
セグメンテーションフォルトになる可能性がある
(少なくとも僕の環境では起こった)
データ作っているところでM/3とかでいいかな

95%以上は、XY[r]のアクセスと判明。

>>481
配列の動的確保つかうといい。

(x,y,z)のノルムの小さい順に並べるなどして、XYのランダムアクセスを減らせばいいかもしれない。

具体的なデータを見ながら改良するほか無いと思う。
XY[r]のランダムアクセスをなくせれば良いが、元のをこれ以上改善できるところがない。

>>477
固定小数点演算にすればいいんじゃないの?

u_long sqrt2(u_long f)
{
　　u_long s = f,t;
　　if(x == 0)　return 0;
　　do {
　　　　t = s;
　　　　s = (t + f / t) >> 1;
　　}while(s < t);
　　return　t;
}

int XY[M], b[N];
int x[N], y[N], z[N];
int xi, yi, zi;

for(int i = 0; i < 40000; i++) {
　　xi = x[i]; yi = y[i]; zi = z[i]:
　　for( int j = i+1; j < 40000; j++) {
　　　　r = sqrt2(　(xi-x[j])<<1 +
　　　　　　　　　　(yi-y[j])<<1 +
　　　　　　　　　　(zi-z[j])<<1　　) + 0.5;
　　　　XY[r] += b[i]*b[j];
　　}
}

sqrt2()関数はここから持ってきた。
　ttp://www.geocities.co.jp/SiliconValley-PaloAlto/5438/sqrt.htm

>>479
自分のPCとコンパイラだと２５秒くらいかかります
１秒以下というのはコンパイラやPCの性能の違いかもしれないです
もしそこまで早くできるなら十分なのですが・・・

>>482
そこが大きいと思ってたけどそんなにですか・・・
ありがとうございます

>>480>>482
そうなんだ。じゃぁ、>>486は意味無いのねorz

>>484,485
ランダムアクセスがXY[r] += b[i]*b[j];におけるボトルネックということですか・・・
でも、データはかなりランダムに配置されていてrの最小値が10000、最大値が200000くらいなので
ノルムでソートしたらそれのほうが時間がかかりそうです・・・

>>488
自分のプログラムではsqrtを省略する時ｒの値がMより大きくなるため、
XY[1000] += b[i]*b[j]みたいな感じプログラムを回していました

そのせいでランダムアクセスが起きず、
速度が上昇→sqrtがボトルネック
のように勘違いしていたみたいです。
お手数をおかけして申し訳ないです

速いメモリを使うか、並列計算だな。
GPUは使ったことないけど、こういった単純な計算には向いていそう。とおもうだけど実測はしていない。
CPUのマルチスレッドでも速くなると思うけど実測はしていない。

並列4スレッドだと例えばこうやるんです。
メモリ共有すると衝突で遅くなると思うので、実メモリが十分にあったら別々に確保。


スレッド1 ： for(int i = 0; i < 40000; i+=4) {　XY0[r]・・・ }
スレッド2 ： for(int i = 1; i < 40000; i+=4) {　XY1[r]・・・ }
スレッド3 ： for(int i = 2; i < 40000; i+=4) {　XY2[r]・・・ }
スレッド4 ： for(int i = 3; i < 40000; i+=4) {　XY3[r]・・・ }

for( r = 0; r < M; r++) {　XY[r]=XY0[r]+XY1[r]+XY2[r]+XY3[r]; }

>>493
ありがとうございます。

それならインテルコンパイラでコンパイルを行うと勝手にMMX最適化を
行ってくれるのではないか、という認識でいます。

ですので、現時点では並列計算は考えていません、
認識が間違っていたら申し訳ないです

>>492は、マシン4台あったら良いけど。
一台でやるとランダムアクセスが一気に4つ来るだけで速度が速くならないか。

i=39999の時、jのループは飛ばされるだけなのでi<39999にすれば数クロック節約出来るんじゃね

>>478
> #define M 300000
> x[i] = rand() % M;

32bitのコンパイラなら、普通はRAND_MAXって32767程度だと思う。
だから、これだとx,y,zのサンプルデータが小さすぎるんでないかな？

static int XY[M], b[N];
static double x[N], y[N], z[N];

こうしてたの忘れてました、すいません

今時のcpuはmmxじゃなくてsseだな。
iccを使えるなら、OpenMPの指定がらくだから試してみるといい。
# そしてがっくりくる、とw

>>498
どうせだし、ちょっと調べてみます
ありがとうございます

iccのOpenMPて最適化に制限ないの?
VCだとPGOが使えなくなるぽいけど

>>482
かなり大きなキャッシュが必要だな

for (i = 0; i < 40000; i++) {
x[i] = rand() % M;
y[i] = rand() % M;
z[i] = rand() % M;
b[i] = rand() % 100;
}
memset(XY, 0, sizeof XY); //できるかぎりキャッシュに残るように分離した

テキトーに並列処理すると、余計に時間が掛かってしまった。
／(^o^)＼

こういうのは、IntelよりAMDのCPUの方が有利かもね。
loopを微妙に解いてprefetchするとかで。

メモリランダムアクセスがネックだから。
同一メモリにアクセスする限りは、並列化しても大して速くならないことは目に見えているな。

XY[0]〜XY[M/2-1]、XY[M/2]〜XY[M-1]とアクセスを局所的になるようにCPUを
割り当てると速くなるかもしれない。

CPUのキャッシュに残るように、メインメモリへアクセス減らすようにするといい。
なるべく同じXY[r]へのアクセスを増やすこと。

r を近場の連続したとこに溜めといて、裏で書き込むとか

>>505-507
それはちょっと無理じゃないかな。
>>477
> #define M 300000
> int XY[M], b[N];
> ・rの最大値は200000程度
必要なキャッシュは800kB。結構デカイ。
short intとかWORDとかの16bitに入れたほうが簡単かも。

数キロのダブルバッファでも駄目かのう
組みたくないが

jをインデックスにしたメモり参照が、XYをキャッシュから弾き出すんだろ
ループを工夫して対策するしかない

int b[N];　double x[N], y[N], z[N];
を部分的にCPUキャッシュに乗せて
XY[M]と併せて全てがキャッシュに乗るようにする。
まずCPUキャッシュにのっている部分だけで計算をすすめて
終わったら次を読み込む。

XYが10個でも、キャッシュから追い出されて速度低下する。他の配列が優先されてしまうんだな。強制でCPUキャッシュに配置する方法あるか?

#include <math.h>
#include <stdio.h>
#define M 10
#define N 50000
#define R 50000
unsigned int xor128();
void main() {
int i, j, r, *b = new int[N];
float *x, *y, *z;
x= new float[N]; y= new float[N]; z= new float[N];
unsigned int *XY = new unsigned int[M];
for(i = 0; i < M; i++) XY[i]=0;
r = (int)(M/sqrt(3.0));
for(i = 0; i < N; i++) {
b[i]=1 + i%32768; x[i]=xor128()%r; y[i]=xor128()%r; z[i]=xor128()%r; }
unsigned int sum=0;
for(i = 0; i < R; i++) {
for( j = i+1; j < R; j++) {
r = sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]) + (z[i]-z[j])*(z[i]-z[j])) + 0.5;
sum+=b[i]*b[j];
//XY[r] += b[i]*b[j];
}}
printf("%d\n",sum);
}

unsigned int xor128() {
static unsigned int x=123456789UL,y=362436069UL,z=521288629UL,w=88675123UL;
unsigned int t=x^(x<<11); x=y; y=z; z=w; return w^=(w>>19)^t^(t>>8); }

>>512
他の配列をcache不可な場所に配置するのはどうだろうか。

配列はshort intとfloatにするのはどう？

レジスタ命令付けてもたいした効果無いし。無視されてる?
強制的にキャッシュに乗らせない命令もあるの?

>>514
(x,y,z)のdoubleをfloatへ節約してみたがダメだった。CPUキャッシュサイズには依存するが。

[j]で参照しているメモリが1M以上ある
これがXYをキャッシュから弾き出している

ターゲットのキャッシュはどのくらいのサイズなのかな？

なんか一個の構造体に整理とか、できないか

単純にキャッシュの使い分けでいいんじゃね？
struct CACHE {
int r;
int b;
};
CACHE c[N];
を追加して

for(int i = 0; i<40000; i++) {
　for(int j=i+1; j<40000; j++) {
　　// 読み込み:キャッシュをフルに使う
　　// 書き込み:追い出されてもＯＫ
　　int r = static_cast<int>(sqrt(
　　　(x[i]-x[j])*(x[i]-x[j]) +
　　　(y[i]-y[j])*(y[i]-y[j]) +
　　　(z[i]-z[j])*(z[i]-z[j]))+0.5);
　　c[j].r = r;
　　c[j].b = b[i]*b[j];
　}

　for(int j=i+1; j<40000; j++) {
　　// 読み込み:追い出されてもＯＫ
　　// 書き込み:キャッシュをフルに使う
　　XY[c[j].r] += c[j].b;
　}
}

少しは速くなるはず

お手上げ。

for(int k=0; k < 40000; k += 256)
{
for(int l = 0; l < 40000; l += 256)
{
for(int i = k; i < min(40000,k+256); i++)
{
　for( int j = max(k+1,l); j < min(40000,l+256); j++)
　{
　　r = sqrt((x[i]-x[j])*(x[i]-x[j]) +
　 　　(y[i]-y[j])*(y[i]-y[j]) +
　　　(z[i]-z[j])*(z[i]-z[j]))+0.5;
　 　XY[r] += b[i]*b[j];
}
}
}
}

256エントリーずつにした

どのくらい速度上がったのか比較を乗せて。

汚いプログラムで悪いけどやってみた
ttp://ideone.com/nkhXc

チョットだけ速くなったかな

えらく手が込んでるな。いつもそういう感じなのか。

あんまり適当なベンチだと何が悪いか分からなくなるので、いつもこんな感じです
ソースの骨組みは前からあるのでそれを改造して作ってます

>>524
使うメモリを二分割とか、三分割にしたらもっと速くならない?
こんな感じで。
　for(int j=i+1; j<40000; j++) {
　　if (c[j].r<(i+200000)/2)
　　　XY[c[j].r] += c[j].b;
　}
　for(int j=i+1; j<40000; j++) {
　　if (c[j].r=>(i+200000)/2)
　　　XY[c[j].r] += c[j].b;
　}

>>520
>>520を利用したら計算時間が25秒->20秒まで早くなりました！
構造体にこんな使い方があるなんて知りませんでした。

あと、今日誤差を許容して計算してみたら、Mのオーダを一つ落とせそうな事に気づきました。
これらを利用したら合計計算時間を半分近くまでできそうです。

他の方の意見も非常に参考になるので色々と試しています
様々な意見を出していただいてありがとうございます！

>>520
>>520を利用したら計算時間が25秒->20秒まで早くなりました！
構造体にこんな使い方があるなんて知りませんでした。

あと、今日誤差を許容して計算してみたら、Mのオーダを一つ落とせそうな事に気づきました。
これらを利用したら合計計算時間を半分近くまでできそうです。

他の方の意見も非常に参考になるので色々と試しています
様々な意見を出していただいてありがとうございます！

>>520の考えを利用したらかかっていた時間が25秒から20秒まで短縮されました！
ありがとうございます！！構造体のこういう使い方は始めて知りました。

あと、今日計算していて気づいたのですが、誤差を許容してMのオーダを１つ下げてもそれほど結果は変わらないみたいです
これらを利用したら全体の計算時間を半分くらいにできるかもしれません。


他の意見も参考にして色々試しています。
様々な意見をありがとうございます、非常に参考になります。

反映されてないから連投してた、申し訳ないし恥ずかしい・・・

rはiとjについて対象な値だから、i<jの時に計算したrを覚えておき、j>iのときは計算せずに覚えておいたrを使えば
計算時間半分になるんじゃん？
関係ないがiとjが出てくるコードは読みにくくてたまらん。xとyのほうがいい。

>>532
i<jとj>iは同じだろう…ってのは置いといて

for(int i = 0; i < 40000; i++)
{
　for( int j = i+1; j < 40000; j++)

常に j>i だよ。
もともと半分しか計算してない。

>>527
Mの大きさを1/10,1/100にそれぞれしたときかかる時間は
22.352->21.563->21.523
程度の短縮だったので、提示していただいた考えではあまりうまくいかなさそうです
やはりランダムアクセスにおいてキャッシュがうまく働いていないのかと・・・

知識不足で>>520の方法でなぜ短縮されるのかがよくわかりませんが・・・

>>534
> やはりランダムアクセスにおいてキャッシュがうまく働いていないのかと・・・
だからランダムでもXY[M]がキャッシュに入る様、二分割三分割でやろうって話し。

>>535
>>512で示していただいてますが、Mを10にしてもキャッシュをうまく使えないのならメモリを分割しても
うまくいかないと思います

>>534のレスでは>>527への応答になっていませんね、すいません。

アクセスを局所的にして、キャッシュ溢れを防ぐという意味で>>522が一番有効な気がするが。

>>536 atmwri?

実際にやってみましたが>>527、>>522の方法では逆に遅くなってしまいました。

XY[r]へのランダムアクセスがボトムネックで、
jが大きすぎるため、キャッシュがXYの方に割り当てられず、
Mのを小さくしてもXY[r]のアクセスにキャッシュを使うことができない
というのが現在の認識です。

ランダムアクセスよりキャッシュから追い出される事が問題。
アクセスを局所に集中させるという方向は間違っていないはず。

>>493の
>それならインテルコンパイラでコンパイルを行うと勝手にMMX最適化を
>行ってくれるのではないか、という認識でいます

コレ見てSSEでもいいんじゃね？って思ってSSE2版を追加しました(一度に２個のsqrtを計算してるだけですが）
ttp://ideone.com/8ZS47

i i+1 i+2 i+3を同時に計算したら、キャッシュの入れ替えが減ると思っていたが。もしかしたら無意味になるかも思って手を出していなかった。
速くなったか。

自分の考えてたのとは違うか

>>539

>>522は自分で書いて何だが、会社辞めて何年もプログラム書いていないし、
コンパイラも入れていないから駄目な気がする
すまぬ

>>520,>>541ってすげー

iccなら、ループ内が不自然に複雑じゃなければsseを使ったベクタ化してくれると思う。

x,y,zを近場に置けない？

>>544
別に凄くは無いですよ。google先生が凄いんです

>>542
一番いい最適化の方法だと自分は思います。複雑な演算をしている間にプリフェッチが完了すればメモリアクセスを
隠蔽できるので

double を float にしても、ちょい速くなるね。
bxyz を構造体にしても変わらなんだ。

転送量が削減できるからな。

全部SSE2でやってみたけど微妙すぎる
関数が大きいから命令キャッシュから溢れているかも
ttp://ideone.com/P8jIP
疲れたのでROMに戻ります

>>496
遅レスだが、
gcc version 4.2.1 (Apple Inc. build 5664)
RAND_MAX = 2147483647
gcc a.c -O2 -Wall

>>551
RAND_MAXでかくていいなぁ。
ちなみにsrandの引数の型ってどうなってる？
64bitになってるのかな？

>>552
unsigned

>>479の実行結果
1秒未満

>>550の実行結果
res:477 -> 32.4342
res:520 -> 31.6174
res:520s -> 34.1533
res:520s2 -> 31.2566

なんだが、議論を続ける理由は何だろう？
例えばデータ量が数桁大きくなった場合でも適用出来る方法を探る、とか？

>>552
stdlib.h @ MSVC
#define RAND_MAX 0x7fff

>>554
イマイチ、状況が解らないんだよね。

intやdoubleの四則演算の300000, 50000 の配列なんて、
ベクタ化でガッツリ早くなるのに。

>>520
色々なアイデアを出してくださって非常に参考になりました。
SSEに関しては、もう少しでインテルコンパイラが使えるようになるので、
それを導入してから参考にさせていただきます。本当にありがとうございます。

>>548
大きい配列を扱う場合はfloatの方が少し早いみたいですね、知りませんでした。
ですがこれも何故か遅くなってしまったので保留しておきます。

>>554
実際には時間を変えた複数のデータの比較になるので、一つ一つの計算が早ければ早いほど望ましいです。
あと>>479のままでは私のPCではコンパイルできないので、データを十分に計算していない可能性があるのではないかと・・・

>>556
floatを使うときは、doubleとの変換が発生しないように注意。
具体的には、定数は必ずfをつけるかキャストするとか、標準関数もfloat版を使うとか。
手っ取り早い検証方法としては、アセンブリ出力をしてcvtなんちゃらのニモニックを探せばいい。
あ、勿論、gccの場合は-msse2 -mfpmath=sseを忘れずに。

>>556
> 私のPCではコンパイルできない

どんな環境か知らないけど、配列を動的確保してないからじゃない？

ttp://ideone.com/Sicye

>>558
すいません、コンパイルできないじゃなくてコンパイルしても動かないの間違いでした
動的確保の代わりにstatic int, static double を使ってプログラムを動かしているのですが
動的確保したほうがいいのでしょうか？

>>557
どこかで無駄な変換が起きてる可能性がありますね、
アセンブリはあまり理解していないですが、
そちらからも無駄がないか調べてみたいと思います。ありがとうございます。
ちなみにVisual C++2010でやってます。

>>559
> コンパイルしても動かない

32bitバイナリで、スタックエラーでしょ？

スタック・ヒープってのがあって、mallocやnewすると、ヒープ領域が使われて
自動変数は、スタック領域が使われるんだよ。MSVCの既定では、１MBだから

int XY[300000], b[50000]; 　// int型 (4Bytes) * (300000 + 50000)
double x[50000], y[50000], z[50000]; // double型 (8Bytes) * (50000 + 50000 + 50000)

簡単に溢れるじゃんｗ　Cellみたいにアーキテクチャによっては、
スタックが非常に高速なメモリーだったりするんだけど、スタック領域は大きくないんだよ。

コンパイラによっては、staticキーワード付けるとヒープ領域使うらしいけど
所詮環境依存だからね。

>>560
環境依存ならstaticは使わないほうが良さそうですね、

だとすると、
>>554は全部スタック領域で演算できてるから早いのでしょうか
それとも、計算時に何らかのエラーが発生しているため早いのでしょうか
もし前者なら1秒未満というのは非常に魅力的です

>>554

>>479の実行結果
1秒未満

>>550の実行結果
res:477 -> 32.4342


何でこうなるの

精度が重要でない限りは、配列はfloatがいい。容量削減。
現代のパソコンは複数のソフトが動くから、他のソフトに迷惑掛けないのが高速化のコツ。
スワップアウトを何度もやると遅い。

1秒未満って、異常終了してるだけだろ。
newやvectorで動的確保した方が良い。
staticは遅いのと、容量確保に限界がある。
動的確保も限界があるがそっちのほうが大きい。

スタックもヒープも、物理的にはメインメモリで同じだから。
コンパイル時に確保が決定している固定領域がスタック。
コンパイル時に確保が決まっていない領域がヒープ。
自プログラム、他のソフトにとっても、使っていないメモリは解放した方が、空きが増えて速度が上がるので動的確保の方が良い。

>>554
>>479は計算結果を表示していないから計算自体が最適化でなくなってるんじゃないの？
バグにしかみえないんだけれど…

>>554
>>479をそのままコンパイルしてやってみましたが18秒かかりました
1秒未満というのはちょっと考えづらいです・・・

>>563
後の参考になります。ありがとうございます。
しかし今回時間がかかっている部分の計算は、ほとんどがintの配列に格納されることと、
sqrtの引数・戻り値がdoubleであることからfloatを使う旨みはあまりなさそうでした

今回のケースは、CPUキャッシュから、よく参照される配列が追い出されないことが大事なわけで
sqrtの計算部分は無視できるよ。
全体の容量削減が追い出されない可能性をあげる。

>>564-565
ありがとうございます。早くなりそうなら動的確保に変えてみます
その場合、calloc関数でも構わないのでしょうか？
C++は全然していないので・・・質問ばかりですいません

>>568
なるほど！
ということはメモリを動的確保して、例えばx,y,zをintで表現できれば
キャッシュ内に配列が収まる可能性があるということですね
これはちょっと光が見えてきた気がします！

callocでも同じ。最終的には、WinAPIのメモリ確保関数を呼び出してるだけとおもう。C、C++でセイノウ差は無い。

>>567

static int XY[M], b[N], r, i, j;
static double x[N], y[N], z[N];

一番簡単に修正するには静的領域に置くのがいいな
元のプログラムは多分スタックオーバーフローで異常終了している

>>567
r,i,jは分けないと

アンカミス
>>572で示す>>567は>>571の間違いスマソ

>>573
static int XY[M], b[N];
int r, i, j;
static double x[N], y[N], z[N];

こういう事だね了解

UNIXやLinuxはスタック領域が不足すると自動的に拡げてくれるディストリビューションがあるからな
あれは正直羨ましい

Intel C/C++ コンパイラでベクタ化すると、こんな感じ。
http://www.dotup.org/uploda/www.dotup.org2040834.zip.html

MSVCのデバッグビルドで、実行すると120秒。
ICCで最適化したら、12秒

そろそろ速いマシン欲しいわー。

メモリの動的確保を行う前に、インデックスの数をできる限り減らして、
全ての変数をスタック領域内に入れて計算を行いましたが
結局は>>520のやり方の方が早かったです・・・
これだと動的確保の処理を入れると余計に時間がかかりそうです

今の考え方のままだとそろそろ頭打ちかもしれないです

XY[r] += bi * b[j]; を別のループで回してみたら、3秒縮まった。
L2Cacheに収めると、劇的に早くなるだろうね。

http://www.dotup.org/uploda/www.dotup.org2041723.zip.html

(x,y,z)をcharかshort int変換したら容量削れる。

良い方法考えついた。

>>580
大きいL2キャッシュマシンを用意するんですね

L3キャッシュだろ?

>>567
>557は言っている。sqrtf()を使えと。

>>477
rは最大、sqrt(3)*Mに成り得るから、
X：int XY[M]
O：int XY[2 * M]
の方がいいと思う。

>584
floor(sqrt(3)*(M-1) + 1/2)
ようやくこの話が出たか
>47ではなくて>479に言うべきだけどな

>>585
アンカーは正しく使えよ。
専ブラならいいけど、そうでない人が困るだろ?

>>585
＞rは最大、sqrt(3)*Mに成り得るから
絶対になりませんよ。

>>477 には、"#define M 300000" "rの最大値は200000程度"
って書いてあるんだから。

お、アンカ間違えたw 上は>>585じゃなくて>>584宛て

>>578
そのやり方でやってみましたが、

>>520 -> 22.105sec
>>578 -> 27.413sec

という結果でした。

しかし、自分でTestCodeのcalc3の部分をコンパイルして計算したところ、
倍近く時間がかかったので、インテルコンパイラには期待が持てそうです。
ありがとうございます。

>>520

↓

for(int i = 0; i < max; i++){
　const int bi = b[i];
　const int xi = x[i];
　const int yi = y[i];
　const int zi = z[i];

　for( int j = i+1; j < max; j++){
　　c[j].r = sqrt((xi-x[j])*(xi-x[j]) +
　　　(yi-y[j])*(yi-y[j]) +
　　　(zi-z[j])*(zi-z[j]))+0.5;
　　c[j].b = bi*b[j];
　}

　for( int j = i+1; j < max; j++)
　　XY[c[j].r] += c[j].b;
　
}

>>578を利用してこのように書き換えると
22.188sec, 22.328sec -> 20.645sec, 20.670sec
と、少し速度があがりました！
参照を減らすのはもっと早くやっておくべきでした。

浮動小数の計算はコンパイラオプションに/fp:fastを指定すると余計な変換を省ける。

bi * b[j] は下のループでもいいと思ったが
上のループの方が速いのかのう

コンパイル環境用意していない者の戯言です

>>590
そのくらいの速度向上でいいなら、 float 化が一番楽じゃないかねえ。
sqrtf と +0.5f に気をつけるだけじゃん。

一般に単にfloat化するとsqrtf使っても若干遅くなるはず。SSE2使っていいなら別だが。

そんなところが遅いわけではないので関係なし。

float化で数秒速くなったけどね。i7で。

マルチスレッドに対応しました
メモリ動的確保に対応しました
>>477がC++をやってないのでC言語にも対応しました
ttp://ideone.com/F48Ay
適当に弄って遊んでくださいな

>>597
本当に何から何までありがとうございます！
プログラムだけでなく、ベンチマークも非常に参考になります
これからコードを書くときも参考にさせていただきます

>>520のコードでなぜ速くなるのかが、昨日やっと理解できて

double x[N], y[N], z[N];
int b[N], r[N], XY[M];

for(int i = 0; i < max; i++){
　const int bi = b[i];
　const int xi = x[i];
　const int yi = y[i];
　const int zi = z[i];

　for( int j = i+1; j < max; j++){
　　r[j] = sqrt((xi-x[j])*(xi-x[j]) +
　　　(yi-y[j])*(yi-y[j]) +
　　　(zi-z[j])*(zi-z[j]))+0.5;
　}
　
　for( int j = i+1; j < max; j++)
　　XY[r[j]] += bi*b[j];
}

このように書けば、書き込みの無駄が省ける事に気づきました
これで1%ほど速度が上がりました

あと、>>505や>>540で言われていた局所性ということもやっと分かりました
最初はb~z[i],b~z[j]を使っていたので、キャッシュが追い出されて十分に使えなかったんだと思います

しかし、試しに

for( int j = i+1; j < max; j++)
　　XY[c[j].r] += c[j].b;

を消して計算したところ15秒ほどかかったので、
局所性を使ってもそれほど速度は変わらないかと思いました
>>482で95%がX[r]へのランダムアクセスと書かれていましたが
もしかしたら、どこか他にボトルネックがあるのかもしれません

また、試しに

int B = 0;
for( int i = 0; i < max; i++)
　for( int j = i+1; j < max; j++)
B++;

と、書いてみたところ、計測不可能なくらい時間がかかりました
b~z[N]を定義していないプログラムだと3秒程度で計算が終わったので
ヒープ領域が関係あるのかと思いましたが、もし原因がわかる方がいたら教えて下さい。
連投申し訳ありません。
520さんのコードでももう少し調べてみようと思います本当にありがとうございます。

>>600
Windowsが動くようなマシンは、ヒープもスタックもメインメモリ。
つまり変数へのアクセス速度は、ほぼ変わらない。

ただCPUには、メインメモリのキャッシュ領域がある。
そこは、32KB程度の小さい領域。

アクセス先の配列が数十KBくらいなら、CPUのキャッシュが効いて
非常に高速になるはず。

このアルゴリズムでは、全ての配列が大きくて
キャッシュには非効率的になってるんだお。

アクセスする先を数十KB程度毎に区切れるように、
アルゴリズムの最適化するのが、一番。

って話だよ。

すいません。

＞また、試しに
以降は再度計算したら3秒程度で計算が終りました。

>>601
自分の付け焼刃的な考えでは、>>599の

for( int j = i+1; j < max; j++)
　XY[r[j]] += bi*b[j];

の部分を消したらキャッシュに全て乗ってかなり速くなると思ったのですが、あまり速くなりませんでした
これはb[N],x[N],y[N],z[N]が大きすぎるため(それぞれ、200KB程度)、配列がキャッシュに乗り切らず、結局は何度もアクセスをしているため、
キャッシュの局所性を利用したぶんしか速くならなかったとういうことでしょうか。

コンパイラの最適化で不要な計算を落とすのがある。

>>477と>>520はコンパイラのオプション次第で同じくらいの速度になるね
参考まで。

-O3
res:477 -> 19.3800
res:520 -> 11.8600
res:520s -> 7.1000

-O3 -funroll-loops
res:477 -> 11.4100
res:520 -> 11.0900
res:520s -> 6.7000

>これはb[N],x[N],y[N],z[N]が大きすぎるため(それぞれ、200KB程度)

x,y,zがdoubleならそれぞれ400KB程度

gccとVCは速いね
なんでBCCは遅いんだろ

そりゃほぼ最適化ないし

そっか
コンパイルが馬鹿っ速い代わりに最適化無しか

http://codepad.org/Op0Jt0gx
スレッド2つにすると少しだけ速くなるみたい。
例のテンプレートは使ってないので悪しからず。

ノーマルでもCPUキャッシュ次第で変わるんだ。
スレッドにするとメモリアクセスがよりランダムになってしまいキャッシュ溢れで遅くなる可能性。
全部CPUキャッシュに乗れば良いが。
環境によって変わる。

最初からほとんど改良できる余地は無くて、速度は環境依存なのでもう改良しなくて良いと思う。
これが言いたかった。

>>610
今の問題はL3/LLがあふれることではなくL2のことでしょ
ならば一般的な2コアCPUの場合は片方のL2が遊んでるから使おうと考えるのが自然
実際うちでは1スレッドで10秒、2スレッドで8秒くらいだしっていう

やっぱり>>597のが速いなw
アセンブラつかうなという縛りで、intrin使用はずるいような気がしないでもないけれど。

>>611
>>604が書いているように、ほぼ同等の速度となるものに対して、
>>477が、速くなりました！といっているということは、
少なくともロジック以外の面では改良の余地があったってことじゃないのかな。

x,y,z 近くにおくのって今まででてきたっけ？
それともそもそもだめなん？
ttp://codepad.org/92NIdZeV

構造体変えると15秒くらいはやくなった。
環境は Linux のみなんで、ごめん。

CentOS(VBox) corei7 860 gcc-4.1.2

% gcc 615.c -lm -O3 -funroll-loops
% ./a.out
original took 7.114642 sec
xyz_near took 7.254803 sec
% ./a.out
original took 7.169084 sec
xyz_near took 6.879905 sec
% ./a.out
original took 6.539106 sec
xyz_near took 7.331002 sec

>>520からの流れはC++だったのでオリジナルの速度に差が出ているようで
xyzを近くに配置することの有意差は認められなかったかなぁ。

コンパイラによる最適化を考えると表面的なコードはこれ以上いじらない方が良い気がしてきました
色々と考えてみましたが、コーディング以外で速度を上げる方法として


１．r[j] がint型であるのでint型を受け取ってint型を返すsqrt関数を用いる
→アルゴリズムは幾つかあったが、sqrtの方が速い
→テーブルを作るにはrが大きすぎる

２．3点a,b,cがあったときa,b,cの座標と、ab,acの長さが既知であるとき、
　　bcの長さを簡単な計算で求められないか
→ベクトルや、三角関数で考えると無理
→しかしsqrtを使用しないクロック数の少ないアルゴリズムあるかもしれない

３．b[i]最大値は100程度なので、b[N]をchar型にできる。
→キャッシュの大きいマシンがあれば二つ目のループを全てキャッシュに乗せられるかも
４．r[i]をr^2[i]のまま計算を行い、sqrtが40000^2回行われるのを防ぐ
→r^2[i]を入れるXY[M]のMが大きくなりすぎるため、r^2[i]を規格化しなければならないが、その時の誤差がどの程度か


というものを今のところ考えています。

実際に確認してもXY[r[i]]へのアクセスとsqrtの計算は同じくらい時間をとっている事がわかったので、どちらかの計算が省略できれば速度は上がるはずです。
また、並列化や、配列の位置を調整することは、人間の手で行うことが果たして良いことなのかわからないのでICCを使える様になってからにしておきます。
もし何か気づいたことがあれば教えて下さい。

このスレのおかげで、プログラムの速度が上がり知識も増えました。しかし、これ以上の高速化はデータを見ながらの作業だと思います。
ですので、一旦ここでこの話題は終了とさせていただきます。
520さんをはじめ、様々なアイデアをだしていただいた皆様、ありがとうございました。

最適化に手を出すと不毛な消耗戦になるからね。

熱い議論の後に素人丸出しの質問ですみませんが
上記やりとりも含めた最適化に関するスキルは
みなさんどうやって習得されたのでしょうか？

もちろん「（CPUなどの）仕様を確認」と「ひたすら実践あるのみ」
というのは前提だと思いますが、取っ掛かりや基礎的な知識の
習得などはどうされたのかな、と…

例えばC++の勉強をするのに膨大な仕様書をいきなり読む人と
いうのは中々いなくて、普通は入門書を読むことでスタート地点に
立ちますよね。最適化にはそういった定番の入門書のようなものは
あるのでしょうか？


自分なりに調べてみたところ

プログラマのための硬派なコンピュータ学
http://www.amazon.co.jp/dp/4798023027/

プロセッサを支える技術
http://www.amazon.co.jp/dp/4774145211/

マイクロプロセッサ・アーキテクチャ入門
http://www.amazon.co.jp/dp/4789833313/

この辺りの書籍は参考になるのではないかと思いましたが
これらはあくまでも理論的な背景であって実践的なスキルとは
また別の話になりますよね？

何か参考になる書籍なりサイトなりあれば是非教えてください。

>C++の勉強をするのに膨大な仕様書をいきなり読む人

いるけど

>>619
なんか、このスレとかで。。。
新しいキーワードを見たらそれしらべて、周辺に転がってる情報も集めて。。。
今回の話でいえばループ展開とCPUのキャッシュあたりがキーワードになってるよ。
本ならハッカーズデライトが有名かも。

>>620
なかなかいないって書いてるのに。

なるほど、基本的には個別に調査するという感じでしょうか。
書籍についてもありがとうございました。

興味はあったのですが、いまいちどこから手をつけていいのか
わからず困っていたので助かります。

ソースコードを書いて、標準環境でビルドする。

ここで、速度が気になったらWebを読み漁り、
三項条件演算子やi++を++iに書き換えたり
最適化オプションを色々試して、無駄な努力をする。

IntelC/C++コンパイラでビルドしても
大して変わらない事に失望する。

そのうちに、プロファイラを使い始めて
ボトルネックを発見、解消するｗ

ここまで来ると、コンパイラによる最適化を意識したソースコードを書くようになる。
気がする。

>>619
ノイマン型のアーキテクチャなら、高速化というのは結局
1) 計算量を下げる
2) IPC = 1 サイクル当たりの実行命令数を上げる
ということに落ち着く。

で、CPU メーカーやコンパイラメーカーの文書に、IPC を向上させるために
自社の製品にどのような技術が使われているかが、自慢げに誇張気味に
書いてあるから片っ端から読むといい。

ところで君の書き込みは、「手抜きしたい」というように感じてしまう。
ほとんどの人は、効率よく勉強したいと考えて上達したわけじゃない。
片っ端から全部学ぶしかないから、図書館で片っ端から読むのがいい。

どの段階でどの本を読めばいいのかってのはあるかもしれないけどね
でも、熟練度が足りなくて読めなかったら、他の本を読めばいいだけとも

結局さ、自分で触ってtry&Errorを繰り替えさないと
何も解決しないし、何も身につかないよね。

Intel C/C++　コンパイラも VTuneも試用ライセンスを
無料で取得できるんだから、弄ってみれば良いんだよ。

指定桁数で四捨五入する以下の関数の実行速度を上げたいの。
(valueは正、digitsは0〜5が保証される)
これ以上速くできる？

double NormalizeDouble(double value, int digits) {
　　static double t0[] = { 1, 10, 100, 1000, 10000, 100000 };
　　static double t1[] = { 1, 0.1, 0.01, 0.001, 0.0001, 0.00001 };
　　return (int)(value * t0[digits] + 0.5) * t1[digits];
}

韓国アイドルグループ「2PM」のテギョンが、韓国女優キム・テヒ主演の日本ドラマにキャスティングされ、フジテレビ「僕とスターの99日」に出演することがわかった。

　テギョンの所属事務所JYPエンターテインメントは29日、テギョンが「僕とスターの99日」で、キム・テヒに接近する謎の男テソン役にキャスティングされた、と明かした。
テギョンの日本ドラマ出演は、今回が初めてだ。

　来月23日より初放送される「僕とスターの99日」は、フジテレビが日本のゴールデンタイムである日曜夜9時に編成した「ドラマチック・サンデー」で放送されるロマンチックコメディー。

　韓国のトップスターハン・ユナ（キム・テヒ）と彼女の日本撮影で99日間の契約警護を務めるボディーガード（西島秀俊）の秘密のロマンスを描く。

　テギョンが演じるテソンは、やや暗い性格のベールに包まれたキャラクターだ。
彼には夢があるが、実現することができずに夢をあきらめてきた男。誰にも話せない大きな秘密を持っている。

　所属事務所は「テソンの秘密は、主人公2人はもちろん、パパラッチ役である要潤まで引き込み、彼らの人生に大きな影響を与える。
ドラマのストーリーを作っていく上で、重要な役柄になるだろう」と伝えた。

なお、テギョンは韓国でドラマ「シンデレラのお姉さん」や「ドリームハイ」を通じて演技に挑戦していた。

http://www.asahi.com/showbiz/korea/AUT201109290027.html

>>627
ある様な無い様な。

10進数で小数点第二位を四捨五入する場合を考える。
この時、0.05以上なら切り上げ。未満なら切り捨てになる。
一方、double型の指数部を見れば仮数部の実際の小数点を特定出来る。
0.05は 0.0000_1100_1100_1100_1101…であるため、特定した小数点の下位ビットから「1100_1100_1100_1101…」に該当するビットと「1100_1100_1100_1101…」とを大小比較する。
小さければ該当ビットをクリア。
大きければ該当ビットをクリアの上、その小数点に0.1を加算する。

なんか間違えている気がする。

t0, t1をfloat型にして、計算部分でdouble型にcastしてみる。

>>630
低レベルすぎなので結構です。

>>630
遅くなる。

>>629
例えば0,23は0,2と0.03に分けられるが、0.2を2進数表記すると…。
そう、単純にクリアしたらダメだねぇ〜

どうしても、x10,x100,x1000の処理は必要か。

>>632
CPU次第だけど、cacheの境界に合わせれば、floatだと一本に入りきる。
連続しない呼出なら、有効だと思ってみた。

>>633
仮数部をlong型に取り出し、x10dを実行。
すると実小数点は3桁右に移動するので、そこに0.5dを加算。
加算後、実小数点以下はクリア。
/10dを実行すると小数点が元に戻るので、元のdouble型にそのままはめ込む。

こんなんでも同じ結果が得られる。
でも、doubleとlongの乗算時間は同じな気がするし、castが減ってもそんなに早くなるとは思えない orz
FPGAなら間違いなく速くなるんだけどね。

VC++だと2008あたりからdouble→intのキャストが高速化されてるから
キャストは大して負荷にならないんだよね。

ところで>>627のコードだと、valueの最大値が21474になってしまうが
それは問題ないの？

それってSSE2使ってるからじゃないの？> キャストが高速化

だんごだったらどうするんだろ、とおもってたらだんごｗ

>>634
よくそんな役立たずでコテつけれるな。寒心するわ。

>>627
環境によっては int にキャストするより floor のインラインアセンブラや intrinsics を使った方が早いだろうね。
そして呼び出し側の設計しだいでは SIMD 版を作って呼び出すようにするとよりいいだろうね。
許されるなら double ではなく float にすると、SIMD の並列実行数が上がっていいだろうね。

ところで、それを高速化したところで、プログラム全体の処理が目に見えて早くなるとは思えない。
VTunes とかの CPU イベントをカウントできるプロファイラにかけてみた方がいいと思うよ。試用版もあるし。

>>640
大量の座標を処理するようなもので、各座標の値を整数化したいのかもしれないじゃない

>>635
2進じゃなくて10進で四捨五入したいからそれだとだめじゃない?
FPGAだとしても。
>>636
それは気づかんかったｗでも大丈夫。値域もvalue*pow(10,digits)は
MAXINT以下が保障されるということで。
>>640
CygWinなんだけど、g++-4 の最強オプション教えて。ググっても出てこない...
-mcore=nativeとか使えなくなった?
floor()にしてみたけどインライン展開されなかった。
floorf()にしても展開されなかったけど速くはなった。

>>642
> 2進じゃなくて10進で四捨五入したいからそれだとだめじゃない?
小数点第一位の四捨五入は簡単だよ。
そこが0なら0.5未満だから切り捨て。
そこが１なら0.5以上だから切り上げ。
1ビット見るだけで判断出来るんだ。

>>643
なるほど。
でもx10はいいとして/10はどうすんの?

浮動小数点だから気にしなくてよかったりしないの

>>643
ちょっとunsigned long long f:52;とかしてｺﾞﾆｮｺﾞﾆｮやってみたけど
もちろん全然ダメだったw
>>645
いや、FPUがあるのに高速除算機分のセルを使ったりすることもないだろう
と思ってね。

固定小数点演算って、案外知られてないんだな。

いや、ほかの部分はdoubleが必要なんだよ。

fortranには今も４倍長精度ってあるの？
メインフレームのFORTRAN77にはあった記憶があるが。

とんでもなくスレ違い。

switchにしたらちょっと早くならない？

>>651
遅くなった。

むしろ128ビット浮動小数点数はやっと標準化されたところだから、まだこれから

なんかレベル低いんだな。

おまえモナ〜

Or演算って遅いのか？
And演算やXor演算の倍近くかかるんだけど。


やってる処理は10000×10000、32bit画像の全画素に固定の32bitの値をAnd演算、Or演算、Xor演算するだけ。

環境
Win7 64bit VS2008
計測結果※clock()を使用
&= 69
|= 140
^= 68

せめて80〜100くらいに押さえたい。

>>656
ビット演算自体は高速化できるかよくわからんけど
配列アクセスなどの部分で高速化可能かも。
現ソースどうなってる？

測定順序を変えたら結果が変わりそうだなw

>>657

こんな感じ。
const unsigned int flag;//引数。

int wh=Image.Width()*Image.Height();
unsigned int* ptr=Image.Buffer();
while(wh--){
*ptr&=flag;//ここを|=等に変える。
ptr++;
}

Imageは自作クラスでunsigned intのポインタを持っていてBuffer関数はそのポインタを返すだけの物です。

計測した三つの関数の違いはWhileループの中のコメントがある行だけなんだ。

>>658
試してみたら変わったw
最初が遅いんだ。
キャッシュとかされてるのか？

今時されないCPUが有るのか？

>>661
キャッシュって数Kバイトときいてたから10000×10000×4バイトもキャッシュするのかなとおもって。

>>662
キャッシュラインサイズ分先読みする.

こんな単純な処理、アセンブラ使えよ

>>663
ソレは微妙に違う。

>>664
こんな単純なプログラムでもコンパイラの最適化よりアセンブラの方が速くなるのですか？

>>665
後学のためにも教えてもらえると助かります。

キャッシュサイズはターゲットCPUの資料を開発元のサイトで見つければいい。
最近の Intel のなら L3 が 8MB くらいあるんじゃないの。
それでも
> 10000×10000×4バイト
なら入らないけど。
もっと大きくして試してみたら。

キャッシュサイズについてまで言及するなら環境依存スレの話題になるんじゃね
まあここでもいいけど

>>666
一部を読むだけで1line読み込むから、『微妙に違う』と書いてみただけ。

RMMAだと、
mov eax, [esi-16] // read cache lines
mov eax, [esi-32]
mov eax, [esi-48]
とか書いているね。

core i7だと、forループのアンロールはいくつ単位で行えば良いの？

必要なだけ。

>>656
http://pastebin.com/pkrh7E0L

x86だけど演算によって速度に差が出ている様子はないなあ
x64ならcompiler intrinsicsを使えばいいと思うけど

キャッシュに関係があると思うならprefetch命令で配列を読みこめばいいと思うし

しかしアセンブラって面白いな
OSのお陰で暴走しても大抵止められるしとにかく速い
ただ　REALTIME_PRIORITY_CLASS　には注意が必要だな
これが入っているとドライバにすら優先するのでこれで暴走すると事実上止められない→リセット

NORMAL_PRIORITY_CLASSにすると暴走は止められるが誤差が大きくなるので
確実に暴走しない事を確かめてから REALTIME_PRIORITY_CLASS にすると
正確な値が測定出来る

2行目以降でアセンブラに関連する内容が見当たらないような。
> とにかく速い
これだろうか。

>>675
いやそういう意味じゃない

>>672のSetPriorityClass()は一つ使い方を間違えると止まる物も止まらなくなってしまう
という話
しかし簡単に止まるようにすると測定誤差が大きくなるという諸刃の剣

要するに1行目はいらないってことか

読み流してくれればいいじゃん
なんでそんなに突っかかってくんの

突っかかってないよｗ
ちなみにプロセス優先度はタスクマネージャからも変えられるから、使ってみるといいかもね

>>679
悪い悪い
でもうっかりRealTimeProcessにして動かしちゃうと、タスクマネージャすら反応しなくなるよ
やってみればわかる

マウスも止まるし

プロセス優先度について知ったばかりかと思って、コード書かなくても試すことは出来るよって伝えたかったんだ。
でも運用環境と似た状態で測定しないと気づかないことも多いと思うよ。
ある程度の指標にはなるだろうけど、その辺って難しいなぁといつも思う

今時のOSで動かすようなアプリで、正確な計測って何の意味があるんだろう。
つーか、そんなに速さを追求したいならWindowsなんて使わなければいいのに。

大発見だったんじゃないか？よくあること。

スレの流れを見て
os内のプロセスの優先度と
cpuの特権レベルを一瞬混同したのは俺だけでいい

>>682
演算の種類によって本当に差が出るのか調べてみたかったわけです

>>683
そんな事はない
このパフォーマンスカウンタは数年前から使っている

>>660
>最初が遅いんだ。

ディスクキャッシュ関連かな
自分もプログラムの速度を検証するときは、最初は除外しているよ

いまだにシングルコア使ってるのか？

マルチコアでもプロセス優先度は全てのコアに掛かるから関係ない
むしろコア一つを優先度無視するように設計するのも手だね

お前ら責任持ってここで暴れてる馬鹿たち引き取ってよ

http://toro.2ch.net/test/read.cgi/tech/1334374186/

>>689
明らかにスルースキルの問題だ。
自分らのごみは自分らで始末しろ。

それにここに来たとして、
「インライン展開でコンパイル結果のコード量が減ることがあるよね」
「そうだね」
で終わり。
オーバーロードのあのケースに、ああいう難癖の付け方をするのが、無能か精神疾患だ。

例えば、
「ARM 向け gcc はベクトルレジスタにそこまでの最適化を施さないから、『俺は』演算子オーバーロードではなく3引数の関数で実装する」
ならいいんじゃないの。

演算子オーバーロードを使わない最適化の上での理由はいくつかあっても、あのスレの議論では全然出てきてない。
理解してない問題にかみつくから「彼」が調子に乗るのであって、まるでお前らの責任。

まるで？

他人事を装ってるが誤魔化せないもんだな

シングルコアですら無かった。

>>686
最低と最高のパフォーマンスを除外して、残りの平均値を取らないの？

中央値と標準偏差とか、他の要約統計量も。

>>694
異常値が両端の一件ずつまでで済むという保証はないのだから
平均値なんか使わずに中央値使え

でもいきなり中央値やモードで比較すると、平均の結果が都合悪いんだろうなと思われてしまう。
外れ値の存在を強調してもいかにも言いわけっぽいんだよ。
まじで困っている

平均値・・徒競争
中央値・・パン食い競争
最頻値・・デカパン競争

>>697
被害妄想だな
つべこべ言わず中央値使え

平均値や最小値・最大値を提示する必要が無いなら、中央値でも良いだろうがね。

時と場合によるわ。

>>700
ベンチマーク測定で最大値なんてただのノイズ
そんなもの提示する必要あると言われる会社なら辞めてしまえ

>>701
つ >時と場合によるわ。

>>702
で、ベンチマークの場合は？

たくさん繰り返されたベンチマーク測定の集計で、
その最大値も大事な情報だから提示する必要性ありなんて主張する奴がいたら
そいつをクビにするよう動くべきだし、それができないならそんな会社捨てろ。

どれか一つ出すなら中央値だな。
もう一つ足すなら平均値。
さらにもう一つ足すなら分散値。
さらにさらにもう一つ足すなら歪度。

最小値と最大値の一件ずつだけを除外する、つまり2件目に異常値を含むことはないと決めつけて、最小値と最大値だけを極端に価値がないものとする>>694みたいな奴もいる。
逆に最小値と最大値を異常値と見なさず提示する必要まで考慮している、つまり場合によっては報告する必要があるだろうと考えるほど最小値と最大値に価値があるものとする>>700みたいな奴もいる。

この両者の両極端は互いに意見が大きく食い違っているが、同じ穴の狢。
算術平均を使うべきではないところで無理矢理使おうとするからそんな発狂を引き起こす。
なぜ無理に算術平均を使いたがる？

GCのベンチマークで最大停止時間も知りたいのに
「中央値取ってきました！最大値？捨てましたよ？」
とか言ってきた馬鹿が居たら首切るよ

>>707
お前はGC書いたことあるの？
最大停止時間を求めるのに実測の最大値を使うとか馬鹿じゃね？

実測値も使いますよ？論文読んだ事無いの？

そもそもベンチマークで期待値が存在しない前提なのが頭おかしい
数学知らんアホだから意味分からんと中央値を妄信してるんだろうな

数学知らん奴は何かと平均値を使いたがるよな

代表値で語るのは分布見てからにせえよ。

分布を把握する手段として代表値を明らかにするんだよ

>>713
平均値や中央値で分布がわかるわけないだろ。中学からやりなおせ。

>>714
誰もそんなこと言ってないのでは？

平均値や中央値だけが代表値だと思ってるのでは

>>715
はあ？713を読めよ

>>716
代表値と呼ばれるものは平均値、中央値、最頻値など。
この他に基本統計量として最大最小値、標準偏差、四分位、尖度歪度などがある。
しかし歪度まで見ても二山分布とかはわからないから、統計を始めたばかりの者は
まず分布を見ろと口うるさく言われたりする。

さて、ベンチマーク結果の話から逸脱してるのは何番の人でしょうか？（１０点）

そもそも、分布を見るとは代表値を見ることに等しいのだが

１６分位とか３２分位を見てりゃだいたいのことが分かる

>>712
代表値を無視して分布を見るのは不可能じゃないか？
グラフで表示したものを見るにしても、それは代表値の表現方法を変えてるだけで、そこで見えてるのも絵にされた代表値だろ？

>>722
標本と代表値を混同してる？

>>723
標本が100万件あった場合
標本をそのままプロットして100万件の点を描画するのではなく
代表値に変換してそれを折れ線グラフで描画するのが普通では？

http://ja.wikipedia.org/wiki/%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB:Normal_distribution_pdf.png

こういうグラフのことか？
こういうグラフならたしかに標本ではなくて代表値を使ってるな

>>694
なんでそこで平均値使いたがるの？
上と下を破棄する考えがあるならその延長線上に中央値があると思うんだけど

>>724
それは統計で言う「代表値」じゃないな。

>>726
素朴な疑問なんだが…。
1秒/2秒/3秒/4秒/10秒の計測値があった場合に「中央値」って、3秒となるの？

>>728
もちろんそうですよ。
明らかに 10 や 1 は異常値でしょう？

メジアンとモードは違うしな

>>727
何言ってんの。
四分位数や十分位数や百分位数など分位数はみんな統計上の代表値。

>>723
普通、グラフで現すのは生の標本そのものじゃなくて集計したデータじゃない？

>>731
集団の傾向を少数(普通は1つ)で代表する値だからこそ「代表値」というタームで
呼ばれているわけで。
百分位が代表値だなんて書いている本どこかにあるのか？
おまえさんの脳内定義じゃなくて。

>>733
四分位や十分位は代表値として良く出てくるけど、
あれは代表値ではないと？

分位数は代表値でそ
どの本にも書いてます

四分位数が代表値ではないなんていう脳内統計学を語る奴には何も教えてやるな。絶対に相手をするな。ここは小学校じゃねえぞ。

分位数は代表値にあらず説が出た時点で退場でしょ

もう元データそのままでいいよ。
N個あれば、N分位数だ。

>>734
>>735
四分位のようなよく使われる統計量を代表値の範疇に含める考え方は
あるかもしれんが、十分位や百分位まで代表値と呼んでいるのは見たこと
ないねぇ。
どの本でもというが、その本では要約統計量ならばすべて代表値としているのか？

>>738
元データが { 1, 2, 5 } の3個の場合、
せめて
0.5 .. 1.5 : 1個
1.5 .. 2.5 : 1個
2.5 .. 3.5 : 0個
3.5 .. 4.5 : 0個
4.5 .. 5.5 : 1個
の5つに分けないと全体の形を正確に知れないのだから、
元が3個でも五分位は必要だ。

>>739
Ｎ分位数のうち、四分位数は代表値になれて、十分位数は代表値になれないという意見なんですね。
Ｎがいくつ以下なら代表値になれるんですか？
そんな話はどこにも見たことがないので詳しく教えてください。

七分位数くらいまでは代表値なの？

統計の本を見てみりゃほとんどの本で「代表値」のところの例に「分位数」が書かれてるはずだがな

>>740
それは分位数を誤解していると思う

くそー、俺が間違ってた。

偉そうな物言いしてごめんな。酒飲んで寝る。

百分位数は代表値として有名だと思ってたが、ひょっとして違う？

ある値が分布のどの辺りにいるかをパーセンタイルで表すのはよく見るけど、
分布そのものを百分位で表すのはそんなにあるかな？

数学知らんプログラマの特徴

1 何かと平均値を使いたがる（極力中央値を使わない）
2 最小と最大の一件ずつを異常値として棄却したがる
3 平均値・最小値・最大値を重視
4 代表値を見ずにグラフを見て分布を把握したがる
5 代表値軽視・標本値重視（代表値を使わず標本値を使ってグラフを描こうとする）
6 分位数に馴染みがない
7 分位数は代表値にあらず説を主張する

>>748
分布形状を人間を介さずコンピュータに判断させるときは百分位数が活躍
ネットゲーの負荷解析で何かの閾値を越えたら異常事態としてアラートを発生させるシステムで重要

>>749
> 4 代表値を見ずにグラフを見て分布を把握したがる

これは無いわー。
アホの中央値信者くんだけじゃね？こんなこと言ってんの。
まあ馬鹿だから中央値しか知らんのだろうけど。

ていうか、平均値とりたがるアホも大概だけど、
アホのお前は平均値が意味をなさない条件すら知らなそう。

>>729
たった5個のサンプルで「明らかに異常値」ですかwwwwww
アホはすごいなー

>5 代表値軽視・標本値重視（代表値を使わず標本値を使ってグラフを描こうとする）

これ何が悪いのか意味わからんわ。

>>753
分布のグラフは、分位数という代表値をグラフ化したものじゃね？

連続値を適当な精度で離散化するのと
分位数の区別が付かないアホが居る事に
驚きを禁じ得ない

目視は重要なんだけどな。
正規性検定が受かってもqqプロットは載せるべきとされてる。
人間の直観はやっぱすごい

>>756
結局は人間の目視を必要とするという考えで作られたシステムとは

例：
全国に大量に配置された地震計のデータを集計し、統計的な処理をした挙げ句、プロットされた絵を担当者が見て「これは地震が発生したな。規模はおそらくマグニチュード△だろう」と判断して、緊急地震速報を発信する

>>756
人間の直観？
人間の直感？

>>757
必要と言うか確認。
逆に、どんな検定でも駄目だったが
ヒストグラムやqqプロットでそれっぽいのでオケとはならない。

人の目が必須デバイスというのは
プログラマっぽいくない考えのような

>>758
今は、辞書的に「直感」と「直観」が同じ意味らしいな。
昔は使い分けろと注意されたものだが。

合計を求めるコード

double sum=0;
for (int i=0;i<N;i++)sum+=a[i];

はNが非常に大きい時、最後の方で大きな数+小さな数となり、
計算精度が落ちてしまうと思うのですが、これを回避するアルゴリズムを教えてください。

>>762 ソートして小さい方から足していく

sum=0;
d=0;
t=0;
for (int i=0;i<N;i++){
t=(a[i]+d)+sum;
d=(a[i]+d)-(t-sum);
sum=t;


for (i = 0; i < N; i++) {
t = s + (f[i] + r);
r = (f[i] + r) - (t - s);
s = t;
}

多倍長整数を使う。

もう、一文字とか文字列とか
そんな概念ある言語なんて終わってる
終わりすぎてるってことにいい加減気づけよ
極左かお前らｗｗｗｗｗｗｗｗｗｗｗｗｗｗ

>>762
そこまで分かってるんなら、配列分割して、それぞれの合計を足し合わせれば良いじゃない

浮動小数点数を理解してない奴はレスしない方がいいと思う

>>762
a[]をソートして小さい方から足せば桁落ちは最小限に出来る

絶対値の大きい方から足していって、絶対値が充分小さくなったら打ち切る。
精度は落ちるが高速だぜw
つーか、単に「ソートして小さい方から」だと拙い。

>>770
お前は科学技術計算プログラムは作れないな

単純に小さい方から足すだけだと、Nが大きすぎるとダメだね。
doubleの精度で問題になるほどNが大きかったら全部足すのは
無駄だとは思うがw

ソートして小さいほうからがつたないってのは、
絶対値の大きな負数のことを考慮していないって言いたいんだと思う。
精度は落ちるが高速って書いてるからちゃんと分かってる人なんじゃないかな。

引き換え、Nが大きすぎると小さいほうから足すだけじゃだめだという意見はよくわからない。

ソートされた100件ほどの数値の配列があり、与えられた値をランク分けするために
この配列のどの位置に該当するかを求める処理があります(std::lower_bound()のような)。
これまではバイナリサーチをしていたのですが、SSEを使って高速化できないかと考えています。
SIMDに適したサーチアルゴリズムなどはないでしょうか？
なお、テーブルは変化しませんので構造を変えてもかまいませんが、入力の方は事前に
ソートなどを行うことは難しいです。

>>774
100件ぐらいしか無いんだから確実で簡単なハッシュ関数作るとかは？
「数値」たって範囲も何も分からんが、バイナリサーチで困るほどなのか……

配列はランクの境界値で、間隔も一定ではありませんので、一致比較ではなく
どうしても大小比較する必要があります。
バイナリサーチよりさらに高速化したいというのは、単に入力が多いためです。

もうちょっと詳細知りたい……
入力のサイズとか型とか(整数か実数か、とか)範囲とか
ビット演算とかバケットソートとか、どんな手段が使えそうか分からないとヒント出しようがない

ボトルネックが違う悪寒。

>>777
扱う数値はshortあるいはfloatで、入力は数百万件あります。
スレッドを分割したりしてはいますが、どうしても1秒を超えるくらいの時間が
かかってしまうので、SSEを使ってあと4倍かせめて2倍くらい速くできないかと
考えています。
質問したかったのは、SIMDに適したサーチアルゴリズムがないかということです。

数百us単位のスループットが要求される処理のソフト化を試みています。
その過程で分かったことを以下にまとめます。
間違っていないでしょうか？

■WindowsAPIやDirectXなどのAPIは、カーネルモードへの遷移が必要なため、
大きなオーバーヘッド（数千クロックオーダー）が生じる。
DirectXではドライバへのコマンドをある程度キューに蓄積しておき、
まとめて送ることでオーバーヘッドを低減している

■マルチタスクOSでは、単一のプロセッサでプロセスを切り替えて実行
（コンテキストスイッチング）させている。
これはマルチスレッドプログラムにおけるスレッドの切り替えでも発生する。
現代x86CPUはハードウェアによるコンテキストスイッチングを搭載しているにもかかわらず、
Windowsでは技術的な事情からソフトウェアによるコンテキストスイッチングを行っているため、
オーバーヘッドが大きい。
CPUに搭載されている物理コア数に応じたスレッド数を立ち上げて処理させる場合、
コンテキストスイッチングは（他プロセス（ここでは相対的に低負荷とする）との切り替えを除いて）
必要ないはずであるが、実際はコア数に比例したパフォーマンス向上が見られないことから、
なぜか不要なコンテキストスイッチングが働いている。

ちなみに、何千、何万というスレッドを扱うGPUではハードウェアによる1クロック切り替えを行っているので
オーバーヘッドはない。

■SIMD演算もマルチスレッドと同様に（粒度は異なるものの）並列演算手法の一つであるが、
コンテキストスイッチングが発生しないため、並列化数に比例した（場合によってはそれ以上）の
パフォーマンス向上が得られるため効率が良い。

>>780
色々微妙。一番の問題点だけ指摘。
不要なコンテキストスイッチングが発生していないとしても、
コア数に比例したパフォーマンス向上が得られると期待できるケースは稀。

>>781
ループ間でのリソース競合がない完全に独立した並列処理（例えば配列要素同士の演算）でもでしょうか？
そのような処理を試しても、並列数（物理コア数）に比例した性能は得られませんでした。

>>780
＞数百us単位のスループットが要求される処理のソフト化を試みています。
どう見ても主目的は別。
うせろ。

Windowsと一口に言ってもバージョンによって違うしな。
Windows7(64bit)だとcore数に対してほぼリニアに性能が出た。10%くらい誤差は
あるだろうけど。
逆にSIMDはコンテキストスイッチのオーバーヘッドがないと言っても、処理内容に
よってはそれ以上にプログラミング上のオーバーヘッドが大きかったりして、
演算器の並列数だけきっちり性能が出せる条件は限られる。

>>784
自分が試した環境はWindowsXPでした。
Windows7では改善されているんですね。
SIMD化に関するご意見は承知です。
SIMD演算に持っていくためのデータ構造の変換等が避けられないケースがありますし。

ハイパフォーマンスなプログラムを目指す上で、
本質とは関係ない処理をいかに避けるかが課題となるので、
プロファイラを導入するなどして問題個所を潰していきたいと思っています。

>>779
ソートされてて数百万件あったらバイナリサーチが速いに決まってる。
ただ、事前に（例えば）千件ごとに抽出したテーブルを作っておいて、そこから探すというなら、SIMD最適化の余地もあるかもしれない。
最適化であって、サーチアルゴリズムと言うわけじゃないけど。
そしてそれでも、キャッシュメモリの効率を考えると、バイナリサーチより速くなるかは疑問だ。
最適化ってのは例えば 32 回とかのループアンロールして、それを SIMD 並列化ね。

あとは、最近検索された結果を覚えておいて、それをソートしておいて、バイナリサーチすることで、事前に範囲を絞り込める。
検索される値に偏りがあるなら平均時間が改善されるだろう。

最後に、データベースがメインメモリになければ SIMD で最適化する余地はほとんどない。
そして本当にメインメモリにあってバイナリサーチしてるのに1秒もかかるなら検索の問題じゃない。プロファイラなどを試すべきだ。
試しに 1GB の float 配列を全探索するとウチの PC で0.5秒位。バイナリサーチなら数マイクロ秒。

>>786
いえ、そうではなくて、100件ほどの配列のサーチを数百万回行うということです。
最初はバイナリサーチをそのまま並列化しようとも考えましたが、配列を参照する
部分が並列化できないので他に良いアルゴリズムがないか探しているところです。
見つからないようであれば、最初の考え通り比較のみの並列化でやろうと思いますが。

キャッシュ化とかできないの？

その変化しないテーブルが本当に不変なら、
if ( x < 100 ) {
&nbsp;if ( x < 50 )
&nbsp&nbsp&nbsp...
else {
&nbsp&nbsp&nbsp...
というように全部展開してコンパイルしたら多分速くなるし、並列化の効率も上がるだろう。
short なら結構期待できるし、float でも正の数しかないなら浮動小数点数表現を int で比較できて結構いけるかも。
SIMD 最適化は、SSE だとレジスタ少な過ぎて速くならないのではなかろうか。
GPGPU は案外いけるかも？
いろんなアイデアがあるが、他のことが分からんと、これ以上はなんとも。

バイナリサーチを即値でやるだけに見えるけど、SIMDでどう並列化できるんだろう？

値とインデックスをひっくり返したハッシュとか作ればよかったのではないの？

SIMDは基本ベクトル演算なわけで、定型的な単純な処理を多数行うのが得意なだけ
一回の計算あたりのクロック数は減らせても
アルゴリズムの計算量（オーダー）自体を少なくするわけではないから向かないよ

SIMD以外なら
・入力に偏りがあればバイナリサーチの分割点を調整することで速くなりそう
・値範囲がそれほど大きくないなら全範囲を展開したランクテーブルを表引き
　例えば0-7の値範囲に対し[0,3,5,6]というランクテーブルを[0,0,0,1,1,2,3,3]と展開
・ >>786 が言うようにループアンロール
・バイナリサーチの範囲をMSB等で最初に絞る方法
　例えばMSB4bitに対する上下範囲を16通り作っておいて、バイナリサーチの初期値にする。

さすがにSIMDでオーダーが変わると考えるプログラマはいないだろう。

ヒープソートみたいなアクセス方法の4分木や16分木使えばいいんじゃない？
ソートされた木なら比較結果をhaddでまとめて子世代のインデックスを計算すればいいと思うよ。
末端の無効な要素は最大値でも入れときゃなんとかなりそかな。

>>792
昔マンデルブロ集合計算するプログラムで、計算の終わった要素だけ順次差し替えてく方式を試したことがあるよ。
入れ替え処理は重いけど、普通SIMD化する場合は全要素の計算が終わるまでループするからトータルでは速くなった。
単純な処理でなくてもコストに見合う効果が得られる可能性があるから考える価値はあるよ。
実際は難しいケースが多いだろうけど。

数百万件の入力を最初に16分割するのにならSIMD最適化の余地があるのでは。
その分割されたレコードがある範囲について数千件程度たまるたびに、その範囲内での正確な位置を検索するスレッドに投げる。
まあ、単に今のをスレッド分割するのに比べて、労力に見合うほどの効果があるかは疑問だけど。

100分割の範囲特定なら7回アンロールして途中の条件分岐排除したほうが速いんでない？とは思う。

今時のマルチコアCPUで数百万件の処理に1秒かかるのかなぁ。
4GHz1コアで4百万件のデータでも1処理あたり4.0e9/4.0e6/7=140クロックも必要ないと思うんだよね。
ひょっとしたら再帰使ってたりだとか、分割するところでcmovみたいな計算型の命令使わずにブランチ使うコード吐いてて
大量の予測ミスが発生してたりとか・・

三年前の i7 950 3GHz で、128要素の float 配列に対して 400万回の std::lower_bound() を行って0.25 秒位。
VC++2008 /O2。最適化なしだと 0.7 秒程度。
ちなみに単純に8000ループごとにスレッド分割するだけで倍速以上になった。

さらにSIMDで4要素まとめて処理できそうだな

できそうなんだけど、それをどういうアルゴリズムでやればいいかわからん、
てのが元の質問だろ。
俺もわからんが。

アルゴリズムもなにも4要素丸ごとcmpgtpsでマスク生成してptestやるだけですがな
何番目の要素がヒットしたかは、pmovmskbで汎用レジスタに転送してbitscanすればわかる

こんばんわ。

>>800
それって比較だけだよな。
次のインデックスを計算して比較対象をセットする部分はシリアルにやらざるを
得ないんじゃないの？

そういうのはHaswell以降（vgather系の命令）にならないとだめなんじゃないの？

Haswellの新命令一覧ってどっかにない？

1ノード4要素の木?

そもそも目的はなんだ？
ソートって本当に必要？

合計値の誤差を減らしたいだけのためにソートなんて必要無いぞ。
単精度なら倍精度、倍精度なら多倍精度に変換してから加算すればいいだけだろ？

ああもちろんソフトウェア多倍精度は遅いかもしれないが、たいがいDRAM帯域のほうがネックになるからｗ

簡易的には指数オーダーごとにグループをわけて加算するのが低コストかもね

もちろんこれもSSE*がつかえる。
値をブロードキャストしてcmpXXps/pdでビットマスクして論理和とってから加算すればいい。

>>806
数百万個の値を、100程度の区間に分類したいんだと。
分類してどうしたいのかは知らん。
数百万個のレコードを個別に何かするのかもしれないし、個数が必要なだけかもしれない。

正直何がやりたいのかハッキリ言わなきゃわからんな

とりあえずいまどきのマシンはSIMD化よりもまず先にメモリ読み書きを最小限にしたほうが性能出ると思う。

いきなり合計とか誤差とか出てきて何かと思ったら、>>774のソートの質問と
それ前の合計を求める話を混同してるんだな。

最適化しすぎてうっかり必要な命令を削っちまったんだろうな

>>809
質問者は>>774,776,779,787かな。

以下のコードをVC++2012でコンパイルすると一回の検索が30クロックちょとだったから、
>>797の人のstd::lower_bound()より約6倍高速。
ただし、データ数が2のべき乗の制限があるから余ったところはFLT_MAXでも詰めとく必要があるのと、
VC++2008や2010のfloatでは分岐のあるコードになって半分の速度になって、
逆に整数だと2008や2010の方がこれより5倍近く速くかった。
2012はflotat・intどちらもcmov使ってるけど、最近のCPUはcmov遅いからその影響みたい。

float&nbsp;*top&nbsp;=&nbsp;array;
float&nbsp;key,&nbsp;cmp;
int&nbsp;nelm&nbsp;=&nbsp;128;
int&nbsp;half;

half&nbsp;=&nbsp;nelm&nbsp;>>&nbsp;1;

/*&nbsp;ここからコピペで7個ならべる&nbsp;*/
cmp&nbsp;=&nbsp;*(top&nbsp;+&nbsp;half);
top&nbsp;+=&nbsp;(cmp&nbsp;<=&nbsp;key)&nbsp;?&nbsp;half&nbsp;:&nbsp;0;
half&nbsp;>>=&nbsp;1;
/*&nbsp;ここまで&nbsp;*/

特殊文字変換で変になっちゃた。

float *top = array;
float key, cmp;
int nelm = 128;
int half;

half = nelm >> 1;

/* ここからコピペで7個ならべる */
cmp = *(top + half);
top += (cmp <= key) ? half : 0;
half >>= 1;
/* ここまで */

> 2012はflotat・intどちらもcmov使ってるけど、最近のCPUはcmov遅いからその影響みたい。

それ毎回ランダムな値で検索してる？
float配列の値に対して比較値の分布は均等になってる？
もし偏りがある状態で反復してみて分岐したほうが速いといってるのなら計測方法見直す必要がある。

ところでcomiss + jcc ってMacro OPs fusion対応してたっけ？

>>815
2010の整数はsetとdec使うのに対して2012はcmovなので遅いということで
float・intとも分岐の方が遅くなってます。

>>799,802
SIMD化するとしたら木を浅くするのが効果的だから、_mm_sad_epi8(comp_result, zero)とかが使えるだろう。

comiss + cmovかな？
cmovを使わない方法があるとすれば、cmpssでall 1 or 0のビットマスク作って
汎用レジスタに転送（extractps or movd)してandとって加算かな。
何となく遅そうだ。

>>817
2012はその組み合わせになってた。
普段のマシンはcore 2だからデコーダの制限でcmovが遅くなってるのかも。
昔は1クロックで実行できてたんだよね。
2012でcmov使うようになったのは/arch:SSE2が標準になったのとネハ以降が主流になったからかもね。

ルンゲクッタをSIMD化する良い方法があったら教えてください。

数独ギバー＆ソルバー
http://katahiromz.web.fc2.com/sudoku/
これを高速化する方法を教えて下さい。お願いします。

それ、ビットボード使えないかなあと思った事がある。
81ビット×9でボードを用意して、それぞれのマスの１〜９の可能性をビットで表現する。

これならビット演算だけで可能性をマスクする事ができる。

bsrとかbsfで検索すると数独とか将棋の
AI関連のページがやたらと引っかかっていた古き良きSSE2時代

誰か知ってたら教えてください。
コードの質問に関係する部分は

unsigned __int64 point;
unsigned __int32 bit;
〜中略〜
//point = 1ull << bit;
point = 0;
_bittestandset64(&amp;point,bit);
でこれをコンパイルして
xor ecx, ecx
bts rcx, rax
の様になるようにはどうすればいい。
当然bitは0〜63の範囲内に入ってます。
__assumeは既に試してみてます。
コンパイラはVS2010、2012で試してみました。

iccなら最適化うまくいくのかな？

ttp://technet.microsoft.com/ja-jp/subscriptions/z56sc6y4.aspx

>>824

情報ありがとう。でも2010のそれに相当するページを見ていた。
問題はbtsのdestにメモリを使ってしまうことが問題。

thats shitty japanese

unsigned __int64 point;
unsigned __int32 bit;
〜中略〜
point = 1ull << bit;
if (!(amp & point))
point = 0;

例示したコードにごみが入ってた！

正しくは
unsigned __int64 point;
unsigned __int32 bit;
〜中略〜
//point = 1ull << bit;
point = 0;
_bittestandset64(&amp;point,bit);

やりたいことはもともとあった
unsigned __int64 point;
unsigned __int32 bit;
〜中略〜
point = 1ull << bit;
を高速化したい。
ターゲットCPUはSandy Bridge以降。

お願いします。

またごみが入ってる！amp;は無視してください

2ちゃんねる用ブラウザ「ギコナビ」 Part64
ttp://anago.2ch.net/test/read.cgi/software/1350168418/64

64 名前：名無しさん＠お腹いっぱい。 [sage]： 2012/11/08(木) 18:52:58.35 ID:fox14i8S0 (3)
>>63
レスエディタのメニューから特殊文字変換の下の「Space/Tab→&amp;nbsp;」のチェックを外してください

inline
iint64_t
hoge(int bit)
{
static unsigned int64_t _hage[64]=
{
1,2,4,8,16,32,64,128,以下略
};

return _hage[bit];
}

>>831
ありがとうございます。
試してみたところ状況によって速くなったり遅くなったりでした。
他の箇所の最適化をしてみてからまた試してみたいと思います

>>831 const使えよ

constつけたら、早くなるのけ？

constをつけないstatic変数はwritableなグローバル変数と解釈されるよね。
スコープは閉じててもポインタかなんかでアクセスしようがあるから勝手に定数化できない。

constをつければ定数領域からアクセスするだけのコードになる。
x64のバヤイこれだけですむ。_hageはRIP相対の32ビット値。

hoge:
　　mov rax, [_hage + rcx*8]
　　ret

んでもってconstになってないと、C/C++ランタイムのスタートアップルーチン（main関数より前の）で
_hageの値を定数領域からwritableな領域にコピーやったりするかもしれない。
これが無駄。
もし逆アセンブルやる機会があったら調べてみて。

ワンチップマイコンだと高速化のためにテーブルを多用するケースがあるんだけど
constならROM化できるというメリットがあるんだわ。
ROMはある程度余裕あるけどRAMリソースは限られてるから書き換える必要のない値は
なるべく固定にしてしまったほうがいい。

チンピラに煽られるとは思わんかった、それも、即興で書いたもんに

ROMとRAMのアクセス速度の違いを無視してROMから
読むだけだから速いってのは…

内蔵ROMよりRAMのほうが速い実装なんてあるの？
CUDAでも定数メモリ（デバイス側から見れば一種のROM）はシェアードメモリ（RAM）より高速で
容量も大きいからパラメータは極力定数化したほうがいい。

しかしstaticでメモリを確保すると、プログラムが動いている間ずっとwritable領域に全てのデータを
配置しておかないといけない。

ランダムテーブル参照に使う配列はともかく、x86は単一の64ビット固定値程度なら
イミディエイト値として命令ストリームに埋め込むことができる。

EEPROMって、書き込みが遅いのはともかく、読み出しも遅くなかった？

マスクROMのつもりで書いたんだが・・・
どっちかというと速度云々よりRAMの容量の制約という観点で考えて欲しい。

const修飾がついていようがいまいが、どのみち配列はメモリに展開するかもしれない。
別にRAMのほうが速いならそれでもいいんだけど、必要なときに読み出せばいいでしょ
ただのstatic修飾だとプロセスが動いている間【常に】メモリに配置されてるということが無駄なわけよ。

SRAMでも書き換える必要ないものならCPUコア側からみてRead Onlyで使われる。
（CUDAの定数メモリがそうだしL1Iキャッシュもそう）

CUDAのコンスタントメモリってFermiでなくなってなかったっけ？？

そんなに切迫しているのか。
組み込みのRAMってどのくらいのサイズなの？
SoCで512バイトって聞いたことあるけど…。

Cでいうローカル変数なんか注意しないといけないし、
関数コールのネストも計算しないとならないですね。
メモリはローカル変数無しのグローバル変数のワークエリア
使いまわしかな。
動きはROMのテーブルか処理(コード)で実装しなければならなさそう。

ああ、512バイトとか、ここまで来たらスレ違いかな。
mallocなんかとても使えなさそう。。

AVRでメモリ0バイトでレジスタが32個だけてのもあったぞ
Ｃコンパイラの対象外だったけどな、128バイトのモデルからは使える

>>842このスレ、
main以外★mallocの後にfree不要と言うバカいるの？
http://toro.2ch.net/test/read.cgi/tech/1352812333/
と勘違いしてた。。(恥ずかしい)

>>843
レジスタ32個ですか。
8ビットだとすると32バイトのRAMと考えられなくも
ないですが…、すごい世界ですね。
ありがとう

自分もRAM128バイトのRISC CPUで仕事したことある

> 内蔵ROMよりRAMのほうが速い実装なんてあるの？
９０年台のパソコンはBIOSのROMをメインRAMにコピーして、アクセススピード稼いでたの知らんのけ？

先日、組み込みの仕事を受けたら、対象機はItaniumだったでござる
VMSは癖があるなぁ

CUDAの定数メモリを持ち出してるくせにマスクROMのつもりとか…
専用のキャッシュを持った定数メモリを持ち出して速いとか…
しかも速度の話からRAMの容量の話にすり替えちゃってるし…

アフォが沸いてるなぁ

> CUDAの定数メモリを持ち出してるくせにマスクROMのつもりとか…

CUDAの定数メモリの実体はSRAMだが、CUDAコア側からの書き戻しがされないことが
保障されているから速い。
Writeに割かない分Readに帯域を割いているからね。

コア側からは読み出さないことで一種のROMとして使ってる。
EEPROMだって書き換えを頻繁にやらないからROMだと言ってるだけで実際は不揮発性のRAMだろ？ｗ

普通のPCのアプリの話をするなら、いったんRAM上に展開されて実行される。
でも全部がアプリケーション側で書き換えできるわけではない。
.rodataや.textは読み出し専用のセクションだ。

> しかも速度の話からRAMの容量の話にすり替えちゃってるし…

容量については最初の最初っから言及してましたが？↓

> ワンチップマイコンだと高速化のためにテーブルを多用するケースがあるんだけど
> constならROM化できるというメリットがあるんだわ。
> ROMはある程度余裕あるけどRAMリソースは限られてるから書き換える必要のない値は
> なるべく固定にしてしまったほうがいい。

別に組み込みに限らずconst指定をサボるのは良くないよ。
定数が重複する場合、コードサイズの最適化で1箇所にまとめてしまうようリンカに指示することができるが、
書き換え可能な静的データとして配置されている場合、いくらデータが重複していても纏めることができない。
プログラムサイズが肥大化することになり、結果的にキャッシュのヒット率など速度面にも悪影響を
及ぼす可能性がある。

とはいってもx86の場合は定数データが重複していてもコードのディスプレースメントフィールドが
8ビットに収まるなら結果コードがコンパクトというケースもあるので一概に重複を排除しろとも言えないが

>>849
無能自慢してるのがまだわかってないの？

>>850 おまえがな

組み込みのマイコンが逝ってる系だけとでも思ってるんかね

単語知ってる自慢をもっとやってよ

書き換えないテーブルにconst修飾子を使うべき理由を一例として述べてるだけであって
別にそれが全てではないのも事実ですな
ROMよりRAMのほうが速い環境があるからといってconst指定が不利になる理由はないはずですが
（というかRAMにプログラムを読み出してくるのはどのみちROMなりストレージなんですけどね）

つまらない揚げ足とりに終始して自分のミスを誤魔化そうとするのはみっともないです。


逆に、ROMよりRAMのほうが速いと、定数配列をstatic constではなくmutableなstatic変数として
用いたほうが有利なんですか？

パソコンならconstあるなしで速度はあんま変わらんのと違うか？
constあるなしで実行コードの最適化した汗比較してみたけど、変わらんかった、gccは
パソコンなら変数は実行前に配置されてるでしょ
関数内で宣言してるから、外から書き換えられることはない
タンゴはグローバル変数が好きなの？

const が駄目なんて一言も言ってないぞ
const 付けた方が速いから付けろって言ってるから突っ込んだだけ
const 付けた方が速くなる環境もあるかもしれないが、それが const を
付ける本来の理由か？
const 付けたら絶対速くなるのか？

> 関数内で宣言してるから、外から書き換えられることはない

とはいってもポインタでアドレス取ってくればアクセス可能なので、constにする以外で
外部から書き換えできないことが言語仕様上保障できないのがC/C++の制約ですよ。

ある程度共通で使ってる定数配列なら必要に応じてグローバル化するけどね。
たとえば別の関数で全く同じ定数テーブルを使ってる場合はテーブルを共通化したほうが
キャッシュの効率が上がるはずだ。

constにしたほうが「速い」なんて一言も言ってないのですが
constにしない理由はないし、しないことで不利なケースのほうが多いだけで。

自分で暴走するもん作ってますって逝ってないかい？

外部から書き換えられないことが保障できないというのは
同じプログラム内の別の場所に同じようなデータがあっても
書き換えによって別々の値を持つ可能性があるということ。
初期値が同じだからといってテーブルを1つに纏めるような最適化を
コンパイラ・リンカ側でやってくれない。


LUTを使った最適化でのパフォーマンス低下の最大の原因はキャッシュミスだ
十分なプロファイリングをしたうえで本当に全体性能に影響があるかどうかを検討したうえで使う
1割未満の使用率の関数で安易にLUTを使うのは感心しない。

タンゴ自慢もっとやって

>>858
>>834 に対して >>835 は何？
速度に対する話でしょ

お前の言ってることは
const にすれば ROM化出来る
ROMの方がRAMより速い（アクセスするコードの話も含めて）
だから const 付けろ
これをグダグダ言ってるだけじゃん

速度の話じゃないとしたら
>>838 の「内蔵ROMよりRAMのほうが速い実装なんてあるの？」は
どこから出てきたの？

>>854 の　「つまらない揚げ足とりに終始して自分のミスを誤魔化そうとするのはみっともないです。 」を
そっくりそのまま返してやるよ

片山がconstを使えと言ってるからそれに対してその理由をフォローしただけだけど？
「早くなるのけ？」（速くではなくて？）の回答は環境に依存するが、
少なくともconstを付けたら遅くなるハードウェアなんてものは知らない。

> んでもってconstになってないと、C/C++ランタイムのスタートアップルーチン（main関数より前の）で
> _hageの値を定数領域からwritableな領域にコピーやったりするかもしれない。
> これが無駄。
> もし逆アセンブルやる機会があったら調べてみて。
>
> ワンチップマイコンだと高速化のためにテーブルを多用するケースがあるんだけど
> constならROM化できるというメリットがあるんだわ。
これが速度の話じゃ無いとは思わなかったわ

最初っからメモリサイズの問題に言及してるだろ

まぁ、つけられるconstはつけておけってこった。

> メモリサイズの問題
?

constをつけるべき理由を勉強しなおしてからおいでください

知ってるタンゴがつきてきた？

言ってることを理解しようとしないやつに何を言っても無駄です。

書き込み禁止の意味
link時の配置が通常の初期化付き変数と違う場所になる

関数内でstatic宣言した変数を書き換えられる腕をお持ちの方には参りました。

// 普通にできるだろ。
int * func()
{
static int static_var;
printf("%d\n", static_var);
return & static_var;
}
`
int * tmp = func();
* tmp = 1;

そういう関数じゃないんだけど、話題になってるのは

>>872
お前のせいで台無しだ

>>871
> link時の配置が通常の初期化付き変数と違う場所になる

とは限らないが、.dataと.rodataで配置を分けるから結果的にそうなることが多いかもな
よーするに理屈を全然理解してないのね

>>872みたいに関数内で定義したstatic変数を外部から書き換えできるような関数なんていくらでも作れるし
実際にあるんだよね（C文字列を返せみたいなのは特に多い）
外部参照を意図したものかそうでないかをコードの流れを読んでコンパイラが判断するのは難しい。

>>873
そういう関数と>>831の関数でのstatic変数の使われ方の意味を処理系が容易に判断してくれるとでも？


というか俺的には>>831の一番の突っ込みどころは、CPU組み込みのビットシフト命令は0-63以外の値が
与えられても通常安全だが、そのテーブル参照に置き換えるとページ違反になるかもしれないことね。
俺なら最初に bit &= 0x3f; とでもやっておくわ。

あと容量の問題についてもう少し言及しておくと、inline関数は通常ヘッダに書くものだが
そのヘッダをincludeしたソースごとに_hage[64]の実体が定義されることになるかもしれない。
これが大きな配列だと結構問題になる。




で、肝心のが速いかどうかについてもう少し。
命令のレイテンシを考えればshl rax, clよりmov rax, [mem]が速いわけがないんだが
Sandy Bridge以降ではロードユニット2本あるからシフト(ユニット1本)よりスループットが
稼げるケースも存在しなくはない。
その辺の理屈まで説明できないと片手落ちだわね。

超単語、乙

あれここで教えられたコードってconstついてなかったのね。
一目見てルックアップテーブルと認識したから
テストしたコードではconst付きで試しています。
ちなみに前提条件としてbitは0〜63に限定してるので
(デバッグビルドではそれ以外の値が来た時点でassertしてる)
テーブル参照でも問題ありません。

むしろ_bittestandsetで何か問題あったのか問いたいね。
VCの組み込み関数って値を2個以上返す命令は一方の値をポインタで受け取るようにはなってるけど
最適化でレジスタ渡しになるのでストア命令が生成されることはないと把握してる。
オプションは /Ogty になってる？

IACAとかでプロファイルとってみて、btsを発行してるポートがボトルネックになってて
Loadユニットに空きがあるようなら部分的にテーブル参照に置き換えてみるのもいいと思う
→えいちてぃーてぃーぴー://software.intel.com/en-us/articles/intel-architecture-code-analyzer

問題はストア命令が生成されること。
オプションは /O2を指定してるから問題ないと考えてる。
msdnによると等価オプションに/Og,/Ot,/Oyが含まれてるし……

bittest系の命令はsrcに64以上の値が来た場合、
destで指定されたアドレスからsrcビット目のデータを見るから
うまくコンパイラにsrcが0〜63であることを伝えないと
レジスタ渡しになってくれないみたい。

今日、constを付けたり外したりして試してたら、
基本的にはconst付けたほうが速かった。
割と分かりやすいレベルで変わったな。

__m128に付けたら遅くなったりした。

>>879
＞destで指定されたアドレスからsrcビット目のデータを見るから
＞うまくコンパイラにsrcが0〜63であることを伝えないと
メモリオペランドでもオペランドのサイズ自体は変わらないから関係ないでしょ。
__assume(bit >= 0 && bit <= 63);とか入れてみても影響ないね。
レジスタだと不都合があるとも思えんし……
コード生成のバグ？なのかね。

> __m128に付けたら遅くなったりした。
これ興味深いな。何故だろう?

>>881
Intelのマニュアルを見れば分かるけどメモリオペランドと
レジスタオペランドで動作が違う。
レジスタオペランドだと剰余を求めてみるビットを決めるが
メモリオペランドだと、例えば6400あたりが渡されたとすると
800バイト先あたりの値を見る。

>>883
おぉ、マニュアル見たら確かにそんな挙動になってるね。
__assmumもダメならVCでは無理なんじゃないの？
_bittestandset64を3つ並べたらleaまで3回出力されてたよ。

もう少し詳しく書くと、
クラスのメンバ関数内でローカル変数でconstで指定してたある変数を、他のメンバ関数と共有したくなったので、
クラスのメンバ変数（constなしでコンストラクタで初期化）にしたら遅くなった、ということ。
同じ場所でconst外すのも試しとくべきだったな･･･。

スタックからヒープに移ったって話じゃないかよう

ヒープって遅いんすね･･･

m |= 1 >> n;

みたいな式で勝手にbtsに展開してくれるのが理想なんですけどね。
ちなみに x << n | x >> (64-n) なら大体のコンパイラでrotlに展開してくれたけど

1 << nですた

rotにならない助けて

単純にスタックだとcallされた時点で参照される→キャッシュラインに乗る率が高くなるからな

gcc 使えよ。
vector_size とか便利すぎる。

突然ですみません。
VC2010ExpressとIntel Composer XE 2013(体験版)とで実行時間を比較していたのですが、
前者で/O2のみ付けて生成した実行ファイルだけ異常に遅いという現象が発生したのです……。

プログラムは、ヒッチコック・ベアストウ法に従ってn次方程式を解く時間を計測する、といったものです。
計算量のオーダーはO(n^2)になるはずなので、条件を変えつつ平均計算時間を測定していました。

実行バイナリは、
VCの方で「/Od」「/O2」「/O2 /arch:AVX」、
ICXEの方で「(引数無し)」「/QxAVX」の
5パターンを試しました。

「/Od」>>「/O2 /arch:AVX」までは予想通りだったのですが、どうも「/O2」のタイムが振るいません。
具体的には、2000次方程式を100回解いて平均時間(ミリ秒)を出した際に、
それぞれ「312.78」「478.93」「10.24」「11.39」「11.32」となりました。
いくらなんでも「/Od」より遅いとか異常です。

ソースコードと各実行ファイル、測定条件・時間や自環境を記したテキストを以下に配布しますので、
どなたか速度低下の原因を考えてくださいませんか……？

ファイルURL：http://www1.axfc.net/uploader/so/2798834.zip

>>893
まずは結果が一致しているのか確認してみては

>>894
確認しようにも、乱数を元にした初期化を使っているので、単純な比較ができないんですよね‥…
外部ファイルを読み込めるように修正してから再度チェックするべきでしょうか＞

乱数の種、同じにしたら毎回同じなのでは？

>>896
あ、その手がありましたか。早速試してみます。

コンパイラが違うと同じとは限らんな

毎回同じ乱数を生成する my_rand(); を作るべし

コード中、「srand((unsigned)time(NULL));」となっていたところを
「srand(765);」と書き換えて、再度計測しました。結果、
size　　　Od　　　O2　O2AVX　　 icl　　　iclAVX
500.　 　 4.54　. 12.98　1.51　　　1.63　　　1.69
707　　 13.63　. 43.47　1.99　　　2.22　　　2.24
1000.　 34.67　121.20　3.16　　　3.48　　　3.44
1414　113.17　245.40　5.57　　　6.22　　　6.26
2000　303.54　432.40　9.79　.　11.03　.　11.02
(100回平均。単位はミリ秒)
また/O2だけ遅いです……。

最適化と相性が悪いんだろうかね

/O2 = /Og /Oi /Ot /Oy /Ob2 /Gs /GF /Gy
らしいので、どれが悪さしてるか調べてみたら？

こんなことあるんだなぁ･･･。