55700


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

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

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

[code]

    ## 配列同士の乗算を行い，その配列を返す
    # 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
    
[/code]


CC BY-SA 4.0
2019-06-10T11:06:31.837
55676
2019-06-11T11:27:28.017
2019-06-11T03:53:15.900
30173
30173
question
ruby
配列同士の乗算をなるべく高速に行う方法を教えてください


回答ではありませんが、[Benchmark.realtime](https://docs.ruby-
lang.org/ja/2.5.0/class/Benchmark.html#M_REALTIME) を使用して、参考までに実行時間を計測してみました。

[code]

    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
    
[/code]

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

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

> Threads  
>  Speedup for blocking operations

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

[Ruby 2.5.0 リファレンスマニュアル > スレッド](https://docs.ruby-
lang.org/ja/2.5.0/doc/spec=2fthread.html)

> ネイティブスレッドを用いて実装されていますが、現在の実装では 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 change** と **Extra memory used** の部分ですが、fork
and exec されるプロセス内で参照される外側のスコープのオブジェクトがプロセス空間にコピーされる事を意味しています。今回のベンチマークでは以下の、

[code]

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

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

[code]

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

を

[code]

    c.collect{|j| j * 2}
    
[/code]

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

**実行環境**

[code]

    $ 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
    
[/code]

**Ruby script to measure execution time**

[code]

    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 s\n", i+1, p[:tag], Benchmark.realtime{p[:proc].call})
    }
    
[/code]


CC BY-SA 4.0
2019-06-11T11:04:45.017
55700
2019-06-11T11:04:45.017
55676
answer


まず、マルチスレッドは無意味です。GVLがあるため、マルチコア環境でもコアは一つ分の計算しかされません。スレッド切り替えがあるため、むしろ遅くなります。

かといってマルチフォークは微妙です。計算対象が大量にある場合、コア数分だけ区切りを付けて走らせれば意味がありそうですが、一つあたりの計算量が少ない場合はプロセス間のやり取りを行う処理の方が負荷が高く、良い結果は得られないでしょう。

ということで、シングルスレッドのまま高速化を考えました。

まずは、ループを回すは`upto`やRangeを使う、配列は`map`で作る、むしろ`zip`を使って添字アクセスをなくすというものです。後述のベンチマークの結果を言うと、ちょっと遅いぐらいと言う結果でした。コードがRubyらしくなるというメリットしかえられないでしょう。

次に標準添付の[matrix](https://docs.ruby-
lang.org/ja/latest/library/matrix.html)ライブラリを使うことです。[Matrix#entrywise_product](https://docs.ruby-
lang.org/ja/latest/method/Matrix/i/entrywise_product.html)というメソッドが用意されていますので、これをそのまま使えば良さそうです。が、ベンチマークでは速さが半分になってしまいました。

最後の本命は[Numo::Narray](https://github.com/ruby-numo/numo-
narray)です。Pythonでいうnumpyのようなライブラリです。

これらについてベンチマークを取ってみましょう。実行前に、`gem install benchmark-ips numo-
narray`としてライブラリは入れといてください。(純粋な速度比較のために、オリジナルからは最初のサイズチェックは削除しています。)

[code]

    # frozen_string_literal: true
    
    require 'benchmark/ips'
    require 'matrix'
    require 'numo/narray'
    
    ## 配列同士の乗算を行い，その配列を返す
    # arr1 * arr2
    def twoArrayMultiplication(arr1, arr2)
      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
    
    def multi_upto(a, b)
      size = a.size
      result = Array.new(size, nil)
      0.upto(size - 1) do |i|
        result[i] = a[i] * b[i]
      end
      result
    end
    
    def multi_upto_map(a, b)
      0.upto(a.size - 1).map { |i| a[i] * b[i] }
    end
    
    def multi_range_map(a, b)
      (0...a.size).map { |i| a[i] * b[i] }
    end
    
    def multi_zip_map(a, b)
      a.zip(b).map! { |x, y| x * y }
    end
    
    def multi_matrx(a, b)
      Matrix.row_vector(a).entrywise_product(Matrix.row_vector(b)).to_a.first
    end
    
    def multi_narray(a, b)
      (Numo::DComplex[*a].inplace * Numo::DComplex[*b]).to_a
    end
    
    if $0 == __FILE__
    
      size = 10000
    
      a = (0..size).map { rand((-1.0)...1.0) + rand((-1.0)...1.0) * 1i }
      b = (0..size).map { rand((-1.0)...1.0) + rand((-1.0)...1.0) * 1i }
    
      # check
      answer = twoArrayMultiplication(a, b)
      pp answer == multi_upto(a, b)
      pp answer == multi_upto_map(a, b)
      pp answer == multi_range_map(a, b)
      pp answer == multi_zip_map(a, b)
      pp answer == multi_matrx(a, b)
      pp answer == multi_narray(a, b)
    
      Benchmark.ips do |x|
        x.report('original:') { twoArrayMultiplication(a, b) }
        x.report('upto:') { multi_upto(a, b) }
        x.report('upto map:') { multi_upto_map(a, b) }
        x.report('range map:') { multi_range_map(a, b) }
        x.report('zip map:') { multi_zip_map(a, b) }
        x.report('matrix:') { multi_matrx(a, b) }
        x.report('narray:') { multi_narray(a, b) }
        x.compare!
      end
    end
    
[/code]

私の手元(Ruby
2.6.3)ではオリジナルが一番速かったです。仕組み上は、Numo::Narrayの方が速いはずなのですが、そうにはなりません。どうやら、Numo::DComplexをArrayに変換するところが遅いようです。最初に作成する配列を小さくするとその違いはより顕著になります。

もし、Numo::Narrayのみを用いて、Numo::Narrayのまま計算を行っていけば、それが一番速いでしょう。しかし、Arrayとの相互変換が随所にあると、そこがネックになる可能性があります。


CC BY-SA 4.0
2019-06-11T11:27:28.017
55701
2019-06-11T11:27:28.017
7347
55676
answer