はじめに

ブログのアクセス解析を見るとプログラムの高速化についての記事へのアクセスが多いですね。

jyuch.hatenablog.com

こんな具体性のない記事が『VB 高速化』での検索の割と上位に出てきてしまうのはさすがに申し訳ないので、今回はちょっとだけ具体例を挙げながら高速化について説明できたらなと思います。

パフォーマンスを測るために以下のヘルパをあらかじめ定義しておきます。

Public Class Runner

    Public Shared Sub Run(target As Action,
                          targetName As String,
                          Optional preLoopCount As Long = 100,
                          Optional measureLoopCount As Long = 1000)

        For i = 1 To preLoopCount
            target()
        Next

        Dim watch = New Stopwatch()
        watch.Start()
        For i = 1 To measureLoopCount
            target()
        Next
        watch.Stop()

        Console.WriteLine("{0,-20} Total:{1}ms Average:{2}ms",
                          targetName, watch.ElapsedMilliseconds, 
                          watch.ElapsedMilliseconds / measureLoopCount)
    End Sub

End Class

最初の計測しないループはメソッドの初回呼び出し時のJIT コンパイルの影響を受けないよう*1に最初のほうの計測を切り捨てるために回しています。

余談なんですが、ここでは横にスクロールしないように適当に改行してますがこういう感じに改行するの弊社は嫌いなんですよね。なんか間延びしてるような感じで。

Step1 処理の遅くなるパターンの回避

結論から先に行ってしまうと、特別必要じゃない限りOption Strict Onでプログラムを書きましょう。

単純な（単純にしすぎて最適化の影響をモロに受けてそうですが）メソッドとその実行結果を見てみましょう。

Option Strict On

Public Module StrictOn

    Public Sub [On]()
        Result += Add(Date.Now.Second, Date.Now.Second)
    End Sub

    Private Function Add(x As Integer, y As Integer) As Integer
        Return x + y
    End Function

End Module

Option Strict Off

Public Module StrictOff

    Public Sub Off()
        Result += Add(Date.Now.Second, Date.Now.Second)
    End Sub

    Private Function Add(x, y)
        Return x + y
    End Function

End Module

Module Module1

    Public Result As Integer

    Sub Main()
        Runner.Run(AddressOf [On], NameOf([On]), measureLoopCount:=10000000)
        Runner.Run(AddressOf Off, NameOf(Off), measureLoopCount:=10000000)

        Console.WriteLine(Result)
    End Sub

End Module

最適化の結果によるメソッド呼び出し自体のスキップを無理やり回避するために変数に足しこんで表示させてます。

On                   Total:2173ms Average:0.0002173ms
Off                  Total:2948ms Average:0.0002948ms

なんとも言い難い結果ですが、全く同じ処理でも確実に遅くなっています。なんで違いが出たか、順を追って見てみましょう。

まず、Onを基準として見てみましょう。

DataTime.Now.Secondの1つ目が呼び出される
DataTime.Now.Secondの2つ目が呼び出される
1、2の結果が引数としてAddが呼び出される
Addの中で足し合わせられる
足し合わせられた値が返却される
返却された値がResultに足し合わせられる

次にOffの場合です。

DataTime.Now.Secondの1つ目が呼び出される
引数がObject型のためボックス化が行われる（ムダその1）
DataTime.Now.Secondの2つ目が呼び出される
引数がObject型のためボックス化が行われる（ムダその2）
2、4の結果が引数としてAddが呼び出される
なんか頑張って足し合わせる（なんか頑張るところがムダその3）
頑張って足し合わせた値が返却される
返却された値をObjectからIntegetに変換する（ムダその4）
変換した値をResultに足し合わせる

と、Onのときより明らかに多いステップ数で実行されています。

とまぁ、Option Strict Offのときに有効になる暗黙の型変換を使用してしまうと回避できるオーバーヘッドを抱え込んでしまうことになります。また、同様にOption Strict Offのときに有効になる遅延バインディングが激遅なのはかなり有名ですね。

そしてそれを手っ取り早く回避する方法がOption Strict Onでコンパイル時に禁止してしまうことです。

ただ、どうしても遅延バインディングを使わなければならない場面も長い人生であるかもしれません。その時は最低限の遅延バインディング及び暗黙の型変換となるようにいい感じにコードを書いてやる必要があります。

