Crystal高速化 WaitGroupを利用した並列処理

Crystalフォーラムで、コラッツのステップ数を計算する処理がGo言語よりも遅いため、どうすれば数値計算を高速化できるかが話題になった。そこで登場した高速化手法をChatGPTにまとめてもらった。

そのChatGPTのまとめをさらに人力で簡潔にまとめると

- 整数型の変換はなるべく避ける（全部Int64を使ってもよい）（床除算）
- Crystalの数値計算はオーバーフローのチェックに時間がかかるので不要なら省く
- ビット演算を使用する
- `--mcpu native` フラグが効く場合がある
- `WaitGroup`を使ってProducer-Consumerパターンによる並列計算ができる

ということになる。

https://forum.crystal-lang.org/t/there-is-a-way-to-optimize-this-program/6947


| 最適化手法                          | 説明                                                                                                                                                                    | Crystalのコード例                                                                                  |
|-----------------------------------|---------------------------------------------------------------------------------------------------------------------------------------------------------------------|----------------------------------------------------------------------------------------------------|
| 整数型の変換                       | `UInt32`から`Int64`への変換。これにより、Goと同じ整数型を使用し、互換性とパフォーマンスが向上。                                                                                           | `def collatz(seed : Int64)`                                                                      |
| 床除算`//`の使用                  | 通常の除算`/`を床除算`//`に変更。これにより整数の除算結果が正しく計算されるようになる。                                                                              | `seed //= 2`                                                                                      |
| オーバーフロー処理                  | `&+`, `&*=`, `&+=`を使用してオーバーフローを回避し、計算のオーバーヘッドを減少。                                                                                       | `steps &+= 1` <br> `seed = seed &* 3 &+ 1`                                                       |
| ビット操作の使用                    | `mod` や `div`演算の代わりにビットシフト演算を使用し、より高速な計算を実現。                                                                                            | `while seed.even?` <br> `steps += seed.trailing_zeros_count` <br> `seed >>= seed.trailing_zeros_count` |
| `--mcpu native` フラグの使用       | コンパイル時にCPUの命令セットに最適化されたコードを生成し、パフォーマンスを向上。                                                                                    | `crystal build --release --mcpu native file.cr`                                                  |
| 並行処理によるパフォーマンス向上 | `spawn`および`Channel`を使用して、バッチごとに並行処理を行うことで全体の処理時間を短縮。 <br> `WaitGroup` でファイバーの管理を効率化。                                                                      | 詳細なコードは下記参照。                                                                              |


### `WaitGroup` を利用した並行処理のコード例

```crystal
require "wait_group"

def collatz(seed : UInt64)
  steps = 0_u64
  while seed > 1
    tz_count = seed.trailing_zeros_count
    steps &+= tz_count
    seed >>= tz_count
    if seed > 1
      steps &+= 1
      seed = seed &* 3 &+ 1
    end
  end
  steps
end

TOTAL_SEEDS = 1_000_000_000
BATCH_SIZE = 3_125_000
batches = TOTAL_SEEDS // BATCH_SIZE
done = Channel(Nil).new(batches)
wg = WaitGroup.new(batches)

def process_results(batch_index, results)
  results.each_with_index do |steps, seed_index|
    seed = BATCH_SIZE * batch_index + seed_index + 1
    if seed.divisible_by? 1_000_000
      print "Seed #{seed.format} Steps: #{steps}\r"
    end
  end
end

start = Time.measure do
  batches.times do |batch_index|
    spawn do
      results = Slice(UInt64).new(BATCH_SIZE)
      BATCH_SIZE.times do |seed_index|
        seed = (BATCH_SIZE * batch_index + seed_index + 1).to_u64
        results[seed_index] = collatz(seed)
      end
      process_results(batch_index, results)
      wg.done
    end
  end
  wg.wait
end

puts "\ncollatz(mt) took: #{start}"
```

なお、最近WaitGroupには糖衣構文が用意されたので、もっと便利に書けるかもしれない。

https://github.com/crystal-lang/crystal/issues/14820