或るプログラマの一生

前の記事で ULxx の median decode が遅くなると書きました。実際どうなってるのかという話です。

gradient/left の decode は遅くなっていないので、怪しいのは tuned_RestoreCylindricalWrongMedian8 ということになります。最後の for ループの部分は以下のようになっています。

    for (; p < pSrcEnd; p++, q++)
    {
        __m128i top = _mm_cvtsi32_si128(*(const uint32_t *)(q - cbStride));
        __m128i grad = _mm_add_epi8(left, _mm_sub_epi8(top, topleft));
        __m128i pred = _mm_max_epu8(_mm_min_epu8(_mm_max_epu8(left, top), grad), _mm_min_epu8(left, top));
        __m128i value = _mm_add_epi8(pred, _mm_cvtsi32_si128(*(const uint32_t *)p));
        *q = _mm_cvtsi128_si32(value);
        left = value;
        topleft = top;
    }

ただし、pSrcEnd と cbStride は関数の引数です。

これが VS2015 だと以下のようになります。

000007FEB485D680 4D 85 C0             test        r8,r8
000007FEB485D683 74 48                je          tuned_RestoreCylindricalWrongMedian8<6>+17Dh (07FEB485D6CDh)
000007FEB485D685 49 F7 DB             neg         r11
000007FEB485D688 48 2B D1             sub         rdx,rcx
000007FEB485D68B 0F 1F 44 00 00       nop         dword ptr [rax+rax]

000007FEB485D690 C4 C1 79 6E 2C 0B    vmovd       xmm5,dword ptr [r11+rcx]
000007FEB485D696 C5 D9 DE D5          vpmaxub     xmm2,xmm4,xmm5
000007FEB485D69A C5 D1 F8 C0          vpsubb      xmm0,xmm5,xmm0
000007FEB485D69E C5 F9 FC CC          vpaddb      xmm1,xmm0,xmm4
000007FEB485D6A2 C5 F9 6E 04 0A       vmovd       xmm0,dword ptr [rdx+rcx]
000007FEB485D6A7 C5 E9 DA D9          vpminub     xmm3,xmm2,xmm1
000007FEB485D6AB C5 D9 DA D5          vpminub     xmm2,xmm4,xmm5
000007FEB485D6AF C5 E1 DE E2          vpmaxub     xmm4,xmm3,xmm2
000007FEB485D6B3 C5 D9 FC E0          vpaddb      xmm4,xmm4,xmm0
000007FEB485D6B7 C5 F9 7E E0          vmovd       eax,xmm4
000007FEB485D6BB 49 FF C1             inc         r9
000007FEB485D6BE 88 01                mov         byte ptr [rcx],al
000007FEB485D6C0 48 8D 49 01          lea         rcx,[rcx+1]
000007FEB485D6C4 C5 FA 6F C5          vmovdqu     xmm0,xmm5
000007FEB485D6C8 4D 3B C8             cmp         r9,r8
000007FEB485D6CB 72 C3                jb          tuned_RestoreCylindricalWrongMedian8<6>+140h (07FEB485D690h)

x86 ではメモリアクセスのアドレスの指定でレジスタを2つ使う場合に「レジスタ+レジスタ」しか使えない（「レジスタ-レジスタ」は使えない）ので、先に -cbStride を計算しておいてから、 q + (-cbStride) の形に置き換えているわけです。

で、VS2017 ではどうなるかというと、

000007FEB4795E70 4D 85 C0             test        r8,r8
000007FEB4795E73 74 4B                je          tuned_RestoreCylindricalWrongMedian8<6>+180h (07FEB4795EC0h)
000007FEB4795E75 48 2B D1             sub         rdx,rcx
000007FEB4795E78 0F 1F 84 00 00 00 00 00 nop         dword ptr [rax+rax]

