配列に循環的にアクセスする方法3つの速度を調べてみた


配列に循環的にアクセスする方法で、ぼくが知っているものは3つあります。それぞれの書き方の紹介と、速度検証をしてみます。

速度検証はUnityのProfilerという機能を用います。

今回検証するスクリプト

LengthSpeedTest.cs

using UnityEngine;

public class LengthSpeedTest : MonoBehaviour {

    int testCount = 1000000;
    const int ArrayLength = 1 << 2;
    readonly int mask = ArrayLength - 1;

    int idx = 0;
    int[] intArray = new int[ArrayLength];

    // Use this for initialization
    void Start () {
        idx = 0;
        Profiler.BeginSample("ClampPattern1");
        clamp1();
        Profiler.EndSample();

        idx = 0;
        Profiler.BeginSample("ClampPattern2");
        clamp2();
        Profiler.EndSample();

        idx = 0;
        Profiler.BeginSample("ClampPattern3");
        clamp3();
        Profiler.EndSample();

        UnityEditor.EditorApplication.isPlaying = false;
    }

    void clamp1()
    {
        for (int i = 0; i < testCount; i++)
        {
            if (++idx >= intArray.Length) idx = 0;
            intArray[idx] = 0;
        }
    }

    void clamp2()
    {
        for (int i = 0; i < testCount; i++)
        {
            intArray[++idx % ArrayLength] = 0;
        }
    }

    void clamp3()
    {
        for (int i = 0; i < testCount; i++)
        {
            intArray[++idx & mask] = 0;
        }
    }
}


3つ目の方法は配列の長さが 2 の n 乗でないと使えないので今回は配列の長さ(ArrayLength)を 1 << 2 (= 4) とします。

全体の流れは、処理開始直後に3つの方法で配列に一定回数(testCount)だけ繰り返しアクセスし、かかった時間を Profiler で調べたあと処理を停止するだけです。

1つ目(Clamp1)はインクリメントして配列の要素以上の数になった場合は 0 に戻す方法。一番一般的な気がします。

2つ目(Clamp2)はインクリメントしたものを剰余演算したものをそのままインデックスとして使用する方法。1つ目のやり方をそのまま縮めたような意味になります。

3つ目(Clamp3)はインクリメントしたものを (配列の長さ - 1) でマスクする方法。上記の通り、この方法は配列の長さ等の最大数に使いたい数が 2 の n 乗でないと使えません。

2 の n 乗は 2 進数では例えば 10010000 であり、それらから 1 を引くと 01101111 です。一番大きい桁以外はすべて 1 になるのがミソですね。そのため、++idx & mask は1つ目、2つ目の方法と同じ結果になります。ちょっとトリッキーな書き方です。

さて速度検証の結果です。

100,000回

Clamp1 Clamp2 Clamp3
0.96ms 0.74ms 0.66ms

1,000,000回

Clamp1 Clamp2 Clamp3
9.49ms 7.23ms 5.71ms

10,000,000回

Clamp1 Clamp2 Clamp3
109.08ms 68.80ms 63.85ms

思ったより2つ目と3つ目の差がないのが意外でした。
1つ目の方法を使っている方は2つ目の方法に乗り換えるといいかと思います。
2つ目と3つ目の比較ですが、3つ目の方法は使うための条件があって直感的でもありません。また、繰り返す回数が今回のようにめちゃくちゃ膨大である場合にやっと数字上では違いが判る程度のものです。

という訳で、普段は2つ目の方法を使い、データ構造を自作するなど速度に特にこだわりたい場合は3つ目を使うといいかな、と思いました。