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

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

#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
らしいので、どれが悪さしてるか調べてみたら？

こんなことあるんだなぁ･･･。

まず確認する必要があるのは、
最適化による数値誤差で
ループ数に変化がないかだな

テキトーに
インライン展開されないコードがあるから、遅くなってるとか

アセンブリ出力してみればいいじゃん。
後は、プロファイラでホットスポットを割り出したり。

多分、x87命令が使われていて遅くなってる
/arch:SSE2を追加してみたら？

/Odでも使っとるがな。

/Ogを外すと幾分マシになる。
#pragma optimize("g", off)

/fp:preciseからstrictに変更しても良くなるね。
fastは遅い。

VC11じゃ別に遅くなったりしないんだけどな

>>893
BCC 6.4.4でCodeGuardを掛けてみた。

Error 00001. 0x400000 (Thread 0x0124):
Exception 0xC0000091:
| dai2.cpp line 141:
| printf("n = %d ", n);
| lambda = c[n-2] * c[n-2] - c[n-3] * (c[n-1] - b[n-1]);
|>dp = (b[n-1] * c[n-2] - b[n] * c[n-3]) / lambda;
| dq = (b[n] * c[n-2] - b[n-1] * (c[n-1] - b[n-1])) / lambda;
| /* Δp,Δqをp,qに反映 */
Call Tree:
0x004017C4(=dai2.exe:0x01:0007C4) dai2.cpp#141
0x32C9C8CA(=CC32120MT.DLL:0x01:09B8CA)

Exception 0xC0000091とはfloat overflowなので、大きすぎる値が入って実行不能な
状態です。ちなみにn=430〜470位の範囲で(乱数を初期値にしているからか)出ます。

COBOLがC/C++より処理が早いというのは本当ですか？早いならなぜですか？

>>911
時と場合に寄る。
配列を対象に演算したりすんのは、得意だよね。

>>912 �d

COBOLが走る環境では大抵CPUが10進演算サポートしてるから、キャラクタ10進数や2進化10進数の演算はベラ速いね

>>914
いまどき速いと言われるCPUで10進演算をサポートするものなんか無いだろ

最近だとIBMのPOWER6/7でハードウェアサポートが付いてる
一般人には触る機会がほとんど無いが……

「SPARC64 X」では、10進演算、暗号処理、コピーなどのソフトウェア処理の一部を
プロセッサで実行するソフトウェア・オン・チップを採用し、最適化されたソフトウェア
との組み合わせで、さらなる飛躍的な性能向上を実現します。

>>917
Javaのシェアをx86からごっそり奪うつもりだろう
それにJavaの超越関数はIEEE754の64bit精度なので、内部で80bit精度で
演算しているx86は結果が異なって来るとしてソフトウェアエミュレーションしてるもんなあ

strictfpじゃない場合は結果が異なることを容認してるんじゃないの？

SSE2も使えないJVMなんか使うから

お薦めのC++のルンゲクッタクラスはありませんか？

>>915
そもそもCOBOLはPCでは使われないからなぁ

http://special.nikkeibp.co.jp/ts/article/aa0e/109171/
http://software.fujitsu.com/jp/cobol/products/#os-linup
http://jp.opencobol.org/

>>923
中間言語or機能拡張前提では言語の種類は問わないってのが今のトレンドなんだな

そもそもCOBOLはPCでは使われないからなぁ

[Mac/NUC] AGK / DarkBASIC / Basic4GL / 99BASIC 2013 Part.1
http://jbbs.livedoor.jp/bbs/read.cgi/computer/43761/1367197701/l100

ここまでllvmなし

テンプレートの最適化って技術的にはどうなん？

「クロスワード ギバー」
http://katahiromz.web.fc2.com/xword/

これを高速化する方法を教えて下さい。お願いします。

自分で考えろアホ

アルゴリズムの最適化はスレ違いだ。自分で考えろ。

>>929
1マス1Byteにしてみれば？
0=空白,1=黒,2=ア みたいに

>>929
マルチポスト
ttp://toro.2ch.net/test/read.cgi/tech/1371305675/615

コーディングレベルでの最適化は玄人しかやらないほうがいい
初心者〜中級者がやってもほとんど変わらないか、かえって遅くなる

std::string やコンテナ周りの記述は、最適化でも消えない無駄な書き方をするのは多い
記述方法を変えるだけで 30% も高速化して、個人的な報酬の面ではうはうはだったけど、
会社としてはまずいんじゃなかろうか、と思った

