憂鬱な午後のひととき

8月30日_

印象に残ってるバグ

因果律を否定するバグにあるような, 乱数の違いで発現したバグは一度遭遇したことがある. 一見無関係のはずのstatic変数(コンストラクタ内でrand()を呼んでいた)を追加すると別のところが狂うという, 似たパターンだった.

私の中で一番強烈に印象が残ってるのはあるdirectShowのコーデック開発中に遭遇したやつ. ライブラリ側を少し改良してはテストしてコミットを繰り返す. もちろんテストは通ってることを確認する. しばらくしてそれを呼び出すサンプルアプリで使うとOSごと(Windows 2000だった)リブートすることが発覚.

実はデコーダに耐性をもたせるのって結構大変で, わざととんでもなくやらしく破損したデータを作ってマルチメディアプレーヤに食わせると, OSをも巻き込んでハングしまうというのはちょいちょいあった(NTカーネルだったはずなのに!). もちろん自分のエンジンはそうならないように頑張る.

でも今回はそうじゃなくて単なるコンソールアプリで即リブート. エンジンはテスト通ってるのだからサンプルアプリでどこかしくったか, でもこちらは殆ど触ってないぞと思いつつ探す. するとソースコードの整形の前後でコミットしたものの差でリブートする/しないを分けることが判明.

整形したのはもともと別プロジェクトのやつを引っ張ってきてコーディングスタイルが違ったから. もちろんdiffをとっても改行やインデントの違いぐらいしかない. その時点で頭の中は???で埋まる.

二分法的にどこが原因か探すのだが, とにかく問答無用でリブートなので保存したファイルも壊れたりしてチェックが大変.

どうにかして, 端末に進行結果を出力するprintfの1行だけが違うというところまで追い詰める. しかしdiffを表示してもその違いがよく分からない. よくよく見ると, どうやら何かの手違いで文字列の中のスペースがタブになっていた. それがリブートするか動作するかの差になってる.

まさかコンソールに文字を出すだけで落ちるわけがないと決めつけていたが, そのあたりでWindows 2000のバグとちゃう? と思うようになる. 結局タブとバックスペースの組み合わせを何回か表示するだけのプログラムで落ちると確定.

流石に当時発売直前だったXpなら大丈夫だろうと思って社内のマシンで試してもらうとそちらでも落ちた. うひゃ.

そのあとは, 当時の私の掲示板に書いたり[567], 同僚にfj.osやcomp.os.ms-windowsに投稿してもらったりした[Windows 2000がハングアップするバグについてとか Bug which crash Windows 2000 and XP]. なつかしー.

とんちんかんな回答があったり, あまりの現象にくだらないジョークと思われたり. Cだけじゃなくてperlやバッチファイルでも落とせるというのでちょっとした話題になってたらしい.

今改めて検索するとThe CSRSS Backspace Bug in Windows NT 4/NT 2000/NT XPというページがあった. なるほど, Linuxのprocess 1に相当するものが死んでpanicになっていたのか.

8月29日_

『001にやさしいゆりかご』(松村栄子)

『雨にも負けず粗茶一服』は大学受験生のモラトリアムだった. こちらは周囲になじめない高校生の万里が大学を経て社会人になるまでを描く. あちらは明るかったがこちらは相当湿っぽい. その分ずっとリアル.

たとえばゲームづくりにはまって勉強もせずバイトに励む予備校生.
〈きちんと勉強した学生たちはプログラマになって安月給で深夜までこき使われる〉 〈馬鹿馬鹿しくて受験勉強などする気にならない〉

短大を出て先に結婚して子供ができた知人. 「(社会は)不公平. 男の子は何やったって, 社会の方でちゃんと拾ってくれる. (中略)結局どっかで見切りつけて家庭に引っ込むしかないんじゃないの?」

ラストで万里が, 結婚することになった知人に対して思う感想が恐ろしい. そこまで醒めてるのか.

ところで今の大学生はサイボーグ009ってどの程度知ってるのだろう.

8月26日_

SSEによる倍精度指数関数の高速な実装
(fast double precision exponential function with SSE)

気が早いけど次回のx86/x64最適化勉強会2用のネタのやつ. ラボユースの合宿の合間に作ってたのを(少しだけ)整理した. ソースコードはfmath.hpp. ベンチマークコードはfastexp.cppで, これはexp(x)の高速計算 ～実験編～で使われているものを若干手直しさせていただいた.

