69コメント28KB

＝＝処理を早くする＝＝

■ このスレッドは過去ログ倉庫に格納されています

0001名無しさん＠お腹いっぱい。

NGNG

皆さんの経験を語ってください
とりあえずif文を減らす、比較対象を0にする、代入を減らす
位しか思いつかないのですが
今圧縮解凍をやっています
初心者なので難しい話にはついて逝けませんが
皆さんの経験を圧縮解凍に限らず語ってください

0002名無しさん＠お腹いっぱい。

NGNG

> とりあえずif文を減らす、比較対象を0にする、代入を減らす

そういうレベルの話をする前に、
アルゴリズム的なことはちゃんと考えているか？

0003名無しさん＠お腹いっぱい。

NGNG

当たり前過ぎるが、ループ内(複数回実行される部分)の計算量を減らす。
まあ、アルゴリズムとも言えるが、良い例が出ているので。
http://piza.2ch.net/test/read.cgi?bbs=tech&key=965775993

0004名無しさん＠お腹いっぱい。

NGNG

昔は、ヒープよりスタックのほうが速いという理由で、
malloc()、reallc()をやめて、なるべく再帰で組むとか、
qsort()やhashを使うとか、ソートやデータの入れ替えも
実体に対して行わず、なるべくポインタに対して行う
とかやったけど、最近はどうなのかな？ふぅ。

0005名無しさん＠お腹いっぱい。

NGNG

プロファイラ使え

0006名無しさん＠お腹いっぱい。

NGNG

レジスタ上でうねうねやる。メモリはできるだけ使わない。

0007名無しさん＠お腹いっぱい。

NGNG

まず現状分析
圧縮が早い方が良いのか
展開が早い方が良いのか
それとも平均的な方が良いのか
圧縮率を下げても速度重視なのか、
またはその逆なのか、
動的に調整できるべきなのか
小手先のテクニックは目的から方法を選んでから

0008名無しさん＠お腹いっぱい。

NGNG

インラインアセンブラ使え

00098

NGNG

8:2は見極めろよ

0010名無しさん＠お腹いっぱい。

NGNG

>>8
intelのP6アーキテクチャーだと、効果が無い場合が多いから気をつけること。
勿論、効果がある場合もあるが。。。。
(RSB:Return Stack Buffer)
>>9
なにそれ？

00119じゃないけど

NGNG

>10
80対20の法則だったか、、、
全コードの内20%が性能の80%を出すとかだったような、うろ覚え。

プログラム以外でも、何故かたいてい当てはまる不思議な法則

0012名無しさん＠お腹いっぱい。

NGNG

>10＠｀11
プログラムの２０%のコードが全体の８０％のCPU時間を消費するとか
２０%の社員が全社の８０%の利益を生むとか
２０%のプログラマがプロジェクトの８０%のバグを生むとか

昔はやったマーフィーの法則にも乗ってた尾

0013名無しさん＠お腹いっぱい。

NGNG

saru

0014名無しさん＠お腹いっぱい。

NGNG

速度に関して８対２の法則が当てはまるプログラムはお馬鹿の作った
プログラムな可能性が高し。そこまで重いルーチンがあれば
そこだけは気合をいれて高速化しておくべき。結果一箇所に処理負荷
が集中することはなくなる。

0015名無しさん＠お腹いっぱい。

NGNG

８対２の２の部分が計測した結果判明してからの高速化でしょ。

0016>14

NGNG

エラー処理も他の処理と同じ頻度で処理するコードを書けるなんて
君はすごい人だな（ｗ

0017名無しさん＠お腹いっぱい。

NGNG

読み難くなるけど、早くなる（悪いプログラムと紙一重）

・再起を使わない
・ループを展開する
・div()などを使う
・関数などは展開する
・データなどを変換しないように作る
・使用頻度の高い関数などをアセンブラにする
・etc...

0018名無しさん＠お腹いっぱい。

NGNG

ここにも、コンパイラが最適化したコードよりアセンブラで書いたほうが
速いと思ってるぢぢゐが・・・

0019名無しさん＠お腹いっぱい。

NGNG

