卜部昌平のあまりreblogしないtumblr

最速の memset64 を求めて

今回のお題は char 幅じゃなくて word 幅の memset 、つまりプロトタイプだと

void* memset64(void* destination, uint64_t image, int num_words);

をどれだけ高速に行うかという話。なぜ高速化するかというと、塗りつぶす領域がけっこうでかいから。

候補 1: REP STOS

void*
memset64(void* d, uint64_t i, int n)
{
    asm("cld; rep stosq;" :: "D"(d), "a"(i), "c"(n) : "memory");
    return d;
}

最近の CPU はクソ賢い。そのため、下手に手で loop unrolling するよりも、逆に CPU に「ここはループなんだぞおおお～」というのを明示的に指示してあげたほうが CPU 側が勝手かつ不気味に最適な挙動を示しやがる。そういう意味では現代はある種の CISC ルネサンスとよべる時期ではあるのだろう( 10 年後はわからんが)。

あとこのコードはレジスタ移動と retq までカウントしても関数全体でたったの 13byte (gcc -O3 実測値)というコンパクトさも魅力。 ICache ほとんど汚染されない。

候補 2: 教科書通りのナイーブなコード

void*
memset64(void* d, uint64_t i, int n)
{
    uint64_t* p = d;
    for(int j=0; j<n; j++) {
        p[j] = i;
    }
    return d;
}

現代では CPU の次に賢いのがコンパイラである。下手に手で loop unrolling するよりも、このようなあからさまなループを書いてあげると、コンパイラの側で適切に速そうなコードを生成してくれて、実際に速い。なおこの場合手元の gcc は、関数先頭で　punpcklqdq　で %xmm0 にパターンを生成しておいてから movaps で 128bit づつ塗りつぶしてゆくループを勝手に生成していた。なかなかの賢さ。

もちろんループがじゅうぶんにタイトなので、 CPU の側でも「これは memset なんじゃね?」的な行間の読み方をしてくれることが可能で、それも高速化に寄与している。と思われる。

候補 3: __builtin_memcpy

void*
memset64(void* d, uint64_t i, int n)
{
    uint64_t buf[] = { i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, };
    size_t j = n * sizeof i;
    while(j > sizeof buf) {
        __builtin_memcpy(d, buf, sizeof buf);
        d += sizeof buf / sizeof i;
        j -= sizeof buf;
    }
    __builtin_memcpy(d, buf, j);
    return d;
}

CPU とコンパイラの次に賢いのがライブラリなので下手に手で loop unrolling するよりもスタック上にパターンを作って memcpy するほうが速い、のだけれど、実は gcc にはビルトインの memcpy 実装があって、そいつを使ったほうが速くなる。なんでかというとこの場合では変数 buf をどのようにスタックの上に置くかは gcc が勝手に決めていいので、 buf の前後にパディングとか入れ放題なため、最適な位置に置いた上でアライメントが揃ってる前提の memcpy を生成できるからだ。 libc だとそういう前提は置けない。

なお gcc が自動で生成する memcpy のコードはたとえば -march=athlon64 と -march=core2 では入る nop の数が違う(ジャンプ先アドレスのアラインも取ってる)とか buf のサイズを変えると生成されるコードの戦略も変わる (-mstringop-strategy=) とか無駄に華麗な仕様になってるので、アセンブラが読める人は読むとニヤニヤできる。必見である。

候補 4: glibc の memcpy

#include <string.h>
void* memset64(void* d, uint64_t i, int n) __attribute__((__optimize__("no-builtin")));

void*
memset64(void* d, uint64_t i, int n)
{
    uint64_t buf[] = { i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, i, };
    size_t j = n * sizeof i;
    while(j > sizeof buf) {
        memcpy(d, buf, sizeof buf);
        d += sizeof buf / sizeof i;
        j -= sizeof buf;
    }
    memcpy(d, buf, j);
    return d;
}

おまえら __attribute__((__optimize__)) 知ってっか? 関数単位で最適化つけたり取ったりできるんだぜ最近は。

まあいいやそんで、普通にコンパイルしてしまうと memcpy は gcc のビルトインになってしまうので、上記のように　-fno-builtin 相当の指定をしてあげて、ちゃんと callq memcpy@plt が生成されていることを確認すべき。で、その memcpy がどこからやってくるかに関してはよくわからないというか、 nm /lib64/libc.so.6 したら no symbols とか言われるし、んなわきゃねーと思うのだが、まあよくわからん。