200行もかけた関数のデバッグ頼まれて、sprintf()一回呼ぶだけに書き換えたら詐欺呼ばわりされたのを思い出した。
寧ろ、もとの関数を書いた奴にこそ文句を言うべきだろうに。

>>936
内容が分からんから何とも

諸君はgprof使ってるか？ 色々捗るぞ

自分が書いたコードではあまり使わないけど、他人が書いたコードの初動調査には重宝するね。

GCCって最適化が何種類かあるみたいだけど
どのオプションが最強？

-O9じゃねーの？

自分で調べられないようならとりあえず -O2 使っとけ。
-O3 だと、たまに妙なバグを踏んだりする危険がちょっと高いから。

そのレベルなら-Oでいいだろ。今だと普通に-O2相当だ。

最適化厨

最適化中

メモリに余裕があるアプリならもうshortとかは使わない方がいいのかな

使えよ。
movzx/movsxなんて通常のmov命令と比べてもゼロコスト同然なんだし

今はキャッシュの利用効率とかで速度が決まる時代だから、メモリ節約する意義は昔より大きいくらいだよ。

そのマシンのワードサイズより小さい転送はむしろペナルティがある

なぜ、そしてどこにペナルティがあるのか説明できたらOK
そうでなければ理解してないので却下

組み込み経験者だと、1ビットの信号を8ビットのポートに出す話を譬えに出すだけでわかってくれる問題だな。

レジスタの部分アップデートが、なんでパイプラインの邪魔になるのか、まで説明できるかな組込み屋さんはw
（できる人も一定割合でいるとは思うけどね）

上位ビットのゼロクリアあるいは符号拡張する命令を備えてないプロセッサが
どれだけあるのかと。
x86でもQuarkあたりでもmovsx/movzxは使える

パーシャルレジスタストール？？

>>953

>>952
レジスタリネーム機構は毎回新しいレジスタを確保して演算結果を格納するから
部分的な更新があると一回の参照で処理できないからね
movzxとかvzeroupperで依存関係の問題を解決できるのは更新されなかった部分をゼロとみなすことが可能になるから

アセンブラレベルの最適化を勉強したいけど、本とか一冊もないのな

最近はインテルの出してるドキュメント嫁とか、そういう感じ？

古い本だけどHacker's Delightは現代でも通用する部分はある

やっぱりソースコードこそ最良の教科書
gccのソース読め

COINSもよろしく

>>940
-O2がいいよ
-O3でGCCビルドするとバグって通らない

「最適化がバグってる」とか主張する奴の何割が
規格違反のコードを書いてるんだろうな

うむ。
strict aliasing ruleについて完璧に理解している奴だけに許された台詞だよなw

gccの最適化で落ちるってのは最近どっかで見たような
↓これもいい例だが

http://homepage1.nifty.com/herumi/diary/1401.html#8

その例だとコンパイルは通っているんだな。
>962の言う「通らない」は何のことなんだろ。

バリデーションじゃね？

>>965の例のASM出力見る限りでは一応intの境界にあわせてやれば
通るコードにはなってるようだ。
16バイト境界に合ってないからというよりint境界にあってないのが直接の原因。

アラインメント制約が緩いx86だから最適化してない状態ではたまたま動くだけで
RISCだとアラインメント例外吐くかアドレス下位2〜3ビットを無視してロードだろうな。

最適化すると内部エラーでコンパイルできないってのは時々出くわすような。
リンク時の最適化オプション使うと処理が複雑になるからバグやエラーになりやすいのでは？

前に別スレに書いたVC2012の_mm256_extracti128_si256のバグは最適化すると
処理対象のレジスタがおかしくなるってやつだったな。
あれは結局2013で直ってるからそれで解決という返事だったよ…
これね
＞VC2012 x64コンパイラの_mm256_extracti128_si256バグにハマってしまった。
＞当面は_mm256_extractf128_si256使って回避した方がいいよ。

http://www.beta.microsoft.com/VisualStudio/feedback/details/812347/visual-c-17-18-sse-avx-bugs

こんなのあったんだな。
Intrinsicsってキャストがすごいめんどくさいわ無駄なvmov*を吐くわで
自動ベクトル化やりつつ細かいところをNASM/YASMでいいやと
思ってしまった。
ところでcmovに対応する組み込み関数ってないよね？

