(VBで)Ifを使わない関数が遅い原因を調べる
2019年09月11日 10時16分 - [プログラムな?話]
<2019-09-14 追記あり>
以前書いた3値の中央値をIfを使わずに求める方法で、少なくとも自分の環境のVBAではIfを使った方が速いと書いた。
が、原因がよくわからずモヤっとしていた。
試しにC++で同じように比較してみたところ、C++ではIfあり・なしで処理時間にそう大きな差はなかった。この違いは何なんだろうか?
試しにオンラインでアセンブリを確認できるサイトで、C++で書いたコードをアセンブリ言語にしてみた(Visual Studioのコンパイルのオプションでアセンブリを出力することもできたが、こちらのサイトでやった方がコードが見やすかった)。
int med(int a, int b, int c) {
return a ^ b ^ c ^ (-(a < b) & (a ^ b)) ^ (-(b < c) & (b ^ c)) ^ (-(c < a) & (c ^ a));
}
↓
mov edx, DWORD PTR _a$[esp-4]
mov eax, edx
mov ecx, DWORD PTR _c$[esp-4]
push esi
mov esi, DWORD PTR _b$[esp]
xor eax, esi
push edi
xor edi, edi
cmp edx, esi
cmovl edi, eax
cmp ecx, edx
cmovl edx, ecx
xor edi, edx
cmp esi, ecx
cmovl esi, ecx
xor edi, esi
xor edi, ecx
mov eax, edi
pop edi
pop esi
ret 0
上記のコードは最適化を有効にしている(/O1)。アセンブリはあまり詳しくないが、'-(a < b) & (a ^ b)'的な部分の処理が以下のような感じで非常にシンプルになっている。
mov edx, DWORD PTR _a$[esp-4]
mov eax, edx
mov esi, DWORD PTR _b$[esp]
xor eax, esi
cmp edx, esi
cmovl edi, eax
先にa^bを計算してeaxレジスタに保存しておき(4行目)、a<bを評価し(5行目)真なら値をコピーする(6行目)。最適化を行わないと、以下のようになってしまう。
mov eax, DWORD PTR _a$[ebp]
cmp eax, DWORD PTR _b$[ebp]
jge SHORT $LN3@med
mov DWORD PTR tv68[ebp], 1
jmp SHORT $LN4@med
$LN3@med:
mov DWORD PTR tv68[ebp], 0
$LN4@med:
mov ecx, DWORD PTR _a$[ebp]
xor ecx, DWORD PTR _b$[ebp]
mov edx, DWORD PTR tv68[ebp]
neg edx
and ecx, edx
aとbを比較し(2行目)、a<bなら1(4行目)、a>=bなら0(7行目まで)を一旦格納してから符号を反転し(12行目)、a^b(10行目)の結果をand演算(13行目)している。&は論理積(and)のビット演算子だし-は符号を反転するので、これが本来的な動作ではある。
が、大小を比較して(cmp命令)フラグレジスタを見て1か0を格納し(jge命令・mov命令・jmp命令)符号反転(neg命令)したものをビット演算(and命令)する代わりに、大小を比較して(cmp命令)フラグレジスタを見て値をコピーするか何もしない(cmovl命令)ようにしても同じ結果が得られるし、この方がすっきりするしずっと速い。
まぁ、C++の方はこうなってた。最適化スゴイ。cmovlスゴイ。
さてVBだ。VBはオンラインでこう、中身・・・中間言語・・・MSIL、を見る、とかいうのがないので、Visual Studioに附属しているIL Dasmを使った。
Function Med(ByRef a As Long, ByRef b As Long, ByRef c As Long) As Long
Return a Xor b Xor c Xor ((a < b) And (a Xor b)) Xor ((b < c) And (b Xor c)) Xor ((c < a) And (c Xor a))
End Function
↓
IL_0000: ldarg.0
IL_0001: ldind.i8
IL_0002: ldarg.1
IL_0003: ldind.i8
IL_0004: xor
IL_0005: ldarg.2
IL_0006: ldind.i8
IL_0007: xor
IL_0008: ldarg.0
IL_0009: ldind.i8
IL_000a: ldarg.1
IL_000b: ldind.i8
IL_000c: clt
IL_000e: ldc.i4.0
IL_000f: cgt.un
IL_0011: neg
IL_0012: conv.i8
IL_0013: ldarg.0
IL_0014: ldind.i8
IL_0015: ldarg.1
IL_0016: ldind.i8
IL_0017: xor
IL_0018: and
IL_0019: xor
IL_001a: ldarg.1
IL_001b: ldind.i8
IL_001c: ldarg.2
IL_001d: ldind.i8
IL_001e: clt
IL_0020: ldc.i4.0
IL_0021: cgt.un
IL_0023: neg
IL_0024: conv.i8
IL_0025: ldarg.1
IL_0026: ldind.i8
IL_0027: ldarg.2
IL_0028: ldind.i8
IL_0029: xor
IL_002a: and
IL_002b: xor
IL_002c: ldarg.2
IL_002d: ldind.i8
IL_002e: ldarg.0
IL_002f: ldind.i8
IL_0030: clt
IL_0032: ldc.i4.0
IL_0033: cgt.un
IL_0035: neg
IL_0036: conv.i8
IL_0037: ldarg.2
IL_0038: ldind.i8
IL_0039: ldarg.0
IL_003a: ldind.i8
IL_003b: xor
IL_003c: and
IL_003d: xor
IL_003e: ret
このMSILとかCILとかいうのはさっぱりだったが、ldargで引数のアドレスをスタックにpushして、ldind.i~でスタックに積まれたアドレスをpopして値を取得し、i~に応じてint32やint64の数値に置き換えpushしているらしい。ようは命令がすべてスタック上で行われるスタックマシンというやつらしい。
コードを読み解いていくと、どうもスタックというものは一つしかないらしく、絶えずldarg・ldindで引数をスタックに積み込んでは命令を実行してpopされ、またldarg・ldindでスタックに積み・・・ということを繰り返しているように思える。
jmpのような飛ぶ系の命令は使われていないようだが、スタック上を線形に(というのだろうか)行ったり来たりしているように見える。
8行目(IL_0007)まではa Xor b Xor cを実行していて、9行目から24行目(IL_0019)までが'Xor ((a < b) And (a Xor b))'の処理。以降、16行ずつbとc、cとaの処理。
何をしているのかというと、ようは2つの値をスタックにpushして(ldarg.0~2・ldind.i8)大小を比較して1か0をpushして(clt)、なぜか比較結果と0(ldc.i4.0)を比較して1か0をpushして(cgt.un)、符号を反転して(neg)int64に変換して(conv.i8)、もう一度2つの値をスタックにpushして(ldarg・ldind.i8)、2つの値をxorした値を0か-1とandして、その値とあらかじめスタックしていた a Xor b Xor c の値をxorしている。
これをあと2回繰り返している。ようするに最適化していないC++のアセンブリのコードとロジック的にほぼ同じことをやっているようだ。jmp系の命令がない点や比較を2回繰り返している点や、64ビット整数への変換が噛んでいるという違いはあるが。ちなみにLongを全部Integerにしてやってみたが、int64へのコンバートがなくなっただけで処理はほとんど同じだった。
ちなみにIfを使った場合はだいたい以下のような感じになる。
Function Med(ByRef a As Long, ByRef b As Long, ByRef c As Long) As Long
If a < c Then
If b < a Then
Return a
ElseIf B < c Then
Return b
Else
Return c
End If
ElseIf a < b Then
Return a
ElseIf c < b Then
Return b
Else
Return c
End If
End Function
↓
IL_0000: ldarg.0
IL_0001: ldind.i8
IL_0002: ldarg.2
IL_0003: ldind.i8
IL_0004: bge.s IL_0021
IL_0006: ldarg.1
IL_0007: ldind.i8
IL_0008: ldarg.0
IL_0009: ldind.i8
IL_000a: bge.s IL_0011
IL_000c: ldarg.0
IL_000d: ldind.i8
IL_000e: stloc.0
IL_000f: br.s IL_003a
IL_0011: ldarg.1
IL_0012: ldind.i8
IL_0013: ldarg.2
IL_0014: ldind.i8
IL_0015: bge.s IL_001c
IL_0017: ldarg.1
IL_0018: ldind.i8
IL_0019: stloc.0
IL_001a: br.s IL_003a
IL_001c: ldarg.2
IL_001d: ldind.i8
IL_001e: stloc.0
IL_001f: br.s IL_003a
IL_0021: ldarg.0
IL_0022: ldind.i8
IL_0023: ldarg.1
IL_0024: ldind.i8
IL_0025: bge.s IL_002c
IL_0027: ldarg.0
IL_0028: ldind.i8
IL_0029: stloc.0
IL_002a: br.s IL_003a
IL_002c: ldarg.2
IL_002d: ldind.i8
IL_002e: ldarg.1
IL_002f: ldind.i8
IL_0030: bge.s IL_0037
IL_0032: ldarg.1
IL_0033: ldind.i8
IL_0034: stloc.0
IL_0035: br.s IL_003a
IL_0037: ldarg.2
IL_0038: ldind.i8
IL_0039: stloc.0
IL_003a: ldloc.0
IL_003b: ret
bge.sとかbr.sとかいうのがjmp系の命令。ジャンプはするが、処理命令数は最小16~最大21程度に抑えられる。Ifを使わずに計算している方は57。
これはつまり、演算や比較が生じる毎に何度もpushするような処理は遅くなる、ということだろうか。C++は複数の汎用レジスタに値を置けるが、VBはそれができない、ということだろうか。
なんというかこう、なんでcltとcgt.unで2回比較を繰り返しているのかとか、3つしかない引数を何度も何度もpushしているところはなんとかならないのかとか、見るからに一つのスタックだけでやりくりしているように思えるが本当にそうなのかとか、もうちょっとなんとかならないのかと思うところがある。
が、ひとえに自分のスキル・知識が足りてないのが一番の原因ということに行き着いた。現時点では「VBでは条件分岐の有無より演算や比較の回数をとにかく減らした方が効率がいい」ということかなと整理している。ゆくゆくはこういったアセンブリやILといったものを元にしてコードを最適化できるようになりたい。
2019/09/14 追記
よくよく調べてみたら、コンパイルしてMSIL(CIL)が出力されるのはVB.NETだけであって、「VBAが出力するPコードとやらもMSIL(CIL)なんでしょ?」と思ってたらどうやら違ったらしい。死にたい。割と。
「じゃあVBAが出力するPコードとやらはどんなコードなのよ?」と思い調べてみたが、なぜか知らないがかなり情報が少ない。
かろうじて見つけたP-Code Disassemblerなるツールで、Pコードをダンプできるらしいのでやってみた。
Option Explicit
Function Med(ByRef a As Long, ByRef b As Long, ByRef c As Long) As Long
Let Med = a Xor b Xor c Xor ((a < b) And (a Xor b)) Xor ((b < c) And (b Xor c)) Xor ((c < a) And (c Xor a))
End Function
↓
Line #0:
Option (Explicit)
Line #1:
Line #2:
FuncDefn (Function Med(ByRef a As Long) As Long)
Line #3:
Let
Ld a
Ld B
Xor
Ld c
Xor
Ld a
Ld B
Lt
Paren
Ld a
Ld B
Xor
Paren
And
Paren
Xor
Ld B
Ld c
Lt
Paren
Ld B
Ld c
Xor
Paren
And
Paren
Xor
Ld c
Ld a
Lt
Paren
Ld c
Ld a
Xor
Paren
And
Paren
Xor
St Med
Line #4:
EndFunc
このPコードとやらのリファレンスというものがなぜか見つからないので、正直これが正しいのかはわからないが、やっていることはなんとなく想像がつく。LdはLoad、Stは後続の名前の変数へのSet、Letはまんま代入のステートメント、Ltは比較(Less Than)して-1か0をセット、Parenは括弧だから演算の優先順位?・・・うん、ILDasmで見たのとあんま変わらんわこれ。
要はVB.NETにせよVBAにせよ、根本的にはスタックベースで動作している、ということかな・・・っておもいました。
で、そうなるとやはり同じ値を何度も参照するような処理を減らす方がパフォーマンスを改善できる、ということになるか。
とりあえず9つあるParenは3つに減らせるものの、Paren自体は命令の順序を入れ替えてるだけで何のコストも発生していないように思われる(Parenを削っても普通に処理の順序を読み解くことができる→おそらくParen自体は何の命令も発していない)。
研鑽を積もう。