RubyでCPUコアをフル活用してみた

2008年から食べログでプログラマをしているし今でもプログラマをしているおおいしつかさです。
なんで名前がひらがななのかというと、ネットで活動していることが珍しかった時代に会社の人に活動がばれないようにするためでした。ぼくは1995年に「つかさの部屋」というホームページを持っていた黒歴史を持っています。すごくないですか？会社の人にばれたら超まずいでしょう？意味もなく猫の絵文字を入れてみました。ちょっとふざけてみました。だんだん読む気がなくなってきたのでは？

RubyでCPUコアをフルに活用する

Rubyでスレッドプログラミングをしても、CPUのコアを生かすことはできません。
RubyはGiant VM lock(GVL)によって、同時に実行されるスレッドはいつもひとつだけにされているからです。
I/O待ちの場合はGVLは解放されるので複数のスレッドが同時に動くことが可能になります。複数のURLを叩いてデータを取ってくるときなどは有効に働くでしょう。

数値計算を行うような場合はそうはいきません。
たとえば512x512の行列ふたつの積を計算するとしましょう。

# 512x512の行列をふたつ作る
def build(num, max)
  m = []

  num.times do |i|
    m[i] = []
    num.times do |j|
      m[i][j] = rand(max)
    end
  end

  m
end

num = 512
max = 256

a = build(num, max)
b = build(num, max)

このふたつの行列、aとbの積を計算します。素直に考えるとループが3重に必要になるので計算量は$O(n^{3})$になります。

def m_and(a, b, num)
  m = []

  num.times do |i|
    m[i] = []
    num.times do |j|
      m[i][j] = 0

      num.times do |k|
        m[i][j] += a[i][k] * b[k][j]
      end
    end
  end

  m
end

処理時間を計ってみます。

require 'benchmark'
puts Benchmark.realtime { m_and(a, b, num) }

18.133936062455177

18秒ほどかかりました。実行したマシンではCPUのコアが4つあります。処理中のCPU使用率を見てみます。

CPU     %user     %nice   %system   %iowait    %steal     %idle
all     25.00      0.00      0.25      0.00      0.00     74.75
  0      0.00      0.00      0.00      0.00      0.00    100.00
  1      0.00      0.00      1.00      0.00      0.00     99.00
  2    100.00      0.00      0.00      0.00      0.00      0.00
  3      0.00      0.00      0.00      0.00      0.00    100.00

ひとつのコアだけががんばっている状態です。

マルチスレッドで処理をする

マルチスレッドで処理をしてみます。ひとつの行x列の計算は並列に独立して行うことができるので、その単位でデータを分割してそれぞれのスレッドに処理をさせてみましょう。

def t_m_and(a, b, num, t_size)
  m = []
  queue = Queue.new
  threads = []

  num.times do |i|
    m[i] = []
    num.times do |j|
      m[i][j] = 0
      queue.push([i, j])
    end
  end

  t_size.times do
    threads << Thread.new(queue) do |q|
      until q.empty?
        begin
          ti, tj = q.pop(true)
          num.times do |k|
            m[ti][tj] += a[ti][k] * b[k][tj]
          end
        rescue ThreadError
          raise unless q.empty?
        end
      end
    end
  end
  threads.each(&:join)

  m
end

CPUコアは4つなのでスレッド数4で実行します。

puts Benchmark.realtime { t_m_and(a, b, num, 4) }

18.22166531533003

こちらも18秒ほどかかりました。実行中のCPU使用率は以下のようになっていました。

CPU     %user     %nice   %system   %iowait    %steal     %idle
all     25.06      0.00      0.00      0.00      0.00     74.94
  0     29.70      0.00      0.99      0.00      0.00     69.31
  1     28.00      0.00      0.00      0.00      0.00     72.00
  2     22.00      0.00      0.00      0.00      0.00     78.00
  3     20.20      0.00      0.00      0.00      0.00     79.80

全部のコアをちゃんと使っていますが、同時に動けるスレッドはひとつだけのため、トータルの時間はシーケンシャルに処理したときと変わりません。
これをなんとかして全コアをフル活用できるようにしようと思います。

C拡張ライブラリで書く

GVLを解放すれば同時に複数のスレッドを動かせるようになります。今回の行列計算はお互いのスレッドの処理は影響し合わないはずなので、GVLを解放しても問題ないと期待できます。
GVLを解放するためにはCで拡張ライブラリを書く必要があるので、まずはC言語で行列の積の処理を書きます。

