プログラムの高速化について語る

おい，貴様ら！

速いプログラムをつくるテクニックを教えて下さい。

2ｹﾞﾄｽﾞｻﾞｰ

迷ｽﾚの予感

ＣかＣ＋＋でよろしく

そのまえに、4X4行列の逆行列をおしえれ。

アセンブラオンリーで作れ

一．あせんぶらで
るーぷをけずる
一．いんてるしーこんぱいらで
さいてきかこんぱいるする

>>4
そんな小さい行列 高速化するまでもなし
普通にガウスで解けば？

>>6
追加ツッコミ
ループアンローリングすれば削らなくてもそこそこ速くなると思われ

>8哀れ…

めんばへのあくせすはやくするほうほうおしえて

propertyを使う

>>11
ＶＣ＋＋でも使える？

>>12 VC++はその代わり　インライン最適化がそれなりに頑張るから大丈夫
　ツールに応じて上手に設計しなさい

2:8の法則
８割の時間を消費している２割のコードを探す。

メンバ変数をforの判断文に使わない

>>http://www1.odn.ne.jp/synsyr/prog_opt0.html

profileしる!

・遅くないなら速くしようと思わない
・自分で下手にアルゴリズムを発明しない
・予想外に遅いならソースを一度捨てる

>>http://sies.tjsys.co.jp/product/ghs/c/1.html
これってVC++にもあてはまるのか

>>17
profile?

>>19 の続き
特に1.3のところ

>>4
ウィノグラード法を使えば速くなるかとほんのり思う
無理かな

>>20
どこが実際に遅いのかを計測しろってこと。
計測するツールはプロファイラっていう。
ソース見て遅そうとか思っても実際にそれが足を引っ張ってるとは限らない。
呼ばれる回数その他の条件によるし。
>>14 と重なるが。

で、足を引っ張ってる場所が分かったら
まずはアルゴリズムを見直す。処理量自体を削減するのが吉。
どうあがいても理想的な最小の作業しか処理していない様子になった上で
まだ遅いのなら、またプロファイルしてその時点で一番足を引っ張っている場所を再チェック。

すでに最小限の処理らしい場所が遅い原因となってしまったら、やっと小手先最適化スタート。
場合によってはアセンブラの特殊命令使うとかね。

Standard Edition だからプロファイラ使えない
鬱だ死のう

悔しいからストップウォッチで測るYO

void StartTime(void)
{
cout << "計測開始" << endl;
tTemp1 = clock();
}

double StopTime(void)
{
double tTemp2 = (double)(clock() - tTemp1)/CLOCKS_PER_SEC;
cout << tTemp2 << " Sec." << endl;

return tTemp2;
}

あ，グローバル付け忘れ

clock_t tTemp1;

vtuneつかうとか。
＃Stdでつかえたっけかな？

VS.NETBetaについてるC++使う
最適化が良くなってるとか

最適化コンパイラによっては、なまじ昔のコンパイラ向けに手で最適化したコードは
逆にコンパイラの最適化を阻害することがあるね。素直に書いたほうが速いと。

また、ライブラリ関数があるのに手で同じ処理を書くと却って遅いってのもよくあった。

昔はどんなパターンでどんなコードが出るのか、いちいちアセンブリ出力してチェックしたなあ。
最近はそこまでこだわる必要がほとんどなくなってしまったが。
この特徴は覚えてもコンパイラのバージョンが変わっただけで事情が変わるしな。

そういえば最適化キチにはWatcom C++は面白かったな。今はオープンソース化の準備中だっけ?
関数の属性にどのレジスタを壊さないとかの情報をつけられて、コンパイラがそれを元に最適化してくれたりした。
特にインラインアセンブリで関数書くのに有利だった。
ライブラリ関数もかなり最適化がすごかった覚えがあるな。

今のVCのほうが最適化は進歩してるかもしれんが。

最強はベクターシーだ。使った事無いけど。

パイプラインを意識したソースって作れるんかな
誰か情報きぼんぬ

>>31
ジャンプしないように気をつけれ

>>31 まあレイテンシー２くらいならそう難しくもないよ
　でもパソコン用だと　そんなことしてもCPUが違えば意味ないから

DSPなんかだと
　レイテンシが命令によって違うとか、読み書き先で違うとか
　の条件でかつ組み合わせの条件がとかなると
　自分でツールでも作らんとなあ

ガイシュツだがホットスポット叩くのが一番効くね。
同等以上に効くのは利用状況や用途を考慮して内部アーキテクチャを変更すること。
初期の設計と実際の利用状況にギャップがある場合じゃないと成り立たんけどね。
そういう場合には数倍の改善が見られることもある。ま、普通できんが。

キャッシュのミスヒットのペナルティーも、最近バカにならないじょ。

>>34
まさに最適化ですな。

最適コード ←→ 汎用コード

動作の前提条件を絞ることで性能を向上するが
反面、汎用性は落とすのが最適化なんだしな。

最適化は常に大局(全体の構造、設計)から攻めるのが効果絶大なんですな。

速いプログラムを遅く作って、速いコンピュータの前で呆然と立ち尽くすか・・・
楽なプログラムを早く作って、速いコンピュータの前でコーヒーを飲んで眺めるか・・・

それが問題だ。

関数に細かく分割しすぎない。
関数呼び出し時のオーバーヘッドは特にループ処理で困らされる。

不必要に実数演算を行わない。
整数演算に比べて速度に劣る。

不必要にint型やlong型の変数で演算を行わない。
char型でも良いときは、そちらを使う。その方が速い。

細かな配慮が速いプログラムを生む。

char型で計算をする機会って滅多に無いと思うが

×関数に細かく分割しすぎない。
○構造化を先に心がけるべし

×関数呼び出し時のオーバーヘッドは特にループ処理で困らされる。
　正しく構造化したなら困る程のオーバヘッドではない筈

○不必要に実数演算を行わない。
×整数演算に比べて速度に劣る。
　とは限らない。expとか内臓関数を整数で書くより速い場合もあるからね

○不必要にint型やlong型の変数で演算を行わない。
×char型でも良いときは、そちらを使う。その方が速い。
　とは限らない　特に一昔前のチップではcharが混在するとストールする場合あり

>>40
そうそう。(実数の話)
途中で実数計算が必要な場合、整数にしたり実数にしたりなんて変換かけると
そのほうがコストがかかることもある。徹頭徹尾実数にしたほうが速かったりね。
それと、乗除算命令の処理時間も実数のほうが速いプロセッサもあるよな。

>>39
int型のほうが速いんでないの？

pen4からはパーシャルレジスタストールが無くなったってintelは言ってるけど
かと言ってキャッシュ効率を考えてintを避けてucharにしてもいいの？
つまりはmov vs movzxの実行スピードの話なんだけど。

Pentium II から imul/mul は実数演算機に送られるようになりました。
実数乗算が十分早くなったからできるようになったのだけど、
実数演算の順序を妨害したり結構面倒。

>>44 Pentiunからでねーか

4x4行列の逆行列なら、Intelのサイトのどっかにあったでよ。

ほれ。4x4の逆行列の人。探してきてやったよ。
http://www.intel.com/design/pentiumiii/sml/245043.htm

大前提として、CPUベンダもコンパイラメーカーも
平均的なC/C++コードを高速に動かすことを目標にしているハズ。
映像処理・音声処理などのケースを除けば、
とにかく素直なコーディングをするのが長期的にはベストの戦略と存じます。