コンパイラの知り得ない情報（アクセスパターンとか）を知ってる人が
書いたアセンブラは速いよ
よくて倍ぐらいの速度しか出ない気はするけども。

0020>18

NGNG

大抵の場合は人がやった方が速くなるよ。
コンパイラの進歩はそんなに進んでないって事だね。

0021名無しさん＠お腹いっぱい。

NGNG

コンパイラの標準関数やクラスライブラリは安全の為のコードを
何重にも掛けていますから、それで余計に遅いです。

0022>18

NGNG

あのさ、コンパイラで完全に表現出来る事なら、まあ無理に使う必要が無いレベルだと思うよ
でも、アセンブラじゃなきゃ表現出来ない事も多いよ。
たとえば
１）ＣＦ（キャリーフラグ）ＯＦ（オーバフロー）を使う
２）実行番地の保存（コルーチンとか簡易並列処理）

0023名無しさん＠お腹いっぱい。

NGNG

>18
ちみは逆アセしたコードとか見た事あるの？

0024引用くん

NGNG

アルゴリズムはこうです。
void Excpy_memcpyclip(UBYTE *pbDst＠｀ UBYTE*pbSrc＠｀ int iSize)
{
//pbSrcからpbDstに０以外の値をコピーする。
for(; iSize>0 ; iSize--＠｀ pbSrc++＠｀ pbDst++)
{
if(*pbSrc != 0)
{
*pbDst = *pbSrc; //０以外の値をpbDstに描き出す
}
}
}

改善前
extern void Excpy_imemcpyclip(UBYTE *pbDst＠｀ UBYTE *pbSrc＠｀ int iSize);
#pragma aux Excpy_imemcpyclip=\
" test ecx＠｀ ecx"\
" jz quit"\ //０だったら抜ける
" again: mov al＠｀[edx] "\ //alにpbSrcの色データを入れる
" test al＠｀al "\ //if(*pbSrc == 0)
" je check "\
" mov [esi]＠｀al "\ //*pbDst=*pbSrc ０以外なので書きだす
" check: "\
" inc edx "\ //pbSrc++
" inc esi "\ //pbDst++
" dec ecx "\ //iSize--
" jnz again "\ //iSize!=0の間はループする
"quit: "\
parm [esi][edx][ecx] modify [al esi edx ecx];

改善後
pbSrcから３２Ｂｉｔレジスタへ一気に４バイト読み込んで、メモリアクセス回数を４分の一に減らす。
extern void Excpy_imemcpyclip(void *pBuffer＠｀void const *pSorce＠｀ int const iSize);
#pragma aux Excpy_imemcpyclip=\
"mov edi＠｀ecx"\
"shr edi＠｀2"\
"test edi＠｀edi"\
"jz loop1"\
"again4: mov ebx＠｀[eax] "\
" test bl＠｀bl "\
" je check1 "\
" mov [esi]＠｀bl "\
" check1: "\
" test bh＠｀bh "\
" je check2 "\
" mov [esi+1]＠｀bh "\
" check2: "\
" lea eax＠｀ [eax+4] "\
" shr ebx＠｀ 16"\
" test bl＠｀bl "\
" je check3 "\
" mov [esi+2]＠｀bl "\
" check3: "\
" test bh＠｀bh "\
" je check4 "\
" mov [esi+3]＠｀bh "\
" check4: "\
" dec edi"\
" lea esi＠｀[esi+4]"\
" jnz again4 "\
"loop1:"\
"mov edi＠｀ecx"\
"and edi＠｀3"\
"test edi＠｀ edi"\
"jz quit"\
"again: mov bl＠｀[eax] "\
" lea eax＠｀[eax+1]"\
" test bl＠｀bl "\
" je check5 "\
" mov [esi]＠｀bl "\
" check5: "\
" dec edi"\
" lea esi＠｀[esi+1]"\
" jnz again"\
" quit: "\
parm [esi][eax][ecx] modify [bl edx eax edi esi];

改善前は486DX-33MHzで30f/sでしたが改善後は90f/sとなり３倍高速になりました。

002518

NGNG

