憂鬱な午後のひととき
C++WG AdHoc会議のお知らせ[随時募集中]
FSIJの
g新部、バグを追う旅 2010に行ってきた.
packageのメンテナーは枯れてないマイナーな環境にも対応しないといかんので大変.
"Threads and fork on machine with VIPT-WB cache"はマルチスレッドでforkしたとき, メモリcacheを物理アドレスではなく仮想アドレスで管理するCPU(intelのは大丈夫)上のOSが正しくcacheを破棄しないと非常によくわからないバグになるという話.
マルチスレッドでforkしたらあかんやろと思ったけどロギングのためにsystem()関数を呼んだだけ(?)と言われるとやってしまいそうな気もする.
帰ってから
マルチスレッドのプログラムでのforkはやめようとか
マルチスレッドのプログラミング(Sunのpdf)の「プロセスの生成時のforkの問題」を眺めて,
やっぱり難しいと再認識した.
・
Xbyakにjbやjnaeはあるのにjcが無かった(どれも同じ意味). 今頃気づくなんてと慌てて追加した.
・もう10年以上950円/月でniftyを使ってるけど昔からの会員の
ホームページサービスは上限20MBで追加するなら300MBあたり525円/月.
新しいやつは
100円/月で1GB. サービスが違うから直接は比較できないけど, この不公平感はなんだろう.
朝4時頃ふとgcc 4.5で遅い理由に心当たりがついて試してみたら解決した. 結果としてgcc 4.5は悪くない.
分かってみれば答えは簡単やけど, 個人的に結構はまって悩んだので, ちょっと出し惜しみして状況のおさらいから.
- ペアリングのベンチマークが同一オプションでgcc 4.3に比べてgcc 4.5は遙かに遅かった.
- ベンチマークの値自体は信用できる. 測定時の環境の影響は誤差の範囲.
- ペアリングは整数演算主体のとある確定的なアルゴリズム. その演算時間の殆どはmulというある種の乗算が占める(表のmulとペアリングの処理時間比がほぼ一定なのも傍証).
- mulはtemplateとintrinsic数命令からなる関数のかたまりで, 最適化されること前提のコードである(eg. 再帰templateでループ).
で, 何故mulが遅いのか調べる. 4.みたいな場合はプロファイラはそれ自体が影響を及ぼすので使えない. そもそも遅い箇所もどれぐらい遅いかも分かってる. 知りたいのは何故か, 何が悪いのかだ.
テストプログラムは次の感じ. 最初にmulのベンチマークしてからいくつかの単体テストをして最後にペアリングのベンチマークをとる.
void benchMul()
{
// mulのベンチマーク (A)
// (B)
}
int main()
{
benchMul();
// (C)
unitTest_1();
...
// (D)
...
unitTest_n();
// (E)
benchPairing();
}
ここで次のような奇妙な現象に遭遇した(
19日のそれ).
- 上記テストでmulとペアリングのスコアがgcc 4.5では遅い.
- (C)でexit(1)するとmulのスコアがgcc 4.3並に戻る. この時点で多少混乱する.
- (D)でexitするとmulのスコアが多少悪化する. (E)でexitするともっと悪くなる.
- (B)でexit(1)するのが一番速いのかと思いきや遅いまま. もう何がなんだか.
(B)でexitと(C)でexitの違いはなんだよ, なんでそれがそれより上のコードに影響を与えるのだと思いつつ, asm出力を比較してみる.
すると全然コードが違うのでdiffがとれなくて目でdiffするしかないのだけど, どうやら(B)でexitした場合は(A)のinline展開があまりされていないということが分かった(ここまで昨晩).
inline化されないから遅いというのは想定した理由の一つではあったが, なんでexitが影響するのか見当がつかなかった. でもコードが増えると遅くなるという傾向から, それ系のオプションを探せばいいのではと気がついたのが朝4時.
gccのドキュメント探して見つけた
--param inline-unit-growth=1000 \
--param max-inline-insns-single=1000
をつけると劇的に改善して4.3と同等かちょっとよいぐらいになった(値は試行錯誤の適当. -finline-limitはあまり効果が無かった). gccは最適化でinline関数などを埋め込む場合に, ある一定以上の規模を超えるとやめてしまうようになっている(やみくもにinlineしてもキャッシュを汚染するだけやし).
もともと単体テストなどで大量のinline関数が埋め込まれているところに, gcc 4.3とgcc 4.5で最適化ロジックの変更で出力コード量が変わり, その上限にひっかかってしまったのが理由みたいだ.
gcc 4.3 → 4.4 → 4.5でinline化される対象が増え, 逆に制約にひっかかってinline化されなくて遅くなっていたのかもしれない.
どうりで原因追求のためにmulだけ取り出して
asmを見ても分からなかったわけだ.
ここまでくると上記の奇妙な現象も分かる. main()の中でexitするとそれ以降のコードは最適化により除去され(A)でinline化できる量も増えて速くなる.
(C), (D), (E)と下がるにしたがって(多分(A)に割り当てられるなんらかの量が減って)inline化されにくくなるわけだ. そして(B)でexitした場合はmain()関数が(C)以降のコードを除去できなくて残ったままなので4. の様に遅いままとなる(削除してくれてもいいような気がするが).
試しにvoid benchMul()の直前に
void benchMul() __attribute__((noreturn));
という関数が戻らないことを示すプロトタイプ宣言を追加して(B)でexitすると(C)でexitしたのと同じ結果になった. ああすっきりした.
ちなみに-Winlineオプションをつけるとどの関数がinline化されなかったか, その場合にどうすればよいのかの判断ができる(最後に気がついた).
../src/f3base193.h:242:30: warning: inlining failed in call to
'V128 MIE_ETAT::getTri(const Xbyak::uint32*) [with int bit = 3,
int w = 8, int pos = 3, Xbyak::uint32 = unsigned int]':
--param large-function-growth limit reached
・ひたすら固定長乗算を作ってた. 64bit環境で256bit x 256bit = 512bitならKaratsubaは遅いな.
16回のmulが9回に減ってもaddやsubが増えるので全然ペイしない. 筆算方式(mulが16回)の中でいかにレジスタを使い回すかがポイントみたい. もちろんadd/subの回数が最小でも速いとは限らない.
初めて汎用レジスタ16個使い切った. レジスタ割り当てと演算順序をがらりと変えて何度か作り直してると, 最後にはゼロから書いても一発で動作するようになった.
人として何か間違ってる気がしないでもない.
・higeponさんに指摘されて
x64プログラミングを加筆修正した.
2分法で遅くなってる部分を探そうとコードを消していくと計測結果が変わる不思議. 困ったな.
・gcc 4.5.0の遅い原因を探そうとmulパートのベンチマークが終わったところでexit(1)したらmulの処理時間がgcc 4.3.3並になった.
今更時間計測をポカミスしてるとは思いたくないのだけど(体感速度も明らかに違う)何か変だな. unrollされすぎてキャッシュからはずれてるとか.
・こないだ
『国銅』を読んでたときに, そういや奈良の大仏は何度も見てるけど, 鎌倉のは見たこと無かったっけ, と行ってみた.
こちらは建物の中に入って無いので外からでも見える.そんなに大きくなく, ちょっと猫背っぽい(うつむき加減だからかな). 天気がよいのでしんみりという感じではない. 暗いところにある方が雰囲気が出るのかも.
帰り, ドーナツ買って食べようとしたら目の前でドーナツが消滅した. 一瞬何が起こったのか理解できなかったがどうやらとんびにさらわれたらしい. あまりに鮮やか.
奈良ではソフトクリームを鹿に奪われたこともある. 隙だらけなんやろか.
あらためて
鎌倉の大仏見るとでかい. 解放感があるので小さく見えたか.
gcc 4.5.0をダウンロードしてビルド. 必要な外部ライブラリがまた増えてる.
以前 gcc 4.3.3から4.4.0にしたとき
ペアリングのプログラムが
遅くなってたのでどうなったのかテスト.
pairing on 32bit Core2Duo 1.8GHz single thread
| VC2008 | VC2010 | gcc 4.3.3 | gcc 4.4.0 | gcc 4.5.0 |
|---|
| mul(clk) | 2409.96 | 2409.96 | 2976.48 | 5347.20 | 13737.34 |
|---|
| pairing(msec) | 1.547 | 1.397 | 1.577 | 2.675 | 7.174 |
|---|
gcc 4.3.3 vs. VC2008のときは若干VC勝利, みたいな感じだったのにその後のgccはずたぼろ. VCは順当に高速化されてるのに何故だろう. しゃれにならないぐらい遅い.
さすがにこれは原因を探さんとなあ.
fmathも見てみる.
fmath on 32bit Core2Duo 1.8GHz [unit:clk]
| VC2008 | VC2010 | gcc 4.3.3 | gcc 4.4.0 | gcc 4.5.0 |
|---|
| exp | 22.9 | 19.2 | 19.5 | 18.8 | 19.2 |
|---|
| exp_ps | 80.4 | 50.7 | 83.1 | 83.5 | 83.8 |
|---|
| log | 21.7 | 18.8 | 21.7 | 21.0 | 21.5 |
|---|
| log_ps | 70.9 | 47.8 | 81.0 | 81.8 | 81.5 |
|---|
こちらは遅くなってはいないけどVC2010には劣ってる(てかVC2010凄い). gccのSIMD系intrinsicはまだまだみたい.
とみながたけひろさんにgcc 4.5から新設された-fexcess-precision=fastをつけないと浮動小数点数計算は遅いと
教えていただきました. VCの/fp:fastみたいなもんですかね. ただ今回のベンチではすでに-mssse3 -mfpmath=sse -ffast-math -march=core2つけてたせいか結果に変化はありませんでした. 多分そのオプションはFPUを使ったときのものなのでしょう. ペアリングの方はそもそも浮動小数使ってないです.
もう一度
Xbyak更新
sampleのテストが(win/Linux/Mac) x (32/64)bitの6パターンチェックしなきゃいけなくて大変.
でもおかげで64bit環境に大分慣れた. あと, gitの勉強もかねて
githubにも置いてみた.
Xbyak更新(Macのための微調整)
xbyak_util.hで
#define __cpuid(eaxIn, a, b, c, d) __asm__ __volatile__ \
("cpuid\n" : "=a"(a), "=b"(b), "=c"(c), "=d"(d) : "0"(eaxIn))
というコードを書いていたけど32bit Macでは
can't find a register in class `BREG' while reloading `asm'.
と文句を言われるので
#define __cpuid(eaxIn, a, b, c, d) __asm__ __volatile__ \
("pushl %%ebx\n" \
"cpuid\n" \
"movl %%ebp, %%esi\n" \
"popl %%ebx" : "=a"(a), "=S"(b), "=c"(c), "=d"(d) : "0"(eaxIn))
とebxの代わりにesiを使った. Linuxでも-fpicだとそうなるのかと試したけど違った(picモードでもebxは使える).
Macのgcc特有の現象みたいだ. 後でTAKESAKOさんから
インラインアセンブラでCPUIDその２にあるように
-mdynamic-no-picをつけるとebxも使えると教えていただいた(がこのオプションはLinuxのgccには無い).
VCはintrinsic関数が充実してるとは言え, carry系など足りないものもある. ほんのちょっとだけasm使いたいときは関数呼び出しにするコストが馬鹿にならないのでやっぱりinline asm欲しいなあ.
なんで64bit版ではなくしちゃったのだろう. iccだと使えるみたいだからそちらにするか(マニュアルみる限りgccとVCのinline asm両方サポートしてるみたい).
『国銅』(帚木蓬生)
今年は平城京遷都1300年でNHKでもいろいろ特集がある. あんなでかい大仏今までよく残ってるなと感心する.
その際どうしても教科書に出てくるような歴史上の人物に目がいく. この本はそうではなく, 人足として働いていた(無名の)若者を焦点に当てた.
片田舎で毎日ひたすら銅の原料を掘る.
次は何日も掛けて精製する. 何カ月も掛けて船で運ぶ. 都へ行くのも命懸け. 嵐にも会うし海賊も出る.
都についても何年も掛けて少しずつ大仏を組み立てる. もちろん過酷で怪我や病気で死ぬ仲間も多い. 食事も貧しい. 気が遠くなりそう.
といって小説全体は暗いわけではない. 役人もたまにはみなにごちそうして労ってくれるし, 仲間が死ねば悲しんでくれる頭領もいる.
基本的に"悪人"は出てこない(いやもちろん盗人や殺人はあるけど).
そんな中, 主人公は僧に文字や薬草を教えてもらったり, 仏教の教えを聴いたりする. 都では詩も学ぶ.
僅かな休暇も薬草取りや文字や詩の勉強に費やす姿が尊い. どんな仕事でも心の持ち方でうまくやる.
たいしたものだと思う. ようやく帰郷が許されても帰りももちろん命懸け. ここまで来たら無事帰りついて欲しいものだが.
ラストの決意もいい. いや, すばらしい本だった.
平均年収が300万を切ったって？ それ間違いですから
リンク先で取り上げられている記事は導入部分が平均年収294万5000円を前提に書かれた勘違いだったのだから, そこだけ変更しても論調はおかしくなるしその他の数値の信頼度も低くなる.
単なる
訂正ではなく撤回してしきり直すべきでは.
注文していた本棚が届く. 想像以上に重たくて組み立てるのに難儀した. ただ結構ちゃちい.
3万円て高いなと思ってたけどそうじゃなかったのか. 自分が幼稚園かそこらからある実家の本棚はどっしりとしていつまでもありそうだけど, これはそんなにもたなそう.
PRML読書会に参加.
かなり
ヘビーな計算だった. n_shuyoさん説明うまいなあ.
n_shuyoさんに手取り足取り教えてもらいつつ
Polynomial Semantic IndexingというのをC++で実装してみた.
実際にはSparse Vectorとかは持ってたりするので実装自体はさくっとできたのだけど学習のためのデータとかやりかたとか何も分からんかったのだ. とりあえず動いてるっぽい.
こういう方面はあんましやったことなかったので面白いなあ.
pdfcrop.pl
・pdfファイルの余白を削ってくれる. eprintとか余白が大きいのが多いので印刷時にとても便利だ. TeXやperlを入れておけばwindowsでも使えた.
・『新世界より』(貴志祐介)
上下合わせて1000ページ長. ボリューム感たっぷり. 最初160ページぐらいは少年少女のどこか牧歌的な雰囲気の冒険だったのが, 突如過酷な戦闘シーンへ.
そういえば作者は『黒い家』や『天使の囀り』を書いた人だった. 後半は漫画の『HUNTER x HUNTER』(ここ何年か見てないけどまだやってるのかな)みたいな呪力(超能力)と駆け引き満載. しかもグロテスクで残虐. 恐ろしいけど途中では止められない.
設定が緻密でとにかく凄い小説だった.
64bit整数をdoubleに入れたり戻したりしてた.
uint64_t i = 0xb64000000000ecbf;
double b = i;
std::cout << std::dec << "i="
<< i << ", " << std::hex << i << std::endl;
printf("b=%18f, %.16a\n", b, b);
i = b;
std::cout << std::dec << "i="
<< i << ", " << std::hex << i << std::endl;
// 32bit win
i=13132496513412426943, b64000000000ecbf
b=13132496513412428000.000000, 0x1.6c8000000001e000p+63
i=9223372036854775808, 8000000000000000 // ***
// 64bit win
i=13132496513412426943, b64000000000ecbf
b=13132496513412428000.000000, 0x1.6c8000000001e000p+63
i=13132496513412427776, b64000000000f000
// 32bit/64bit linux
i=13132496513412426943, b64000000000ecbf
b=13132496513412427776.000000, 0x1.6c8000000001e000p+63
i=13132496513412427776, b64000000000f000
そりゃ規格外だけど32bit winの***の値おかしくないか?(VC9/VS2010共に)
ちなみに%aを使うと浮動小数点数を16進数表記できるというのを初めて知った. C99で入ってたのか. VCでも使えるとは素晴らしい.
ただVCのは文字幅指定子(.16とか)を指定しないときの挙動が違うっぽい.
// gcc
0x1.6c8000000001ep+63 // C99の仕様
// vc
0x1.6c8000p+63
近くの公園に花見に行ってみたけどえらい寒くてちょっと残念.
・
C++0x Adhoc会議受け付けのお知らせ. typoなどの些細なミスなら
BBSに書いてくださってもよいかも.
・n個の配列xとスカラー値の筆算による素朴な多倍長掛け算は, C++で
// out[n+1] <- x[n] * y
void in_mul(Unit *out, const Unit *x, size_t n, Unit y)
{
Unit H = 0;
for (size_t i = 0; i < n; i++) {
Unit t = H;
Unit L = _umul128(x[i], y, &H);
out[i] = t + L;
if (out[i] < t) {
H++;
}
}
out[n] = H;
}
とかできる. _umul128は64bit VC専用の組み込み関数で64bit x 64bit = 128bit
([H:L] = x[i] * y)を計算できる優れもの. carryは無いのでif()を使って繰り上げてる.
そこはadcを使いたいし, gccでも共用したいとすると
Xbyakを使えばコア部分は
こんな感じで書ける. Unitは32bitのときuint32_t, 64bitのときuint64_t.
void genMul()
{
using namespace Xbyak;
inLocalLabel();
// 変数設定
...
const int s = (int)sizeof(Unit);
xor(d, d); // H = 0
L(".lp");
mov(t, d);
mov(a, ptr [x]);
mul(y); // [d:a] = [x] * y
add(t, a);
adc(d, 0); // d++ if carry
mov(ptr [out], t);
add(x, s);
add(out, s);
sub(n, 1);
jnz(".lp");
mov(ptr [out], d);
// レジスタ復元
...
ret();
outLocalLabel();
}
個人的にはこれ以上は望めないほどシンプルかつasmに1対1であり, しかも32bit/64bitを共通化できて満足なんだけど"変数設定"と"レジスタ復元"のところがダサい.
具体的には変数設定の部分はこんな感じ.
#ifdef XBYAK32
const Reg32& a = eax;
const Reg32& d = edx;
const Reg32& t = ebp;
const Reg32& out = edi;
const Reg32& x = esi;
const Reg32& n = ecx;
const Reg32& y = ebx;
push(ebx);
push(esi);
push(edi);
push(ebp);
const int P = 4 * 4;
mov(out, ptr [esp + P + 4]);
mov(x, ptr [esp + P + 8]);
mov(n, ptr [esp + P + 12]);
mov(y, ptr [esp + P + 16]);
#else
const Reg64& a = rax;
const Reg64& d = rdx;
const Reg64& t = r11;
mov(r10, rdx);
#ifdef XBYAK64_WIN
const Reg64& out = rcx;
const Reg64& x = r10; // rdx
const Reg64& n = r8;
const Reg64& y = r9;
#else
const Reg64& out = rdi;
const Reg64& x = rsi;
const Reg64& n = r10; // rdx
const Reg64& y = rcx;
#endif
#endif
32bitと64bit Winと64bit gccの呼び出し規約が異なるのでこうしないといけないがレジスタの割り当てがなかなか覚えられなくて自分で
x64 アセンブリ言語プログラミングをみるはめになる.
あまり抽象化してしまうとasmと1対1が崩れるのでそれはやりたくないが, こういうコードを毎回書く(しかも微妙に異なる)のも難.
なんとかまとめようといくつか試してるんだけど32bitと64bitが違いすぎてしっくりこない.
higeponさんにちょっと相談してみたら「64bit gccしか考えない(下手な抽象化はしない)」と言われた. まあ, それもありなんやけど. うまい方法ないかな.
御意見は光成滋生<herumi@nifty.com>までお願いします