intか charか、関連。
http://pc.2ch.net/test/read.cgi/tech/1006834463/926-932

なるほど。興味深いので実験してみた。
BOOL a;
bool b;
for(...) a = TRUE; // mov dword ptr [addr_a], 1
for(...) b = true; // mov byte ptr [addr_b], 1
代入は確かに語長が関係するね。(mem to memのopだし)

問題は
for(...) if(a) c = 1; // 速い
for(...) if(b) c = 1; // 遅い
これはやっぱパーシャルレジスタストールだね。

特に何の解決にもならんけど、そうか。boolって1byteだったのね。。知らんかった。。

pen3だとdoubleよりfloatのが速いけど
pen4だとSSE2で逆になる？

main(){}

>>52
execve(2)のベンチマーク

＞pen4だとSSE2で逆になる？
メモリ帯域の問題があるから、float < doubleにはならないとおもう。

>>51
>>54

メモリの帯域もあるけど、
そもそも同時演算数が半分になるから半分以下の速度になる。

SSEでfloat４個同時演算できるのが、
SSE2でdouble２個だから。
レイテンシ変わってるはずだが、２倍も変わってないだろう。
つーことでSSE2はfloatで精度が足りない場合くらいにしか使えない。

＞SSEでfloat４個同時演算できるのが、
Pen3のSSEは、float４個に２クロックかかる、って
肉系が書いてたような。

>>56

SSE2のdoubleの処理は、1クロックなの？
それなら使い道多いにあるなぁ。

なんでポインタって速いんですか

　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ･∇･)　＜　カステラ
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ･∇･)　＜　１番！
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ･∇･)　＜　電波は
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　(;´Д｀)　＜　２ch！
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ･∇･)　＜　３時の駄スレは
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ﾟДﾟ)　＜　晒しage！
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪

↑一匹多いよ

　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ･∇･)　＜　カステラ
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ･∇･)　＜　１番！
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ･∇･)　＜　電波は
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　(;´Д｀)　＜　２ch！
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ･∇･)　＜　３時の駄スレは
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪
　 ∧∧　　　／￣￣￣￣￣￣￣￣
　( ﾟДﾟ)　＜　晒しage！
　 | っ |っ　　＼＿＿＿＿＿＿＿＿
　 ⊂ノ〜
　 ∪

↑一匹多いよ

↑ほのぼのしててﾜﾗﾀ

っていうか、横に並べろよ

>>47
ありがとう。

お礼に、いいこと教えてあげよう。 float型をint型に変換する、VC++の内部関数__ftoi()めちゃ遅い。
例えば、こんなシチュエーションあるでしょう

float dot = dotproduct3( &v1, &v2 )
int r, g, b;
r = (int)(material.r * dot * 255.0f);
g = (int)(material.g * dot * 255.0f);
b = (int)(material.b * dot * 255.0f);

V-TUNEでアナライズすると、このキャストがかなりボトルネックになっていることがわかります。

googleの検索はどうしてあんなに速いのですか？

膨大な量のＨＰから瞬時に探すなんて不可能です。

http://pc.2ch.net/test/read.cgi/tech/1012536901/909
でも聞いたのですが、レスが付かないのでここで聞きます。

>>66
1.常にWebページをあちこちから集めまくってキャッシュしてるから。
2.Linuxマシン1万台のクラスタリングの威力。

1万台ですか。 スゴイですね。
ＨＰの内容はハードディスクにでも覚えているのでしょう。

でも、単純にＨＤ内から検索キーを探しているだけでしょうか？
もちろんコンピュータの処理能力を増やせば速くなりますが、、、

一つ思い付いたのは、
検索キーと検索結果をキャッシュに入れておく方法です。
これなら同じ検索キーなら瞬時に出ます。

他にどんなことやっているのかな・・・

とりあえずデータベースの基礎でいいから勉強しる。

>>68
AltaVistaは、Alphaマシンの並列処理で、オンメモリ検索だったはず。

分かりましたよ〜。

検索キーをキャッシュの中から探すのではなくて、
あらかじめ、検索キーとその検索キーでヒットするＨＰを対応付けておくんだ。

キーのハッシュ値を使えばそのまま配列が使えるし、
検索結果の順番もあらかじめ決めておけるし、
かなり速くなりそう。

全ＨＰをメモリ上に置く必要がないし、、、

＞あらかじめ、検索キーとその検索キーでヒットするＨＰを対応付けておくんだ。
なんだネタだったか。

ええ？
違うの？

71が正解ですよね？
これより速い方法はないですよね？

誰か教えて下さい！

よくある手法だけど、さほど精度を求めないのなら
算術関数は極力使わないほうがいいね。
テーブル作ってインデックスジャンプしたほうが効率いいし

>58
放置プレイも可哀想だから、一応レス
メモリ確保しなくていいから。
確保する手順もオーバヘッドもなくなるから効率いいでしょ。
まぁいつもいいとは言わんけど・・・

>>75
最近のＰＣでは、ほとんど速度が変わらないのよ。

>58
いったい何に比べて速いのでしょうか。

>>71
単語でも、長い文章でも、検索に要する時間は同じだけど。

>79
ハッシュ値を求めればあとは同じ速度です。

>78
配列じゃない?

アルゴリズムが単純だが、処理の実行に２週間かかるプログラムが目の前にある。
アルゴリズムは複雑だが改良すれば処理が２時間で終了可能だが、改良に２週間
かかりそうだ。
このプログラムが必要なのは２週間後。
どうする？
このまま行く？ 改良に着手する？

実行回数が一回以下なら前者
二回以上なら後者

処理の実行に２週間かかってもいいならそのまま。

一週間で仕上げて残りの週は遊んで過ごす。

1周間で処理に２〜３日かかるのを作る。

>>82-85
>>81は、ひっかけ問題だよ。
2週間後に必要なのは、"プログラム"つまりソースコードであって、
このプログラムから導かれる結果ではない。

改良するかどうかは、
仕事の重要性・顧客の重要性・技術者の良心・日常の忙しさ
などから決める必要がある。

>>75
　パソコンなら算術計算は精度が荒くてよければ10クロック程度で可能です
　一方テーブルをひくのは、1Gのパソコンで100Mのデータバスで　やっぱり10クロック
　2Gのパソコンなら20クロックで逆転してしまいます

>>58
確保する必要ないってどういうことですか？
newやらmallocやらする必要があるのでは？
厨房でスマソ

入門書を以下略

VCでC++標準のcopy()、fill()あたりが
C標準のmemcpy()、memset()と比べてめちゃめちゃ遅いDEATH……。
組み込み関数相手やからしゃーないねんけどなあ。
いずれ気兼ねせずに使えるよーになってほしー。

>>81は別に引っかけ問題とは思わないけど。
ソースが必要なのか、実行可能ファイルが必要なのか、
どちらとも取れますが、そもそもどっちでも構わない。

誰が「プログラムから導かれる結果」を二週間後に必要と言っているのか・・・。

算術計算の方が速いＰＣでは、テーブル使っても十分速い。

>>65

（__ftoi の続き）
じゃあどうするかというと、それは、"Game Programming Gems 2"　に、トリックが載っています。

__forceinline void FloatToInt(int *int_pointer, float f)
{
　　__asm　fld　　f
　　__asm　mov　edx,int_pointer
　　__asm　FRNDINT
　　__asm　fistp　dword ptr [edx];
}

某ソースから引っ張ってきたが、こーいうのか？
ちなみに>>65のは四捨五入したほーがよいと思ー。