理想を言えばC#のdynamicに相当するものを導入したうえでdynamicと同様の呼び出し機構を利用できればよかったのですが・・・。

Step2 アルゴリズム的に頑張る

アルゴリズムで高速化を図るのが高速化に最も効果的です。

とはいえ、業務で発生する諸問題に対して毎回アルゴリズムからデータ構造からスクラッチするのもなかなか大変です。そのような場合でも、データを格納するコレクションを適切に選ぶだけで速度に大きく差が出ることがあります。

ここでは多数の名前から重複を取り除くとしましょう。

こんなクラスを用意して、

Public Class Name
    
    public ReadOnly Property GivenName() As String
    Public ReadOnly Property FamilyName() As String
    
    Public sub New(givenName As String, familyName As String)
        Me.GivenName = givenName
        Me.FamilyName = familyName
    End sub

    Public Overrides Function Equals(obj As Object) As Boolean
        Dim other = TryCast(obj, Name)

        If other Is Nothing then Return False

        Return GivenName = other.GivenName AndAlso FamilyName = other.FamilyName
    End Function

    Public Overrides Function GetHashCode() As Integer
        Return GivenName.GetHashCode() Xor FamilyName.GetHashCode()
    End Function

    Public Overrides Function ToString() As String
        Return String.Format("{0} {1}", GivenName, FamilyName)
    End Function

End Class

こんな感じに読み取って

Function ReadDataFromCsv() As IEnumerable(Of Name)
    Return File.ReadAllLines("./dummy.csv", Encoding.GetEncoding(932)).
        Select(Function(it) it.Split(","c)).
        Select(Function(it) New Name(it(1), it(0))).
        ToList()
End Function

こんな感じに重複を排除して集計するとしましょう。

Sub UseList(data As IEnumerable(Of Name))
    Dim cache = new List(Of Name)

    for each it in data
        If Not cache.Contains(it)
            cache.Add(it)
        End If
    Next

    'Console.WriteLine(cache.Count)
End Sub

Sub UseSet(data As IEnumerable(Of Name))
    Dim cache = new HashSet(Of Name)

    for each it In data
        cache.Add(it)
    Next

    'Console.WriteLine(cache.Count)
End Sub

こんな感じに呼び出して

Sub Main()
    dim d = ReadDataFromCsv()

    Runner.Run(Sub() UseList(d), Nameof(UseList), 10,20)
    Runner.Run(Sub() UseSet(d), Nameof(UseSet), 10, 20)
End Sub

結果がこれ

UseList              Total:3978ms Average:198.9ms
UseSet               Total:7ms Average:0.35ms

恐ろしく差がでました。

一応雑に解説しますと、HashSetはオーバーライドしたEqualsを用いて同一の値をただ一つ保持するコレクションで、コレクション内の値の検索にGetHashCodeの値を用いて高速化を図ります。ここで、GetHashCodeが返す値が一意である場合の検索はセットが保持する数に関係なく定数時間内に完了します。つまり、保持している要素が1個でも4500個でも同じ時間で検索が完了するということです。

対してListはコレクション内の検索を先頭から行うので、コレクション内に要素がn個ある場合は最悪要素の検索にnに比例した時間かかります。つまり、4500件のデータが保持されている場合は、1件しか保持されていない場合に比べて（途中で見つからなかった場合は）4500倍の時間が掛かるということです。

といった感じで、配列しか使わない配列おじさんは悔い改めてね。

おまけ：Linqを使った場合

Sub UseLinq(data As IEnumerable(of Name))
    Dim c = data.Distinct().Count()

    'Console.WriteLine(c)
End Sub

UseLinq              Total:8ms Average:0.4ms

おぉぉ・・・

Step3 並列化してマルチコアで殴る

アルゴリズム的に改良したがもうだめだ。これ以上は高速化は望めない。という場合に（ほぼ）最終手段として検討するのが並列化です。ただ、すべてのアルゴリズムが並列化可能であるかといえばそうではないので、採用しようとしているアルゴリズムが並列化可能であるか見極める必要があります。

ここでは並列処理の教科書的な問題である値の集計の並列化を行ってみます。

とりあえず並列化してないバージョンを作成、計測してそこからタイムを縮めて行きましょう。

Public Const DataSize = 100000000

