(5) 性能向上

この資料について

この資料では、MRI の性能向上に関するいくつかの考え方、Tips について紹介します。

性能向上とは

ソフトウェアの「性能向上」という言葉を聞くと、多くの場合「高速化」、つまりプログラムの実行時間の短縮を思い浮かべることが多いのではないでしょうか。もちろん高速化は性能向上のもっとも重要なものの一つですが、ほかにも向上するべき性能指標があり、そのどれが重要であるかはアプリケーションの特徴、利用用途によります。

性能指標について、いくつかあげてみます。思いつくままに書いているので、きっとほかにもあると思います。

時間に関する指標
- 実行時間（スループット）
- リアルタイム性（レイテンシ）
- 起動時間
計算資源に関する指標
- メモリ消費量
  - 生きているオブジェクトの数
  - 実メモリ消費量、仮想メモリ空間の広さ（e.g. TLB ミス）
  - プロセス fork 時の Copy on Write の親和性
- CPU の利用率（同じ実行時間なら、少ない利用率の方が良い）
- CPU の活用可能性（多くのCPU資源を利用することで性能改善できるかどうか）
- I/O のための fd 消費量
- ディスク利用量（バイナリサイズ等）

いくつかの性能指標は互いに相関しているものもあれば、逆相関であるものもあります。

相関している例：

メモリ消費量を減らすことでキャッシュミスが減り、スループットが向上する
オブジェクト生成を減らすことで、スループットが向上する

逆相関の例：

リアルタイム性を向上するためにリアルタイム GC を導入 → スループットは低下
ある頻出する特定の値の場合のコードを生成することで高速化 → メモリやディスクをより消費

自分が求める性能向上がどのようなものであるか意識し、またほかの指標に対してどのような影響を与えるか、それが許容範囲であるかを意識することは重要です。また、計算機環境はどんどん変化していくので、昔は有効だった性能改善手法も、今では逆効果、というものもあります。

例えば、大昔はメモリはとても重要な資源でしたが、利用可能なメモリはどんどん増えていきました。しかし、クラウド上の計算機環境を利用することになり、時間課金になると、今度はメモリ資源は貴重なものとして認識されるようになりました。

今、何が課題であるかを適切に把握することが大事です。

性能向上の考え方

まず測ろう

まず、よく言われていることですが、実装する前に、適切に計測することが必要です。

目的がスループットの改善の場合、プログラムの、どの箇所が遅いのかを見極めるのが大事です。 Ruby レベルで stackprof 等のツールを用いて適切に把握し、さらにその箇所を Linux の perf コマンドを用いて詳細に分析することで、MRI のどこを改良すれば良いかわかります。

（ちなみに、これらツールは「嘘」をつくことがあります。あくまで人間の作ったツールなので、100% 信じることはできません（だって、難しいし、デバッグしづらい分野ですから）。何か妙な結果かな、と思ったら、ツールを疑うことも必要になります。何か変な評価結果が出てきてしまった場合、疑い、解決するためには、それらのツールがどのように作られているかを知っておくことが大事です）

アルゴリズムとデータ構造

CS の基礎ですが、性能改善に一番効果があるのは、アルゴリズムを変更することです。

例えば、n 番目のフィボナッチ数を求める、よくあるプログラムを高速化してください、というお題があったとします。定義通りに書くと、このような感じでしょうか。

def fib(n)
  if n < 2
    1
  else
    fib(n-2) + fib(n-1)
  end
end

n = Integer(ARGV.shift || 35)
puts "fib(#{n}) = #{fib(n)}"

全体的な高速化のために、JIT コンパイラ（Just-in-Time コンパイラ、実行時コンパイラ）を開発する、再帰呼び出しを軽量化するために、再帰メソッド呼び出しを、単なるジャンプへ変換する、といった工夫が考えられます。が、それらの工夫では、たかだか数倍から数百倍の高速化しか見込めません（それだけ速くなればいいだろ、という話もありますが）。

もちろん、フィボナッチ数を求めるプログラムは、より高速なアルゴリズムで書き下すことができます。