VC2013で__vectorcallが追加されたけど、旧バージョンやICCでは使えないから
あまり細かいとオーバーヘッドが気になることもありそうな。
intrinsicはインラインで展開されるメリットがあるけど、インラインアセンブラだって
最適化に支障があってもインラインで展開されるんだよなぁ。
VCのx64はそこらが不便だね。

ところで、_mmのSSEコードを_mm256に変換した程度でやたら遅くなる原因ってあるかな？
VEX128のSSEにした時は速くなってるし、インテルのアナライザでもスループットの問題はないから
原因がよく分からなくて。
やたら遅くなるといえばデノーマル数の処理速度には注意って話があったんだけど、
もしかしてAVXのデノーマル数の処理ってSSEの倍くらい掛かる？

ICCには汎用レジスタも含めて極力レジスタ渡しするコール規約として__regcallがある。
小さい関数ならASM化してしまうのも手ですね。

> やたら遅くなるといえばデノーマル数の処理速度には注意って話があったんだけど、

普通にデノーマル数自体が遅い
http://www2.kobe-u.ac.jp/~lerl2/l_cc_p_10.1.008/doc/main_cls/mergedProjects/fpops_cls/common/fpops_denormal_num.htm

ソフト処理だから当然ベクトル幅に比例した時間がかかかる。

0に切り捨てるモード使おうか。
http://www2.kobe-u.ac.jp/~lerl2/l_cc_p_10.1.008/doc/main_cls/mergedProjects/fpops_cls/common/fpops_reduce_denorm.htm





ところで、なんでどこそこにIntelコンパイラのドキュメントのミラーがあるんだろうな

>>971
＞ソフト処理だから当然ベクトル幅に比例した時間がかかかる。
あぁ、やはりベクトル幅が関係しますか。
CPU内部で例外が発生してマイクロコードで実行してるのかな？

>>965の問題はICCだとこんな方法が使える？

http://www.isus.jp/article/compileroptimization/avx_part3/
＞__assume() を使うことによりコンパイラーの最適化に有用な情報を伝えることが可能です。
＞以下の例では変数 num1 が 8 の倍数である（具体的な値は問わない）と指示することで、
＞b[0], b[0+num1], b[0-num1] が同じ 32 バイト境界のアドレスにあることがコンパイラーに伝わります。
＞void foo(float *restrict a, float *b, int n, int num1){
＞ int i;
＞ __assume_aligned(a, 32);
＞ __assume_aligned(b, 32);
＞ __assume(num1%8==0);
＞ for (i=0; i<n; i++){
＞ a[i] += b[i]+b[i+num1]+b[i-num1];
＞ }
＞}

何言ってるんだか。
コンパイラへの指示で、使い方の制約じゃないから関係ないや。

埋め

976

977

978

あと一つ

980

実に6年越しでやっと消費出来たのかー。
感無量だね。
次スレどうするのかしら？

究極の最適化は「何もしないこと」である。



というわけで次スレも最適化してしまおう。

次スレいらないでしょ

最適化すると、別スレならずに他のスレにインライン展開されるな

最適化を定義しよう

必要なら立てればいいじゃん。
俺には「高速化手法」スレと何が違うのかわからない

必要な人いる？

SIMD or マルチスレッド

以上。


って感じだしなぁ･･･ｗ

てすぽ

あとは
・省メモリ化やストリーム制御命令によるキャッシュ効率の向上
・アルゴリズム自体の見直し

大体にC/C++の単発ネタスレ多すぎる気がするんだが
とりあえず俺的に移行先スレはこんなところで。


【C++】高速化手法【SSE】
http://peace.2ch.net/test/read.cgi/tech/1130349336/

アセンブラ 13
http://peace.2ch.net/test/read.cgi/tech/1314512680/

OpenMPプログラミング
http://peace.2ch.net/test/read.cgi/tech/1102483474/

GPGPU#5
http://peace.2ch.net/test/read.cgi/tech/1281876470/

【O(n)】計算量の評価方法について【O(log n)】
http://peace.2ch.net/test/read.cgi/tech/1363854937/

まあ、高速化手法が一番良さそうだね

うん、このスレはお役御免。
ご苦労様でした ∠(｀・ω・´)

6年間お疲れ様でした

うんこの、スレは、お役御免

995

カウントダウンー

996

へいへいへーい

999

1000

このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。