static VALUE
and(VALUE self, VALUE a, VALUE b, VALUE num)
{
  long *ma, *mb, *mc;
  long n;
  VALUE result;

  n = NUM2LONG(num);
  ma = ary_to_cary(a, n);
  mb = ary_to_cary(b, n);

  mc = and_matrix(ma, mb, n);
  result = cary_to_ary(mc, n);

  ruby_xfree(ma);
  ruby_xfree(mb);
  ruby_xfree(mc);

  return result;
}

void
Init_fullcore_matrix(void)
{
  VALUE cFullcoreMatrix = rb_define_class("FullcoreMatrix", rb_cObject);

  rb_define_method(cFullcoreMatrix, "m_and", and, 3);
}

扱いやすいように、二次元配列を一次元配列に変換しています。ary_to_caryでrubyのArrayをcのlong*に変換しています(標準の関数ではありません。これ用に書いたものです。載せてませんけど)。
and_matrix関数は以下のようにしました。

static long *
and_matrix(long *a, long *b, long num)
{
  long *m;
  long i, j, k;
  long index;

  m = (long*)ruby_xmalloc(sizeof(long) * num * num);

  for(i = 0; i < num; i++) {
    for(j = 0; j < num; j++) {
      index = i * num + j;
      m[index] = 0;
      for(k = 0; k < num; k++) {
        m[index] += a[i * num + k] * b[k * num + j];
      }
    }
  }

  return m;
}

これを実行してみます。

fm = FullcoreMatrix.new 
puts Benchmark.realtime { fm.m_and(a, b, num) }

0.39124061167240143

圧倒的な速さです! 18秒かかっていた処理が391ミリ秒になりました。

CPU使用率は以下のとおり、ひとつのコアだけが頑張っています。

CPU     %user     %nice   %system   %iowait    %steal     %idle
all     25.00      0.00      0.25      0.00      0.00     74.75
  0      0.00      0.00      1.00      0.00      0.00     99.00
  1      0.00      0.00      0.00      0.00      0.00    100.00
  2    100.00      0.00      0.00      0.00      0.00      0.00
  3      0.00      0.00      0.00      0.00      0.00    100.00

このコードを元にマルチスレッド処理に書き直します。

マルチスレッド処理にする

面倒くさいのでOpenMPでさくっと処理を書きます。

static long *
and_matrix(long *a, long *b, long num)
{
  long *m;
  long i, j, k;
  long index;

  m = (long*)ruby_xmalloc(sizeof(long) * num * num);

  #pragma omp parallel for private(j, k, index)
  for(i = 0; i < num; i++) {
    for(j = 0; j < num; j++) {
      index = i * num + j;
      m[index] = 0;
      for(k = 0; k < num; k++) {
        m[index] += a[i * num + k] * b[k * num + j];
      }
    }
  }

  return m;
}

実行してみると、

0.13279788196086884

あれ、GVL解放してないのに速くなりました。RubyのThreadを介していないからですね。4分の1に近い値になっていることを考えると、ちゃんと4つのコアを有効に使っているようです。
速すぎてsarでちゃんと計測できないので、2048x2048の行列で計算してみます。

10.213115755468607

さすがに10秒かかります。CPU使用率は以下のとおり。

CPU     %user     %nice   %system   %iowait    %steal     %idle
all     99.50      0.00      0.50      0.00      0.00      0.00
  0    100.00      0.00      0.00      0.00      0.00      0.00
  1    100.00      0.00      0.00      0.00      0.00      0.00
  2    100.00      0.00      0.00      0.00      0.00      0.00
  3    100.00      0.00      0.00      0.00      0.00      0.00

全コアをフル活用するようになりました。

Rubyで全コアをフル活用しているんじゃなくて、ただCでスレッドプログラミングを書いただけのようにも思えますが、夢でも見ているのでしょうか。
なんとなく負けた気がするので、RubyのThreadを使った上で全コアをフル活用してみます。当初の予定通り、GVLを解放してみます。

GVL解放用のC拡張ライブラリを書く

GVLを解放するためにはC拡張ライブラリで書く必要があるのですが、さらにつけくわえるとGVLを解放中はRubyの関数に触ってはいけません。
このため、C拡張ライブラリのインスタンス内に、long*に変換したふたつの行列を持っておいて、ひとつの列xひとつの行計算を行うメソッドを提供します。RubyのThread処理内でこのメソッドを呼ぶイメージです。

typedef struct _matrix {
  long *a;
  long *b;
  long num;
} *matrix;

struct and_data {
  matrix m;
  long i;
  long j;
  long result;
};

...

static VALUE
and(VALUE self, VALUE i, VALUE j)
{
  matrix m;
  struct and_data data;

  Data_Get_Struct(self, struct _matrix, m);
  data.m = m;
  data.i = NUM2LONG(i);
  data.j = NUM2LONG(j);

  and_matrix(&data);

  return LONG2NUM(data.result);
}

