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

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

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

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

ということになる。

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

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

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には糖衣構文が用意されたので、もっと便利に書けるかもしれない。