で、しょうがないので適当な main こさえて a.out を gdb でアタッチして disass memcpy を眺めたところによると、あー、 duff’s device? のように見えるな。違うかもだけど。先頭の方でぴょこぴょこジャンプ系のインストラクションが繰り返されたあと、データサイズによっては prefetcht0 等を挟みつつ、基本は mov でべたーっと展開されている、ようなコードに見える。これはこれで華麗なテク満載のコードだな。ハンドアセンブル職人さんの力作だろう。

候補 4: 手で loop unrolling したコード

void*
memset64(void* d, uint64_t i, int n)
{
    uint64_t* p = d;
    switch(n % 16) do {
    case  0: p[n--] = i;
    case 15: p[n--] = i;
    case 14: p[n--] = i;
    case 13: p[n--] = i;
    case 12: p[n--] = i;
    case 11: p[n--] = i;
    case 10: p[n--] = i;
    case  9: p[n--] = i;
    case  8: p[n--] = i;
    case  7: p[n--] = i;
    case  6: p[n--] = i;
    case  5: p[n--] = i;
    case  4: p[n--] = i;
    case  3: p[n--] = i;
    case  2: p[n--] = i;
    case  1: p[n--] = i;
    } while(n);
    return d;
}

まあこういうのを専門用語で愚策を弄するというのですね。このコードの問題点は

• そもそも switch は枝の先頭に到達する可能性が case で突入してきた場合と上から fall through してきた場合の 2 通りあって、その両方で最適に動くようにコードを生成するとえてしてあまり速くない。
• amd64 には 16 個も GPR がないので、 fall through に耐えるように n をレジスタに保存しようと思ってもレジスタが足りなくてトリッキーなことに
• かといってスタックに積んだら負けですよねー

などがあるのではと思われる。逆に利点は

• たとえ gcc -O3 でも本当に書いたとおりのアセンブル出力になるので、何が起こってるかわかりやすい。

とかくらい?

実験してみよう

さてここで、適当に 1GiB くらい malloc してきてメモリ塗りつぶす速さを比較してみましょう…なんだけど、ここで Linux ではちょっと罠があって、つまりやつらはメモリを over commit しやがる。そのため、 1GiB とか malloc したとしてもその瞬間には実際には物理ページはまだ割り当てられてなくて、塗りつぶしが本当に始まりだしてから徐々に確保されてゆく。つまりこのての関数のベンチマーク取ると概ねの場合で pager と swapper ががんばった時間が処理の大半を占めてしまって、あんまり意味のある結果になんねえわけ。もちろんそれを回避するためにちゃんと mlock(2) しとけという話。もっというと最初そのせいで全然おかしいデータが取れて悩んだ俺の時間を返せという話。

まあそんで、その罠は回避したので以下にグラフを貼っておく。縦軸は時間、横軸はmlockした領域のバイト数。もちろん malloc と mlock の時間は含まない。実験環境はちょうど余っていたという理由で Core2Duo(Merom) なノート PC であるため、もっとちゃんとした環境で計測すべきではある。

視えるかね。親切心から注意しとくけどお前らが普段見慣れないはずの両対数グラフだからねこれはね。でまあ、こうやってみると特に書きこむ領域が大きくなってきた時に memcpy 使ってるやつは安定した速さが出ているのが分かる。 MiB 級のアクセスになったところで他のやつががくっと遅くなってるのは多分 L2 からあふれたからだと思うんだけど、そこで memcpy があんまり影響受けてないのは prefetch してるからか? よくわからん。対数グラフで見づらいけど、1GiB の場合で memcpy とそれ以外は 4 倍ほども速さに差がある。

逆に KiB 級のアクセスの時は for loop が最速になっていて、やはりグラフからは見づらいけど rep stosq のだいたい倍くらいの速さ。つまりここから推察するに rep stosq と for ループは core2 内部ではほとんど同じ μOP に変換されていて、この速さの差は純粋に for は movaps だから 128bit 単位で書いてるという違いなのだろうと思われる。 SSE なんて意味ねーよと思ってたがこういうふうにちゃんと使われてるところを見るとやっぱ無駄ではなかったのだなあ。

一番下の方の比較にはあんまり意味が無い気もするが、そのへんの領域で unrolling が一番速いのはようするに一回もループ回ってないからという話に過ぎないだろう。逆に memcpy はそのへんの領域はスタックの上にパターンを作るコストが無視できなくなってくるのだと思われる。

まとめ

• キャッシュに載りきらない領域での memcpy の速さは本物
• キャッシュに載るサイズなら変な考えは起こさずに for で回しましょう
• こんなにきれいな実験結果が出るとは思わなかった