ホーム > アセンブリ言語 > 掛け算を imul 命令を使わずに高速に計算する (x86/x64)

掛け算を imul 命令を使わずに高速に計算する (x86/x64)

x86/x64 には掛け算命令（mul, imul）がありますが、あえてほかの命令を使って掛け算と同等の処理を行うことがあります。
たとえば、x64 の rax レジスタの値を 5 倍するのに、imul rax, rax, 5 ではなく、lea rax, QWORD PTR [rax+rax*4] とすることがあります。このほうが高速だからです。
ほかの倍数についても見てみましょう。

動作確認環境

  • Windows 11 Home 24H2
  • Visual Studio Community 2022 (Visual C++)

掛け算命令を使わずに 5 倍を計算

上記の 5 倍の例ですが、次のように引数を 5 倍する C 言語の関数を書き、

__int64 mul5(__int64 i)
{
    return i * 5;
}

Visual C++ x64 版でコンパイルし（「/c」はコンパイルのみでリンクはしない、「/O2」は速度最適化、「/FAs」はアセンブリリストを出力、の意味）、

C:\tmp> cl /c /O2 /FAs mul.c
Microsoft(R) C/C++ Optimizing Compiler Version 19.43.34810 for x64
......

生成されたアセンブリリストを見ると、

C:\tmp> type mul.asm
......
lea     rax, QWORD PTR [rcx+rcx*4]
......

掛け算の imul 命令ではなく、実効アドレスロードの lea rax, QWORD PTR [rcx+rcx*4] 命令で 5 倍の計算をしていることがわかります。rcx レジスタの値に rcx レジスタの値を 4 倍した値を加算した結果を rax レジスタにセットしています。要するに rax = rcx + rcx * 4 です。

被乗数が rcx レジスタで、積が rax レジスタなのは、x64 呼び出し規約に従っているためです（参考文献 [1]）。被乗数も rax レジスタにしたい場合は、引数ではなく関数の戻り値から取ってくるとよいでしょう。
たとえば次のソースをコンパイルしてアセンブリリストを見ると、

__int64 fn();

__int64 mul5()
{
    return fn() * 5;
}

被乗数が rax レジスタになります。

C:\tmp> type mul.asm
......
lea     rax, QWORD PTR [rax+rax*4]
......

2 ～ 16 倍の掛け算の結果

この方法で、2 倍 ～ 16 倍の掛け算についてコンパイラの出力を調べました。結果を以下に示します。

乗数被乗数 が rcx の場合被乗数 が rax の場合コメント
2 lea rax, QWORD PTR [rcx+rcx]add rax, rax
3lea rax, QWORD PTR [rcx+rcx*2]lea rax, QWORD PTR [rax+rax*2]
4lea rax, QWORD PTR [rcx*4]shl rax, 2
5lea rax, QWORD PTR [rcx+rcx*4]lea rax, QWORD PTR [rax+rax*4]
6lea rax, QWORD PTR [rcx+rcx*2]
add rax, rax		lea rax, QWORD PTR [rax+rax*2]
add rax, rax
7imul rax, rcx, 7imul rax, rax, 7工夫なし
8lea rax, QWORD PTR [rcx*8]shl rax, 3
9lea rax, QWORD PTR [rcx+rcx*8]lea rax, QWORD PTR [rax+rax*8]
10lea rax, QWORD PTR [rcx+rcx*4]
add rax, rax		lea rax, QWORD PTR [rax+rax*4]
add rax, rax
11imul rax, rcx, 11imul rax, rax, 11工夫なし
12lea rax, QWORD PTR [rcx+rcx*2]
shl rax, 2		lea rax, QWORD PTR [rax+rax*2]
shl rax, 2
13imul rax, rcx, 13imul rax, rax, 13工夫なし
14imul rax, rcx, 14imul rax, rax, 14工夫なし
15imul rax, rcx, 15imul rax, rax, 15工夫なし
16shl rcx, 4
mov rax, rcx		shl rax, 4

一部を除き、掛け算の imul ではなく実効アドレスロードの lea や左シフトの shl や足し算の add を使って倍数を計算しています。3 倍、5 倍、9 倍が lea 命令ひとつで処理できるのがおもしろいですね。

本当に imul より lea のほうが速いのか

そもそもですが、本当に imul より lea のほうが速いのかという疑問があります。実験してみましょう。

最近の CPU は複雑で、条件によって動作が変わるため測定が難しいですが、今回は以下の x64 アセンブリ言語プログラムで試してみます。

EXTERN GetTickCount: PROC
EXTERN printf: PROC

.data
PRINTFORMAT  BYTE  "time: %ld ms ", 0Dh, 0Ah, 0

.code
main PROC
    ;------ スタックの確保と整列
    sub     rsp, 28h

    ;------ 開始時刻の取得
    call    GetTickCount
    mov     r10d, eax

    ;------ 10 億回の繰り返し
    mov     rcx, 1000000000

