K.Sasada's Home Page

Ruby の高速化の道。

ボスから、 http://kokizzu.blogspot.jp/2015/02/c-java-hhvm-ruby-nodejsrhinojscspidermo.html をぱっと見せられて、「メモリを減らしたい」と言われる。いわゆる業務命令というやつだ。

今回考えるプログラムをこのページから引用する。

##############################
# scomb.rb
def newGap gap
    gap /= 1.3;
    gap = gap.to_i;
    return 11 if gap == 9 or gap == 10
    return 1 if gap < 1
    gap
end
def combSort a
    len = a.length
    gap = len
    swapped = false
    begin
        swapped = false
        gap = newGap gap
        (0...(len-gap)).each do |i|
            if a[i] > a[i+gap]
                swapped = true
                a[i], a[i+gap] = a[i+gap], a[i]
            end
        end
    end while gap > 1 or swapped
end
N = 10000000;
arr = N.times.map{|x| (N-x).to_s }
combSort arr
(1...N).each{ |z| print '!' if arr[z]<arr[z-1] }

比較的簡単だ。実行結果も引用する。

$ ruby --version
ruby 2.2.0p0 (2014-12-25 revision 49005) [x86_64-linux]
$ time ruby scomb.rb
CPU: 114.67s    Real: 115.21s   RAM: 870612KB

これを、手元の環境でも同じように測ってみる（手元では trunk が動いている。ちなみに、Windows 上の VirtualBox 上の Ubuntu）。

CPU: 108.87s    Real: 109.11s   RAM: 860996KB

まぁ、ほぼ同じようなものだ。

さて、現状認識から始めよう。

まず、最後の行のほうで、10000000 = 10_000_000 = 10M 個の配列を作っている。64bit CPU 上で動いているので、必要なメモリ量を試算すると、

• 10M 個の要素の配列 = 1 エントリ 8 byte（ポインタサイズ）* 10M エントリ = 80 MB
• 各要素には短い文字列 = 40 byte（RVALUE のサイズ） が 10 M 個 = 400 MB

併せて、だいたい 500MB が必要なところだろう。あと、Ruby の GC の戦略は、10M 個確保されていたら、1.8 倍くらいは作れるようになっているので、10 M * 1.8 = 18 M 個の RVALUE が用意されていると思う。なんで、8M 個の RVALUE = 8M * 40B = 320 MB くらい、余分に確保されて、これらを足し合わせると、400 MB + 80 MB + 320 MB = 800 MB ということで、RAM: 860996KB ってのは、まぁまぁ納得いく数であろう。

さて、GC チューニングでなんとかなるだろうか。まず、1.8 倍確保するからしんどいのであって、これを 1.2 倍くらいにおさえるとどうだろう。RUBY_GC_HEAP_GROWTH_FACTOR では、メモリが足りない時、1.8 倍じゃなくて、別の倍率にするための仕組みなので、これを 1.2 倍程度にしてみるとどうだろうか。

$ RUBY_GC_HEAP_GROWTH_FACTOR=1.2 /usr/bin/time -f "\nCPU: %Us\tReal: %es\tRAM: %MKB" ./miniruby -I../../trunk/lib -I. -I.ext/common   ../../trunk/test.rb

CPU: 108.32s    Real: 108.49s   RAM: 745388KB

しめしめ。メモリ消費が減った。でも、あんまり減ってないですね。

そもそも、このプログラムでどこがメモリを食うのだろう？　combSort(arr) の中を見ても、とくにメモリを食いそうなところは無いんですよね。試しに、combSort(arr) を呼ばずに実行するとどうなるか見てみよう。

CPU: 3.09s      Real: 3.16s     RAM: 527452KB

さっき計算した、500MB というのが出てきた。ということは、やはり combSort(arr) の中でメモリを消費しているらしい。でも、どこでオブジェクトを作っているんだろう？

というときに、https://github.com/ko1/allocation_tracer gem を使う。

##############################
# scomb.rb
def newGap gap
    gap /= 1.3;
    gap = gap.to_i;
    return 11 if gap == 9 or gap == 10
    return 1 if gap < 1
    gap
end
def combSort a
    len = a.length
    gap = len
    swapped = false
    begin
        swapped = false
        gap = newGap gap
        (0...(len-gap)).each do |i|
            if a[i] > a[i+gap]
                swapped = true
                a[i], a[i+gap] = a[i+gap], a[i]
            end
        end
    end while gap > 1 or swapped