今回二つ関数を追加した.
一つはstd::exp(double)の代替となるfmath::expd(double);
もう一つは配列に対してexpdを適用するfmath::expd_v(double *px, int n);. こちらはSIMDを利用している.

平均0, 標準偏差1の正規分布から1000000個生成した乱数に対してベンチマークを行った. Remez…は上記ページの岡崎直観さんの配列版expの実装. ベンチマークの中のstd::expとfmath_expdは単にn回呼び出すので速度的に不利.

expのベンチマーク[64bit Linux + i7-2600 3.4GHz + gcc 4.4.5]
関数 clk std::expに対する最大誤差 2乗平均誤差
std::exp 69.118263 0.000000e+00 0.000000e+00
Remez 9th [0,log2] SSE 16.900997 1.909579e-14 9.909547e-15
Remez 11th [0,log2] SSE 19.805610 2.571683e-16 6.146323e-17
fmath::expd 12.103163 6.575812e-16 1.117645e-16
fmath::expd_v 8.256045 6.575812e-16 1.117645e-16

std::expに対してfmath::expdは5倍以上速い. 精度についてはexpdは9次の最良多項式近似よりよいが, 11次版には劣る. 速度はそれらの2～2.5倍ある. わりとよい感じ. コードは以下. 式の意味は最適化勉強会にて. 

static inline double expd(double x)
{
    const ExpdVar<>& c = local::C<>::expdVar;
    const uint64_t b = 3ULL << 51;
    union di {
        double d;
        uint64_t i;
    } di;
    di.d = x * c.a + b;
    uint64_t iax = c.tbl[di.i & mask(c.sbit)];
    double t = (di.d - b) * c.ra - x;
    uint64_t u = ((di.i + c.adj) >> c.sbit) << 52;
    double y = (c.C3[0] - t) * (t * t) * c.C2[0] - t + c.C1[0];
    di.i = u | iax;
    return y * di.d;
}
8月25日_

xor eax, eax vs. mov eax, 0

ときどきの雑記帖で呼ばれたので. 私はxor使うなあ. movを使うのはフラグを変更したくないときぐらい. 「xor eax, eaxが演算するので遅い」というのはどのCPUだろ. むしろ, Sandy Bridgeだとそういうxor eax, eaxなどのzero idiomは実行ユニットを消費しないとありますね(最適化マニュアルの2.1.3.1とか「Intelプロセッサ最適化マニュアルを読もう」のout-of-orderエンジンのリネーマ付近). Pentium4もそれようの特殊なサポートをする, Core Duoは実行ユニットを消費するとある. でもどれも殆ど分からないレベルだと思います. 実際, 

#include <stdio.h>
#include <xbyak/xbyak.h>
#include <xbyak/xbyak_util.h>

const int N = 1000000;

struct Code : public Xbyak::CodeGenerator {
    Code(bool useXor)
    {
        mov(ecx, N);
    L("@@");
        if (useXor) {
            xor(eax, eax);
        } else {
            mov(eax, 0);
        }
        sub(ecx, 1);
        jnz("@b");
        ret();
    }
};

void test(bool useXor)
{
    Code code(useXor);
    void (*f)() = (void (*)())code.getCode();
    Xbyak::util::Clock clk;
    for (int i = 0; i < 1000; i++) {
        clk.begin();
        f();
        clk.end();
    }
    printf("%.3f\n", clk.getClock() / double(N) / clk.getCount());
}

int main()
{
    test(true);
    test(false);
    test(true);
    test(false);
}

みたいな単純ループで試すとi7, Xeron, Core2Duoで有為な差は見られませんでした. むしろ, mov eax, 0なら5byte, mov rax, 0なら7byteも消費する方が痛いんじゃないかと.

試しにコードサイズと実行速度の関係に関する話で試したicache.cppで大量のxor eax, eaxとmov rax, 0を連続実行したときの速度を計ってみる. するとxor eax, eaxはコードサイズに関係なくコンスタントに速いけどmov rax, 0は数十KBを超えたあたりで速度低下が発生しました(i7, Xeon, Core2Duo). 命令長が長いのでデコードが追いついてないんでしょうね.

8月24日_

よみがえるトライグラフ

