Swift Benchmark#

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との演算ができないという問題がありました。

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;
    }
}

$ 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

乱数生成#

疑似乱数生成には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 時間位かかる計算になります、だめだこりゃ。

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>()
}