end

require 'allocation_tracer'
require 'pp'

pp ObjectSpace::AllocationTracer.trace{
  N = 1000#0000;
  arr = N.times.map{|x| (N-x).to_s }
  combSort arr
  (1...N).each{ |z| print '!' if arr[z]<arr[z-1] }
}

こんな感じで使う。ObjectSpace::AllocationTracer.trace で囲っただけ。ちなみに、傾向を見たいだけだから、10M 個じゃなくて 1K 個にしておく。そうすると、

{["../../trunk/test.rb", 31]=>[1004, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 17]=>[24, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 20]=>[2546, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 33]=>[1, 0, 0, 0, 0, 0]}

こんな結果が得られる。

これは、["../../trunk/test.rb", 31] という場所で、[1004, 0, 0, 0, 0, 0] こんな結果が出た、という意味だけど、ちょっと細かい情報が多くてわかりづらいと思う。

• 最初のカラムは 1004 個のオブジェクトがこの行で生成されたということ
• 2つめは 0 個の旧世代のオブジェクトが生成されたということ
• 3つめは、全部の年齢を数えたら 0 だったということ
• 4つめは、最小の年齢が 0 だったということ
• 5つめは、最大の年齢が 0 だったということ（つまり、2〜5つ目を見ると、すぐに死ぬオブジェクトばっかり作りやがって、ってことがわかる）
• 6つめは、RVALUE 以外で消費したメモリ消費量（のヒント。死んだときに数える）

ということを意味しているんだけど、まぁ最初のカラム（生成数）だけ見ていればいいと思う。

31 行目は配列を map で作っているから 1004 個のオブジェクトが出来ているけれど、次に多いのが 20 行目の 2546 個生成されたオブジェクト。具体的には "a[i], a[i+gap] = a[i+gap], a[i]" これ。一体何が出来ているのか？

より詳しく知るためには、こんな風に使う。

ObjectSpace::AllocationTracer.setup(%i{path line type})
pp ObjectSpace::AllocationTracer.trace{
  ...
}

これで、type ごとに統計を取るようになる。結果は、こんなふうになった。

{["../../trunk/test.rb", 31, :T_DATA]=>[1, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 31, :T_ARRAY]=>[1, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 31, :T_NODE]=>[2, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 31, :T_STRING]=>[1000, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 17, :T_STRUCT]=>[24, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 20, :T_ARRAY]=>[2546, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 33, :T_STRUCT]=>[1, 0, 0, 0, 0, 0]}

20行目は T_ARRAY、つまり配列がガンガン出来ている、ということがわかる。はて、なんで配列？

実は、Ruby の多重代入は、配列を返す。何を言っているのかわからないのと思うので、具体例を出す。

x = (a, b = 1, 2)
p x #=> [1, 2]

x は、(a, b = 1, 2) という式の値を参照している。allocation_tracer を使ってみれば、明らかだ。

require 'allocation_tracer'
require 'pp'
ObjectSpace::AllocationTracer.setup(%i{path line type})
pp ObjectSpace::AllocationTracer.trace{
  a, b = 1, 2
}

これを実行すると：

{["../../trunk/test.rb", 5, :T_ARRAY]=>[1, 0, 0, 0, 0, 0]}

こうじゃ。5行目、つまり "a, b = 1, 2" で T_ARRAY のオブジェクトが 1 つ生成されていることがわかる。

この生成された [1, 2] というオブジェクトなんてつかわねーよ！　と思うかもしれないし、過去の私もそう思ったので、使わないことが明らかな場合、つまり、この値を捨てていることが明らかであるとき、配列を生成しないようにしている。

require 'allocation_tracer'
require 'pp'
ObjectSpace::AllocationTracer.setup(%i{path line type})
pp ObjectSpace::AllocationTracer.trace{
  a, b = 1, 2
  nil
}

の結果は、

{}

つまり、何のオブジェクトも生成されていないことがわかる。

以前のプログラムでは、多重代入の値が、それをくるむブロックの値として返されており、そこで必要かもしれないから、丁寧に配列を返す。しかし、nil を返すことを明示することで、配列を生成しないようになったということである。

よしわかった、nil を入れればいいんだな、ということで、入れてみたら

##############################
# scomb.rb
def newGap gap
    gap /= 1.3;
    gap = gap.to_i;
    return 11 if gap == 9 or gap == 10
    return 1 if gap < 1
    gap
