或るプログラマの一生

Golden Cove（Alder Lake の P コア）で、同じ scale のロードを連続で 3 回？繰り返すと、3 回目がものすごく遅くなっているように見える、という観測をしました。Gracemont（Alder Lake の E コア）ではそうはなっていないようです。

UtVideo のハフマンデコードのアセンブラルーチンには以下のような部分が存在します。

    movzx   eax, byte ptr [rbx + %c[offsetof_cslen] + r11*2]
    add     cl, byte ptr [rbx + %c[offsetof_cslen] + r11*2 + 1]
.if %c[sizeof_combined_t] == 4
    mov     r11d, dword ptr [rbx + %c[offsetof_sym] + r11*4]
.elseif %c[sizeof_combined_t] == 8
    mov     r11, qword ptr [rbx + %c[offsetof_sym] + r11*8]
.else
.err
.endif

で、圧縮比が低いクリップのために、combined_t を uint16_t にしたらどうなるか、というのを試すために、以下のようにしました。

    movzx   eax, byte ptr [rbx + %c[offsetof_cslen] + r11*2]
    add     cl, byte ptr [rbx + %c[offsetof_cslen] + r11*2 + 1]
.if %c[sizeof_combined_t] == 2
    movzx   r11d, word ptr [rbx + %c[offsetof_sym] + r11*2]      ; <- これ（uint16_t 用）を増やした
.elseif %c[sizeof_combined_t] == 4
    mov     r11d, dword ptr [rbx + %c[offsetof_sym] + r11*4]
.elseif %c[sizeof_combined_t] == 8
    mov     r11, qword ptr [rbx + %c[offsetof_sym] + r11*8]
.else
.err
.endif

圧縮比が非常に低い場合、uint16_t が一番早いはずですが、予想に反して猛烈に遅くなってしまいました。

で、シンボル部分のロード方法をいろいろと変えてみたところ、以下のようになりました。

    movzx   r11d, word ptr [rbx + %c[offsetof_sym] + r11*2]      ; 遅い
    mov     r11w, word ptr [rbx + %c[offsetof_sym] + r11*2]      ; 遅い
    mov     r11d, dword ptr [rbx + %c[offsetof_sym] + r11*2]     ; 遅い
    movzx   r11d, word ptr [rbx + %c[offsetof_sym] + r11*4]      ; 遅くない（デコード結果は正しくないが速度は変わらないはず）

なんで！？と思いつつ、そこは元に戻しつつ HUFFMAN_DECODE_TABLE の中の cslen のサイズが4バイトになるように変更してみました。

    struct
    {
        uint8_t symlen;
        uint8_t codelen;
        uint16_t reserved;      // <- 追加
    } cslen[1 << LOOKUP_BITS];

    movzx   eax, byte ptr [rbx + %c[offsetof_cslen] + r11*4]
    add     cl, byte ptr [rbx + %c[offsetof_cslen] + r11*4 + 1]

そしたら uint16_t は遅くならず、代わりに uint32_t の方が猛烈に遅くなりました。同様に8バイトになるように変更したら、uint64_t のが遅くなりました。

じゃあってんで symlen や codelen がバイト配列になる（scale が 1 になる）ように変更したところ、uint16_t uint32_t uint64_t のいずれも遅くなりませんでした。

    uint8_t symlen[1 << LOOKUP_BITS];
    uint8_t codelen[1 << LOOKUP_BITS];

というわけで「同じ scale で3回連続してロードすると猛烈に遅い」という風に見えるわけですが、最適化マニュアルを見てもそんなことは書いてないわけで、全く謎です。

なお、遅くならないケースであっても、uint16_t を使うのは有意点がなかったので、ボツになりました。