Sub Main()
    Dim data = InitData()

    Runner.Run(Sub() SingleReduction(data), Nameof(SingleReduction))
End Sub

Function SingleReduction(data As Long()) As Long
    Dim sum = 0L

    For i = 0 To DataSize - 1
        sum += data(i)
    Next

    Return sum
End Function

Function InitData() As Long()
    Dim a(DataSize - 1) As Long
    Dim r = New Random(1)

    For i = 0 To DataSize - 1
        a(i) = r.Next(10)
    Next

    Return a
End Function

SingleReduction      Total:107732ms Average:107.732ms

ここで残念なお知らせです。弊社のパソコンは2コアなのでどんなに頑張っても2倍しか高速化されません。まぁ、倍になれば御の字ということで頑張りましょう。

とりあえず並列化してみましょう。

Public Class BadParallel1

    Private _sum As Long = 0

    Private Sub ParallelAdder(data As Long(), startIndex As Integer, endIndex As Integer)
        For i = startIndex To endIndex
            _sum += data(i)
        Next
    End Sub

    Public Shared Function AddParallel(data As Long()) As Long
        Dim b = New BadParallel1
        Dim s = data.Length \ 2

        Dim t1 = New Task(Sub() b.ParallelAdder(data, 0, s))
        Dim t2 = New Task(Sub() b.ParallelAdder(data, s + 1, data.Length - 1))

        t1.Start()
        t2.Start()

        Task.WaitAll(t1, t2)

        Return b._sum
    End Function

End Class