end
def combSort a
    len = a.length
    gap = len
    swapped = false
    begin
        swapped = false
        gap = newGap gap
        (0...(len-gap)).each do |i|
            if a[i] > a[i+gap]
                swapped = true
                a[i], a[i+gap] = a[i+gap], a[i]
                nil                               # ここに nil を入れてみた
            end
        end
    end while gap > 1 or swapped
end

require 'allocation_tracer'
require 'pp'
ObjectSpace::AllocationTracer.setup(%i{path line type})
pp ObjectSpace::AllocationTracer.trace{
  N = 1000#0000;
  arr = N.times.map{|x| (N-x).to_s }
  combSort arr
  (1...N).each{ |z| print '!' if arr[z]<arr[z-1] }
}

しかしやっぱり

{["../../trunk/test.rb", 32, :T_DATA]=>[1, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 32, :T_ARRAY]=>[1, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 32, :T_NODE]=>[2, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 32, :T_STRING]=>[1000, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 17, :T_STRUCT]=>[24, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 20, :T_ARRAY]=>[2546, 0, 0, 0, 0, 0],   <-- これ
 ["../../trunk/test.rb", 34, :T_STRUCT]=>[1, 0, 0, 0, 0, 0]}

配列は生成される。はてな？

実は、a[x], a[y] = 1, 2 のような（左辺値にメソッド呼び出しなんかがある）多重代入では、真面目に配列を作っている。というのも、副作用の恐れがあるため、実行順序を適切に並べるため、具体的にはこの例だと、a[x] = 1, a[y] = 2 と順番に実行するためである。

逆に、そうじゃなくても良い場合を考える。

a, b = 1, 2

このとき、Rubyのスタックマシンの VM はこんなふうに実行する。

push 1
push 2
set b # スタックトップの 2 を pop して b にセット
set a # スタックトップの 1 を pop して a にセット

このとき、設定順は b, a の順である。しかし、a[x], a[y] には副作用がある可能性がある。例えば、設定されたときにログを出力するかもしれない。なのでさっきと同じように、

push 1
push 2
set a[y]
set a[x]

とすることはできない。なので、どうしているかというと、1度配列を作って、

push 1
push 2
newarray 2 # [1, 2] を作る
expandarray 2 # スタックに配列を逆順に展開 2, 1 と置かれる
set a[x] # a[x] = 1 をする
set a[y] # a[y] = 2 をする

というふうに実装されている、というわけである。

さて、ここまでわかると、多重代入を使うからダメ、ってことがわかるので、これを分解してみる。

##############################
# scomb.rb
def newGap gap
    gap /= 1.3;
    gap = gap.to_i;
    return 11 if gap == 9 or gap == 10
    return 1 if gap < 1
    gap
end
def combSort a
    len = a.length
    gap = len
    swapped = false
    begin
        swapped = false
        gap = newGap gap
        (0...(len-gap)).each do |i|
            if a[i] > a[i+gap]
                swapped = true
                x, y = a[i+gap], a[i] # ここをかっこ悪く変更した
                a[i] = x
                a[i+gap] = y
                nil
            end
        end
    end while gap > 1 or swapped
end

require 'allocation_tracer'
require 'pp'
ObjectSpace::AllocationTracer.setup(%i{path line type})
pp ObjectSpace::AllocationTracer.trace{
  N = 1000#0000;
  arr = N.times.map{|x| (N-x).to_s }
  combSort arr
  (1...N).each{ |z| print '!' if arr[z]<arr[z-1] }
}

が、

{["../../trunk/test.rb", 34, :T_DATA]=>[1, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 34, :T_ARRAY]=>[1, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 34, :T_NODE]=>[2, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 34, :T_STRING]=>[1000, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 17, :T_STRUCT]=>[24, 0, 0, 0, 0, 0],
 ["../../trunk/test.rb", 36, :T_STRUCT]=>[1, 0, 0, 0, 0, 0]}

こうなって、見事に配列が無くなったことがわかる。

さて、ではこれを、元々のお題である 10M 個で実行してみる。

$ /usr/bin/time -f "\nCPU: %Us\tReal: %es\tRAM: %MKB" ./miniruby -I../../trunk/lib -I. -I.ext/common   ../../trunk/test.rb

CPU: 102.89s    Real: 103.14s   RAM: 527712KB

見事、理想的なメモリ使用量になったのでした。

（続くかもしれない）