>>81
1/60秒毎に演算結果を求められるプログラムを１年間かけて作っていますが、なにか？

>>94
それだと何の工夫もない、もろストレート組みだよね。　ラウンディング(frndint) のクロックサイクル数って幾つだろう？　それに拠っては遅い。
"Game Programming Gems2" のやつは、マジ、トリッキーだよ。
アセンブラで書くとこんな感じ。　ちなみにBIASの値は、本でみてみて。

fld dword ptr [f]
fadd dword ptr [BIAS]
fstp dword ptr [intValue]
mov eax, [intValue]
sub eax, [BIAS]

>>92
今のCPUは命令実行速度よりもメモリアクセス速度の方が何倍も遅いから、
>>87はそのテーブルをひく作業の方が速いとは限らないと言ってると
思うんだけど。もちろん遅いとも限らないが。

テーブルが速いかどうかはテーブルがキャッシュに入るほど小さいかどうか

http://www.stereopsis.com/FPU.html
む、ここにもなんかあったぞ。float→int変換。
まだカンペキには理解してないんだが、
浮動小数の仮数をそのまま整数に換えちまうわけか。

んで、下は10万回変換させてみた結果。ループ含む。
0.015306 secs : normal cast
0.003773 secs : Real2Int

整数のまま計算すりゃいいんじゃないの　足算引算は並行して実行されるし

ちなみに、自分の場合、高速なのが必要なら
平方根やhypotや３角関数は整数で計算してるけどね

諸悪の根源であるx86のFPUアーキテクチャを何とかしてくれ

3DNow!とか、SIMDとか。

>>102
あれは8086-8087間のインターフェイスを簡単に取れるようにするために
考えられたアーキテクチャなんだよな。
コプロセッサを内蔵した今となっては、何でいちいちメモリを経由して
データを受け取らなきゃならないのかわからん。
ええ、スタック内ではレジスタ−レジスタ間演算も可能ですよ。でも
Ｃ言語の実数演算の式をそのように最適化してくれるコンパイラは見た
ことない。

age

>>101
実装によるけど、floatを多用するような３Ｄ系とかだと、hypotも平方根も３角関数も、floatに統一した方が速いと思う。
sqrtも三角関数も、ＦＰＵのインストラクションがあるからね。

>>104

確かに、昔はどうであれ、FPUのレジスタに値をロードするのに、メモリを経由しなきゃいけないのはタコだと思う。

fstp dword ptr [memory]
mov eax, [memory]
ってやんなきゃいけない。

普通、
fstp eax
ってできそうなものじゃん。

mov dword ptr [ten], 10
fld dword ptr [ten]
って感じで、即値もダイレクトにロードできないしね。

fld dword ptr 10
ってやりたいじゃない。

>>107
過去との互換性を保つためだからアーキテクチャまで変えるわけにはいかないだろ。
3D NowとかSSEとか使いこなせない頭で安易に批判するんじゃねーよ

「とりあえず、何でもいいから、とにかく、一日でも早く市場に出す」社訓はいいかげんに見直すべきだな
ちまちましたしょーも無い命令追加ばっかりすんな！＞Intel&AMD

>>109
マーケティング戦略だからしょうがない。
クロック数を上げるか、命令を追加するのが
消費者にとって一番分かりやすい指標だから。

>>108
こうできたらよかったのにっていう話してるんだろ。
何を根拠に、そんなしょうもないことではりきってるわけ？
SSEは、ディフューズ光計算とかの高速化に使ってますが何か？

まあﾏﾀｰﾘと卓球でもしようぜ。
( ´ー)ρ┳┻┳°σ（ー｀ )

この間、最適化について話し合っていたら、
「インタプリタを使っているならコンパイラ言語に乗り換える」という意見が出ましたがこれって最適化って言いますか？
また、「速いマシンを購入する」も最適化ですか？

後者は最適化とはいわないが、
問題の解決手法の１つではあるな。

>>88ですがマジレスきぼんぬ

>>115
何が知りたいのかわからん

>115
おれも解らん。
レス先間違えている？

星の動きをシミュレーションするやつで、
通常、N個星があれば、1回の計算にN*(N-1)回の演算が必要だったのを
擬似アルゴリズムを使って高速化できた、という話の詳細をｷﾎﾞﾝﾇ

>>118
Programs in perl (邦題 珠玉のプログラミング) かなんかで見かけたような