L_Repeat:
    ; lea 命令で 5 倍
    ; lea      rax, QWORD PTR [rax+rax*4]
    ; lea      rax, QWORD PTR [rax+rax*4]
    ; lea      rax, QWORD PTR [rax+rax*4]
    ; lea      rax, QWORD PTR [rax+rax*4]
    ; lea      rax, QWORD PTR [rax+rax*4]
    ; lea      rax, QWORD PTR [rax+rax*4]
    ; lea      rax, QWORD PTR [rax+rax*4]
    ; lea      rax, QWORD PTR [rax+rax*4]
    ; lea      rax, QWORD PTR [rax+rax*4]
    ; lea      rax, QWORD PTR [rax+rax*4]

    ; imul 命令で 5 倍
    ; imul     rax, rax, 5
    ; imul     rax, rax, 5
    ; imul     rax, rax, 5
    ; imul     rax, rax, 5
    ; imul     rax, rax, 5
    ; imul     rax, rax, 5
    ; imul     rax, rax, 5
    ; imul     rax, rax, 5
    ; imul     rax, rax, 5
    ; imul     rax, rax, 5

    dec      rcx
    jnz      L_Repeat

    ;------ 終了時刻の取得
    call    GetTickCount

    ;------ 所要時間を表示
    sub     eax, r10d
    mov     edx, eax
    lea     rcx, PRINTFORMAT
    call    printf

    ;------ 戻り値の設定
    xor     eax, eax

    ;------ スタックの解放
    add     rsp, 28h
    ret

main ENDP

END

MASM でアセンブルします。

C:\tmp> ml64 test.asm /link user32.lib msvcrt.lib legacy_stdio_definitions.lib
Microsoft (R) Macro Assembler (x64) Version 14.43.34810.0
......

実行します。

C:\tmp> test.exe
time: 265 ms

単純な 10 億回ループで、265 ms でした。

次に、コメントアウトしてある「lea 命令で 5 倍」直下の 10 個の lea 命令を有効にして再コンパイル、再実行します。

C:\tmp> ml64 test.asm /link user32.lib msvcrt.lib legacy_stdio_definitions.lib
......
C:\tmp> test.exe
time: 2641 ms

「この時間 – 単純ループの時間」を、「lea 命令で 5 倍」命令の 100 億回の実行時間とします。2641 – 265 = 2376 ms です。

続いて、「imul 命令で 5 倍」直下の 10 個の imul 命令のほうを有効にして再コンパイル、再実行します。

C:\tmp> ml64 test.asm /link user32.lib msvcrt.lib legacy_stdio_definitions.lib
......
C:\tmp> test.exe
time: 8250 ms

「この時間 – 単純ループの時間」を、「imul 命令で 5 倍」命令の 100 億回の実行時間とします。8250 – 265 = 7985 ms です。

このようにして、被乗数が rax レジスタの場合の他の乗数についても測定しました。結果を以下に示します。グラフが長いほど所要時間が長い、つまり遅いことを意味します。

所要時間の比率は、lea や shl や add が 1 なのに対し、imul は 3 という結果になりました。

なお、時間は 10 回測定して平均を算出しています。CPU は少し古い Core i5-8265U です。

おわりに

掛け算を imul ではなく lea や shl や add で計算する例について見てきました。
昔に比べると掛け算命令はずいぶん速くなりましたが、それでもまだ、可能であれば、実効アドレスロードやシフト演算や足し算で計算したほうが速いようです。

追記

その後、インテルのドキュメント [3] に次の表があることに気付きました。

レイテンシー（命令を構成しているすべてのマイクロオペレーションの実行が実行コアで完了するのに要するクロックサイクル数）を見ると、

  • add : 1
  • lea（2 引数以下） : 1
  • shl : 1
  • imul : 3

となっており、測定結果と一致します。imul はほかの命令の 3 倍であり、また、計算には rax レジスタのみを使っており前の命令が終わらないと次の命令が実行できないからです。

一方、imul のスループット（発行ポートが同じ種類の命令を再度受け入れられるようになるまで待たなければならないクロックサイクル数）は、

  • imul : 1

となっています。前後に依存関係がなければ 1 サイクルで実行できることを意味し、実際、次のコードの箇所を、

......
    imul     rax, rax, 5
    imul     rax, rax, 5
    imul     rax, rax, 5
    imul     rax, rax, 5
    imul     rax, rax, 5
    imul     rax, rax, 5
    imul     rax, rax, 5
    imul     rax, rax, 5
    imul     rax, rax, 5
    imul     rax, rax, 5
......

次のように書き換えても、実行時間は同じ約 8000 ms でした。

......
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
    imul     rax, rax, 5
    imul     r8, r8, 5
    imul     r9, r9, 5
......

したがって、実際のプログラムでは上の棒グラフのイメージよりも速く imul 命令が処理されることが期待できます。

参考文献

[1] やや低レイヤー研究所「x64 呼び出し規約をわかりやすく説明してみる (Windows)」
https://yaya.lsv.jp/x64-calling-convention/

[2] やや低レイヤー研究所「x64 アセンブリ言語で、Windows API や C 言語のライブラリを呼び出す .exe, .lib, .dll を開発する (Windows, MASM)」
https://yaya.lsv.jp/masm_x64_sample/

[3] インテル「インテル (R) 64 および IA-32 アーキテクチャー 最適化リファレンス・マニュアル参考訳 Volume 2」2024
https://www.isus.jp/wp-content/uploads/pdf/64-ia-32-architectures-optimization-manual-vol2_JA.pdf