static VALUE
new(VALUE klass, VALUE a, VALUE b, VALUE num)
{
  matrix m;
  VALUE obj;

  obj = Data_Make_Struct(klass, struct _matrix, NULL, destroy_matix, m);

  m->num = NUM2LONG(num);
  m->a = ary_to_cary(a, m->num);
  m->b = ary_to_cary(b, m->num);

  return obj;
}

void
Init_nonblock_matrix(void)
{
  VALUE cNBMatrix = rb_define_class("NonblockMatrix", rb_cObject);

  rb_define_singleton_method(cNBMatrix, "new", new, 3);
  rb_define_method(cNBMatrix, "m_and", and, 2);
}

destroy_matix関数とかは省略しています(ruby_xfree呼ぶだけです)。

and_matrix関数は以下の通りです。

static void *
and_matrix(void *data)
{
  long i, j, num, k, result;
  long *a, *b;
  struct and_data *d;

  d = (struct and_data*)data;

  num = d->m->num;
  a = d->m->a;
  b = d->m->b;
  i = d->i;
  j = d->j;

  result = 0;
  for(k = 0; k < num; k++) {
    result += a[i * num + k] * b[k * num + j];
  }

  d->result = result;

  return NULL;
}

and_matrixがvoid*で引数を受け取ってvoid*で値を返しているのは、のちほどGVL解放処理を入れやすくするためです。

Rubyで書いたスレッド処理のコードで、このライブラリを利用します。

require './nonblock_matrix'
def t_m_and2(a, b, num, t_size)
  m = []
  queue = Queue.new
  threads = []
  nb = NonblockMatrix.new(a, b, num) # C拡張ライブラリを使う

  num.times do |i|
    m[i] = []
    num.times do |j|
      queue.push([i, j])
    end
  end

  t_size.times do
    threads << Thread.new(queue) do |q|
      until q.empty?
        begin
          ti, tj = q.pop(true)
          m[ti][tj] = nb.m_and(ti, tj) # C拡張ライブラリ内で実装したひとつの列xひとつの行の計算処理
        rescue ThreadError
          raise unless q.empty?
        end
      end
    end
  end
  threads.each(&:join)

  m
end

実行してみます。

0.48769768700003624

488ミリ秒です! ここの処理をCにしただけでも相当に速くなりました。全処理をCで書いたときに匹敵する速さです。
当然ですが、スレッドはひとつずつ動くのでCPU使用率は以下のような状態です。

CPU     %user     %nice   %system   %iowait    %steal     %idle
all     25.00      0.00      0.25      0.00      0.00     74.75
  0     26.00      0.00      1.00      0.00      0.00     73.00
  1     20.00      0.00      0.00      0.00      0.00     80.00
  2     30.00      0.00      0.00      0.00      0.00     70.00
  3     23.23      0.00      0.00      0.00      0.00     76.77

GVL解放!

いよいよ、GVLを解放します。
C拡張ライブラリ内で実装した、and_matrix 関数をGVLを解放した上でコールします。
GVLを解放して関数を呼ぶには、rb_thread_call_without_gvl関数を使います。

rb_thread_call_without_gvl(and_matrix, &data, RUBY_UBF_PROCESS, NULL);

rb_thread_call_without_gvl関数で指定する関数は、void*で引数を受け取ってvoid*で値を返す必要があります。and_matrixはこれ用にインターフェースを定義していたので簡単ですね。

実行してみます。

1.4591152295470238

あれ、遅くなってしまいました。

CPU使用率を見てみます。

CPU     %user     %nice   %system   %iowait    %steal     %idle
all     56.11      0.00     10.28      0.00      0.00     33.61
  0     60.44      0.00     14.29      0.00      0.00     25.27
  1     61.80      0.00      8.99      0.00      0.00     29.21
  2     42.86      0.00      9.89      0.00      0.00     47.25
  3     58.43      0.00      7.87      0.00      0.00     33.71

CPUコアをフル活用とまではいきませんでしたが、60%を超えることはできました。
しかしCPUのリソースを使っているのに遅くなっているので、何か無駄なことをたくさんしているようです。systemの値が跳ね上がっていますね。

rubyのthread.cに以下のようなコメントがありました。

 NOTE: Releasing GVL and re-acquiring GVL may be expensive operations
       for a short running `func()'. Be sure to benchmark and use this
       mechanism when `func()' consumes enough time.

今回のようにすぐに終わる関数を何度も呼ぶとコストのほうが高くなるようです。

おしまい

ちなみに最初のrubyのコードで2048x2048の行列を計算したら1467秒かかりました。

明日の記事は @maguhiro さんの「MS Teamsへのメッセージ送信用Bitrise Stepを作ってみた」です。