規格大好きなconstなんとかさんも知らなかったトライグラフ(まあこちらはC/C++ですが). 今までのgccではデフォルトoffで-trigraphをつけたときだけ有効だったのに-std=c++0xではデフォルトonになってたのですね. 逆に今まで問答無用でonだったVCでは, VC10からデフォルトoffになってます. というわけで2年以上前に書いたトライグラフと正規表現についての記事は今では結果が逆転しています. gccとVCのトライグラフにまとめておきました.

8月23日_
前回の最適化勉強会の後に書いたSSE4.2の文字列処理を使うときのアライメントについての補足記事ではまっている方がいらっしゃったので資料(SSE4.2の文字列処理命令の紹介)も一言更新しておいた.
8月22日_
x86/x64最適化勉強会2.
定員を超えてしまったので会場を秋葉原UDXに変更して30人にしました.
8月19日_
x86/x64最適化勉強会2の予告.
まだ定員に余裕があるので(20人を超えるなら会場変更予定)興味ある方ぜひ. 発表したい方もぜひぜひ.
8月18日_
ラボユースの中間成果報告会. 私は主にsinya8282さんの担当だったのだけど, こうしてまとめて各自の発表を見るとみんなてんでばらばらにとんがってて面白い. 未踏のPMよりははるかに深く開発者の開発に関わり, インターンよりはずっと自由にさせるという試みは希有なものじゃなかろうか.
8月17日_

合宿のお手伝いの合間に私はexp(x)の高速計算 ～実験編～より速いexpの実装を試みることにした. 以前, fast approximate float function fmathではfloatに対する高速なexpの実装をしたけど今回はそれの応用でdouble版に挑戦. 多分, うまくできると思う.

寝不足で恐ろしく頭が痛い. バファリンを飲んでも効かないなあ.

8月16日_

サイボウズ・ラボユースの合宿というのがあった. その中間成果報告会が18日にある.

その余興でRubyに意図的に仕込んだいくつかのバグを制限時間1時間内に見つけろというタイムトライアル競技(CTF)があった. 問題自体はセキュリティ&プログラミングキャンプで実施されたものらしい(cf. 「Rubyのバグを探せ」問題).

ラボユースの人に混じって(セキュリティキャンプにかかわってなかった)私や他のラボの人も一緒に参加する. それは負けられないじゃないか.

みなに暗号化されたzipファイルが渡され, よーいどんで進行役の西尾さんそのzipパスワードを明かす. ラボのshuyoさんはさんはRubyをビルドできないというハンディの中, 何故か解いていく. ラボユースのConstellationさんはちゃくちゃくと解いていく. 流石, かなりのいろんなソースを読んでるからか.

私はというと, 何故かマシンがRubyのビルド中にハングアップして電源ボタンを押しても電源オフにできなくなった. バッテリーを抜いて強制電源オフという荒技. 「うぉ」とか「ひゃあ」とかうるさい. 慣れてないまま40分近く経過したところでまだ1問も解けてないの私だけ. これはやばい.

50分近く経過してなんとか初級編の2問解けた. で, 慣れたのかそこから2分ごとに1問解くという追い上げで時間内に上級編までの5問, ロスタイムに出題文のセキュリティホールをついたチートでhard.zipも解いた.

一応, 盛り上げ役にはなったかも. 面白いけどやっぱ競技プログラムは向いてなさそうだ.

8月15日_
Xbyakでimm8の符号拡張でミスってたところを修正. まだそんなバグが残ってたんだなあ. ユーザからのフィードバックはありがたい.
8月12日_
x86/x64最適化勉強会第2回を10月あたりにしようかと計画中. 日程を決めたいので発表したいという方連絡ください. 前回参加できなかった人もぜひ.
8月11日_
朝から「今日はハンバーガーを食べたい!」という日のときに, 水道橋にあるおいしいらしい店に初めて行ったらお盆休みだったときのショックの大きさ.
8月9日_

SSE4.2文字列処理のアライメントに関する補足の続き

結局, 16bteアライメントされていないと通常のページ境界(ページサイズ4096byte)を跨いでしまう可能性がある. それを避けるには与えられたスタート地点を16byteアライメントするよう補正処理をしてからpcmpistriでループするようにする. そうすればお尻の部分で'\0'を超えて何バイトか読み進めることはあっても境界を超えることはない.

gccのstrchrを見るとやはりそのようなコードになっていた. 自分でpcmpistriを使うときはお尻がページ境界にきてないように文字列がおかれてることを保証するか, gccのみたいに安全に処理する必要があるようだ.

ところでそのgccのstrchrでは最初int cが'\0'かどうかを判別するのに 

 test sil, sil

