JavaのStream APIはうまく使えば超速い

# はじめに
Javaには並列ストリーム（ParallelStream）という並列処理を手軽に書ける機能があり、うまく使えば性能を大幅に上げることができます。
Java8で追加された機能なので今更ですが、最近並列ストリームの良さを実感することがあったので書いてみます。

# 動作環境
* macOS Mojave
* 2.5 GHz Intel Core i7（8コア）
* JDK13

# 内容
ここでは0から6億までの数値について、カプレカ数（定義2）[^1]であるかどうかを調べるコードを例にして、並列ストリームの効果を見てみます。
[^1]: カプレカ数が何なのかは知る必要はありません。とにかくCPUに負荷をかける何らかの処理です。それでも知りたい人という方はググってください。あと、6億という数字には特に意味はありません。いい感じに処理時間がかかる件数というだけです。

## 並列ストリームを使わない例
まずは並列ストリームを使わない例を見てみます。（順次ストリーム）
だらだらと長いので、とりあえず下のmainメソッドを見てください。

```java
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.LongStream;

public class ParallelStreamSample {
    // カプレカ数（定義2）かどうか
    private static boolean isKaprekarNumber2(long n) {
        List<Character> chars = String.valueOf(n)
                                    .chars()
                                    .mapToObj(c -> (char)c)
                                    .collect(Collectors.toList());
        // min
        chars.sort(Comparator.naturalOrder());
        var min = parseLong(join(chars));

        // max
        chars.sort(Comparator.reverseOrder());
        var max = parseLong(join(chars));

        return n == (max - min);
    }

    private static <T> String join(List<T> list) {
        var sb = new StringBuilder();
        for(T item : list) {
            sb.append(item);
        }
        return sb.toString();
    }

    private static long parseLong(String s) {
        if(s.isEmpty()) {
            return 0;
        } else {
            return Long.parseLong(s);
        }
    }

    public static void main(String[] args) {
        System.out.println("--------------------");
        System.out.println("カプレカ数 定義2");
        long start = System.nanoTime();
        LongStream.rangeClosed(0, 600_000_000)
                // 順次ストリーム（通常はこの呼び出しは不要だが、並列ストリームとの対比のため記述している）
                .sequential()
                .filter(n -> n % 9 == 0)
                .filter(ParallelStreamSample::isKaprekarNumber2)
                .forEachOrdered(System.out::println);
        long end = System.nanoTime();

        System.out.printf("処理時間(ms): %d\n", (end - start) / 1_000_000);
        System.out.println("--------------------");
    }
}
```

私の環境では下記のような結果になりました。

```
--------------------
カプレカ数 定義2
0
495
6174
549945
631764
63317664
97508421
554999445
処理時間(ms): 60284
--------------------
```

1分ちょっとかかっています。もう少し速くしたいところですが、並列ストリームを使うとどれくらい速くなるでしょうか？

## 並列ストリームを使う例
次に並列ストリームを使う例を見てみます。

```java
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.LongStream;

public class ParallelStreamSample {
    // カプレカ数（定義2）かどうか
    private static boolean isKaprekarNumber2(long n) {
        List<Character> chars = String.valueOf(n)
                                    .chars()
                                    .mapToObj(c -> (char)c)
                                    .collect(Collectors.toList());
        // min
        chars.sort(Comparator.naturalOrder());
        var min = parseLong(join(chars));

        // max
        chars.sort(Comparator.reverseOrder());
        var max = parseLong(join(chars));

        return n == (max - min);
    }

    private static <T> String join(List<T> list) {
        var sb = new StringBuilder();
        for(T item : list) {
            sb.append(item);
        }
        return sb.toString();
    }

    private static long parseLong(String s) {
        if(s.isEmpty()) {
            return 0;
        } else {
            return Long.parseLong(s);
        }
    }

    public static void main(String[] args) {
        System.out.println("--------------------");
        System.out.println("カプレカ数 定義2");
        long start = System.nanoTime();
        LongStream.rangeClosed(0, 600_000_000)
                // 並列ストリーム
                .parallel()
                .filter(n -> n % 9 == 0)
                .filter(ParallelStreamSample::isKaprekarNumber2)
                .forEachOrdered(System.out::println);
        long end = System.nanoTime();

        System.out.printf("処理時間(ms): %d\n", (end - start) / 1_000_000);
        System.out.println("--------------------");
    }
}
```

コメント以外で変更したのは一行だけです。（`sequential()`を`parallel()`にした）
これにより、順次ストリームではなく並列ストリームが使えるようになります。

こちらは、私の環境では下記の結果になりました。

```
--------------------
カプレカ数 定義2
0
495
6174
549945
631764
63317664
97508421
554999445
処理時間(ms): 22366
--------------------
```

およそ22秒です。順次ストリームでは1分くらいかかっていたので半分以下の処理時間です。素晴らしいですね。

## なんで速くなるの？
順次ストリームでは単一のコアだけを使って実行するのに対して、並列ストリームではマルチコアで処理を分担して実行するためです。サボっているコアを鞭打って働かせて速くするみたいなイメージです。（あくまでもイメージ）

# 並列ストリームを使うための条件について
今回のサンプルだとたった一行変更するだけで速くなりましたが、いつもそのようにうまくいくとは限りません。並列ストリームの恩恵を得るためには、いくつか条件を満たしている必要があります。

