Think Stitch
PRINCIPIA  最近の更新


x86 でリンクコール

プロセッサの中には、サブルーチンコールのための命令で、戻り先アドレスをスタックに積む代わりにリンクレジスタと呼ばれるレジスタに格納するものがありますよね。 この方式を仮にここではリンクコールと呼ぶことにします。 これに対して x86 のように戻り先アドレスをスタックに積む方式をプッシュコールと呼ぶことにします。

一般に、サブルーチン呼び出しはツリー状になりますよね。 したがって、別のサブルーチンを呼び出すサブルーチンでは、結局リンクレジスタの値をスタックに保存することになります。 しかし、呼び出しツリーの葉に対応するサブルーチン、つまりそこだけで処理が完結して他のサブルーチンを呼び出さないサブルーチンではリンクレジスタを保存する必要がありません。 ツリーの形はさまざまになるので、葉の数の比率がどれくらいということは一般にはいえませんが、葉のところでスタックへの書き込みがなくなる分だけ速くなることが期待できます。

x86 の 64 bit 命令セットでは RIP 相対アドレッシングが追加されました。 これを使うと戻り先アドレスを簡単に取得できます。 そこで、RIP を使ってリンクコールをシミュレートとして、call 命令と実行時間を比較してみました。 ディスプレースメントが 32 bit なので、ちょっと命令長が長くなりますけど、メモリへの書き込みのコストと比較してどうでしょうか。

リンクコール

リンクレジスタとして rcx を使うことにします。 引数渡しの部分を無視すると、通常のサブルーチン呼び出しは次のようになります。

    call subroutine
subroutine:
    ...
    ret

これを次のようにします。

    lea rcx,[L0]      ; rip relative
    jmp subroutine
L0:
subroutine:
    ...
    jmp rcx

call 命令は 1 バイト+ディスプレースメント 4 バイトで合計 5 バイトです。 これに対して RIP 相対の lea 命令は命令 3 バイト+ディスプレースメント 4 バイト、さらに jmp 命令が call 命令と同じく 5 バイトあるので、合計 12 バイトになっちゃいます。 ret 命令は1バイト、jmp rcx は2バイトです。したがって、命令の長さではリンクコールの方が圧倒的に不利です。

計測方法

計測は rdtsc 命令を使って行うことにします。rdtsc は CPU のクロックをカウントしている内部レジスタの値を読み出す命令です。 これだけだと命令のリオーダー機能で順序を入れ替えられてしまう可能性があり、正確な計時ができないので、cpuid 命令を使って順序を守るように強制します。 計測のためのテンプレートコードは次のようにしました。

test0:
    cpuid
    rdtsc
    mov r8d,eax
    mov r9d,edx
    ;; ここに計測コードを置く
    cpuid
    rdtsc
    sub eax,r8d
    sbb edx,r9d
    shl rdx,32
    or rdx,rax
    mov rax,rdx
    ret

プッシュコールとリンクコールそれぞれについて、16個のサブルーチンを用意し、順番に呼び出すようにします。 各サブルーチンはリターンするだけで、それ以外は何もしません。

align 16
test1:
    cpuid
    rdtsc
    mov r8d,eax
    mov r9d,edx
    ;; begin
    call test10_sub 
    call test11_sub 
    call test12_sub 
    call test13_sub 
    call test14_sub 
    call test15_sub 
    call test16_sub 
    call test17_sub 
    call test18_sub 
    call test19_sub 
    call test1A_sub 
    call test1B_sub 
    call test1C_sub 
    call test1D_sub 
    call test1E_sub 
    call test1F_sub
    ;; end
    cpuid
    rdtsc
    sub eax,r8d
    sbb edx,r9d
    shl rdx,32
    or rdx,rax
    mov rax,rdx
    ret

プッシュコールの各サブルーチンは次のとおりです。

align   16
test1X_sub:
    ret

続いてリンクコールです。

align   16
test2:  
    cpuid
    rdtsc
    mov r8d,eax
    mov r9d,edx
    ;; begin
    lea rcx,[L0]
    jmp test20_sub
L0:
    lea rcx,[L1]
    jmp test21_sub
