iso tank

（VBで）Ifを使わない関数が遅い原因を調べる

〔プログラムな？話〕 2019/09/11 10:16 No Comment

＜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自体は何の命令も発していない）。

研鑽を積もう。

（VBで）Ifを使わない関数が遅い原因を調べる への Writeback

名前：

URLまたはE-Mail：（※リンク表示注意）

コメント：

情報をクッキーに保存する

trackback URI：

http://iso.tank.jp/puroguramu/ifvsnonif.tarako