## 実行環境がマルチコアであること
これが大前提です。複数のコアを使うことで速くする仕組みなので、シングルコアの環境では速くなりません。むしろ、並列処理のためのオーバーヘッドで遅くなります。

## CPUがボトルネックとなる処理であること
これも大前提です。CPUリソースを余すことなく使うことで速くするようなイメージなので、CPU以外がボトルネックとなっている場合は意味がありません。

## スレッドセーフな実装になっていること
マルチコアで実行するということは、マルチスレッドで実行するということです。そのため、実行する処理はスレッドセーフである必要があります。
前述の `isKaprekarNumber2()` メソッドは引数にのみ依存しているためスレッドセーフですが、引数ではなくフィールドに依存するようなスレッドセーフではない実装ではどうなるか見てみます。（なんか変な例ですが…）

```java
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.LongStream;

public class ThreadUnsafeSample {
    public static void main(String[] args) {
        System.out.println("--------------------");
        System.out.println("カプレカ数 定義2");
        long start = System.nanoTime();

        var myNum = new MyNumber();
        LongStream.rangeClosed(0, 600_000_000)
                .parallel()
                .filter(n -> n % 9 == 0)
                .filter(n -> {
                    // 排他制御なしでフィールドの読み書きを行うためスレッドセーフではない
                    myNum.setNum(n);
                    return myNum.isKaprekarNumber2();
                })
                .forEachOrdered(System.out::println);
        long end = System.nanoTime();

        System.out.printf("処理時間(ms): %d\n", (end - start) / 1_000_000);
        System.out.println("--------------------");
    }

    private static class MyNumber {
        private long num;

        private void setNum(long num) {
            this.num = num;
        }

        // カプレカ数（定義2）かどうか
        private boolean isKaprekarNumber2() {
            List<Character> chars = String.valueOf(num)
                                        .chars()
                                        .mapToObj(c -> (char)c)
                                        .collect(Collectors.toList());
            // min
            chars.sort(Comparator.naturalOrder());
            var min = parseLong(join(chars));

            // max
            chars.sort(Comparator.reverseOrder());
            var max = parseLong(join(chars));

            return num == (max - min);
        }

        private <T> String join(List<T> list) {
            var sb = new StringBuilder();
            for(T item : list) {
                sb.append(item);
            }
            return sb.toString();
        }

        private long parseLong(String s) {
            if(s.isEmpty()) {
                return 0;
            } else {
                return Long.parseLong(s);
            }
        }
    }
}
```

私の環境では、下記のような明らかに不正な結果になりました。

```
--------------------
カプレカ数 定義2
処理時間(ms): 23902
--------------------
```

このように、スレッドセーフではない実装で並列ストリームを使うと期待通りに動作しないので要注意です。
もちろん、 `parallal()` を消すなり`sequential()`に書き換えるなりして順次ストリームで実行すれば正しい結果になりました。（遅くなっているのはさておき…）

```
--------------------
カプレカ数 定義2
0
495
6174
549945
631764
63317664
97508421
554999445
処理時間(ms): 75049
--------------------
```

## 排他制御を行なっていないこと
上記の続きで、フィールドの読み書きの部分で排他制御をすれば正しい結果にはなります。

```java
.filter(n -> {
    synchronized(myNum) {
        myNum.setNum(n);
        return myNum.isKaprekarNumber2();    
    }
})
```

下記が実行結果です。

```
--------------------
カプレカ数 定義2
0
495
6174
549945
631764
63317664
97508421
554999445
処理時間(ms): 90823
--------------------
```

出力結果は正しいのですが、元の実装より1.5倍も遅いです。排他制御することで実質的に単一スレッドでの実行になる（+ 並列実行のオーバーヘッドがある）ためです。これでは何のための並列ストリームかわかりませんね。

# まとめ
並列ストリームをうまく使えば、性能を大幅に上げることが期待できます。しかし、効果を得るための条件も多いので注意して使いましょう。

# 余談
下記の部分について、

```java
// max
chars.sort(Comparator.reverseOrder());
```

本当は下記のほうが速いようです。（この時点で `chars` は昇順ソート済み）

```java
// max
Collections.reverse(chars);
```

しかし、
修正が面倒だし
 本題にはあまり影響しないためそのままにしています。
# 余談その２
性能が高いと評判のM1版MacBook Proを買ったので、どんなものかこちらの記事の例で試してみました。

## 動作環境
* macOS Big Sur
* Apple M1（8コア）
* JDK13

## 測定結果
以下のようになりました。Intel版は再測定はしておらず、再掲です。

|       |順次ストリーム |並列ストリーム|
|---    |---        |---       |
|Intel  |60284ms    |22366ms   |
|M1     |44251ms    |11351ms   |

順当に速くなっているかなと思いました。特に並列ストリームの場合に至ってはほぼ倍の性能です。
もちろんハードの劣化もあるし、OSやらJDKのディストリビューションやらも違うので直接的に比較できるものかわかりませんが、ここまで大きな差であればやはりCPUの性能差が要因ではないかと思いました。

M1版のほうが並列ストリームの効果が特に大きいように見える点は気になりますが、まああくまでも余談ということでここまでにしておきます。