ああ、めまいが…
まず、４８６とかで「速くなったよ」はがぢぢゐだと逝っておこう。
＞１９、２０
最近のプロセッサ用に、アウトオブオーダー実行やディレイドブランチで
パイプラインを乱さないように最適化されたコードより速いコードをアセンブラ
で書くのは、無理です。

＞２１
それは、クラスライブラリの呼び出し部分をアセンブラで書く話ですか？
それとも、クラスライブラリをアセンブラで書きなおす話ですか？
どちらにしても、アセンブラ以外で書いた自前のライブラリに置きかえれば済むことです。

＞２２
ワタシが１８で書いたのは実行速度の事です。
「だからアセンブラで書いたほうが高速だ」という話である事を説明してください。

＞２３
ＭＳＣのＶｅｒ５くらいまでは、コンパイラの吐いたコードを手直しして高速化する
ような事はしょっちゅうやってました。
そもそもワタシは８０８０のアセンブラからプログラムをしています。

＞２４
古いＣＰＵの例を出すんなら、ＭＳＣあたりで、hugeポインタを扱う
コードとかだしたらどうですか？当時なら1ケタ違う例が出せますよ（藁

0026名無しさん＠お腹いっぱい。

NGNG

小手先の高速化よりほかにやることがないですかね。

0027名無しさん＠お腹いっぱい。

NGNG

まぁ、アルゴリズムの大幅な見なおし以外に、効果的な高速化ってケースによりますからね。
まぁ、「これで効果的な高速化が出来る場合もある」ってのはいろいろあるもんですね。
まぁ、どれもいっぱーい廻るループの内側ならそこそこ効果あるんでしょうね。

002822>25

NGNG

>ワタシが１８で書いたのは実行速度の事です。
　私も同じ趣旨ですよ。

>「だからアセンブラで書いたほうが高速だ」という話である事を説明してください。

たとえばＣでスマートに書けるならＣで書いて不満が出るような事は無いでしょう。
ただ、Ｃの範囲ではスマートに書けない事があって、その場合は
アセンブラを併用した方が速いという意味で書いたつもりです

たとえば多倍長処理とかやっぱりキャリーを見たいでしょう？

002922

NGNG

私あてではありませんが、
>アウトオブオーダー実行やディレイドブランチでパイプラインを乱さないよう
>に最適化されたコードより速いコードをアセンブラで書くのは、無理です。
私はＤＳＰも書きますが、手間はかかりますが、やっぱり性能を出すには
それでもやらなければならない事がありますよ。
といってもＤＳＰの場合の最内ループは比較的単純ですけどね。
コンパイラよりは何割かは頑張れますよ

0030名無しさん＠お腹いっぱい。

NGNG

なんか、話がどんどん細かい方にいってるね、おもしろいのでつづけてください。

0031名無しさん＠お腹いっぱい。

NGNG

顕微鏡で覗くミクロの世界だね。

0032>

NGNG

マクロな最適化は人手でやるしかないのでしょうか？

0033名無しさん＠お腹いっぱい。

NGNG

ケースバイケースだということが理解できない１８もかなり厨房度高し‥

0034名無しさん＠お腹いっぱい。

NGNG

マクロな最適化＝不要なプログラムを作らない

日本でもアナリストやコンサルタントがもてはやされるようになって
きたのは、このあたりまえの事実に気付く人がようやく増えたから。

003518>33

NGNG

それは１７に逝ってやってくれ。

0036名無しさん＠お腹いっぱい。

NGNG

ところで最近のコンパイラって、MMXとか3DNow!の命令って
asm命令使わなくっても出してくれるの?

0037>1

NGNG

処理を早くしたい場合、
qsortを使わない>ソートを使わなくてすむ実装を考える
doubleは極力使わない>固定小数点を使う
sin等の関数も使わない>テーブルを参照する
malloc等の速度を計測する>必要に応じてwwwに転がっている高速なやつを使う
strchr等の関数を計測する>必要に応じて以下同文
Cの範囲では、このくらいまで可能と思います

0038名無しさん＠お腹いっぱい。

NGNG