def fib n
  a, b = 1, 1
  n.times{
    a, b = b, a+b
  }
  a
end

n = Integer(ARGV.shift || 35)
puts "fib(#{n}) = #{fib(n)}"

計算量でいうと、O(k^n) だったものが O(n) になりました。n によっては、数百倍などでは効かず、もっとえげつない高速化が達成できます（ちなみに、フィボナッチ数を求めるプログラムは O(log n) で実現できることが知られています）。

というわけで、まずはアルゴリズムを根本的に変更できないか、検討することが大事です。

というのが、よくある性能向上に関する議論なのですが、もうちょっとだけ。

例えば計算量が改善するアルゴリズムがあったとき、与えられた n が十分に小さければ、実はほかの計算量が多いアルゴリズムの方が効率的、ということがあります（例えば、リニアサーチとバイナリサーチ）。また、計算量が優れているアルゴリズムで実装するよりも、計算量について劣っているが、シンプルなアルゴリズムのほうが、すぐに実装できてバグが少ないプログラムになることがあります。速いかもしれないけど、バグがある（かもしれない）プログラムは、そもそも使いたくないですよね。また、実行に3秒かかるプログラム（開発に5分）と、それを改善して 0.3 秒で動くプログラム（開発に1時間）がある時、実は一度しか実行しないのであれば、圧倒的に前者を選択するべきです。

解くべき問題に応じて、執るべき手段を柔軟に選択していきましょう。

MRI のいじりどころ

高速化のために、MRI でいじるべきところを見ていきます。

組み込みクラス・メソッド
- （ほかのものも同じだが）アルゴリズムの改善を検討する。時々、面倒なので非効率（だけど簡単でバグが少ない）なアルゴリズムを使っていることがある。
- 値の特殊化を検討する。よくあるケースを速くできないか検討する。例えば、Array#[] は、小さな整数値（インデックス）を引数に取ることが多い。
標準添付ライブラリ（lib/）
- Ruby で書かれているため、不要なオブジェクト生成を抑制する、といった工夫が有効な場合がある。https://github.com/ko1/allocation_tracer こういうのを使うと便利。
オブジェクト管理、ガーベージコレクタ
- GC アルゴリズムを検討する。でも、まだやることあるかな？
- オブジェクトのメモリレイアウトを検討する。
VM
- 命令セットを検討する。
- JIT コンパイルを検討する。
- 命令置き換え、インライン化等、コンパイラによる最適化を検討する。

ほかにも色々あると思われます。

実際に計ってみよう：実行時間

では、実際に計ってみましょう。

まずは、あるプログラムの実行がどの程度時間がかかるか、その確認です。

Time を使う

プログラムの実行時間を計るには、実行前の時間（t1）と実行後の時間（t2）を取り、その差（t2-t1）を出せば実行時間になります。こんな感じ。

t1 = Time.now
sleep 0.5      # 適当な負荷です。
t2 = Time.now
p t2 - t1

簡単ですね。

benchmark を使う

ただ、毎回 Time.now などと書いていると大変なので、同じことを簡単に行うことができる benchmark ライブラリを使ってみます。

require 'benchmark'

Benchmark.bm{|x|
  x.report{
    sleep 0.5
  }
}

#=> 出力:
#       user     system      total        real
#   0.000000   0.000000   0.000000 (  0.500101)

TIme.now を書くより長くなっちゃってますが、それっぽくユーザ時間、システム時間、合計時間、および実際の時間を表示してくれます。x.report で複数ベンチマークとることもできます。

結果を出力しなくない、という場合、Benchmark.measure で、結果だけを取り出すことができます。

require 'benchmark'

p Benchmark.measure{
  sleep 0.5
}

#=> 出力
# #<Benchmark::Tms:0x000001b58aa0ea10 @label="", @real=0.5000658000062685, @cstime=0.0, @cutime=0.0, @stime=0.0, @utime=0.0, @total=0.0>