000007FEB4795E80 48 8B C1             mov         rax,rcx
000007FEB4795E83 49 FF C1             inc         r9
000007FEB4795E86 49 2B C3             sub         rax,r11
000007FEB4795E89 C5 F9 6E 28          vmovd       xmm5,dword ptr [rax]
000007FEB4795E8D C5 D9 DE D5          vpmaxub     xmm2,xmm4,xmm5
000007FEB4795E91 C5 D1 F8 C0          vpsubb      xmm0,xmm5,xmm0
000007FEB4795E95 C5 F9 FC CC          vpaddb      xmm1,xmm0,xmm4
000007FEB4795E99 C5 F9 6E 04 0A       vmovd       xmm0,dword ptr [rdx+rcx]
000007FEB4795E9E C5 E9 DA D9          vpminub     xmm3,xmm2,xmm1
000007FEB4795EA2 C5 D9 DA D5          vpminub     xmm2,xmm4,xmm5
000007FEB4795EA6 C5 E1 DE E2          vpmaxub     xmm4,xmm3,xmm2
000007FEB4795EAA C5 D9 FC E0          vpaddb      xmm4,xmm4,xmm0
000007FEB4795EAE C5 F9 7E E0          vmovd       eax,xmm4
000007FEB4795EB2 88 01                mov         byte ptr [rcx],al
000007FEB4795EB4 48 FF C1             inc         rcx
000007FEB4795EB7 C5 FA 6F C5          vmovdqu     xmm0,xmm5
000007FEB4795EBB 4D 3B C8             cmp         r9,r8
000007FEB4795EBE 72 C0                jb          tuned_RestoreCylindricalWrongMedian8<6>+140h (07FEB4795E80h)

なんでやねん。ループ外に出してよ。

じゃあソースコードのレベルで明示的に -cbStride を計算したらいいかというとそうはいかず、「最適化」をして同じバイナリを吐いてきます。cbStride を関数に渡すのではなく最初から -cbStride を渡すことにしてアドレスの計算が加算になるようにすると、当然ながら以下のようなバイナリになります。

000007FEB6ED5E70 4D 85 C0             test        r8,r8
000007FEB6ED5E73 74 47                je          tuned_RestoreCylindricalWrongMedian8<6>+16Ch (07FEB6ED5EBCh)
000007FEB6ED5E75 48 2B D1             sub         rdx,rcx
000007FEB6ED5E78 0F 1F 84 00 00 00 00 00 nop         dword ptr [rax+rax]

000007FEB6ED5E80 C5 F9 6E 2C 19       vmovd       xmm5,dword ptr [rcx+rbx]
000007FEB6ED5E85 C5 D9 DE D5          vpmaxub     xmm2,xmm4,xmm5
000007FEB6ED5E89 C5 D1 F8 C0          vpsubb      xmm0,xmm5,xmm0
000007FEB6ED5E8D C5 F9 FC CC          vpaddb      xmm1,xmm0,xmm4
000007FEB6ED5E91 C5 F9 6E 04 0A       vmovd       xmm0,dword ptr [rdx+rcx]
000007FEB6ED5E96 C5 E9 DA D9          vpminub     xmm3,xmm2,xmm1
000007FEB6ED5E9A C5 D9 DA D5          vpminub     xmm2,xmm4,xmm5
000007FEB6ED5E9E C5 E1 DE E2          vpmaxub     xmm4,xmm3,xmm2
000007FEB6ED5EA2 C5 D9 FC E0          vpaddb      xmm4,xmm4,xmm0
000007FEB6ED5EA6 C5 F9 7E E0          vmovd       eax,xmm4
000007FEB6ED5EAA 49 FF C1             inc         r9
000007FEB6ED5EAD 88 01                mov         byte ptr [rcx],al
000007FEB6ED5EAF 48 8D 49 01          lea         rcx,[rcx+1]
000007FEB6ED5EB3 C5 FA 6F C5          vmovdqu     xmm0,xmm5
000007FEB6ED5EB7 4D 3B C8             cmp         r9,r8
000007FEB6ED5EBA 72 C4                jb          tuned_RestoreCylindricalWrongMedian8<6>+130h (07FEB6ED5E80h)

なお、処理対象のラインの前のラインにもアクセスするというのは median decode に限らないのですが、median predict や gradient/left の場合とは違ってこの部分はベクトル化できず、16倍の影響が出て計測誤差に埋もれず観測されたということだと思われます。

しかしこれ、よく見ると VS2015 の場合でもまだ最適解じゃないですね。（r9 使わないで rcx で終了判定すべき）