アセンブラで書いたほうが確実に早くなりますよ。っていうか早く出来ない人は
使わないでしょ。
P6コアのFPUの場合、コンパイラは整数と浮動小数点レジスタがエイリアスされて
いるだけでPORT0以外で並列処理されることを見落としてレイテンシ計算を短く見
積もってくれたりもしますから。後P5コアだとfxchがポストフィックス扱いになる
ことも注意点ですね。

0039名無しさん＠お腹いっぱい。

NGNG

ようするに、出来る範囲で高速化の手法を選べってことだな。
１には理解できない領域に突入してる事は確かだろうが（藁

004039

NGNG

をっと、煽られるまえに書いておこう、オレも理解できない領域に突入してるよ。

0041名無しさん＠お腹いっぱい。

NGNG

たしかに３８はさっぱりわからないな（ｗ

0042名無しさん＠お腹いっぱい。

NGNG

最適化されたコードをさらに研ぎ澄ます
インテルの本とかも、WEBにあるから、そーゆーのみればーー

0043名無しさん＠お腹いっぱい。

NGNG

圧縮伸長なら、ほぼ圧縮伸長ルーチン部が全体の７～９割の処理になるのは判っている
と思う。すでにプロファイル済み。

１）並列処理を出来るように考える
　　ＣＰＵのレジスタ長が32bitとか64bitあるので並列に処理させられるように
　　考えるとＮ倍になる。
２）とにかく検索が高速になるよう「表引等」工夫する

３）アセンブラを視野に入れて、キャリーを使うアルゴリズム
　　シフトだけでなく回転等も使えると考えて最適化を考える
　　で、インラインアセンブラを使う事を厭わない

４）とにかく本人がコンピュータ本だけでなく数学物理迄色々勉強する
　　雑学知識が案外アルゴリズム作成に役立つ

0044名無しさん＠お腹いっぱい。

NGNG

アセンブラでバリバリ最適化しました
Pentium3で速度が上がりました
でも遅くなったと言う人がいます
Athlonでは遅くなりました

要するにターゲットを何にするかも決めずに
最適化がどうのといったところで話しにならん
机上の空論の前にアルゴリズムを見直せ

0045名無しさん＠お腹いっぱい。

NGNG

速度に関係無い話だけどNTPみたくシビアなタイミングが必要な
アプリではアセンブラも現役

004638

NGNG

言葉で説明するのが苦手ですみません。たとえば
fld [memory]
はPORT2で実行されますから実質0クロック扱いにすること、
fadd st＠｀st(1)
fxch st(2)
は実行順番が
fxch st(2)
fadd st(2)＠｀st(1)
と入れ替わりストールの条件が変化するといいたかったわけです。

0047名無しさん＠お腹いっぱい。

NGNG

>44

esiとedi使ったときで速度が違うって聞いたよ>AMD
アルゴリズムでどうにかなるのかな

まあ、アセンブラ使うんだったら、各CPUごとにコード書くんだろうなあ

0048名無しさん＠お腹いっぱい。

NGNG

コンパイラが
REP MOVSD
吐いてるのを見た事無いんだけど、
こういうの使いたければアセンブラ必須ですよね？

>47
例えば、インテルではストールしないけど、AMDだとストールしてしまう
みたいなのってあるんですかねぇ？
AMDのCPUの仕様が知りたい。どっかにないですか？

004948(連カキコ)

NGNG

自分はVC++6.0を使ってるんですが、
ESIとかEDIレジスタをあんまり使ってくれないのは、
気のせいかな？

0050＞３８

NGNG

やっぱりよくわからないので、具体的にコンパイラの吐いたコードと
アセンブラで書いたコードの比較きぼっ

0051>48

NGNG

VCだとmemcpy関数は存在せず以下のように展開される

; 12 : 　　　　memcpy(pDest＠｀pSrc＠｀nSize);

　　　　mov　　　　ecx＠｀ DWORD PTR _nSize$[esp-4]
　　　　push　　　　esi
　　　　mov　　　　esi＠｀ DWORD PTR _pSrc$[esp]
　　　　mov　　　　eax＠｀ ecx
　　　　push　　　　edi
　　　　mov　　　　edi＠｀ DWORD PTR _pDest$[esp+4]
　　　　shr　　　　ecx＠｀ 2
　　　　rep movsd
　　　　mov　　　　ecx＠｀ eax
　　　　and　　　　ecx＠｀ 3
　　　　rep movsb
　　　　pop　　　　edi
　　　　pop　　　　esi