結果は Benchmark::Tms という構造で返ります。詳しくはドキュメントを読んでみて下さい。

実行時間が短いプログラムの時間を計る：その1

このあたりから難しくなってきます。実行時間が短いプログラムの正確な実行時間を取るにはどうすればいいでしょうか。

例えば、s1 = "str1"; s2 = "str2" という二つの文字列 s1、s2 があるとき、この文字列を連結するためには s1 + s2 と #{s1}#{s2} ではどっちが速いか、ということを調べたくなったとします。

素直に書くとこんな感じでしょうか。

require 'benchmark'

s1 = "str1"
s2 = "str2"

Benchmark.bm{|x|
  x.report{
    _a = s1 + s2
  }
  x.report{
    _b = "#{s1}#{s2}"
  }
}

手許での出力結果ははこんな感じでした。

       user     system      total        real
   0.000005   0.000001   0.000006 (  0.000002)
   0.000003   0.000000   0.000003 (  0.000002)

これを見ると、実際の時間は変んないらしい、ということがわかります。

ただ、実はいろんな理由から、短いプログラムの実行時間を正確に計るのは難しい、ということが知られています。そこで、同じプログラムを繰り返し N 回実行し、後で N を割れば正しい実行時間が出来る気がします。

ただ、今度は繰り返しの数 N をどのようにすれば良いかを考えなければなりません。小さすぎれば、やはりまた計れませんし、大きすぎれば、無駄に計測時間を消費してしまいます。

そこで、benchmark/ips ライブラリがよく利用されています。

benchmark/ips は、100ms で何回ループが回るか確認し（M）、その測定結果から、1秒間実行するためには N をどのように決めれば良いか計算します。そして、実際に N 回ループで繰り返した時間を計測することで、ips（iteration per seconds、つまり1秒に何回繰り返しを行うことができたかという指標）を計算します。

実際にやってみましょう。

require 'benchmark/ips'

s1 = "str1"
s2 = "str2"

Benchmark.ips do |x|
  x.report { _a = s1 + s2 }
  x.report { _b = "#{s1}#{s2}" }
end

出力はこんなふうになりました。

Warming up --------------------------------------
                       357.924k i/100ms
                       263.015k i/100ms
Calculating -------------------------------------
                          7.642M (± 8.3%) i/s -     37.940M in   5.007196s
                          4.616M (±11.1%) i/s -     22.882M in   5.032705s

この結果では、7.6M ips と 4.6M ips という結果が出て、1.65 倍、_a = s1 + s2 のほうが速い、ということがわかりました。便利ですね。

実行時間が短いプログラムの時間を計る：その2

benchmark/ips で、うまいこと実行時間を計ることができることがわかりました。ただ、benchmark/ips では各繰り返しにブロックの起動という、比較的処理時間の大きなオーバヘッドを含んでいるため、正しい結果にならない可能性があります。

そこで、繰り返しの最も軽量なものである while ループを使ったプログラムを自動的に生成するのが benchmark-driver です。このライブラリでは、ベンチマーク中の様々な擾乱を排除するように設計されています。計測したいプログラムをブロックでは無く、プログラム文字列を渡すことで、後から計測対象プログラムを生成し、計測します。

具体的にはベンチマークはこのように記述します。

require 'benchmark_driver'

Benchmark.driver do |x|
  x.prelude <<~RUBY
    s1 = "str1"
    s2 = "str2"
  RUBY

  x.report %q{ _a = s1 + s2 }
  x.report %q{ _b = "#{s1}#{s2}" }
end

benchmark/ips とソコソコ似ていますが、プログラムのコード片がブロックでは無く文字列で渡されているのが違います。

結果はこんな感じでした。

Warming up --------------------------------------
       _a = s1 + s2     15.368M i/s -     15.652M times in 1.018515s (65.07ns/i, 188clocks/i)
  _b = "#{s1}#{s2}"      9.331M i/s -      9.465M times in 1.014296s (107.16ns/i, 311clocks/i)
