x64で配列の添字にintを使うと遅い

asm C++ Fortran

こういうツイートを見た。気になったので試してみたら本当にそうらしい。

EAXとかRAXとかいうのはレジスタの名前だ。特にRAXは64ビットのレジスタで、その下位32ビットにEAXとしてアクセスできる。

 .-- RAX ------------.
 |        .----EAX---.
 |        |    .--AX-.
 |        |    |AH|AL|
64       32   16  8 bit

EAXに値をmovすると、上の32bitはゼロになる。だが、ゼロになると困る場合がある。32bitの符号付き整数を64bitに拡張して使いたいとしよう。 EAXに負の符号付き整数を入れた場合、例えば-1は0xFFFFFFFFだが、これを64bitレジスタに入れて上位ビットが0にされると0x0000'0000'FFFF'FFFFになってしまう。 すると今度は負の数でなく、2^32-1という値になってしまい、意味が変わってしまう。 そのため、CPUには符号を考慮してキャストするための命令が用意されており、この機能は符号拡張と呼ばれている。

intは多くの環境で32ビットであり、64ビット環境だとポインタが64ビットなので、配列の添字としてintを使おうとすると符号拡張命令が入って遅くなるということらしい。

確認してみよう。

godbolt.org

これが、

#include <vector>
#include <cstdint>

int nth_int(const std::vector<int>& v, const std::int32_t n) noexcept
{
    return v[n];
}

int nth_uint(const std::vector<int>& v, const std::uint32_t n) noexcept
{
    return v[n];
}

int nth_size_t(const std::vector<int>& v, const std::size_t n) noexcept
{
    return v[n];
}

int nth_uint64(const std::vector<int>& v, const std::uint64_t n) noexcept
{
    return v[n];
}
int nth_int64(const std::vector<int>& v, const std::int64_t n) noexcept
{
    return v[n];
}

こうなった。

nth_int(std::vector<int, std::allocator<int> > const&, int):
        mov     rax, QWORD PTR [rdi]
        movsx   rsi, esi
        mov     eax, DWORD PTR [rax+rsi*4]
        ret
nth_uint(std::vector<int, std::allocator<int> > const&, unsigned int):
        mov     rax, QWORD PTR [rdi]
        mov     esi, esi
        mov     eax, DWORD PTR [rax+rsi*4]
        ret
nth_size_t(std::vector<int, std::allocator<int> > const&, unsigned long):
        mov     rax, QWORD PTR [rdi]
        mov     eax, DWORD PTR [rax+rsi*4]
        ret
nth_uint64(std::vector<int, std::allocator<int> > const&, unsigned long):
        mov     rax, QWORD PTR [rdi]
        mov     eax, DWORD PTR [rax+rsi*4]
        ret
nth_int64(std::vector<int, std::allocator<int> > const&, long):
        mov     rax, QWORD PTR [rdi]
        mov     eax, DWORD PTR [rax+rsi*4]
        ret

確かに、int32_tを渡した時はmovsx（move sign extension）が呼ばれているし、そもそもesiからrsiへmovしていて無駄に見える。64ビット整数版より命令が一つ多い。

少しよくわからないのがuint32_tを渡した時で、符号なしなのでゼロで拡張してくれて良いのでは？と思うのだが、mov esi esiという謎の命令が入っている。なにこれ？意味なくね？

size_tは期待通り、直接アドレス操作に使われている。64bitの整数も同じくだ。

私はもとよりsize_tを使っているのだが、添字をキャッシュしておくようなコードを書いている時に32bitで足りるんだからメモリアクセスの効率を考えると32bitにした方がいいのかなあと考えて試したことがあった。 だがその時あまり速くならず、理由がよくわからないままそのブランチは切り捨てたのだが、もしかしたらここで追加されている命令のせいかもしれない。 おそらくその時足されていたであろう、uint32_tで追加される同じものを同じ所に代入している命令の意味はわからないが……。

ところで、私の知っているいくつかのFortran製のプロダクトでは皆単にintegerを使っていて、64ビットにしていることはほぼ無い。なのでこれは結構インパクトがあるのではと思って適当なコードを書いてみたら、なんだかよくわからなくなっていた。 なぜかは全くわからんが、命令数が異様に多い。C++版が2,3命令のところで9命令もある。-Ofastにしても変わらなかった。読み解くのも面倒になったので貼るだけにしておこう。あとで気が向いたら読む。

godbolt.org

（追記）：読みました。

in-neuro.hatenablog.com