>>115
　親切なオレ様がレスしてやろう。
　まず、レス番号を間違えてるな。>>58の質問に>>76という回答があって、
それに対して>>88と訊いてるわけだろ？　質問するときは、ミスするな。
回答するときにミスするのは「恥ずかしいやつ」として晒されるだけだが、
質問するときにミスすると、そもそも回答が返ってきにくい。
　で、>>76の回答の意味だが。これは、「関数の値渡しとポインタ渡しの違い」
の意味で、「メモリ確保しなくていいから」と答えてあるのだ。
　もし58=88=115なら、58は多分そういう意味で訊いたのではないはずだろ？
「なんでポインタって○○より速いんですか」という形で訊き直せ。
（´-`）.｡oO（と偉そうに回答してみて、>>76の意図が全然違ってたら恥ずかスィ…）

親切なオレ様，ありがとう。
まさにその通りだYO

>「メモリ確保しなくていいから」
コピーによるオーバーヘッドを嫌うから

>「関数の値渡しとポインタ渡しの違い」
引数への

かな。揚げ足捕りに近いのでsage

ヘボイ話だが聞いておくれ。

VC++が吐くアセンブリコードってプロジェクト設定で簡単に見られるやん〜。
今までいちいちデバッガで確認してた俺ってなんなんですか一体。

Winでの開発始めた頃に、最近のcl.exeには
そういうオプションないんだよ〜んみたいな話をどっかで聞いて
ああ、MSならやるかもなあとか勝手に納得してしまってたよ。

>>122
　いや、適切な指摘だと思うぞ。

>コピーによるオーバーヘッドを嫌うから
　そう、それ。俺も「メモリ確保」って言ってしまうのは
しっくり来なかったんだが、適切な言い回しを思い付けなくて、
>>76コピペで済ましてしまった。

>引数への
　こっちは素で気づいてなかった。確かに俺の表現だと、
ナナメ読みしてると関数ポインタと誤解しやすい気もするから、
引数って単語は必須だな。

>>123
プロジェクト設定ってどこで変えるんですか？

あと、アセンブラの命令毎に実行速度書いてある資料って
どうやって手に入れてます？

>>125
　機械語の実行速度って、それこそ CPU メーカーが出している資料
くらいしかないが。ただ、日本語化されていないことも覚悟してな。

　もっとも、今の CPU なんて、見かけ上はほとんどの命令が1クロッ
ク以内に終わるけど。

　インテルの IA-32 プロセッサのデベロッパーマニュアルなんて、
3分冊のPDFで合計 25.2MB……日本語化してくれていることに感謝（ｗ

あんぐらいの英語読めよ。

>>125
プロジェクト設定＞C/C++のファイルリスティングのカテゴリで
リスティングファイルタイプを「ソースコードを含む」あたりに変更する。
これでオブジェクトファイルと一緒に.ASMファイルを吐いてくれるハズ。

実際には最新のスーパースケイラプロセッサだと
複数のパイプラインで同時に実行されてるし、
分岐予測が外れた場合のキャッシュ操作とか諸々考えると、
コードの実行クロック数えながら最適化することは
人間技では無いと思はれ

>>129
VTuneを使って、がりがり最適化してる例を雑誌だか本だかで見たことあるよ。

８６系の場合は一度内部RISCコードにコンバートしてから、それを実行してる
たしか内部コードはプロセッサ毎に違う

>131
μOPのことかな？

>>127は絶対に読めない

低レベルな話でスマソ

C++で複素数クラスつくってるんだけど
四則演算でオペレータオーバーロードすると
参照で値返せないよね｡

かといって
complex &mul(const complex &a, const complex &b, complex &c)
{
c←a*b
return c
}

とすると可解読性が悪くなってしまう｡｡｡
こんなときどうすればいいっすか?

complex mul(const complex& a, const complex& b)
{
complex c;
c = a * b;
return c;
}

しまった、高速化について語るスレか・・・ゴメソ。

考えてみた。
void mul(complex* result, const complex& a, const complex& b)
{
*result = a * b;
}

使う側（例：a*b+c*d）
complex a, b, c, d, e, f, g;
mul(&e, a, b);
mul(&f, c, d);
add(&g, e, f);

まぁまぁの可読性。

complex mul(const comprex& a, const comprex& b)
{ return a * b; }

comprex result = mul(a, b);
まっとうな処理系ならこれで作成される一時オブジェクトは１個だけ。
オーバーヘッドにはならないよ

>>138
NRV (Named Return Value) 最適化ってヤツだね。

>>96
>>99
むかーしから似たような事を考えてる人はいるもので、
ttp://webcat.nii.ac.jp/cgi-bin/shsproc?id=BN00584337
とかにも載ってたりします。＞その手法

>>137
ん?それだと134とほぼ同じですよね?
乗算の関数を呼ぶときに
e = a*b + c*d;
のような形で書けてなおかつ
速さが
complex &mul(const complex &a, const complex &b, complex &c)
あるいは
void mul(complex* result, const complex& a, const complex& b)
のような処理ができれば望ましいんですが仕方ないですか．

やっぱり複素演算では言語仕様でサポートしてるFortranに勝てないのでしょうか
悔しい

>>134
Effective C++より
> 22項：値渡しよりも、リファレンス渡しを使おう。
> 23項：オブジェクトを返さなければならないときに、
> 　　　　リファレンスを返そうとがんばるのはやめよう

一時オブジェクトはたぶん最適化で消えるから心配めさるな。

俺は142じゃないが、同様に。

More Effective C++
項目19:テンポラリオブジェクトの起源を理解する
項目20:戻り値最適化の促進
項目22:単独のopの代わりにop=を使うことを考える

そして最終的な結論。
Exceptional C++
項目20:クラスの機構
引用：
なぜ、標準ライブラリに存在する複素数クラスcomplexを新たに書くのか。
標準ライブラリのクラスにはこれから述べるような多くの問題点がないし、
それらはこの業界で最高の技術を持つ人達の長年の経験に基づいて作成
されたものだ。汝、謙虚な心を持って、再利用すべし。
自分で手作りせず、代わりに既存のコードを、特に標準ライブラリのコードを
再利用すること。標準ライブラリは、速く、簡単で、かつ安全だ。

以上。

ふと興味が湧いたのでVC5SP3で試してみました。長くて申し訳ない。
いや、やっぱ結構賢いですな、いまどきのコンパイラ君。

class Complex {
    double r;
    double i;
public:

    Complex(double r = 0, double i = 0) : r(r), i(i) {}

    friend Complex operator+(const Complex& c1, const Complex& c2);
    friend Complex operator*(const Complex& c1, const Complex& c2);
};

inline Complex operator+(const Complex& c1, const Complex& c2)
{ return Complex(c1.r + c2.r, c1.i + c2.i); }

inline Complex operator*(const Complex& c1, const Complex& c2)
{ return Complex((c1.r * c2.r - c1.i * c2.i), (c1.r * c2.i + c1.i * c2.r)); }


; 26 : Complex e = a * b + c * d;

mov eax, DWORD PTR _d$[esp+12]
mov ecx, DWORD PTR _a$[esp+12]
mov edx, DWORD PTR _c$[esp+12]
push esi
fld QWORD PTR [eax]
fld QWORD PTR [ecx]
fld QWORD PTR [edx+8]
fld QWORD PTR [ecx+8]
fxch ST(3)
fmul QWORD PTR [edx]
fxch ST(1)
fmul QWORD PTR [eax+8]
fld QWORD PTR [eax]
fxch ST(1)
fsubp ST(2), ST(0)
fxch ST(2)
mov esi, DWORD PTR _b$[esp+16]
push edi
fmul QWORD PTR [esi]
fld QWORD PTR [edx]
fxch ST(4)
fmul QWORD PTR [esi+8]
fsubp ST(1), ST(0)
fxch ST(2)
fmul QWORD PTR [edx+8]
fld QWORD PTR [esi]
fxch ST(3)
faddp ST(2), ST(0)
fxch ST(3)
fmul QWORD PTR [eax+8]
fld QWORD PTR [ecx]
fxch ST(2)
fstp QWORD PTR _e$[esp+24]
fxch ST(2)

この話は興味があります.

私の意見としては, 本当に速さがほしかったら
>void mul(complex* result, const complex& a, const complex& b)
のように書いたほうがいい, と思っているのですが,
みなさんはどのようにお考えですか ?

ちなみに私はゲームプログラマとかではないので, あまりカリカリに
最適化とかはがんばりたくない, でも数値計算のパフォーマンスは
ある程度求めたいという, ぜいたくな立場なのですが.

どうしても C++ のクラス + 演算子のオーバーロードではパフォーマンスが
でないもので ...
単に書き方が悪いだけかも.

環境を書き忘れていました.
主に使っているのは Linux 上の gcc(2.95.3, 3.0.4) とかです.
Intel のコンパイラとかだと, 何も考えなくても
かなり実行速度があがるので, すごいなあと素直に感心しています.

Intelのコンパイラって？

>>147
http://www.google.co.jp/search?q=Intel%82%CC%83R%83%93%83p%83C%83%89&hl=ja&btnG=Google+%8C%9F%8D%F5&lr=

>>145
>>138の書き方でいいんじゃないか？
自然だし

STLの<complex>より自作のライブラリの方が
乗算で倍以上速いのですが最適化をかければ同じになりますか？
VC++スタンダードエディションなので最適化かけられないもので

>>150
当方VC6Pro.
おれがジャッジしてやるからどこかにアプしてみれ

Complexの乗算の最速アルゴリズム教えてください

グローバル変数を使わない
ポインタを使わない

>>150
マルチタスクで使えるかとか、いろいろ汎用性を考えると
どうなんだろうか。

なんか高速化について語りたくない奴がいるみたいだな、でてけよ。

register使え。

>>145
>>144にあれこれ付け足して〜

Complex Hoge1(const Complex& a, const Complex& b, const Complex& c, const Complex& d)
{
    Complex e = a * b + c * d;
    return e;
}

Complex Hoge2(const Complex& a, const Complex& b, const Complex& c, const Complex& d)
{
    Complex e;
    Complex t1;
    Complex t2;

    Mul(&t1, a, b);
    Mul(&t2, c, d);
    Add(&e, t1, t2);
    return e;
}

この２つはほぼ同一のアセンブリコードと相成りました。（って当たり前？）
Hoge2式でも、大抵のケースでは無駄になってしまうんじゃないかなあ。
確保済みのComplexに対しての大量一括計算か何かがあれば
有効になってくるかもしんないけど。

gcc なら戻り値の拡張文法使って自分でできたはず・・・

inline Complex operator+(const Complex& c1, const Complex& c2)
#if defined(__GNUC__)
　　return ret(c1.r + c2.r, c1.i + c2.i)
{
}
#else
{
　　return Complex(c1.r + c2.r, c1.i + c2.i);
}
#endif

>>150=妄想君
ってことでＯＫ？

妄想君です

いや､自分の書いてるのは単に上に書いてあるようなやつで
難しいことは一切やってません

だから乗算なら
オペレータ * で引数を２つ参照で受けて
return complex(c1.re*c2.re - c1.im*c2.im, c1.re*c2.im + c1.im*c2.re);
だけです｡

これとSTLの乗算比較してみてください（最適化なしで）
自作の方が速かったのは気のせいでしょうか？

当然ですが mul(&a, const &b, const &c)を使えば
更に速くなりました

一応
コンストラクタも単純に
complex(double _re, double _im) : re(_re), im(_im) {}
としてるだけ。
代入演算子も同じく。

1000万回ループで自作､STLともに

for (int i = 0; i < 10000000; i++) {
　　a = b*c;
}

を実行して時間測ってます｡

他の環境でどうなるのか興味あり
みなさんの環境では<varray>も速いんですか？

あのさー、真面目に動作速度について人にも調べて欲しいんだったら
コンパイルしたらすぐ動くコードくらい用意しなよ。

>>149
行列, ベクトルがまざった数式を, (ほぼ)そのままソースに
書けたらいいなあという思いがあります.
しかもデバッグが容易になると考えています.
確かに昔の人はアセンブラで, mul, add, とか並べていたんだろうけど.

>>163
妄想だからそんなコードは存在しないのです

最近はゲーム屋の行列・ベクトルクラスも
容赦なく演算子オーバーロードが主流とちゃうかな。

まあ、頂点変換とかメッシュ処理とかは
専用ルーチン用意したりハードに任せたりするとして。

>>157
> Mul(&t1, a, b);
> Mul(&t2, c, d);
> Add(&e, t1, t2);

関係ないかも知れんが、C++でこの書き方はあんまりじゃないか？

t1.Mul(a, b);
t2.Mul(c, d);
e.Add(t1, t2);

せめてこう書いてくれ。

>>167
どっちの書き方もおかしいだろ

struct complex
{
double re, im;

complex(const double _re = 0, const double _im = 0) : re(_re), im(_im) {} // デフォルトコンストラクタ
complex(const complex &c) : re(c.re), im(c.im) {} // コピーコンストラクタ
complex &operator = (const complex &);
complex &operator *= (const complex &);
};

const complex j(0, 1); // 虚数単位ね

complex &complex::operator = (const complex &c) { re = c.re, im = c.im; return *this; }
complex &complex::operator *= (const complex &c)
{
const double _re = re*c.re - im*c.im;
im = re*c.im + im*c.re, re = _re;
return *this;
}

inline complex operator * (const complex &c1, const complex &c2)
{
return complex(c1.re*c2.re - c1.im*c2.im, c1.re*c2.im + c1.im*c2.re);
}

inline complex &mul(const complex &c1, const complex &c2, complex &c3)
{
assert(&c1 != &c3 && &c2 != &c3);
c3.re = c1.re*c2.re - c1.im*c2.im, c3.im = c1.re*c2.im + c1.im*c2.re;
return c3;
}

↑のが問題の複素数っす

ちなみにVC++6.0スタンダードでは
500万回の複素数乗算 a = b*c; を実行してかかった時間が
STL:↑の*:↑のmul
8.08:3.51:1.03
でした｡やはり最適化すれば差がなくなるでしょうか

行列, ベクトルでも malloc() せず, さらに for() ループを展開すると,
>void add(Vector* result, const Vector& a, const Vector& b)
方式とほぼ同じような性能が出るみたいなので,
結局はテンプレートによる実装に行き着くようなきがする.

>>171
STLのvectorってそんなに速いんですか？

ところで malloc()せずにってどういう意味でしょうか．
厨房の質問でｽﾏｿ．確保しないでアクセスしたらエラーが出るのでは?

見にくいので書き直し
>>170 の結果は
STLの　a=b*c;　が　8.08sec
妄想の　a=b*c;　が　3.51sec
妄想の　mul(b,c,a)　が　1.03sec
といった結果になりました｡

プロフェッショナルエディション入手するつもりなので
最適化後の結果も調べてみます

> STLの　a=b*c;　が　8.08sec
> 妄想の　a=b*c;　が　3.51sec
> 妄想の　mul(b,c,a)　が　1.03sec

VC++6.0 で最適化やってみたら
STL ： 0.99 sec
妄想 ： 0.44 sec
妄想mul ： 0.11 sec
だった。

mul が速いのはいいが、STL は何故遅い？

（VC++ のcomplexの operator* はアセンブラのようだが。
<xcomplex> の412行目）

ｽｺﾞｲ150ｻﾝ､ｽﾊﾟｰﾊｶｰﾈ

>> 172

いや, STL の vector ではなくて, a = b * c が mul(b, c, a) 方式くらいの
性能がだせるかもしれないという話です. テンプレートなんたらってのは,
Blitz++ でやっているように, テンプレート使って事前にループとかを
展開するって話です.

出力アセンブリコード確認しといたほうがいいぞよ。
速くなったと思ったら最適化で丸ごと消えてることもあるし。

>>161
> for (int i = 0; i < 10000000; i++) {
> 　　a = b*c;
> }

これ、VC++だと

a = b * c;
i = 10000000;

に展開されてしまうみたいだぞよ。
i を関数外に追い出してみても無駄だった。
なんかこういうののベンチマーク方法論とかないじゃろうか？
実際のコードで使ってみるしかないのか？

最適化しないが、

VC++(マルチスレッドライブラリ使用)
VC6.0 STL complex<double> a = b * c 2874ms
STLPort complex<double> a = b * c 1021ms
妄想君 a = b * c 1031ms
妄想君 mul(b, c, a) 580ms

BCC5.5.1
BCC STL complex<double> a = b * c 1181
妄想君 a = b * c 1101ms
妄想君 mul(b, c, a) 180ms

VC++6.0の標準STLがクソなだけ。
妄想君のmul()はいい性能出てるみたい
BCCのmulの結果が意外。

>>177
volatile int a;

gcc 2.95.3-4
GCC 標準STL complex<double> a = b * c 3805ms
妄想君 a = b * c 1422ms
妄想君 mul(b, c, d) 971ms

Pentium3 500MHz
FreeBSD 5-current, g++ 2.95.3
10000000 回計算するのにかかる時間の総計です.

STL complex<double> a = b * c 0.466sec
妄想君 a = b * c 0.510sec
妄想君 mul(b, c, a) 0.261sec

VC++6.0 最適化後
標準STL complex<double> a = b * c 109ms
STLPort 4.5.3 complex<double> a = b * c 115ms
妄想君 a = b * c 213ms
妄想君 mul(b,c,a) 94ms

最適化まで考慮に入れるとこの結果のようだ

もう終わった話題っぽいけど
一応こっちでも最適化してみた

VC++6.0 Professional SP5, Pen�V500
ループ回数忘れた

デバッグ
標準STL a = b * c 9383ms
妄想君　a = b * c 6038ms
妄想君　mul(b,c,a) 5137ms

リリース
標準STL a = b * c 4556ms
妄想君　a = b * c 4666ms
妄想君　mul(b,c,a) 4496ms

デバッグモードのSTLが異常に遅いのが分からんが
最適化すると変わらない様子…おとなしくSTL使うか.

STLはSTLPort入れとくといいことがある

次は行列演算についてネタ振ってよし？
>>164
うちでは行列もライブラリ自作して行列演算は
complex c;
matrix<complex> m1(10, 10), m2 = m1, m3 = m1;
m2=m1*c*trace(m1);
とか
m1 = m2*m3;
とかしてる.
でも行列の乗算の際にテンポラリの行列が必要だから
"*" 使うといちいち行列の宣言が必要なので
遅くなってしまう．

結局　mul(m1, m2, m3)になってしまうんだけど
マクロか何か使ってもっと見やすく
書けないんだらうかと思う春の夕暮れ。

>>184
んじゃSTLportいれてみるっす｡

http://www.stlport.org/
http://www.boost.org/

この２つは絶対に入れて、存在するクラスは絶対に作らない。
コレで汎用性を保ったままほぼ限界性能を出せるから。

>>187
行列計算あたりは、プロセッサ依存の最適化を入れると性能が上がらん？
和や積を求めるところで SSE 使うとかさ。

>>188
いや、だから汎用性を保ったまま、ね。
局所最適化が必要なら当然そうしなければならない。

>>189
汎用性 = compile anywhere

の意味なら、別に STL の実装内部で SSE 使っても、STL 側の外部インター
フェースに手を入れない限りは問題ないよね。

Intel C++ コンパイラについてくる <valarray> とか、どうなってるんだろ？

>>185
operator * はおそらく一時オブジェクトに対する operator *=で実装されているだろうから、
最適化の具合によっては

m2 = m1 * c * trace(m1)は
Comprex temp(m1);
temp *= c;
temp *= trace(m1);
m2 = temp;

の仮想コードに展開されるはず。

STLの用にそれなりにきちんと設計されたクラスライブラリは
最適化のこともしっかり考えてるよ。

boost.org ってのは知らんかったから, 今から見てみるけど
stlport の valarray はやたら遅いぞ.

>>存在するクラスは絶対に作らない
この言葉が余計なんだと思う。
なんか喧嘩売ってんのかって感じだね。
ここの STL がパワーあるから参考にすれば良いとか書けばいいんじゃない。
必要がなくなれば、そのときは作らなければいいだけの話ですし・・・

>>192
Boost.org は STL とは関係ない、というか STL で標準に入らなかったが
「これは欲しいだろ」と思うようなクラスがいろいろ入ってる。数学関係だと
四元数とか。

（でも shared_ptr と bind イチオシだよな）

>>193
> なんか喧嘩売ってんのかって感じだね。
その程度でカチンと来てると、２ちゃんねる読んでるうちに血管切れるぞ。
気にせず流せ。

regexイチオシなんだが

>>194
ちょうど Quaternion が必要なとこだったので, 後で見てみます.

で, valarray<double> をベクトルとみなして v3 = v1 + v2
を計算してみると, mul(v3, v1, v2) の倍くらい計算時間がかかるみたい.
この差をどう見るかだが ...

環境は Pentium3 500MHz, FreeBSD 5-current, g++ 2.95.3 -O2 ね.

boost.orgのマニュアルみてたけど長いので求刑。

>>191
行列の場合 a *= b の右辺の行列bを参照で渡すと
結局作業用の行列が必要じゃないっすか？
そこをあらかじめ作業用行列を一つ用意しておく必要が
あるのではないかと．．．

ア､書いてて気付いたけど、参照で渡したaの行を
ベクトルに保存して計算すれば aの列の数を持つベクトル
を定義するだけで済むのか

それでも作業用行列ごと渡した方がはやくないっすか

妄想版matrix.h貼り付けたいけど
ちと長い．．．

>>198
どこかのあぷろだに上げろ

>>197
v3 = v1 * v2 ? それとも add(v3, v1, v2) ?

>>199
とりあえず今いる場所にはソースないんで明日
作業場から持ってくる

作業場から２チャンネルに書き込めないんで
complexのときもソース貼れなｶﾀｰﾖ、おかげで妄想君と呼ばれる悲しさ

>>198
よく考えたらそうだった。
逝ってくる。

その辺のホームページから拾ってきたんだけど
valarrayを使った行列の乗算

これと比べていいのかな?

#include <iostream>
#include <valarray>
using namespace std;

int main()
{
　 const int m=1000, k=1000, n=1000;
　 long mk=m*k, kn=k*n, mn=m*n, in,i,j;
　 valarray<double> a(mk), b(kn), c(mn), v1(k),v2(k);

　 for(i=0; i<m; i++)
　 {
　 in=i*n;
　 v1=a[slice(i*k,k,1)];
　 for(j=0; j<n; j++)
　 {
　　 v2=b[slice(j,k,n)];
　　 v2*=v1;
　　 c[in+j]=v2.sum();
　　 }
　 }

　 a.resize(0); // clear aa,bb,cc
　 b.resize(0);
　 c.resize(0);

　 return 0;
}

忘れてた、上の書いたのは妄想君です。
これと妄想matrix.hの m1 = m2*m3を比べてみようかと。

template <typename T = complex>
class matrix
{
private:
int m_row, m_col;

public:
T *m_pMatrix;

explicit matrix(int row = 0, int col = 0) : m_row(row), m_col(col) { NewMatrix(); } // デフォルトコンストラクタ

matrix(const matrix<T> &m) // コピーコンストラクタ
{
m_row = m.GetRow(), m_col = m.GetCol();
NewMatrix();

int n = m_row*m_col;
T *p1 = m_pMatrix, *p2 = m.m_pMatrix;

for (int i = 0; i < n; i++, p1++, p2++) {
*p1 = *p2;
}
}

~matrix() { DelMatrix(); } // デストラクタ

void NewMatrix() { m_pMatrix = new T[m_row*m_col], assert(m_pMatrix != 0); } // 行列の領域確保
void DelMatrix() { delete [] m_pMatrix; } // 行列の領域開放

int GetRow(void) const { return m_row; } // プライベートメンバへのアクセス
int GetCol(void) const { return m_col; }
void SetSize(const int row, const int col) { DelMatrix(), m_row = row, m_col = col, NewMatrix(); }

T &operator () (int row, int col) // 配列演算子
{
assert(row >= 0 && col >= 0 && row < m_row && col < m_col);
return m_pMatrix[row*m_col + col];
}

const T &operator () (int row, int col) const
{
assert(row >= 0 && col >= 0 && row < m_row && col < m_col);
return m_pMatrix[row*m_col + col];
}

matrix<T> &operator = (const matrix<T> &);
};

template <typename T>
matrix<T> &matrix<T>::operator = (const matrix<T> &m) // 行列 ＝行列
{
assert((m_row == m.m_row) && (m_col == m.m_col));

if (&m != this) {
if (m_row == 0 && m_col == 0) SetSize(m.m_row, m.m_col);

int n = m_row*m_col;
T *p1 = m_pMatrix, *p2 = m.m_pMatrix;

for (int i = 0; i < n; i++, p1++, p2++) *p1 = *p2;
}

return *this;
}

template<typename T>
matrix<T> operator * (const matrix<T> &m1, const matrix<T> &m2) // 行列×行列
{
int row1 = m1.GetRow(), col1 = m1.GetCol(), row2 = m2.GetRow(), col2 = m2.GetCol();
int n1 = row2*col2 - 1, n2 = col2*(row2 - 1);
matrix<T> m3(row1, col2);
T tmp, *p1 = m1.m_pMatrix, *p2 = m2.m_pMatrix, *p3 = m3.m_pMatrix, *p4 = p2;

assert(col1 == row2);

for (int i = 0; i < row1; i++, p1 += col1, p2 = p4) {
for (int j = 0; j < col2; j++, p1 -= col1, p2 -= n1, p3++) {
tmp = 0;
for (int k = 0; k < col1; k++, p1++, p2 += col2) {
tmp += *p1 * *p2;
}
*p3 = tmp;
}
}

return m3;
}

↑行列遅いバージョン

つかれたので高速化したのは明日…
つーかようやく今帰宅

ふと思ったけど連続書き込みで荒らしみたい

参考になるからどんどんやってもらえると嬉しいです、そのうち僕も書くかも。
でも今は時間がない。(;;)

STLportのvararrayは問題ありか
http://www.tietew.jp/cppll/archive/274

非常にあたりまえすぎて申し訳ないけど,
汎用的なやつに対しては上のようなものを書いて,
2x2, 3x3, 4x4 は別に用意するっていうのが吉かなあと思います.
この方式だと 2x2 とかに関してはクラス + 演算子のオーバーロードを
用いたやつでも結構いい性能がだせます.

あと new/delete を malloc/free に変えてみると, 速度の点で
おもしろいことがおこるかもしれません. これは行列のサイズ依存かも
知れないけど.

mallocって初期化しないからnewより速いんだったかな？わからん、厨房丸出し。

4*4くらいまでは別に用意するのは禿道、
2*2でオーバーロードで十分なのは作業用の配列が必要ないのが原因と思われ。

ところで行列乗算で乗算回数を減らすアルゴリズムを適用したんだけど
馬鹿でかい(200*200くらい)複素行列くらいじゃないと効き目がないことに落胆の色隠せず。
書き方下手なんじゃろうか。

結局上に書いたのをちょっと書き換えて作業用配列も参照渡しするのが
実用的な行列に対しては自己最速。

>>203 に書いたのと比較したんだけど
203の書きかたがまずいのか妄想Verの方が速かった。
vararray使った速いソースきぼんぬる。

>>211
>2*2でオーバーロードで十分なのは作業用の配列が必要ないのが原因と思われ。
ってどういうこと? 行列の各要素は配列に入れてるんだけど, ひょっとして
x, y, z, w とかいう変数に入れたほうが速い ?

2x2, 3x3, 4x4 で速い要因としては
1. ループが手動で全部展開できる.
2. コンストラクタも matrix(double a11, double a12, double a21, double a22)
とかいう変態的な形が使える.
3. malloc/free がいらない.
4. インラインも展開 OK
5. 逆行列も, 行列式も決めうち可能.
というところかと(ほんとに当たり前のことばかり書いてごめんなさい).
いくつかは賢いコンパイラがよきに計らってくれるんでしょうが ...

ちょうどいい具合にプリフェッチが効いている状態かも

newはほぼ直接mallocを呼び出すのと同じじゃないかなあ
規格上0クリア必須だっけ？＞new

別に0クリアはないけどコンストラクタ呼び出すからmallocの方が手間は減る

けどmallocもANSI準拠だと明示的に未開放でもexitした時に
OSにメモリを返す機構が必要なんで多少のオーバーヘッドはある

速度稼ぐんであればOSべったりのメモリ関数つかうのが良いと思われ

まだいい加減なこというやついるんだな

>>212
要するに演算後の要素を直接与えられた行列の要素を使って
書き出せるってことだよねん？
でも考えてみりゃ*=使わなければ値返す行列が必要か。
結局高速にしたい場合はコンストラクタ作るオーバーヘッドなくすのに
mulみたいにするんだろうか、あるいはここまで最適化してくれるのかな。
試してないけどしてくれそうだね。

>と明示的に未開放でもexitした時に
>OSにメモリを返す機構が必要
はつみみです。

>>217
>要するに演算後の要素を直接与えられた行列の要素を使って
>書き出せるってことだよねん？
ごめんなさい... 日本語が分からない ...

>結局高速にしたい場合はコンストラクタ作るオーバーヘッドなくすのに
>mulみたいにするんだろうか、あるいはここまで最適化してくれるのかな。
>試してないけどしてくれそうだね。
アセンブラのコード見てないへたれだけど, 最適化してくれると思ってる.
最適化してくれないと complex もうまくいかなかっただろうし.

任意の次元の行列はどうしたらいいのか分からないので, 妄想さんに期待.

>任意の次元の行列はどうしたらいいのか分からな
テンプレートでどうぞ。い

>>216
215 にはコテハン「知ったかクン」を贈呈したいと思うが、どうか？

とりあえず Inside the C++ Object Model とエキスパート C プログラミングを
読んで出直して来い。

>>145
漏れの素人考えでは
要素はmalloc使わずに
double e11, e12, e21, e22;
と書けるし
乗算に限らず逆行列でもmallocで作業用の行列をつくることなく直接
det = 1/(_e11*_e22 - _e12*_e21);
e11 = det*e22;
とかfor文使わずに書けるし、これなら実行速度が速くなるかなぁと。
って>>212に書いてあるまんまじゃん（鬱

一般行列の乗算は
>>206の
matrix<T> operator * (const matrix<T> &m1, const matrix<T> &m2) // 行列×行列
を
matrix<T> &mul(const matrix<T> &m1, const matrix<T> &m2, matrix<T> &m3)
にして
matrix<T> m3(row1, col2);
を消せばいいんじゃないでしょうか。

いろいろやってみたけど、小さい行列は
>>212のように matrix2とかmatrix3とか専用クラス作って
中くらいの行列(n = 5 〜 100)は↑に書いたmulで
大きい行列(n > 100)はブロック化するのでfinal answer。

STLのvalarrayは...速いの組める人教えて下さい、おながいします。
>>203みたいに使うとどうも遅くて。

ちなみに大きい行列の場合は
妄想mulよりも>>203の方が速いです。

キャッシュが絡んでるような気がしますがよくわかりません。

http://www.oonumerics.org/blitz/index.html

>>224
照れ屋さんな貴方ってステキ

>>222
>matrix<T> &mul(const matrix<T> &m1, const matrix<T> &m2, matrix<T> &m3)
で, 満足なんですか ? と煽ってみる(w

224 にもあるように一般的な大きさの行列に対してはテンプレートの
再帰的な利用(expression template)になるんですかね ?
ていうか Blitz++ を素直に使え ?

↑再帰的なテンプレートをうまく使えば展開後のソースにfor文が含まれないから
速くなるってことなんだろうか（しったか。）
いや、C++始めたばっかなんでそんな高度なことは考えたこともなかったYO。
時間あれば勉強したいが当分…

ちなみにBlitz++はVC++なので使用不可〜。

http://www.microsoft.com/japan/developer/library/dsmsdn/msdn_090798.htm
もっとテンプレートの勉強にいいページない？

>>227
Generic Programming with C++ Template
http://pc.2ch.net/test/read.cgi/tech/1008593126/l50

のスレでもそのテの話題があるよん。課題は汎用性と効率の両立。

>>190
遅レスですが, Intel コンパイラの valarray って
きわめてふつうな実装に見えます. C++ の入門の本にのっているやつと
あんまり変わらないような ? 違うんかな, 識者のレス求む.

GNU の valarray は遅延評価をやっているみたいです.
全部参照でデータを持っていて, 代入演算子のところでばばっと
演算しているみたい.

>> 227
GNU のやつは add(v3, v1, v2) とかと同じくらいの性能がでるので,
汎用的な行列は遅延評価を組み込んだものにすれば, いいのでは ?

>>230
遅延評価ってなんですかと厨房全開質問決行

何を計算するかを覚えておいて、
実際に演算結果が必要になった時点で計算するやり方。

配列同士の計算だと、全部が全部必要ってわけでもないでしょ？

なるほど、特に長方形行列の積が多い場合は効果が大きそうですね
積を計算する順序でたいぶ計算量が変わりますから

VectorC試した人いる？
もうすぐ出るCマガに記事が載るんでしょ？

http://www.codeplay.com/japanese/

話は変わっちゃいますが、三角関数の高速な計算式誰か知りませんか？
sinは、0<=x<=PI/4のとき 0.99959257 * x - 0.1615350 * x * x * x
ってのは知ってるんだけど、それ以外調べても見つからず。。。
とりあえず、sinとcos、arctanについて知りたいんだけど。
何がやりたいのかと言うと、複素数ベクトルの直行座標<->極座標の変換なんだけど、
特にarctanが重過ぎてお話にならないのです。
誰か高速な手法教えてください。

ちなみに、SIMDで処理したいので、できれば分岐とかないアルゴリズムをキボンヌ。

>>236
　入力の角度精度によっちゃあ、テーブル持った方がいいんじゃないか？

>sinは、0<=x<=PI/4のとき 0.99959257 * x - 0.1615350 * x * x * x
>ってのは知ってるんだけど

理解せずに使って平気かい。
それの求め方分かっていれば他のも求められるよ。

意外と返信早いのね。

>>237
うーん、さすがにテーブルだと、実用的なサイズに収まらないので、
たとえ160〜300クロックかかってもfpatan呼んだ方がマシかも。
>>238
テーラー展開くらいなら多少は。
でも、その式はテーラー展開を途中で打ち切った式より精度が良いとか。

ちなみに、IntelのHPみたら、なんかSSEで各種数学関数を
近似計算してくれるとかいうソースコードを見つけたので
それで解決するかも。5倍は速いみたい。
ほぼフルアセンブラだから、そのまま抜き出して使えば、
かなりの速度向上が望めるかも。

対称性利用でかなり区間を縮小できる･…ってのはもうやってるか。
また、テーブルを間引いて補間多項式も併用できる。
区間が短ければ次数の低い補間多項式でも誤差は小さく抑えられる>>239

CORDIC --- 望みの精度で絶対値と角度が同時に得られる。

絶対値の誤差 2%、角度誤差 0.5度程度だったような...で
8087に勝った記憶あり。

検討済みだと思うけど
＞複素数ベクトルの直行座標<->極座標の変換
自体の回数は減らせないの？

>>236
どれくらいの精度でやりたいの？

整数なら分岐有りだけど
ttp://www.infoeddy.ne.jp/~tensyo/prog/ALGO.HTM

整数だけでやればSIMD並の速度が出る場合もあるよ

age

>>236
きゅーすーてんかい

//逆行列
Matrix Inverse()
{
Matrix d;

//行列式計算
f32 d0 = +( (_11*_22*_33)+(_12*_23*_31)+(_13*_21*_32)-(_13*_22*_31)-(_23*_32*_11)-(_33*_12*_21));
f32 d1 = -( (_01*_22*_33)+(_02*_23*_31)+(_03*_21*_32)-(_03*_22*_31)-(_23*_32*_01)-(_33*_02*_21));
f32 d2 = +( (_01*_12*_33)+(_02*_13*_31)+(_03*_11*_32)-(_03*_12*_31)-(_13*_32*_01)-(_33*_02*_11));
f32 d3 = -( (_01*_12*_23)+(_02*_13*_21)+(_03*_11*_22)-(_03*_12*_21)-(_13*_22*_01)-(_23*_02*_11));

f32 s = (_00*d0+_10*d1+_20*d2+_30*d3);

if (s == 0){
//逆行列が存在しない
d.Identity();
return d;
}
//余因子行列計算と係数乗算
s = 1.0f / s;
d._00 = d0 * s;
d._01 = d1 * s;
d._02 = d2 * s;
d._03 = d3 * s;
d._10 = -( (_10*_22*_33)+(_12*_23*_30)+(_13*_20*_32)-(_13*_22*_30)-(_23*_32*_10)-(_33*_12*_20)) * s;
d._11 = +( (_00*_22*_33)+(_02*_23*_30)+(_03*_20*_32)-(_03*_22*_30)-(_23*_32*_00)-(_33*_02*_20)) * s;
d._12 = -( (_00*_12*_33)+(_02*_13*_30)+(_03*_10*_32)-(_03*_12*_30)-(_13*_32*_00)-(_33*_02*_10)) * s;
d._13 = +( (_00*_12*_23)+(_02*_13*_20)+(_03*_10*_22)-(_03*_12*_20)-(_13*_22*_00)-(_23*_02*_10)) * s;
d._20 = +( (_10*_21*_33)+(_11*_23*_30)+(_13*_20*_31)-(_13*_21*_30)-(_23*_31*_10)-(_33*_11*_20)) * s;
d._21 = -( (_00*_21*_33)+(_01*_23*_30)+(_03*_20*_31)-(_03*_21*_30)-(_23*_31*_00)-(_33*_01*_20)) * s;
d._22 = +( (_00*_11*_33)+(_01*_13*_30)+(_03*_10*_31)-(_03*_11*_30)-(_13*_31*_00)-(_33*_01*_10)) * s;
d._23 = -( (_00*_11*_23)+(_01*_13*_20)+(_03*_10*_21)-(_03*_11*_20)-(_13*_21*_00)-(_23*_01*_10)) * s;
d._30 = -( (_10*_21*_32)+(_11*_22*_30)+(_12*_20*_31)-(_12*_21*_30)-(_22*_31*_10)-(_32*_11*_20)) * s;
d._31 = +( (_00*_21*_32)+(_01*_22*_30)+(_02*_20*_31)-(_02*_21*_30)-(_22*_31*_00)-(_32*_01*_20)) * s;
d._32 = -( (_00*_11*_32)+(_01*_12*_30)+(_02*_10*_31)-(_02*_11*_30)-(_12*_31*_00)-(_32*_01*_10)) * s;
d._33 = +( (_00*_11*_22)+(_01*_12*_20)+(_02*_10*_21)-(_02*_11*_20)-(_12*_21*_00)-(_22*_01*_10)) * s;
return d;
}

余因子行列と行列式による4×4逆行列の算出アルゴリズムを書いてみました。
がんばればSIMDで最適化できそうではあるのですが、
ガウス法による算出とどちらが良いと思われますか。

後50行くらい書いたらコンパイラがcore吐きそうなコードだな

特異行列の逆を単位行列としてしまって良いのかと小一時間問い詰めたい。

>>248
何事もなく過ごせるかと思ったのですが（ｗ
本当は例外投げるべきなんでしょうけど。

>>247
47 は読みましたか ?
まさにあなたの知りたいことがのっていると思います.

てか, 下げそこなった.

>>248
だって、例外投げるようにしたら少し遅くなっちゃうんですもの。
（by 元の行列を返してる不届き者）

>>250
今読んだ。うーん流石インテル。
知りたい情報がずばり詳細に。

このやり方は、クラマーっていうのか。
クラマールール英語で言うとかっこｲｲ。

http://www2.tky.3web.ne.jp/~bandai/24net/prog2/tips1.html
VCはﾀﾞﾒ?