[Java] 速度比較テスト（配列アクセス順序・スコープ外宣言・Collections.swap・for ループのチューニング）

Java での基本操作について速度の比較をしてみました。
Windows 10 + jdk1.8.0_111 で調べました。
CPU: i7-3770K @3.5GHz (8 MB SmartCache)

比較に利用したコードはページの下のほうに載せています。

# 配列へのランダムアクセス vs 連続アクセス
次のコードの速度を比較しました。
int 型の配列です。

```java:SequentialAccess.java
for (int j = 0; j < accessRange; ++j)
{
    int rn = rng.nextInt(accessRange);
    array[j] = rn; // ここが違う
}
```

```java:RondomAccess.java
for (int j = 0; j < accessRange; ++j)
{
    int rn = rng.nextInt(accessRange);
    array[rn] = j; // ここが違う
}
```

結果。アクセスする範囲が $10^5$ のあたりから差がつき始め、要素数 $10^8$ へのアクセスでは、２倍以上の差がつきました。

int 型が 32 ビット整数で 4 バイトのはずなので、
配列数 $10^5$ のとき、4 bytes * 100 K で約400KB，
配列数 $10^8$ のとき、4 bytes * 100 M で約400MB の容量を使っているはずです。

実行速度を気にする場合、512KB 以上のメモリアクセスでは、アクセス順序を気にしたほうがよさそうです。（筆者の環境）

