「AMDで使うと遅いんだけど」 x86/x64最適化勉強会 #4 LT 梅澤威志 (UMEZAWA Takeshi) @umezawa_takeshi

Q: dis ってんの？ A: disasm なら少々…

※ http://pc11.2ch.net/test/read.cgi/avi/1205486331/178 自己紹介 映像可逆圧縮コーデック Ut Video Codec Suite の作者 ※ http://umezawa.dyndns.info/wordpress/?cat=28 ある２ちゃんねらー曰く、 UtVideo唯一の欠点 作者がニコ厨 ※ http://pc11.2ch.net/test/read.cgi/avi/1205486331/178 まったくツンデレなんだから…

前置き 今回話すことは、何人かの人は過去の x86/x64最適化勉強会で雑談などで既に聞いているはずです。 blog を検索しても出てきます。 知ってる人は寝てていいです。

あるユーザの報告 「AMD で ULRG や ULRA を使うとエンコードがすごい遅いんだけど」 ULRG は内部保持形式が RGB 8bpc のもの。 ULRA は同じく RGBA 8bpc のもの。 ULY2 (YUV422 8bpc) や ULY0 (YUV420 8bpc) は遅くないらしい。 デコードはエンコードほどではないが、やっぱり遅いことは遅いらしい。

実測 確かに遅い。 ULRG は 24bpp であり、16bpp である ULY2 と比較して同じ画像サイズの時 1.5 倍ぐらい遅いことが期待されるが、エンコードの場合は期待されるより3倍ぐらい遅い。 明らかに何かおかしい

エンコーダの実装 以下の順序で処理する。 Packed → Planar 変換 フレーム内予測 ハフマン符号化 フレーム内予測とハフマン符号化は種類によらず全く同じ処理なので、Planar 変換に問題がありそう。 本来は全体の 1 割ぐらいの時間なんだけど…

Planar 変換 r = VirtualAlloc(NULL, width * height, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE); g = (ditto) b = (ditto) for (p = srcbegin; p < srcend; p += 3) { *(g++) = p[1]; *(b++) = p[0] - p[1] + 0x80; *(r++) = p[2] - p[1] + 0x80; }

ちょっと変えてみる…速度変わらず r = VirtualAlloc(NULL, width * height, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE); g = (ditto) b = (ditto) for (p = srcbegin; p < srcend; p += 3) { *(g++) = p[1]; *(b++) = p[0] - p[1]; // + 0x80; *(r++) = p[2] - p[1]; // + 0x80; }

さらに変えてみる…やっぱり遅い r = VirtualAlloc(NULL, width * height, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE); g = (ditto) b = (ditto) for (p = srcbegin; p < srcend; p += 3) { *(g++) = p[1]; *(b++) = p[0]; // - p[1] + 0x80; *(r++) = p[2]; // - p[1] + 0x80; }

遅くなくなった！？ r = VirtualAlloc(NULL, width * height, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE); g = (ditto) b = (ditto) for (p = srcbegin; p < srcend; p += 3) { *(g++) = p[1]; *(b++) = p[0]; r++; }

対照群：遅いまま r = VirtualAlloc(NULL, width * height, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE); g = (ditto) b = (ditto) for (p = srcbegin; p < srcend; p += 3) { *(g++) = p[1]; *(b++) = p[0]; *(r++) = 0; }

ULY2 の場合（遅くない） y = VirtualAlloc(NULL, width * height, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE); u = VirtualAlloc(NULL, width * height / 2, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE); v = (ditto) for (p = srcbegin; p < srcend; p += 4) { *(y++) = p[0]; *(u++) = p[1]; *(y++) = p[2]; *(v++) = p[3]; }

Q: なぜこうなるのでしょう？

A: store で毎回 L1 キャッシュミス するから

VirtualAlloc() 呼び出しプロセスのアドレス空間を予約あるいはコミットする。 POSIX の mmap() に似ている。 予約あるいはコミットするアドレスは「割り当て粒度 (allocation granularity)」に丸められる。 ページサイズ (=4KiB) ではない。 少なくとも Windows XP～7 においては、Win32 での割り当て粒度は 64KiB である。

AMD の L1 キャッシュ 長らく 命令 64KiB + データ 64KiB の構成 長らく 2-way セットアソシアティブ

両方合わせると… VirtualAlloc() で割り当てられたバッファは 64KiB 境界に整列しているので、各バッファの先頭アドレスは全て同じエントリアドレスを持つ。 ULRG では g, b, r のポインタが同じ速度で進み「常に」同じエントリアドレスになるため、1 バイトアクセスするたびにキャッシュミスして猛烈に遅くなる。

解決方法 ポインタが同じ速度で進むのだから、最初からずらしておけば今度は絶対に同じエントリアドレスにはならない。 p は 3 倍速で進むのでエントリアドレスが重なることがあるが、その時でも同じエントリアドレスを使っているのは 2 つだけなのでセーフ。

これで解決 r = VirtualAlloc(NULL, width * height, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE); g = VirtualAlloc(NULL, width * height + 256, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE) + 256; b = VirtualAlloc(NULL, width * height + 512, MEM_COMMIT|MEM_RESERVE, PAGE_READWRITE) + 512; … ※ 256 でいいかどうかは議論（というか計測）の余地がある。

当時（あまり）考えなかったこと L1 キャッシュを共有する複数の物理スレッド Intel HT とかのことだが、Intel 系だと 8-way なので、2 スレッド走っても 1 スレッドあたり 4-way で問題なし。 AMD Bulldozer の場合、L1 は Bulldozer モジュールごとではなくコアごとに持ってるらしいから、半分にはならない？

まとめ？ キャッシュの連想度にも（たまには）気を付けましょう。 でも 2-way はひどいと思います。 Intel は 8-way なのに。

Q: 結局 x86 関係あんの？ A: さあ…？