としていた. そっか, 64bitだとrsiやrdiの下位8bitを使えるのだった. Xbyakでも対応させたのに忘れてた.

あとsinya8282さんの資料も公開された(資料集).

8月8日_

SSE4.2の文字列処理命令の紹介に関する補足
二つある. どちらも重要.

1. アライメントに関して
たとえば文字列を取得するintrinsic版のstrlenについて 

size_t strlenSSE42_C(const char* top)
{
    const __m128i im = _mm_set1_epi32(0xff01);
    const char *p = top;
    while (!_mm_cmpistrz(im, *(const __m128i*)p, 0x14)) {
        p += 16;
    }
    p += _mm_cmpistri(im, *(const __m128i*)p, 0x14);
    return p - top;
}

のように書いてたのはよくなかった. これはたまたま 

L("@@");
    add(a, 16);
    pcmpistri(xm0, ptr [a], 0x14);
    jnz("@b");

のようにコード生成されていたのでalignementされていない文字列に対しても動作していたけど, 

L("@@");
    add(a, 16);
    movdqa(xm1, ptr [a]);
    pcmpistri(xm0, xm1, 0x14);
    jnz("@b");

のようにalignment前提のコード生成されてしまうと動かない. 

size_t strlenSSE42_C(const char* top)
{
    const __m128i im = _mm_set1_epi32(0xff01);
    const char *p = top;
    while (!_mm_cmpistrz(im, _mm_loadu_si128((const __m128i*)p), 0x14)) {
        p += 16;
    }
    p += _mm_cmpistri(im, _mm_loadu_si128((const __m128i*)p), 0x14);
    return p - top;
}

とすべきであった. すいません. 他の関数も同様. 調べた限りでは速度の変化は殆ど無い.

2. ページ境界をまたがる文字列について
たとえば文字列の先頭アドレスがmod 4096で-3にあり, -1に'\0'があった場合, そのアドレスに対してpcmpistriを実行するとどうなるのか. 

 (readアクセス可能) | (readアクセス不可なページ)
     | -3 | -2 | -1 |  0 | +1 | +2 | ...
       'a'  'b' '\0'| '?'  '?'  '?'
       ↑
       ここからpcmpistri
  1. '\0'を検出した時点でそれ以降を読み込まずアクセス違反にならない.
  2. 16byte読み込むのでアクセス違反を起こす.

の二つが考えられて前者だったらいいなと思っていたが後者だった.

つまりSSE4.2の文字列処理命令を使う場合は文字列の最後が'\0'のあとも次の16byte境界まではアクセス可能なように配置しておく必要がある.
strchr_sse42.cppをWindows環境で-check [0|1]オプションをつけて実行すると -check 1のとき落ちることから分かる.

8月6日_
x86/x64最適化勉強会1
なんとか無事終了. ustがうまくいったりいかなかったり, 運営が手間取ったりと申し訳ない. 主催するというのはたいへんだなあ. 名前だけはwebなりでよく見かけていたけど会ったことなかった方々に会えたので満足. でもこれまた初めてお会いした@takehiro_tさんとは殆どしゃべれなかった. 残念.
個人的にはw_oさんのベンチマークの結果から理由を探していく部分が興味深かった.
反省点 : 発表の間は5分マージンを入れておく. タイマーあるとよさげ.
とりあえずいくつかの資料へのリンク(uploadされれば随時更新).
# ustへのリンクを追加しました.
  1. herumi : 条件分岐とcmovとmaxps[ust-1]
  2. m_asama : IA32/Intel64におけるキャッシュ利用最適化[ust-2]
  3. sinya8282 : 正規表現とJITと並列化とベンチマーク[ust-3]
  4. TAKESAKO : ビットを数える[ust-4]
  5. herumi : SSE4.2の文字列処理命令の紹介[ust-5]
  6. kzmogi : CODEC屋のx86/x64最適化[ust-6]
  7. w_o : k10 vs CoreMA[ust-7]
  8. nothingcosmos : 本物のX86Optimizerはiccを使う[ust-8]
  9. shudo : shuJITコンパイラネタ[ust-9]
8月1日_
x86/x64最適化勉強会1
一人, 二人ぐらいなら(せまくて申し訳ないのだけど)発表者枠で追加できるかも. 参加希望の方メールください.
昔
[Back]
御意見は光成滋生<herumi@nifty.com>までお願いします