0052名無しさん＠お腹いっぱい。

NGNG

厨房な質問ですみませんが、プロファイルとかプロファイラーってなんですか？
VCやVSについてるんですか？
教えてください。

0053FBI職員

NGNG

特殊な能力の持ち主に難事件の解決のヒントをもらっています。
これをプロファイリングといいます。

005447>48

NGNG

>例えば、インテルではストールしないけど、AMDだとストールしてしまう
>みたいなのってあるんですかねぇ？
午後のこ～だの作者のとこに少しだけ
ttp://homepage1.nifty.com/herumi/adv/adv30.html

>AMDのCPUの仕様が知りたい。どっかにないですか？
ここかなぁ
ttp://www.amd.com/support/techdocdir.html

005550>38

NGNG

void foo(float *p3＠｀ float *p1＠｀ float *p2)
{
　　*p3 = p1[0]*p2[0] + p1[1]*p2[1] + p1[2]*p2[2] + p1[3]*p2[3]
　　　　+ p1[4]*p2[4] + p1[5]*p2[5] + p1[6]*p2[6] + p1[7]*p2[7];
}
これを gcc -O9 -mpentiumpro -march=pentiumpro -ffast-math -S
でコンパイルすると
mov 　　eax＠｀p1
mov 　　edx＠｀p2
fld 　　dword ptr [edx]
fld 　　dword ptr [edx + 4]
fxch　　st(1)
fmul　　dword ptr [eax]
fxch　　st(1)
fmul　　dword ptr [eax + 4]
faddp
fld 　　dword ptr [edx + 8]
fmul　　dword ptr [eax + 8]
faddp
fld 　　dword ptr [edx + 12]
fmul　　dword ptr [eax + 12]
faddp
fld 　　dword ptr [edx + 16]
fmul　　dword ptr [eax + 16]
faddp
fld 　　dword ptr [edx + 20]
fmul　　dword ptr [eax + 20]
faddp
fld 　　dword ptr [edx + 24]
fmul　　dword ptr [eax + 24]
faddp
fld 　　dword ptr [edx + 28]
fmul　　dword ptr [eax + 28]
faddp
mov 　　ecx＠｀p3
fstp　　dword ptr [ecx]
こうなりました。
手作業で最適化するとPentiumPro用だと
mov 　　EAX＠｀p1
mov 　　EDX＠｀p2
fld 　　dword ptr [EAX + 0*4]
fmul　　dword ptr [EDX + 0*4]
fld 　　dword ptr [EAX + 4*4]
fmul　　dword ptr [EDX + 4*4]
fld 　　dword ptr [EAX + 1*4]
fmul　　dword ptr [EDX + 1*4]
fld 　　dword ptr [EAX + 2*4]
fmul　　dword ptr [EDX + 2*4]
fld 　　dword ptr [EAX + 3*4]
fmul　　dword ptr [EDX + 3*4]
fld 　　dword ptr [EAX + 5*4]
fmul　　dword ptr [EDX + 5*4]
fld 　　dword ptr [EAX + 6*4]
fmul　　dword ptr [EDX + 6*4]
fxch　　st(4)
faddp　　st(6)
fld 　　dword ptr [EAX + 7*4]
fmul　　dword ptr [EDX + 7*4]
fxch　　st(3)
faddp　　st(5)
faddp　　st(5)
faddp　　st(3)
fxch　　st(1)
faddp　　st(3)
faddp
mov　　EAX＠｀p3
faddp
fstp　　dword ptr [EAX]
こうなります。fldをレイテンシ計算からはずしているところが味噌です。
ただしスタックが深いためDOS窓が開いていると頻繁にタスクのスイッチング
が入るようでレジスタの退避に時間がかかってかえってスピードが落ちます。

0056名無しさん＠お腹いっぱい。

NGNG

FPUはにがてだな。。整数の方は多少わかるんだけど。

fld;fmulは同時実行できるが
faddpが間に入るとダメってこと？
fld;fmul
faddp
fld;fmul
faddp
とはいかないってことなのかな。