L1:
    lea rcx,[L2]
    jmp test22_sub
L2:
    lea rcx,[L3]
    jmp test23_sub
L3:
    (中略)
LE:
    lea rcx,[LF]
    jmp test2F_sub
LF:
    ;; end
    cpuid
    rdtsc
    sub eax,r8d
    sbb edx,r9d
    shl rdx,32
    or rdx,rax
    mov rax,rdx
    ret

リンクコールの各サブルーチンは次のとおりです。

align   16
test2X_sub:     
    jmp rcx

さらに加えて、比較のために16回異なるアドレスに書き込みを行うコードと読み出しを行うコードを用意しました。

test3:
    cpuid
    rdtsc
    mov r8d,eax
    mov r9d,edx
    ;; begin
    mov [rsp-8],rax
    mov [rsp-16],rax
    mov [rsp-24],rax
    mov [rsp-32],rax
    mov [rsp-40],rax
    mov [rsp-48],rax
    mov [rsp-56],rax
    mov [rsp-64],rax
    mov [rsp-72],rax
    mov [rsp-80],rax
    mov [rsp-88],rax
    mov [rsp-96],rax
    mov [rsp-104],rax
    mov [rsp-112],rax
    mov [rsp-120],rax
    mov [rsp-128],rax
    ;; end
    cpuid
    rdtsc
    sub eax,r8d
    sbb edx,r9d
    shl rdx,32
    or rdx,rax
    mov rax,rdx
    ret
test4:
    cpuid
    rdtsc
    mov r8d,eax
    mov r9d,edx
    ;; begin
    mov rax,[rsp-8]
    mov rax,[rsp-16]
    mov rax,[rsp-24]
    mov rax,[rsp-32]
    mov rax,[rsp-40]
    mov rax,[rsp-48]
    mov rax,[rsp-56]
    mov rax,[rsp-64]
    mov rax,[rsp-72]
    mov rax,[rsp-80]
    mov rax,[rsp-88]
    mov rax,[rsp-96]
    mov rax,[rsp-104]
    mov rax,[rsp-112]
    mov rax,[rsp-120]
    mov rax,[rsp-128]
    ;; end
    cpuid
    rdtsc
    sub eax,r8d
    sbb edx,r9d
    shl rdx,32
    or rdx,rax
    mov rax,rdx
    ret

各テストコードの呼び出し直前に Sleep(1) を呼び出しました。これでタイムスライスがリセットされるかどうかはわかりませんが、ある程度は実行環境がそろうでしょう。 今日日の CPU は内部のスケジューリングもメモリシステムも複雑なので、このようなコードで何がわかるのか疑問なところもありますけど、まあ1つの参考にはなるでしょう。

計測結果

計測結果は次のようになりました。 計測は 10,000 回行いました。左からテスト番号、平均、標準偏差です。 empty はテスト部分を空にした場合です。 計測環境は Core2Duo E6600 2.4GHz, Windows 7 64bit, メモリ 4G bytes です。

0 422.434 26.301  empty (reference)
1 511.622 66.824  push call
2 517.975 76.065  link call
3 450.864 35.552  write
4 426.162 28.062  read

10,000 回の測定後、仮平均を計算して、それから仮平均の2倍を超えるデータを取り除いています。取り除いたデータは 0.2% 以下でした。

結果はプッシュコール、つまり通常の call 命令の方がわずかに実行時間が短いということになりました。 ただばらつきがかなり大きいので、実際のコードではほとんど影響ないかもしれません。 個人的な予想は裏切られたのですが、call 命令には特別扱いがあるかもしれないなどと勝手な想像をしていました。 (サブルーチン先でスタック上にある戻り先アドレスを読み出すようにしてみましたが、ほとんど影響はありませんでした。)

もう1つ意外なことに、read の実行時間が write を上回ることが何度かありました。 やはり read の方がキャッシュの影響を受けやすいのでしょうか。分散は小さいのですけどね。

結論としては、素直に call 命令を使っておけ、ということのようです。レジスタは増えたとはいえ貴重ですしね。

2013/10/25
© 2013,2014,2015 PRINCIPIA Limited