inner.hの int bの後の;が抜けた

common.h
/* 共通ヘッダ */
struct A* func1(struct A* p, struct A* q);
void func2(struct A*);
...

user.h
/* ユーザ用ヘッダ */
struct A { int a; };
#include "common.h"
...

inner.h
/* 内部実装用ヘッダ */
struct A { int a; int b }
#include "common.h"
...

では駄目なの?

>世の中無知な人だらけなのか、googleが大したことのないツールなのか。
逆のパターンでミスってしまったことがある私は何も言えない(^^;

って±のことを言うのですが、ぐぐってみると上から十件くらいは、
暗号を複号するツールだったり、複号事象だったりします。
世の中無知な人だらけなのか、googleが大したことのないツールなのか。

それは、member template と partial specialization の機能を使えば
普通のtemplateで可能ですね...

if(バグ付でコンパイルしたい気分){
　符号付shortを符号無に拡張する;
}
…そんなコンパイラ、アリですか？

それも試してみたんだけど駄目。途中にprintfを入れるとOK。
多分気分しだい(苦笑)。

short a;
volatile int b = a;
long long c = b;
は駄目?

C++に限った話ではないですが、x(a++);は、tmp = a; ++tmp; x(a); a = tmp;
と等価になります(これをどう最適化するかはコンパイラ次第)。
a++の評価で tmp = a; ++tmp;
x(a++)の評価で x(a);
x(a++);で;が来たので副作用を行なうので a = tmp;
となります。stlのコンテナはこのCの評価順を模倣して演算子が定義されて
いるのでthe_container.erase(it++); ということが出来るのでした。
これはSTLをやってると必ず一度は議論になります

> 他の人のために補足しておくと

フォローありがとうございます。
私はC++不可の環境で開発することが多く、C++での開発は数えるほどしかないのでまだまだ勉強中です。

お返事ありがとうございます。
Google で検索して、
http://www.sun-inet.or.jp/~yaneurao/cppmaniax/chap0004.html
ここのページを読んで納得しました。
これに限らず、規格書をきちんと読まないと危険ですね。気をつけないと。

> 規格上 erase() の返り値は void です。

他の人のために補足しておくと、連想コンテナ(map/multimap/set/multiset)の erase() の場合
です。シーケンス(deque/list/vector) の erase()では削除した要素の次の要素を指すイテレータを返します。

>iterator erase(iterator it) は削除された次のデータを指すイタレータを返すので、
> itr = map.erase(itr);
> と書くのが普通ではないですか?

規格上 erase() の返り値は void です。
iterator が返るのはVC++の独自拡張で他のコンパイラでは使えないんです。

9月13日の日記で

> map.erase(itr++);

としていますが、iterator erase(iterator it) は削除された次のデータを指すイタレータを返すので、
itr = map.erase(itr);
と書くのが普通ではないですか?

MSDN 2003/1 の map::erase には以下の記述があります。
>iterator erase(
> iterator _Where
>);
>iterator erase(
> iterator _First,
> iterator _Last
>);
(略)
>Return Value
>For the first two member functions, a bidirectional >iterator that designates the first element remaining beyond >any elements removed, or a pointer to the end of the map if >no such element exists.

いや、そうじゃなくて(補完する機能があるというのは教習所でなくったってなんらかの本で知るでしょう)あの実験での「見えない」と目をつぶったときの「見えない」とは意味が異なることに私が気がついてなかったなということです。
盲点の解説については光が視神経にたどり着くまでの話しか見たこと無かったのです。

脳が視神経から送られる画像を補完する機能を持っていることは、運転免許
を持っている人なら、教習所で教えられたはずだと思うのですが....

ちなみにintel版はこんなの。

http://www.intel.com/jp/developer/software/products/mkl/features.htm

http://pc.watch.impress.co.jp/docs/2003/0702/amd.htm

amd版のMath kernel Libraryですね。BLAS+LAPACK+FFT(複素数もアリ)。32bit版もサポートするので、intelでもP4なら走ると思いますが。 3DNowの時と違ってターゲットは科学技術用途なんでしょうけれど。再配布とかのライセンスの詳細がよくわからないです。

>昔の「平均的な」お父さん像とはすごく離れていると思います。
大学のときの友達の家ではご飯はかならずお父さんのお茶碗からよそると決まってたそうです。
お父さんの帰るのが遅いときは一度お父さんのお茶碗によそってからお釜に戻していたそうな。
お風呂や新聞も同じようなものらしい。結構驚いた記憶が。

向田邦子のお父さんは特別厳しい人だったということを聞きます。昔の「平均的な」お父さん像とはすごく離れていると思います。

> 16byteアライメントってなんですか？

PenIIIやPen4ではSSE利用時にデータのアクセスが128bit(=16byte)単位で行えます。
そのときにメモリのアドレスが16byteの倍数になっていないと高速に動作しないという現象があるのでデータをそのように配置する必要があります。
これを16byteアライメントといいます。

> SSEをVC++6.0では使えないのですか？
http://msdn.microsoft.com/vstudio/downloads/tools/ppack/download.aspx
を入れれば組み込み命令として使うことが出来ます。

はじめまして。

SSEの使い方を調べているうちにこのページにたどり着きました。
それでいろいろ分からないことがあって、教えてもらいたくて書きこんでいます。答えてもらえると幸いです。

16byteアライメントってなんですか？
SSEをVC++6.0では使えないのですか？

返信おねがいします。

> これは条件が大雑把だからかな?
こんな感じ
http://homepage1.nifty.com/herumi/adv/adv43.html#019
です。結論は見え見えだが...

これは条件が大雑把だからかな?
min(x, y)^2 == 1 - max(x, y)^2 (*)
なら大分減るかも。
たとえば x=1, |y|<√(ε/2) の場合は x^2+y^2は1になるけど(*)は殆どの場合成立しない。ただしεはDBL_EPSILON。

あまりに不規則で予想できませんね。
どうなってるんだろう。

というか止めていなかったのに今気付いたんだけど、
n = 16
n = 17
solution: [ 1 2 4 8 16 32 27 26 11 9 45 13 10 29 5 17 18 ]
見事に私の予想は外れ。n=15,16は解なしなのにn=17は解あり。

> ひたすら場合わけ&計算って感じなんですね。
> あんまりうれしくない...
四色問題もそうだったし、コンピュータ援用で解決する問題はそういう結末のことが多いみたい。

> これでしょうか
> http://www.oishi.info.waseda.ac.jp/~oishi/draft.pdf
どうもありがとうございます。
ひたすら場合わけ&計算って感じなんですね。
あんまりうれしくない...

これでしょうか
http://www.oishi.info.waseda.ac.jp/~oishi/draft.pdf
http://arxiv.org/PS_cache/math/pdf/9811/9811073.pdf

> > それより今年素因数分解(素数判定じゃないよ)が多項式時間で解けることが証明されたって本当?
> それは聞いたこと無いなあ。もし本当ならえらいこっちゃ。
> #以前の素数判定みたいに係数がめちゃくちゃでかい?
あるいは n^100 だったりして。大騒ぎになってないところを見ると実用的ではないのかな?
ま、量子コンピュータが出てしまえば素因数分解も(楕円)離散対数もアウトだからね。

> それより今年素因数分解(素数判定じゃないよ)が多項式時間で解けることが証明されたって本当?
それは聞いたこと無いなあ。もし本当ならえらいこっちゃ。
#以前の素数判定みたいに係数がめちゃくちゃでかい?

Van der Werdenが無理を証明したと思うけど、最密充填が証明された話は聞かないよ。
それより今年素因数分解(素数判定じゃないよ)が多項式時間で解けることが証明されたって本当?

もうあきらめます....

n = 13
n = 14
solution: [ 1 2 21 17 11 5 9 4 26 6 47 15 12 7 ]
solution: [ 1 2 13 7 5 14 34 6 4 33 18 17 21 8 ]
solution: [ 1 2 28 14 5 6 9 12 48 18 4 13 16 7 ]
solution: [ 1 10 2 16 32 20 3 21 33 5 4 22 8 6 ]
solution: [ 1 5 2 24 15 29 14 21 13 4 33 3 9 10 ]
solution: [ 1 15 34 2 3 17 7 6 8 4 19 9 48 10 ]
solution: [ 1 4 20 2 12 3 6 7 33 11 8 10 35 31 ]
solution: [ 1 12 48 6 2 38 3 22 7 10 11 5 4 14 ]
solution: [ 1 33 14 36 2 16 6 5 8 4 3 25 21 9 ]
solution: [ 1 12 11 6 2 18 16 35 21 4 3 40 5 9 ]
solution: [ 1 9 8 28 2 24 5 6 44 14 20 7 12 3 ]
solution: [ 1 25 23 4 10 2 3 17 11 7 6 45 21 8 ]
solution: [ 1 9 14 26 4 2 11 5 3 12 27 34 7 28 ]
solution: [ 1 19 16 5 8 2 7 55 11 14 12 6 24 3 ]
solution: [ 1 12 22 7 17 2 18 10 23 32 25 6 5 3 ]
solution: [ 1 4 6 31 3 13 2 7 14 12 17 46 8 19 ]
solution: [ 1 17 8 5 24 14 2 4 3 12 27 34 22 10 ]
solution: [ 1 8 16 10 12 19 2 11 4 3 42 27 23 5 ]
solution: [ 1 18 7 17 15 14 2 4 56 5 23 10 3 8 ]
solution: [ 1 4 8 52 3 25 18 2 9 24 6 10 7 14 ]
n = 15
n = 16

という訳で n = 7 以上の素数の場合にのみ解なしという予想はもろくも崩れさりました。 n=15が解なしなので。 n=15に半日以上かかり、n=16は未だに何も表示しません。このあたりが限界か。
枝刈りも途中で重複が出たらアウトにしているだけなので理論的にもっと深いことが分れば何かできるでしょうけど。

>10秒程でn=11 の解なしが分かる。
そこまでいくにはまだしばらく電車の中で悩む...

寝てたら無駄に気付いたので、更新。3秒程で n=10 10秒程で
n=11 の解なしが分かる。いまだに n=12 の解の5つ目が出て
なかったのが2分ほどで、
n = 12
solution: [ 1 2 14 4 37 7 8 27 5 6 13 9 ]
solution: [ 1 2 9 8 14 4 43 7 6 10 5 24 ]
solution: [ 1 2 12 31 25 4 9 10 7 11 16 5 ]
solution: [ 1 2 14 12 32 19 6 5 4 18 13 7 ]
solution: [ 1 7 2 22 4 16 3 11 29 21 12 5 ]
solution: [ 1 11 2 8 7 25 6 3 27 20 19 4 ]
solution: [ 1 6 2 33 17 14 12 10 15 3 16 4 ]
solution: [ 1 14 3 2 4 7 21 8 25 10 12 26 ]
solution: [ 1 31 10 2 4 3 8 13 5 20 14 22 ]
solution: [ 1 9 48 2 4 18 5 11 3 12 13 7 ]
solution: [ 1 8 5 2 18 11 10 22 6 24 23 3 ]
solution: [ 1 6 28 2 13 16 23 19 5 9 8 3 ]
solution: [ 1 3 12 34 21 2 8 9 5 6 7 25 ]
solution: [ 1 4 7 3 16 2 6 17 20 9 13 35 ]
solution: [ 1 35 26 3 11 2 4 21 7 5 10 8 ]
solution: [ 1 15 5 3 25 2 7 4 6 12 14 39 ]
solution: [ 1 41 8 4 17 2 3 6 7 20 10 14 ]
solution: [ 1 7 6 16 15 2 9 10 40 3 20 4 ]
n = 13
と分かる。寝ます。

1分ほどで
n = 10
solution: [ 1 2 6 18 22 7 5 16 4 10 ]
solution: [ 1 36 2 12 7 8 3 13 4 5 ]
solution: [ 1 4 2 20 8 9 23 10 3 11 ]
solution: [ 1 18 3 2 8 4 29 11 9 6 ]
solution: [ 1 4 3 10 2 9 14 16 6 26 ]
solution: [ 1 18 28 5 2 8 6 11 9 3 ]
n = 11

半日後
n = 12
solution: [ 1 2 14 4 37 7 8 27 5 6 13 9 ]
solution: [ 1 2 9 8 14 4 43 7 6 10 5 24 ]
solution: [ 1 2 12 31 25 4 9 10 7 11 16 5 ]
solution: [ 1 2 14 12 32 19 6 5 4 18 13 7 ]
(多分解は5つ以上あるのでn=12は途中)
ということで n=11 以上になると単純な枝刈りではものすごく
遅い。(PPC 600mHzじゃなくて dual 1GHzの方を使えよという
話もある)

枝刈りするときに根本まで刈ってしまっていたのを修正
ここまでに10sくらいかかるようになった。
localhost% g++ -x c++ -O3 a && ./a.out
n = 1
solution: [ 1 ]
n = 2
solution: [ 1 2 ]
n = 3
solution: [ 1 2 4 ]
n = 4
solution: [ 1 2 6 4 ]
solution: [ 1 3 2 7 ]
n = 5
solution: [ 1 5 2 10 3 ]
n = 6
solution: [ 1 2 5 4 6 13 ]
solution: [ 1 2 7 4 12 5 ]
solution: [ 1 3 2 7 8 10 ]
solution: [ 1 3 6 2 5 14 ]
solution: [ 1 7 3 2 4 14 ]
n = 7
n = 8
solution: [ 1 2 10 19 4 7 9 5 ]
solution: [ 1 8 2 3 21 4 12 6 ]
solution: [ 1 12 2 6 3 7 22 4 ]
solution: [ 1 4 2 10 18 3 11 8 ]
solution: [ 1 3 8 2 16 7 15 5 ]
solution: [ 1 3 5 11 2 12 17 6 ]
n = 9
solution: [ 1 2 4 8 16 5 18 9 10 ]
solution: [ 1 16 22 2 3 4 6 8 11 ]
solution: [ 1 8 12 2 3 13 24 4 6 ]
solution: [ 1 14 8 2 28 3 6 7 4 ]
n = 10

> n = 6
> solution: [ 1 2 5 4 6 13 ]
> solution: [ 1 2 7 4 12 5 ]
> solution: [ 1 3 2 7 8 10 ]
> solution: [ 1 3 6 2 5 14 ]
おかしいな、もれてる。枝刈りがおかしいかな。

枝刈りかつ重複なしバージョン。枝刈りがかなりしょぼい。
n=10が解なしと分かるのとコンパイルにかかる時間が同じ
ぐらい... stlのコンパイルは遅し。

localhost% g++ -x c++ -O3 a && ./a.out
n = 1
solution: [ 1 ]
n = 2
solution: [ 1 2 ]
n = 3
solution: [ 1 2 4 ]
n = 4
solution: [ 1 2 6 4 ]
solution: [ 1 3 2 7 ]
n = 5
solution: [ 1 5 2 10 3 ]
n = 6
solution: [ 1 2 5 4 6 13 ]
solution: [ 1 2 7 4 12 5 ]
solution: [ 1 3 2 7 8 10 ]
solution: [ 1 3 6 2 5 14 ]
n = 7
n = 8
solution: [ 1 4 2 10 18 3 11 8 ]
n = 9
n = 10
n = 11

このあと n=11 が解なしと分かるのは1分くらいかかった。
それ以上は実行中。

> [1 3 2 7]
> [1 5 2 10 3]
> [1 7 3 2 4 14]
> という感じかな。

[1 2 6 4]
とか
[1 3 6 2 5 14]
という別解もあるんやね。

鎖状じゃなくて、環状だよね。すると、
[1]
[1 2]
[1 2 4]
[1 3 2 7]
[1 5 2 10 3]
[1 7 3 2 4 14]
という感じかな。

例えばf(x,0)=1-Π_{j=0}^{2n}(1-w^jx)=1-(1-x^{2n+1})=x^{2n+1}
だから明らかに0ではないですよ。

ω^(2n+1)=1, ω!=1の条件が付いてるから、
求める式は0になると思いますが。
証明は書き切れませんので省きますけども。

>明日東京出張なので電車の中で考えるか(^^;
電車の中で考えるんじゃなかった。酔ってしまった。
追求しても面白そうでないのでもう保留かな。

>二項展開して根号の残る項は打ち消し合うから削除しただけ
私もごちゃごちゃやったけどきれいにならない。
で、Σの式がZ係数多項式になるのを示そうとしてるのだけどなかなか。明日東京出張なので電車の中で考えるか(^^;

> > n=4のときは
> > x^9+y^9+9xy(x^2+y)^3 + 3x^3y^3
> > となってアウト。一般形は根号使わないと書けない。
こんなんで良かったら書けるんだけど(根号のやつから殆ど
進化なし--二項展開して根号の残る項は打ち消し合うから削除
しただけ)Σは反則だよね。
y^{2n+1} + {1\over2^{2n}}\sum_{i=0}^n
{}_{2n+1}\mathop{\rm C}{}_{2i}x^{2n+1-2i} (x^2+4y)^i

> n=4のときは
> x^9+y^9+9xy(x^2+y)^3 + 3x^3y^3
> となってアウト。一般形は根号使わないと書けない。
もうちょっと続けると
f0=x^ 1+y^ 1;
f1=x^ 3+y^ 3+ 3*(x*y);
f2=x^ 5+y^ 5+ 5*(x*y)*(x^2+y);
f3=x^ 7+y^ 7+ 7*(x*y)*(x^2+y)^ 2;
f4=x^ 9+y^ 9+ 9*(x*y)*(x^2+y)^ 3+ 3*(x*y)^3
f5=x^11+y^11+11*(x*y)*(x^2+y)^ 4+11*(x*y)^3*(x^2+y);
f6=x^13+y^13+13*(x*y)*(x^2+y)^ 5-26*(x*y)^3*(x^2+y)^2;
f7=x^15+y^15+15*(x*y)*(x^2+y)^ 6+50*(x*y)^3*(x^2+y)^3+ 3*(x*y)^5;
f8=x^17+y^17+17*(x*y)*(x^2+y)^ 7+85*(x*y)^3*(x^2+y)^4+17*(x*y)^5*(x^2+y);
だから何かありそうな気はするけど眠いのでおやすみなさい。

> ポッカ レモン100?
まさにそれでした。
コップにとくとくと注いでごくっと一飲み...

もう答えがでてたのか(^^;
私はまだ求められてないです...

ポッカ レモン100?
それなら私は良く使うよ。ちなみに電気ポットに薄めていれて沸騰させると内壁の赤いのが良く落るよ。

n = 0, 1, 2, 3 のときは
x+y
x^3+y^3+3xy
x^5+y^5+5xy(x^2+y)
x^7+y^7+7xy(x^2+y)^2
となって何となく規則がありそうなんだけど、
n=4のときは
x^9+y^9+9xy(x^2+y)^3 + 3x^3y^3
となってアウト。一般形は根号使わないと書けない。

答はこんな感じかな?
y^{2n+1} + \left({{x+\sqrt{x^2+4y}}\over2}\right)^{2n+1} + \left({{x-\sqrt{x^2+4y}}\over2}\right)^{2n+1}
もちろん計算すれば多項式になるんですがnで一般形を書こうとするとこうなってしまう

おやー。intelはPrescott New Instructionの説明を除去しましたか。http://www.sandpile.org/misc/news.htm
からあと何週間かはpdfをdownloadできるらしいですが。
何故に消すのだろう？さすがにAMDとかVIAの人はもう読んだ後でしょうに。

>(3D Now @intel...)
ですね。私も見たとき pfacc などを思い出しました。
複素数演算のほかには FFT で威力を発揮するかも...

>最初からこういう使いやすげな命令はSSE2にいれとけー。
後だしIntel。

>がまだ羊年対応になってないね。
おお。すっかり忘れてました。大晦日のときは考えていたのだけど...
近いうちに更新します。

レジスタ内水平演算、交互要素の加減算
SIMD要素の隣要素へのコピーとかは複素数演算用かー。
(3D Now @intel...)
あとは128bitアライメント無しのときもそこそこ早いLoad
(Storeは無いの？)
丸め付きFPUstackのPop to register
Threadのwait監視用命令

感想
最初からこういう使いやすげな命令はSSE2にいれとけー。
そうすればgccのC99モード複素数演算のコードもきっと(以下略)
アライメントがなければXMMレジスタをgccが使いこなして(以下略)

真面目なalgorithmの教科書ですね。

ところで、17桁の問題は17で割り切れるほうのやつが、10と17が
互いに素であることを利用しないといけない分だけ高級かな?
平方数のほうは、連続する桁の積が平方数になる、なのでもう少しやさしい?

http://homepage1.nifty.com/herumi/soft.html
の冒頭のメッセージがまだ羊年対応になってないね。

> へるみさん、ありがとうございます！さっそくCマガジン買ってきます。しかしウェーブレット変換は難しいですね。頭から煙が出そうです。
普通のフーリエ変換が理解できるなら、三角関数をWalsh関数系に
置き換えただけです。

> 私は門外漢なのでなんとも言えませんが google で検索すると結構ヒットするようですしとっかかりはいくらでもありそうな。
> Cマガジンでもときどき wavelet の解説が載りますよね。
> そのあたりからはじめればどうでしょうか。
へるみさん、ありがとうございます！さっそくCマガジン買ってきます。しかしウェーブレット変換は難しいですね。頭から煙が出そうです。

> 今、多重解像度解析をやっているんですが何から手をつけて良いやら。
> できたらご意見を聞かせていただきたいです。
私は門外漢なのでなんとも言えませんが google で検索すると結構ヒットするようですしとっかかりはいくらでもありそうな。
Cマガジンでもときどき wavelet の解説が載りますよね。
そのあたりからはじめればどうでしょうか。

ウェーブレット変換のプログラムについて何か教えてくれませんか？
今、多重解像度解析をやっているんですが何から手をつけて良いやら。
できたらご意見を聞かせていただきたいです。

> well-definedなの?って書いてましたがこんな話があるのですね
> >http://www6.plala.or.jp/swansong/003700taikakusen.html
しょうもない突込みをするならば、第n番目の数の少数第n位が
すべて8であれば、くだんの日本語で表される数は
0,9999999999999999999....=1(1未満ではない！)
となるので表の中に出てこないのは当然ですね。

というのはおいといて、自己言及(表に付いての言及)を禁止すれ
ばwell-definedになると思います。

一応確認ですがmoveqの方が速いのは
paddq mm0, [esi]
だから、ってことはないですよね。
por 　　　　　　mm0, [esi]
で結果が変わったりはしないよね？

> 超お久しぶりです。
お久しぶりです(^^;

>別件のつながりで先ほど試したのですが、
>１割ほど高速化されるようです。大きすぎ。
最近のCPUはますますメモリとの速度差が激しくなってますからね...
movups は 4回読んだほうが速いぐらいですし...

超お久しぶりです。
かなり昔にスプライト転送する際、
転送先アドレスのアラインに合うよう、１ドットずつ
ずらしたスプライトを複数保持する、という話があり
ましたのを覚えてますでしょうか。

別件のつながりで先ほど試したのですが、
１割ほど高速化されるようです。大きすぎ。
バカバカしいですが、魅力的です。

well-definedなの?って書いてましたがこんな話があるのですね
>http://www6.plala.or.jp/swansong/003700taikakusen.html

π=4*arctan(1), e=Σ_{n=1}^∞(1/n!) はXの元ですが、
どんな複雑な式（連分数とか）でもTeXを用いれば一直線に
書くことができます。従って「文」を有限なものに限れば
すべての文は有限長の文字列で表されます。よって文字セット
を高々可算とするならばXは可算集合です。

> 気になっていたのですが、なぜライブラリ化すると、遅くなるんでしょう？原因は分かりませんでしたか?
もう一度とってみましたがやはり違う。0.9secと1.0secなので有意差でしょう。
やってて気がついたのですがlibTest.exeをVC++上で[実行]すると非ライブラリ版と同じ0.9secなのにコマンドラインでlibText.exeを実行すると1.0sec。ループを5倍に増やすと4.5secと5secとなって明らかに違う。うーん。

返事が遅れてすいませんでした。大学のレポートが多くて, MTの実験が全然できていない状況です。今度、まとまった時間が作って、へるみさんのコードを解読してみます。

気になっていたのですが、なぜライブラリ化すると、遅くなるんでしょう？原因は分かりませんでしたか?

SSE2 を使ってがんばってみました。
ライブラリにしないバージョン(mymt.dsp)でなら yosirin さんのよりは多少速くなってます。
やはり alignment されていないと駄目駄目みたいですね。
>http://homepage1.nifty.com/herumi/soft/mymt1019.tgz

> すいません。もう一度当てたら動きました。
> SP5にはSP5のprocessor packを当てないといけないのですね。

おお、それはよかったですね。

FastTwisterのx86の部分(Temperingじゃない方)をSSE2で高速化しようと考えているのですが、アラインメントが合わない所が数ヶ所あるためにパフォーマンスが落ちるみたいなんです。
多分、アラインメントさえあっていれば、x86よりもSSE2で書いた方が速くなると思うのですが。どうでしょうか？

少しの工夫でアラインメントを無理やり合わせられる方法があればいいのですが。

すいません。もう一度当てたら動きました。
SP5にはSP5のprocessor packを当てないといけないのですね。

> yosirinさんのプログラムをコンパイルしようとしたのですがうまくいきませんでした。SP5とprocessor packあてたのに変だなあ。

なんででしょう？？
僕のはちょっと古くて、SP4とprocessor packです。
どんなコンパイルエラーが出るのでしょうか？

yosirinさんのプログラムをコンパイルしようとしたのですがうまくいきませんでした。SP5とprocessor packあてたのに変だなあ。

> 確かに速くなってますね。うう私も遊びたい。
実験いつもありがとうございます。
遊んでください(笑)

＃学校のPCでも試してみました。
Pen!!! 450MHz
x86_MersenneTwister() + x86_Tempering() : 5.4980[sec]
x86_MersenneTwister() + MMX_Tempering() : 4.4260[sec]
MMX_MersenneTwister() + x86_Tempering() : 5.3170[sec]
MMX_MersenneTwister() + MMX_Tempering() : 3.6760[sec]

Pen4以外の環境で実行したFastTwisterは, MMXTwisterよりも遅いようです。でも、Pen4ではFastTwisterの方が速いので利用価値はあるかな？Pen4以外でも速くなるように考えてみます。

#祝：１億個/秒の乱数生成速度の達成！
#もうちょっとパフォーマンス上げてみたいですね(笑)

> # ほんの少し速くなりました
x86_MersenneTwister() + x86_Tempering() : 1.6320[sec]
x86_MersenneTwister() + MMX_Tempering() : 1.1320[sec]
x86_MersenneTwister() + SSE2_Tempering() : 0.9610[sec]
MMX_MersenneTwister() + x86_Tempering() : 1.6930[sec]
MMX_MersenneTwister() + MMX_Tempering() : 1.2120[sec]
MMX_MersenneTwister() + SSE2_Tempering() : 1.0210[sec]
確かに速くなってますね。うう私も遊びたい。

MMX_MersenneTwister()を使ったときの値が、Willametteとぜんぜん違いますね。やっぱり。
Northwoodでは、x86_MersenneTwister()でもMMX_MersenneTwister()でも性能があんまり変わっていませんね。(ということはNorthwoodのMMXの性能が改善されたということかな?)

> 私もそのうち試してみます。
よろしくお願いします。

Reloadのswitch部のオーバーヘッドをなくしたやつを作ってみました。
# ほんの少し速くなりました
http://isweb9.infoseek.co.jp/art/yosirin9/beta/FastTwister1.1.zip

> # Northwoodでの結果がどうなるのか楽しみです。
x86_MersenneTwister() + x86_Tempering() : 1.8630[sec]
x86_MersenneTwister() + MMX_Tempering() : 1.1810[sec]
x86_MersenneTwister() + SSE2_Tempering() : 1.0220[sec]
MMX_MersenneTwister() + x86_Tempering() : 1.8420[sec]
MMX_MersenneTwister() + MMX_Tempering() : 1.1820[sec]
MMX_MersenneTwister() + SSE2_Tempering() : 1.0120[sec]
となりました(P4-1.7G)。
私もそのうち試してみます。

返事が遅れてすいません。改造していたらあっという間に時間が過ぎまして、、、。

> ・MMX化しているMersenneTwister();は乱数作成600回に1回程度しか
> 　呼ばれません。配列を読み出すだけの場合も高速化の余地があるかも

その部分を高速化したものを作ってみました。
http://isweb9.infoseek.co.jp/art/yosirin9/beta/FastTwister.zip

# Willametteでもかなり速くなりましたよ。
# Northwoodでの結果がどうなるのか楽しみです。

値のばらつきについて、
・配列はアライメントしないと時によって不利な条件になることがあります
・キャッシュヒットしない条件で測定すると不利です
　例えば前回の読み出しから時間が経っている場合など
・MMX化しているMersenneTwister();は乱数作成600回に1回程度しか
　呼ばれません。配列を読み出すだけの場合も高速化の余地があるかも

それはさておき、
やはりNorthwoodの方が速そうですね。アライメントされていないときの
挙動が良くなったように見えなくも無い・・・かな。
もしくは、unroll で高速化するWillametteは、OoO実行に失敗している
可能性も考えられます。MMXのみ遅いとするとMMXのデコードが遅いか、
レジスタリネームが効いていないか・・・興味深い現象ですね。

P4-1.7G での結果です。
unroll の方が遅いですね...

PerformanceTest1の実行中...
COK MT 2.1130[sec]
MMX MT 0.8010[sec]
MMX(unroll) MT 1.4520[sec]

PerformanceTest2の実行中...
COK MT 2.1130[sec]
MMX(unroll) MT 1.3220[sec]
MMX MT 1.5320[sec]

PerformanceTest_MMXRand
MMX MT 1.5620[sec]

PerformanceTest_MMXRand_unroll
MMX(unroll) MT 1.5120[sec]

PIII-700 での結果です。

PerformanceTest1の実行中...
COK MT 5.2170[sec]
MMX MT 2.0730[sec]
MMX(unroll) MT 1.9730[sec]

PerformanceTest2の実行中...
COK MT 5.2180[sec]
MMX(unroll) MT 1.7920[sec]
MMX MT 2.4040[sec]

PerformanceTest_MMXRand
MMX MT 2.2030[sec]

PerformanceTest_MMXRand_unroll
MMX(unroll) MT 1.8330[sec]

> #レジスタ間movが速くなるとか、Northwood C1 stepでHW
> #プリフェッチがようやくONになるとか、真偽不明な噂は沢山
> #あるけど確認手段が無いよね〜

ゲート数が数千万にもなると完全にバグを取るのは不可能なんでしょうけど、できる限りバグが入っていないCPUを作ってほしいですね。

> 実用上はほとんど影響ないですよ(^^;
> Northwoodで新設されたバグもありますし(^^;
> 唯一キャッシュ倍増というのは御利益ありますけど。

やっぱりL2が512KBだとパフォーマンスは全然違いますか？

> ＃全てのWillametteが数倍遅いとなるとかなりの人が気が付くと
> ＃思うけどなぁ・・・

そうですよね。今回のは稀なケースなんでしょうか？


MMXTwisterのunroll版の整理ができたのでアップしておきました。
#実行結果を報告してもらえたら嬉しいです。
#ブラウザにペーストしてダウンロードして下さい
http://isweb9.infoseek.co.jp/art/yosirin9/beta/MT_testV2.zip

> > 別のマシン(model 0と1の両方)でも同じ傾向になりました。
> > Pen2-400に負けるP4って一体...

へるみさんのNorthwoodの結果を見る限り、Normal rand以外は
Pen2とPen4でクロック比通りに近い速度ですね。アーキテクチャが
異なるのでこれが速いか遅いかは微妙な感じもします(予想より
MMXが速いかな？)

> Northwoodコアの方は期待通りに動いているので、
> Willametteコアはやっぱり何かバグがあるんでしょうね。

errata-N49でWriteCombiningがおかしいとか？そうだとすると
被害範囲が広いのでもっと他にも影響が出るので考え難いか。
仕様上問題の無い些細なバグはerrataに載らないでしょうから
そのあたりですかね・・・

#レジスタ間movが速くなるとか、Northwood C1 stepでHW
#プリフェッチがようやくONになるとか、真偽不明な噂は沢山
#あるけど確認手段が無いよね〜

> Pentium4 Processor Specification Updateを見たんですけど、
> こんなにいっぱいバグがあったなんて知りませんでした。
> Northwoodコアが出てからＰＣ作ればよかった、、、。

実用上はほとんど影響ないですよ(^^;
Northwoodで新設されたバグもありますし(^^;
唯一キャッシュ倍増というのは御利益ありますけど。

> それにしてもPen2-400MHzに負けてるなんてかなりショックです。
> WillametteコアではMMXが正常に機能していないんでしょうか?

数倍遅いというのは致命的ですよね。
でも、Nortwoodで数倍速くなったソフトウェアというのも聞きません。
もっと他のMMXコードや、SSEを使った場合なども調べてみないと
なんとも言えません。まあ、"何か"は起きているみたいですね。
＃全てのWillametteが数倍遅いとなるとかなりの人が気が付くと
＃思うけどなぁ・・・

> 別のマシン(model 0と1の両方)でも同じ傾向になりました。
> Pen2-400に負けるP4って一体...

僕のPen4を調べてみたら、Willametteコアの中でも一番古いRevisionがB2のCPUでした。へるみさんのPen4-1.7GHzのはNorthwoodコアですよね？("憂鬱な午後のひととき"に書いてあったGRX81G/PのリンクでVAIOのスペック見ました)
Northwoodコアの方は期待通りに動いているので、Willametteコアはやっぱり何かバグがあるんでしょうね。

Pentium4 Processor Specification Updateを見たんですけど、こんなにいっぱいバグがあったなんて知りませんでした。こんなことならNorthwoodコアが出てからＰＣ作ればよかった、、、。

それにしてもPen2-400MHzに負けてるなんてかなりショックです。
WillametteコアではMMXが正常に機能していないんでしょうか?

> ・・・悲しい性(^^;
うう、明日は4時半起きなので我慢してやめておきます。

> ほぇー面白いですね。ということはyosirinさんのは
> Willametteということかな？
> MMXかL1キャッシュまわりのバグがあったっけ？errataをチェック？

別のマシン(model 0と1の両方)でも同じ傾向になりました。
Pen2-400に負けるP4って一体...

>この忙しいときにはまると困るので(^^; ほんのちょっとだけ.
ええ、ちょっとだけ(^^;
Pentium2@400MHz
COK randomMT 9.0780[sec]
MMX randomMT 3.4530[sec] => 2.4840[sec]
Normal rand 2.0150[sec]
・・・悲しい性(^^;

> Willametteだとyosirinさんと同じ結果が出ました。
> 古いP4だとmovapsがやたら遅かったとかメモリバスが違うとか
> そんなのですかね。しかし数倍も変わるかなあ。
ほぇー面白いですね。ということはyosirinさんのは
Willametteということかな？
MMXかL1キャッシュまわりのバグがあったっけ？errataをチェック？

> 同一バイナリで違う結果ですか・・・・・何だろ？？
手持ちの別の(笑)P4マシンでテストしてみました。
Willametteだとyosirinさんと同じ結果が出ました。
古いP4だとmovapsがやたら遅かったとかメモリバスが違うとか
そんなのですかね。しかし数倍も変わるかなあ。

> コンパイラがMMXコードの扱いに失敗してるとか？
あ、MT再実験.exeを実行した場合の話ですね。
同一バイナリで違う結果ですか・・・・・何だろ？？

> 私も試してみましたがyosirinさんのは遅い気がします。
MMX版だけ数倍速いですね。
かなり面白い状態ですが、原因は何でしょうか？
コンパイラがMMXコードの扱いに失敗してるとか？

> 現段階でのunroll版のMMXTwisterの性能は以下のとおりです。
> Pen4 1.5GHz
> MMX randomMT 3.6450[sec] >> MMX randomMT unroll版 2.41[sec]
私も試してみましたがyosirinさんのは遅い気がします。
オリジナルのexeで
COK randomMT 2.1130[sec]
MMX randomMT 0.8320[sec]
Normal rand 1.9320[sec]
となりMMX版が速かったのですが...(@P4-1.7GHz)
ちなみにほんのちょびっと修正したら 0.7710secになりました。
まだ unroll はしてないです。

> 単純に1命令で読み込めるデータが多いからです(^^;
> メモリアクセスは1命令/クロックサイクルなので意外と重要です。

なるほど。

> 結果が楽しみです。unrollはPen4にはメリットが無いかもしれませんが、
> 旧世代のCPUのためにしておく方が良いと思います。

さっそく作ってみました。
現段階でのunroll版のMMXTwisterの性能は以下のとおりです。
Pen4 1.5GHz
MMX randomMT 3.6450[sec] >> MMX randomMT unroll版 2.41[sec]

Pen2も実験したかったのですが、今日いきなり液晶ディスプレイのバックライトが壊れて真っ暗になってしまった(バックライトが壊れただけなので明るい所にいけばぎりぎり見えます)ので、実験できませんでした。（1999年１月に購入したVAIOノートです)

unrollだけでまさかこんなに高速化できるとは思ってもいませんでした。また、定数をレジスタに格納してからループするようにしてみたのですが、全然速くならず、逆に微妙に遅くなったので原因がよく分らない状態です。

> 最後の説明で「メモリアクセスはSIMDの方が断然有利です。」
> というのはどういう理由からなのでしょうか？
単純に1命令で読み込めるデータが多いからです(^^;
メモリアクセスは1命令/クロックサイクルなので意外と重要です。

> とりあえず、unroll版のMMXTwisterを作ってみようとおもいます。
結果が楽しみです。unrollはPen4にはメリットが無いかもしれませんが、
旧世代のCPUのためにしておく方が良いと思います。

> ご想像のとおりPentium4は、整数演算に限って言えば、
> MMXよりALUの方が処理スループットが高いです。
> ＃Pen4ではMMXが弱まりALUが強化されているため差が顕著です

はじめまして。お返事ありがとうございました。
やっぱりそうでしたか。

> SIMD用の演算パイプが1本しかないので、過去のように
> MMXの方が必ずスループットが高いという事は無くなっています。
> SSE_INTとALUの場合でもALUの方が速いことがあると思います。
> ただ、Pen4は平均3op/clk発行が限界なので、SIMDを使用して
> 命令数を削減した方が有利な場合は考えられます。また、
> メモリアクセスはSIMDの方が断然有利です。

詳しい説明をしていただき、ありがとうございます。
ちょっと質問があります。
最後の説明で「メモリアクセスはSIMDの方が断然有利です。」というのはどういう理由からなのでしょうか？

> 話は変わりますがMMXTwisterは最適化の余地を残しています。
> 定数のレジスタへの格納、ループの展開などはした方が良いと
> 思います。また、SSE化するならアラインメントされていない
> 読み込みはシフトなどを使用してでも避けるべきです。

計さんへの返事にも書きましたが、とりあえず、unroll版のMMXTwisterを作ってみようとおもいます。

> ループ回数が決まっていてレジスタが余っているのだから，もう1段unrollしてはどうでしょうか？

はじめまして。お返事ありがとうございました。
とりあえず、unroll版のMMXTwisterを作ってみようとおもいます。

> まだちゃんと見てないのではずしてるかもしれませんが
> > movq mm1, QWORD PTR [esi]
> > movq mm2, QWORD PTR [esi+4]
> の alignemnt ミスのペナルティが大きいとか。

このコードはどのCPU(Pen2,Pen4など)でもalignemntミスのペナルティが発生するのでしょうか？（初歩的なことですいません）

> あと dec かなあ。
> つっかレジスタ余ってるのだからdouble***をメモリに置いとくのは凄い無駄な気が。
> 計さんが見たら「もったいね〜」って叫びますね(笑)。

そういえば、Ｃマガジン(2001,10月号)にもincやdecは、Pen4では避けたほうがいいと書いてあるのを思い出しました。

余っているレジスタを最大限に活用しなさいということですね。

> > 実験したソースをここに置いておきました。
> > http://isweb9.infoseek.co.jp/art/yosirin9/beta/MT_test.zip
> 取れないです(^^;

ブラウザにそのURLをペーストしたらうまくダウンロードできました。

寝ぼけていたので削除して書き直します(^^;

ご想像のとおりPentium4は、整数演算に限って言えば、
MMXよりALUの方が処理スループットが高いです。
＃Pen4ではMMXが弱まりALUが強化されているため差が顕著です

SIMD用の演算パイプが1本しかないので、過去のように
MMXの方が必ずスループットが高いという事は無くなっています。
SSE_INTとALUの場合でもALUの方が速いことがあると思います。

ただ、Pen4は平均3op/clk発行が限界なので、SIMDを使用して
命令数を削減した方が有利な場合は考えられます。また、
メモリアクセスはSIMDの方が断然有利です。

話は変わりますがMMXTwisterは最適化の余地を残しています。
定数のレジスタへの格納、ループの展開などはした方が良いと
思います。また、SSE化するならアラインメントされていない
読み込みはシフトなどを使用してでも避けるべきです。

> 計さんが見たら「もったいね〜」って叫びますね(笑)。

はい，叫びました(笑)．それはともかく．

ループ回数が決まっていてレジスタが余っているのだから，もう1段unrollしてはどうでしょうか？

> 何故かPen4のMMX版の方がCOK randomMTよりも遅い結果が出ました。
> 他のマシンではMMX版の法が高速に動作していました。（←予想通り）
>
> 原因は何だと思いますか？

まだちゃんと見てないのではずしてるかもしれませんが
> movq mm1, QWORD PTR [esi]
> movq mm2, QWORD PTR [esi+4]
の alignemnt ミスのペナルティが大きいとか。
あと dec かなあ。
つっかレジスタ余ってるのだからdouble***をメモリに置いとくのは凄い無駄な気が。
計さんが見たら「もったいね〜」って叫びますね(笑)。

> 実験したソースをここに置いておきました。
> http://isweb9.infoseek.co.jp/art/yosirin9/beta/MT_test.zip
取れないです(^^;