配列同士の乗算をなるべく高速に行う方法を教えてください

投稿者: Anonymous

Ruby勉強中の者です.
実数,複素数の2つの配列の乗算がなるべく高速できる方法が知りたいです.

どなたかご教授お願い致します.

現在のコードを以下に示します.

## 配列同士の乗算を行い,その配列を返す
# arr1 * arr2
def twoArrayMultiplication(arr1, arr2)
  # assert的な
  if arr1.length != arr2.length
    puts "2つの配列 arr1 と arr2 の配列のサイズが異なります"
    exit!
  end

  i = 0
  size = arr1.length
  result = Array.new(size, nil)
  while i < size                  # 以降のループを高速化したい
    result[i] = arr1[i] * arr2[i]
    i += 1
  end

  return result
end

解決

回答ではありませんが、Benchmark.realtime を使用して、参考までに実行時間を計測してみました。

1. map after zip            :  9.002 s
2. map with index           :  7.408 s
3. times and collect        :  5.977 s
4. for loop                 :  6.313 s
5. while loop               :  5.825 s
6. parallel(multi threads)  :  7.395 s
7. parallel(multi processes): 22.538 s

※ 実際に使用したスクリプトは最後に記載しています

マルチスレッド・マルチプロセス版では parallel gem(parallel processing made simple and fast) を利用しています。Readme.md にも記載されていますが、

Threads
Speedup for blocking operations

なので、今回の様に乗算だけの場合、マルチスレッド版では実行時間の短縮は見られません。

Ruby 2.5.0 リファレンスマニュアル > スレッド

ネイティブスレッドを用いて実装されていますが、現在の実装では Ruby VM は Giant VM lock(GVL)を有しており、同時に実行されるネイティブスレッドは常にひとつです。ただし、IO 関連のブロックする可能性があるシステムコールを行う場合には GVL を解放します。その場合にはスレッドは同時に実行され得ます。また拡張ライブラリから GVL を操作できるので、複数のスレッドを同時に実行するような拡張ライブラリは作成可能です。

次に、マルチプロセス版は以下の様に説明されています。

Processes

Speedup through multiple CPUs
Speedup for blocking operations
Variables are protected from change
Extra memory used

この Variables are protected from changeExtra memory used の部分ですが、fork and exec されるプロセス内で参照される外側のスコープのオブジェクトがプロセス空間にコピーされる事を意味しています。今回のベンチマークでは以下の、

results = Parallel.map(chunk, in_processes: np){|c|
  c.collect{|j| x[j] * y[j]}
}

配列 x, y がそれぞれのプロセス空間にコピーされる事になります。つまり、要素数 1e+7 の配列オブジェクト2個がプロセス数(np)分コピーされますので、メモリ使用量が莫大でコピーコストも高いものになります。そこで例えば、

c.collect{|j| x[j] * y[j]}

c.collect{|j| j * 2}

に変更してみると、実行時間は 1/9 程度になります(意味のない計算ですが…)。

実行環境

$ grep 'model name' /proc/cpuinfo | uniq
model name  : Intel(R) Core(TM) i5-8500T CPU @ 2.10GHz
$ nproc
6
$ lsb_release -d
Description:    Ubuntu 19.04
$ uname -srm
Linux 5.0.0-16-generic x86_64

Ruby script to measure execution time

require 'benchmark'
require 'parallel'

n = 10_000_000 ## 1e+7
range = 0.1..100.0

r = Random.new
x = n.times.map { r.rand(range) }
y = n.times.map { Complex(r.rand(range), r.rand(range)) }

## Procedures
procs = [
  {
     tag: 'map after zip',
    proc: Proc.new{ x.zip(y).map{|x, y| x * y} }
  },
  {
     tag: 'map with index',
    proc: Proc.new{ x.map.with_index{|a, i| a * y[i]} }
  },
  {
     tag: 'times and collect',
    proc: Proc.new{ x.size.times.collect{|i| x[i] * y[i]} }
  },
  {
     tag: 'for loop',
    proc: Proc.new{
       arr = Array.new(x.size)
       for i in 0...x.size
         arr[i] = x[i] * y[i]
       end
    }
  },
  {
     tag: 'while loop',
    proc: Proc.new{
       arr, i = Array.new(x.size), 0
       while i < x.size
         arr[i] = x[i] * y[i]
         i += 1
       end
    }
  },
  {
     tag: 'parallel(multi threads)',
    proc: Proc.new{
       nt = 6
       results = Array.new(nt, [])
       chunk = (0...x.size).each_slice((x.size/nt.to_f).round)

       Parallel.each_with_index(chunk, in_threads: nt){|c, i|
         results[i] = c.collect{|j| x[j] * y[j]} 
       }
       results = results.flatten
     }
  },
  {
     tag: 'parallel(multi processes)',
    proc: Proc.new{
       np = 6
       n = np * 100
       chunk = (0...x.size).each_slice((x.size/n.to_f).round)

       results = Parallel.map(chunk, in_processes: np){|c|
         c.collect{|j| x[j] * y[j]}
       }
       results = results.flatten
     }
  }
]

## Execute
procs.each_with_index{|p, i|
  printf("%d. %-25s: %6.3f sn", i+1, p[:tag], Benchmark.realtime{p[:proc].call})
}
回答者: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *