Swift Benchmark#

Google が開発した Swift 用のベンチマークライブラリ。下手に自分で書くより、Google 謹製のライブラリを使ったほうが便利そうなので使ってみました。

Random#

現在開発中の Ocean ライブラリがあまりにも遅いのでいろいろ改良してみることにしました

Ocean ライブラリでは乱数を何度も生成するので、乱数生成が遅いとそれだけでボトルネックになってしまいます。ちなみに、オリジナルのコードは以下のような感じになっています。

import Foundation

final class Random {
    private(set) var mSeed1: Int64 = 0
    private(set) var mSeed2: Int64 = 0
    private(set) var mSeed3: Int64 = 0
    private(set) var mSeed4: Int64 = 0

    init() {}

    init(seed: Int64) {
        self.mSeed1 = 0xFFFFFFFF & (0x6C078965 * (seed   ^ (seed   >> 30)) + 1)
        self.mSeed2 = 0xFFFFFFFF & (0x6C078965 * (mSeed1 ^ (mSeed1 >> 30)) + 2)
        self.mSeed3 = 0xFFFFFFFF & (0x6C078965 * (mSeed2 ^ (mSeed2 >> 30)) + 3)
        self.mSeed4 = 0xFFFFFFFF & (0x6C078965 * (mSeed3 ^ (mSeed3 >> 30)) + 4)
    }

    @discardableResult
    func getU32() -> Int64 {
        let n = mSeed1 ^ (0xFFFFFFFF & mSeed1 << 11);

        mSeed1 = mSeed2;
        mSeed2 = mSeed3;
        mSeed3 = mSeed4;
        mSeed4 = n ^ (n >> 8) ^ mSeed4 ^ (mSeed4 >> 19);

        return mSeed4;
    }
}

スプラトゥーンの疑似乱数生成器自体は非常にシンプルです。

計算結果を UInt32 に落とし込むために0xFFFFFFFFで論理和をとっていますがこれがまずなんか遅そうです。仮に論理和計算が 1 クロックで実行できたとしてもインスタンス実行のたびに 4 クロック余計に消費してしまいます。

ただ、そのまま UInt32 で定義するとオーバーフローでエラーが発生して0x6C078965との演算ができないという問題がありました。

オーバーフロー演算子を使う#

調べてみたところ、デフォルトでは Swift はオーバーフローをエラーとして返すようなのですが、オーバーフローを許容するオーバーフロー演算子なるものがあり、それを使えば C のようにオーバーフローを利用した計算が可能になるようなのです。

final class Random {
    private(set) var mSeed1: UInt32 = 0
    private(set) var mSeed2: UInt32 = 0
    private(set) var mSeed3: UInt32 = 0
    private(set) var mSeed4: UInt32 = 0

    init() {}

    init(seed: UInt32) {
        self.mSeed1 = (0x6C078965 &* (seed   ^ (seed   >> 30)) + 1)
        self.mSeed2 = (0x6C078965 &* (mSeed1 ^ (mSeed1 >> 30)) + 2)
        self.mSeed3 = (0x6C078965 &* (mSeed2 ^ (mSeed2 >> 30)) + 3)
        self.mSeed4 = (0x6C078965 &* (mSeed3 ^ (mSeed3 >> 30)) + 4)
    }

    @discardableResult
    func getU32() -> UInt32 {
        let n = mSeed1 ^ (mSeed1 << 11);

        mSeed1 = mSeed2;
        mSeed2 = mSeed3;
        mSeed3 = mSeed4;
        mSeed4 = n ^ (n >> 8) ^ mSeed4 ^ (mSeed4 >> 19);

        return mSeed4;
    }
}

というわけでオーバーフロー演算子を利用して純粋な UInt32 だけで計算できるようにRandomクラスを書き直しました。

パフォーマンスを調べる#

試しに Swift 謹製のmeasureを使って計測した結果がこちら。

あれ、なんだか逆に遅くなっているんですけど？？？

いや、でもデフォルトのテストではデバッグビルドで最適化されていないために差が生じないのかもしれません。そこで Swift Benchmark を使って再度計測してみました。

Swift Benchmark#

実行回数を0xFFFFF=1048575にして比較してみました。

$ swift run -c release
[2/2] Build complete!
running UInt32 Random... done! (1642.54 ms)
running Int64 Random... done! (2400.14 ms)

name          time           std        iterations
--------------------------------------------------
UInt32 Random 2034539.000 ns ±   5.17 %        688
Int64 Random  8984566.000 ns ±   2.43 %        155

リリースビルドで測定し直した結果、インスタンス生成の 4.5 倍ほどの高速化に成功しました！

乱数生成#

疑似乱数生成にはgetU32()というメソッドを利用するのですが、こちらも Int64 仕様だったため UInt32 仕様に変更しました。

getU32()は控えめに数えても 1000 億回くらいは呼ばれるので、ここが高速化されることが最もプログラム全体の高速化に繋がります。

こちらは約 8.7 倍程度高速化できました。

Ocean#

import Foundation

public final class Ocean {
    public init(mGameSeed: UInt32) {
        self.mGameSeed = mGameSeed
        self.rnd = Random(seed: mGameSeed)
        rnd.getU32()
        self.mWave = [
            Wave(mGameSeed),
            Wave(rnd.getU32()),
            Wave(rnd.getU32()),
        ]
        self.getWaveInfo()
    }

    private let rnd: UInt32Random

    public private(set) var mWave: [Wave]

    public private(set) var mGameSeed: UInt32
}

さて、次に疑似乱数生成器を持つOceanクラスを定義します。オリジナルのコードは上のような感じです。

これも同じように 100 万回インスタンスを生成してみると…

なんとたったの 100 万件のインスタンス生成に 4 秒もかかってしまいました。この調子でやれば全 43 億通りをチェックするにはこの 4096 倍の時間がかかるので 5 時間位かかる計算になります、だめだこりゃ。

継承クラスにする#

ここで問題になるのはOceanクラスの中でRandomクラスを呼び出しているという点です。

Ocean クラス一つに対して疑似乱数生成器は一つあればいいので、わざわざプロパティとして持たずにOceanクラス自体に疑似乱数生成機能を持たせてやればよいです。

import Foundation

public final class Ocean: Random {
    public init(mGameSeed: UInt32) {
        self.mGameSeed = mGameSeed
        super.init(seed: mGameSeed)
        // 無意味に一回消費
         getU32()
         self.mWave = [
             Wave(mGameSeed),
             Wave(getU32()),
             Wave(getU32())
         ]
         self.getWaveInfo()
    }

    public let mGameSeed: UInt32
    public private(set) var mWave: [Wave] = Array<Wave>()
}

Wave 情報を一回で計算する#

次に重そうなのが配列を一回定義しておいて再度代入しているこの無駄な処理です。

一度計算してそれを代入してしたほうが速いのでそのようにコードを修正します。