Sub Main()
    Dim data = InitData()

    'Runner.Run(Sub() SingleReduction(data), Nameof(SingleReduction))
    Console.WriteLine(SingleReduction(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
    Console.WriteLine(BadParallel1.AddParallel(data))
End Sub

値がおかしなことになっていますね。正しい答えとはまるで違う値になってますし、毎回異なる値を返してきています。

というわけでダメな並列化の例その1、複数のスレッドから共有される可変ステートの同期化を正しく行っていないです。

とりあえず_sum += data(i)について見てみましょう。 VBレベルで見ると一行で記述されているため一回の処理で実行されそうですが、CPUレベルで見ると複数の処理の複合となっています。

_sumの値を読み込む
data(i)の値を読み込み
二つを足し合わせる
足し合わせた結果を_sumに格納する

という処理を行っています。

これが2つのスレッドからバラバラに行われたらどうなるでしょう。

スレッド1が_sumの値を読み込む
スレッド2が_sumの値を読み込み
2つのスレッドが計算をおこなう
スレッド2が値を_sumに格納する
スレッド1が値を_sumに格納する

といった流れになりかねません。この場合はスレッド2の計算結果は_sumに加算されなくなってしまいます。

どうすればいいかといいますと、要するに読み込んで足し合わせて格納する処理を他のスレッドに邪魔されずに処理させればいいのです。

というわけで書き直したのがこちら。

Public Class BadParallel2
    Private _sum As Long = 0
    Private _sync As Object = New Object

    Private Sub ParallelAdder(data As Long(), startIndex As Integer, endIndex As Integer)
        For i = startIndex To endIndex
            SyncLock _sync
                _sum += data(i)
            End SyncLock
        Next
    End Sub

    Public Shared Function AddParallel(data As Long()) As Long
        Dim b = New BadParallel2
        Dim s = data.Length \ 2

        Dim t1 = New Task(Sub() b.ParallelAdder(data, 0, s))
        Dim t2 = New Task(Sub() b.ParallelAdder(data, s + 1, data.Length - 1))

        t1.Start()
        t2.Start()

        Task.WaitAll(t1, t2)

        Return b._sum
    End Function
End Class

SyncLockは単一のスレッドしかその範囲に入らないようにするための構文です。

Sub Main()
    Dim data = InitData()

    'Runner.Run(Sub() SingleReduction(data), Nameof(SingleReduction))
    Console.WriteLine(SingleReduction(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
    Console.WriteLine(BadParallel2.AddParallel(data))
End Sub

こんどは正しく計算できています。ただ、おそい。とにかく遅い。そりゃそうです。本来並列化すべき部分を直列化してしまったのですから。ただ直列化しただけでなく同期化のオーバーヘッドも生じてしまったのでふつうにシングルスレッドで足し合わせるより遅くなってしまいました。

SingleReduction      Total:2148ms Average:107.4ms
BadParallel2         Total:129582ms Average:6479.1ms

というわけでダメな並列化の例その2、ロック待ちで性能が劣化するです。

これらの欠点を解決したバージョンがこちらです。

Public Class GoodParallel

    Private Shared Function ParallelAdder(data As Long(), startIndex As Integer, endIndex As Integer) As Long
        Dim sum = 0L
        For i = startIndex To endIndex
            sum += data(i)
        Next
        
        Return sum
    End Function

    Public Shared Function AddParallel(data As Long()) As Long
        Dim s = data.Length \ 2

        Dim t1 = New Task(Of Long)(Function() ParallelAdder(data, 0, s))
        Dim t2 = New Task(Of Long)(Function() ParallelAdder(data, s + 1, data.Length - 1))

        t1.Start()
        t2.Start()

        Return t1.Result + t2.Result
    End Function

End Class

加算した結果の一時変数を各スレッドごとに持たせ、すべての処理が完了した段階でそれぞれの合計を加算するように変更しました。

Console.WriteLine(SingleReduction(data))
Console.WriteLine(GoodParallel.AddParallel(data))
Console.WriteLine(GoodParallel.AddParallel(data))
Console.WriteLine(GoodParallel.AddParallel(data))
Console.WriteLine(GoodParallel.AddParallel(data))
Console.WriteLine(GoodParallel.AddParallel(data))
Console.WriteLine(GoodParallel.AddParallel(data))
Console.WriteLine(GoodParallel.AddParallel(data))
Console.WriteLine(GoodParallel.AddParallel(data))
Console.WriteLine(GoodParallel.AddParallel(data))
Console.WriteLine(GoodParallel.AddParallel(data))

結果も問題なさそうです。

気になる性能はどうでしょうか。

SingleReduction      Total:105667ms Average:105.667ms
GoodParallel         Total:74578ms Average:74.578ms

さすがに性能2倍とまではいかなかったですね。まぁ、それなりの性能ですね。

という感じで並列化でマルチコアで殴るでした。

おまけ：PLINQ

Runner.Run(Sub() SingleReduction(data), NameOf(SingleReduction))
Runner.Run(Sub() GoodParallel.AddParallel(data), NameOf(GoodParallel))
Runner.Run(Sub() data.AsParallel().Sum(), "PLINQ")

SingleReduction      Total:108780ms Average:108.78ms
GoodParallel         Total:82630ms Average:82.63ms     ←　しれっとさっきよりも悪いスコアを叩き出している
PLINQ                Total:235649ms Average:235.649ms  ←　さらっと直列よりも遅い結果を叩き出したPLINQ殿

終わりに

とりあえず高速化のさわりをやってみました。

弊社の個人的な意見としては並列化は共有される可変ステートの管理やクリティカルセクションの粒度、タスクの分割とスレッドへの割り当てなどシングルスレッドの時にはなかった問題が出てくるのであまり積極的にはやりたくないなぁといった感じです。特に今回の並列化の最初の例のように可変ステートが壊れて値がおかしくなるとデバッグがかなり困難になります。

並列化はどんなに頑張ってもn個のコアがあるCPUで1/nの時間にしか削減できません。*2 ので、遅いといった場合にいきなり並列化を考えるのではなく、まずはアルゴリズム的に高速化できないか検討してみてください。

アルゴリズム的にもう頭打ちで、それでももっと高速化しなくてはならない（≒高速化にコストを払える）場合に並列化を検討するくらいでいいのではないでしょうか。

また、この記事では言っていませんでしたが高速化を図る前にどの処理が遅いのかプロファイルすることを強くお勧めします。プロファイルのない高速化ですと処理に対して時間のかかっていない場所の可読性を下げてあまり効果がありませんでしたで終わる可能性があります。

最後に、検証に使ったコードはこちらになります。

github.com

おわり

*1:JIT コンパイルはアプリケーション実行時に一括でされるのではなく、実行時の初回呼び出し時に行われるのです。

*2:アムダールの法則的に言えば全体の処理のうち並列化できる処理の割合にも依存します。

レンコン畑でつかまえて

VB.NETでも処理を高速化したい　その2

はじめに

Step1 処理の遅くなるパターンの回避

Step2 アルゴリズム的に頑張る

Step3 並列化してマルチコアで殴る

終わりに