それとも後半に秘密が？

005756

NGNG

あと整数の場合(Cで擬似的に説明すると)
long *a＠｀ *b;
a[i+0] = b[i+0];
a[i+1] = b[i+1];
a[i+2] = b[i+2];
a[i+3] = b[i+3];
とするより
a[i+4] = b[i+4];
a[i+1] = b[i+1];
a[i+2] = b[i+2];
a[i+3] = b[i+3];
って感じで一度16バイト先をアクセスしておくと、
キャッシュフィルの関係で速くなる
FPの計算でも使えるんじゃないかな。。

0058>57

NGNG

ふむふむ。サンクス。

0059名無しさん＠お腹いっぱい。

NGNG

<57
aが16バイト境界に配置されてるとしたら、どっちも一緒の気がするです・・・
むしろ、キャッシュへの転送が終わる前にアクセスできる可能性を考えると
アタマからアクセスしたほうが早いような気も…

0060>52

NGNG

プログラムの実行時の動作を分析するツール。主にチューニングに使う。
VC++のPro版以上についてる。

006157>59

NGNG

逆です。
前述の手法は16バイト境界に配置されていないと意味がありません。
一度+16バイトをアクセスしておくと、キャッシュのモジュールが
そこから16バイトをフィルし始めます(+16～+31)。その間CPUは
+4～15のデータ処理し、CPUがそれらを処理し終わった頃には
+20～+31のキャッシュフィルが終わっているので、CPUそれらの
データをキャッシュからアクセスできるので、高速になります。

順順にアクセスした場合+4～+15のキャッシュモジュールが
メモリからフィルするよりもCPUの方が速いので(当たり前。
そのためにキャッシュがある)、CPUは待たされてしまいます。

0062名無しさん＠お腹いっぱい。

NGNG

プロファイラをかけるとコードのどの部分がより頻繁に実行されたか
を調べてくれます。さらにvc++にはありませんがgccやいくつかの
コンパイラはプロファイラの出力を再度読み込んで、その情報を元に
オプティマイズする、という機能もあります。

手間がかかりますが、2～5割速くなります。もちろん人間のオプティマイズ
には及びませんが、広大なプログラムを漠然と(笑)速くするのにはある程度
効果があります。

006359>61

NGNG

すいません、>>57の後は
a[i+4] = b[i+4];
a[i+0] = b[i+0];
a[i+1] = b[i+1];
a[i+2] = b[i+2];
a[i+3] = b[i+3];
だと思ったので・・・

006463（途中でおしちった）

NGNG

で、j+0～j+3にアクセスするのに、一度j+4を空アクセスするのか、と。
すると、処理が終わるのはj+3までキャッシュに入る時間で決まるので一緒
ではないか、と。

つまり、>>57はj+0～j+7までアクセスするっていう事ですよね？

006561>64

NGNG

そうですね。全体を書かないとだめですね。

a[0] = b[0];
for (i = 0; i < 256 - 4; i += 4) {
a[i+4] = b[i+4];
a[i+1] = b[i+1];
a[i+2] = b[i+2];
a[i+3] = b[i+3];
}
a[i+1] = b[i+1];
a[i+2] = b[i+2];
a[i+3] = b[i+3];

といったパターンのように連続して演算する場合です。
上記はメモリコピーですが、原理的には他のパターンにも
当てはまります。FreeBSDのカーネル内のbcopyとかに
使われています。

0066名無しさん＠お腹いっぱい。

NGNG

速いマシンを買う。

0067>66

NGNG

つまらんよ

0068>67

NGNG

でもね仕事だとねそう言いたくなるときもねあるのよ（TT
メモリ32MでNT動かしててスワップしまくっててすげい遅くてさ
テストで32M増設するだけで１０倍ぐらいの速度になるのにさ
プログラム直せっていわれたり（TT
32Mのメモリぐらい俺が自腹切って買うから付けてくれって思う（TT

0069>68

NGNG

ありがちなネタなんでつまらんといったのだが^^;キモチハワカルガ
jmp far [プログラマ板]

■ このスレッドは過去ログ倉庫に格納されています