ぺんぎんさんのおうち

日記です。たまに日記じゃないこともあります。

GMP mpn_zeroの実装

mp_limb_t[CONST_SIZE]をゼロ埋め(初期化)するとき、mpn_zeroを使う方法とmemsetを使う方法があった。また、どちらの方法においても、初期化するサイズを定数とするか変数とするかで場合分けができる。

速度比較を行った結果、サイズを定数としてmemsetを使う方法が最も速かった(サイズは4とした)。 mpn_zeroは、サイズが定数でも変数でも実行時間にあまり差は見られなかった。 memsetでセットするサイズがコンパイル時に決まっている(定数である)とき、コンパイラレジスタを上手く駆使してmemset@pltを呼び出さないコードを生成する。関数callのコストが無い分、実行にかかる時間が短縮される。

GMPを使ったプログラムを書く際、配列のサイズが固定長ならば、ゼロ初期化にはmpn_zeroではなく、memsetを使ったほうがいい。 で話は終わりなのだが、せっかくなのでmpn_zeroの実装を見てみよう。 GMPのヴァージョンは6.2.1。

/gmp-6.2.1/mpn/generic/zero.c

void
mpn_zero (mp_ptr rp, mp_size_t n)
{
  mp_size_t i;

  rp += n;
  for (i = -n; i != 0; i++)
    rp[i] = 0;
}

配列に順にアクセスして0を代入する、シンプルな方法で実装されている。 ポイントなのは、第2引数nがコンパイル時で不定であること。これではベクトル化しずらいので、アセンブル結果はどうしても愚直なfor文になってしまう。

GMPをビルドするとzero.oというオブジェクトファイルが出力される。以下がzero.oをobjdumpでディスアセンブルした結果である。内容は上のソースコードどおり。ベクトル化も効いておらず、64ビットずつ0を埋めている(ビルド環境が32ビットであれば、32ビットずつ0埋めされる)。 つまり、ゼロ埋めするサイズが固定だろうと可変だろうと、for文で0埋めされるので実行速度はほとんど変わらない。

0000000000000000 <__gmpn_zero>:
   0:   48 89 f0                mov    rax,rsi
   3:   48 8d 14 f5 00 00 00    lea    rdx,[rsi*8+0x0]
   a:   00
   b:   48 f7 d8                neg    rax
   e:   48 85 f6                test   rsi,rsi
  11:   74 1a                   je     2d <__gmpn_zero+0x2d>
  13:   48 01 fa                add    rdx,rdi
  16:   66 2e 0f 1f 84 00 00    nop    WORD PTR cs:[rax+rax*1+0x0]
  1d:   00 00 00
  20:   48 c7 04 c2 00 00 00    mov    QWORD PTR [rdx+rax*8],0x0
  27:   00
  28:   48 ff c0                inc    rax
  2b:   75 f3                   jne    20 <__gmpn_zero+0x20>
  2d:   c3                      ret