Calculating -------------------------------------
       _a = s1 + s2     20.664M i/s -     46.103M times in 2.231049s (48.39ns/i, 140clocks/i)
  _b = "#{s1}#{s2}"     10.639M i/s -     27.994M times in 2.631268s (93.99ns/i, 272clocks/i)

Comparison:
       _a = s1 + s2 :  20664061.0 i/s
  _b = "#{s1}#{s2}" :  10639110.2 i/s - 1.94x  slower

これを見ると、前者の方が後者より 1.94 倍速いようです。前の二つの方法よりも、だいぶ数字が違いますね。だんだん、精度が良くなっている、ということがわかると思います。

Note: なんで文字列埋め込みのほうが遅いんでしょうか？　さらなる調査は、Linux の perf コマンドなどで、より詳細に（C 言語レベルで）行うことができます。

Note: 結果中、48.39ns/i とあるのは、1回の繰り返しに 48.39ns（ナノセカンド）かかった（全体の実行時間（2.231049s = 約 2.2 秒）を繰り返しの回数（46.103M回 = 約4600万回）で割った）値です。大分小さな値ですね。

なお、benchmark-driver は、YAML の形でベンチマークファイルを入力可能なので、YAML でまとめて書いておくと良いかもしれません。

prelude: |
  s1 = "str1"
  s2 = "str2"
benchmark:
  - _a = s1 + s2
  - _b = "#{s1}#{s2}"

これを、benchmark-driver コマンドで実行すると、下記の結果が得られます。

Warming up --------------------------------------
        _a = s1 + s2    16.794M i/s -     16.930M times in 1.008076s (59.54ns/i, 172clocks/i)
   _b = "#{s1}#{s2}"     9.850M i/s -      9.956M times in 1.010824s (101.53ns/i, 294clocks/i)
Calculating -------------------------------------
        _a = s1 + s2    19.793M i/s -     50.383M times in 2.545463s (50.52ns/i, 146clocks/i)
   _b = "#{s1}#{s2}"    10.178M i/s -     29.549M times in 2.903267s (98.25ns/i, 285clocks/i)

Comparison:
        _a = s1 + s2:  19793357.8 i/s
   _b = "#{s1}#{s2}":  10177734.1 i/s - 1.94x  slower

ほぼ同じですね。

Note: 例えば、s1、s2 はそれぞれ4文字の文字列でしたが、これが100文字の文字列だったら、結果はどう変わるでしょうか。

これを、Ruby の各メソッド用に用意したのが https://github.com/benchmark-driver/ruby-method-benchmarks でして、これは https://benchmark-driver.github.io/ で定期的に最新の Ruby で計測されています。

（細かい YAML の書き方は、上記リポジトリのサンプルを参照して下さい）

さて、この辺についても、いろいろ小難しい理屈はあるのですが、細かいことはおいといて、いろいろ調べてみましょう。

複数のメソッドを、self や引数を変えながら調べてみると、例えば「1個だけ他のメソッドに比べて遅い」とか、「あるデータを渡すとなぜか遅い」といったことが見つかるかもしれません。見つかれば、それを改善すれば、Ruby の性能改善になります。

このように改善していった @watson1978 さんによる記録が "How to optimize Ruby internal." にまとまっていますので参考にしてみて下さい。

（続く、かもしれない）

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

5_performance.md

5_performance.md

(5) 性能向上

この資料について

性能向上とは

性能向上の考え方

まず測ろう

アルゴリズムとデータ構造

MRI のいじりどころ

実際に計ってみよう：実行時間

Time を使う

benchmark を使う

実行時間が短いプログラムの時間を計る：その1

実行時間が短いプログラムの時間を計る：その2

Files

5_performance.md

Latest commit

History

5_performance.md

File metadata and controls

(5) 性能向上

この資料について

性能向上とは

性能向上の考え方

まず測ろう

アルゴリズムとデータ構造

MRI のいじりどころ

実際に計ってみよう：実行時間

Time を使う

benchmark を使う

実行時間が短いプログラムの時間を計る：その1

実行時間が短いプログラムの時間を計る：その2