|速度比|アクセス速度（横がaccessRange。縦が実行速度。単位はナノ秒）|
|:----:|:--:|
|![速度比.png](https://qiita-image-store.s3.amazonaws.com/0/147332/54cbdced-66eb-3318-d1e4-23aa73c3609c.png)|![配列のアクセス速度比較（対数軸）.png](https://qiita-image-store.s3.amazonaws.com/0/147332/66ac637d-d128-9d27-ba29-e269412eb861.png)|


# for 文内での宣言 vs for 文外での宣言
次のコードの実行時間を比較しました。

```java:InDeclare.java
int sum = 0;
for (int i = 0; i < LOOP; ++i)
{
    int a, b, c, d, e; // for 文内で宣言
    a = i;
    b = a * 2;
    c = a + b;
    d = a + b + c;
    e = a + b + c + d;
    sum += e % 2;
}
```

```java:OutDeclare.java
int sum = 0;
int a, b, c, d, e; // for 文外で宣言
for (int i = 0; i < LOOP; ++i)
{
    a = i;
    b = a * 2;
    c = a + b;
    d = a + b + c;
    e = a + b + c + d;
    sum += e % 2;
}
```

結果。どちらも平均0.41秒で変わりませんでした。
このくらいは簡単に最適化されるのだと思います。
速度低下を怖がって、for 文の外で変数宣言している人がいたので測定してみました。

# Temp Swap vs Collection.swap
次のコードの実行時間を比較しました。
型は、java.util.ArrayList&lt;Integer&gt;です。

```java:IntegerTempSwap.java
for (int i = 0; i < LOOP; ++i)
{
    int rn1 = rng.nextInt(ARRAY_SIZE);
    int rn2 = rng.nextInt(ARRAY_SIZE);
    Integer tmp = aryList.get(rn1);
    aryList.set(rn1, aryList.get(rn2));
    aryList.set(rn2, tmp);
}
```

```java:IntegerCollectionsSwap.java
for (int i = 0; i < LOOP; ++i)
{
    int rn1 = rng.nextInt(ARRAY_SIZE);
    int rn2 = rng.nextInt(ARRAY_SIZE);
    java.util.Collections.swap(aryList, rn1, rn2);
}
```

結果。temp を用いたスワップのほうは、2.05秒。
Collections.swap を用いたほうは、2.06秒と
誤差の範囲ですが、若干 temp を用いたスワップのほうが早くなりました。

Collections.swap を使うと早くなると思っていたので驚きです。
temp を使ったほうが、最適化が働きオーバーヘッドが少ないのでしょうか？

ちなみに、tmp 変数をループ外で宣言しても 2.05 秒と変わりませんでした。

これを ArrayList&lt;Integer&gt; ではなく、int の配列で行うと、2.02秒へと若干高速化されました。

# for ループのチューニング
次のように、同じ処理を２つ並べてループを回すと、1.38 秒から 0.83 秒へと劇的に早くなりました。

for の中に for があるときは、中に入っている for 文を並べて書くとかなり早くなるようです。驚きです。

for 中に for でないものを書き並べた場合では、１パーセントほどのスピードアップになりました。

```java:InDeclare.java
for (int measure = 0; measure < MEASURE_COUNT / 2; ++measure)
{
    {
        int sum = 0;
        for (int i = 0; i < LOOP; ++i)
        {
            int a, b, c, d, e;
            a = i;
            b = a * 2;
            c = a + b;
            d = a + b + c;
            e = a + b + c + d;
            sum += e % 2;
        }
    }

    {
        int sum = 0;
        for (int i = 0; i < LOOP; ++i)
        {
            int a, b, c, d, e;
            a = i;
            b = a * 2;
            c = a + b;
            d = a + b + c;
            e = a + b + c + d;
            sum += e % 2;
        }
    }
}
```

#テストに使ったコード

```java:SequentialAccess.java
public class SequentialAccess
{
    private static final int ARRAY_SIZE = 100000000;
    private static final int LOOP = 10;

    public static void main(String[] args)
    {
        long t1, t2;
        int[] array = new int[ARRAY_SIZE];
        java.util.Random rng = new java.util.Random();

        System.out.println("Sequential Access");

        for (int accessRange = 10; accessRange <= ARRAY_SIZE; accessRange *= 10)
        {
            System.out.print(accessRange);
            System.out.print('\t');

            for (int i = 0; i < LOOP; ++i)
            {
                t1 = System.nanoTime();
                for (int j = 0; j < accessRange; ++j)
                {
                    int rn = rng.nextInt(accessRange);
                    array[j] = rn;
                    // array[rn] = j;
                }
                t2 = System.nanoTime();
                System.out.print(t2 - t1);
                System.out.print('\t');
            }

            System.out.println();
        }
    }
}
```

```java:InDeclare.java
public class InDeclare
{
    private static final int LOOP = 100000000;
    private static final int MEASURE_COUNT = 10;

    public static void main(String[] args)
    {
        long t1, t2;

        System.out.println("in-declare");
        for (int measure = 0; measure < MEASURE_COUNT / 2; ++measure)
        {
            t1 = System.nanoTime();
            int sum = 0;
            for (int i = 0; i < LOOP; ++i)
            {
                int a, b, c, d, e;
                a = i;
                b = a * 2;
                c = a + b;
                d = a + b + c;
                e = a + b + c + d;
                sum += e % 2;
            }
            t2 = System.nanoTime();
            System.out.println(sum % 2 + (t2 - t1));
        }
    }
}
```

```java:IntegerTempSwap.java
public class IntegerTempSwap
{
    private static final int MEASURE_COUNT = 10;
    private static final int LOOP = 100000000;
    private static final int ARRAY_SIZE = 10000;

    public static void main(String[] args)
    {
        long t1, t2;
        java.util.Random rng = new java.util.Random();

        System.out.println("temp swap");

        java.util.ArrayList<Integer> aryList = new java.util.ArrayList<>(ARRAY_SIZE);
        for (int i = 0; i < ARRAY_SIZE; ++i)
        {
            aryList.add(new Integer(i));
        }

        for (int measure = 0; measure < MEASURE_COUNT; ++measure)
        {
            t1 = System.nanoTime();
            Integer tmp;
            for (int i = 0; i < LOOP; ++i)
            {
                int rn1 = rng.nextInt(ARRAY_SIZE);
                int rn2 = rng.nextInt(ARRAY_SIZE);
                tmp = aryList.get(rn1);
                aryList.set(rn1, aryList.get(rn2));
                aryList.set(rn2, tmp);
                // java.util.Collections.swap(aryList, rn1, rn2);
            }
            t2 = System.nanoTime();
            System.out.println(t2 - t1);
        }
    }
}

```