Tech Racho エンジニアの「？」を「！」に。
  1. TOP
  2. Ruby / Rails関連
  3. Ruby: メモ化のイディオムが現代のRubyパフォーマンスに与える影響（翻訳）
  • Ruby / Rails関連

Ruby: メモ化のイディオムが現代のRubyパフォーマンスに与える影響（翻訳）

概要

原著者の許諾を得て翻訳・公開いたします。

CC BY-NC-SA 4.0 Deed | 表示 - 非営利 - 継承 4.0 国際 | Creative Commons

Ruby: メモ化のイディオムが現代のRubyパフォーマンスに与える影響（翻訳）

Ruby 3.2における主要な内部変更のひとつに、オブジェクトシェイプ（object shape）の導入があります。

本記事では、オブジェクトシェイプが導入された理由、仕組み、制限事項について解説します。

🔗 オブジェクトのインスタンス変数はどのように保存されるのか

Rubyは非常に動的な言語なので、インスタンス変数へのアクセスという単純な操作でも多くの作業を伴います。

Rubyオブジェクトは、ほとんどの場合インスタンス変数を「参照の配列」に保存します。

たとえば、インスタンス変数を2個持つシンプルなオブジェクトを作成したとしましょう。

class User
  def initialize(name, admin)
    @name = name
    @admin = admin
  end

  def admin?
    @admin
  end
end

User.new("John", true)

MRIの場合、このオブジェクトは40バイトのオブジェクトスロット（slot）内で以下のように配置されます（ivarはインスタンス変数を表します）。

flags class ivar0 ivar1 ivar2
0x01 User "John" true UNDEF

個別のセルサイズは8バイトです。

第1のセルはオブジェクトのflagsに使われます（flagsにはさまざまな用途がありますが、いずれも本記事では扱いません）。

第2のセルは、オブジェクトのクラスへのポインタを保存します。

そして残りの3つのセルがオブジェクトのインスタンス変数の保存に使われています。

このオブジェクトにはインスタンス変数が2つしかなく、3つ目のスロットは使われていません。

インスタンス変数にアクセスするコードをRubyが実行するときは、変数名を添字（index）に変換可能にする必要があります。

Ruby 3.1以前では、個別のクラスがインスタンス変数を添字にマップするHashを保持していました。これを疑似Rubyコードで書くと以下のように動作します。

class Class
  def initialize
    @instance_variables_index = {}
  end

  def ivar_index(ivar_name)
    @instance_variables_index[ivar_name] ||= @instance_variables_index.size
  end
end

class Object
  def initialize
    @ivars = []
  end

  def instance_variable_get(ivar_name)
    index = self.class.ivar_index(ivar_name)
    value = @ivars[index]
    return value == UNDEF ? nil : value
  end

  def instance_variable_set(ivar_name, value)
    index = self.class.ivar_index(ivar_name)
    @ivars[index] = value
  end
end

user.instance_variable_get(:@admin) # => true

🔗 インラインキャッシュ

ご想像の通り、インスタンス変数にアクセスするたびにHashの探索を強いられると、かなり遅くなります。

探索を毎回行うことを回避するために、Ruby VMではインラインキャッシュ（inline cache）と呼ばれるしくみを使っています。インラインキャッシュは、VMバイトコードの内部に置かれる小さなメモリ領域であり、この種の計算結果を保存することで毎回実行せずに済むようにします。

これを擬似Rubyコードで表すと以下のようになります。

def ruby_vm_get_instance_variable(object, ivar_name, cache)
  if cache.last_class != object.class
    cache.last_class = object.class
    cache.index = object.class.ivar_index(ivar_name)
  end

  value = object.ivars[cache.index]
  return value == UNDEF ? nil : value
end

このようなインラインキャッシュを利用すれば、1個のクラスだけを扱うメソッドがインスタンス変数の添字を探索しなければならない回数が1回で済むようになります。以後の実行では、キャッシュされたクラスを現在のオブジェクトクラスと比較するだけで、マッチした場合にキャッシュ済み添字を直接再利用できるようになります。この動作は、添字の探索を毎回強いられるよりもずっと高速です。

🔗 インラインキャッシュとポリモーフィズム

しかしこうした方法は、単純なポリモーフィズムが存在するとパフォーマンスが下がってしまいます。

require "benchmark/ips"

class Parent
  def name
    @name
  end

  def initialize(name)
    @name = name
  end
end

class Subclass < Parent
end

stable_1 = Parent.new("Odile Deray")
stable_2 = Parent.new("Simon Jérémi")

unstable_1 = Parent.new("Peter")
unstable_2 = Subclass.new("Steven")

puts RUBY_DESCRIPTION
Benchmark.ips do |x|
  x.report("stable class") do
    stable_1.name
    stable_2.name
  end

  x.report("unstable class") do
    unstable_1.name
    unstable_2.name
  end

  x.compare!(order: :baseline)
end

上のコードのベンチマークでは、「同一クラスの2つのインスタンスにシンプルにアクセスするインスタンス変数」のパフォーマンスと、「異なる2つのクラスのインスタンスにシンプルにアクセスするインスタンス変数」のパフォーマンスを比較します。

ruby 3.1.4p223 (2023-03-30 revision 957bb7cb81) [arm64-darwin22]

        stable class     14.222M (± 1.3%) i/s -     71.960M in   5.060612s
      unstable class     11.625M (± 3.2%) i/s -     58.238M in   5.015375s

Comparison:
        stable class: 14221847.8 i/s
      unstable class: 11625350.9 i/s - 1.22x  slower

ご覧の通り、Subclassは見た目も形式も親のParentクラスと同一ですが、これはキャッシュキーとして利用されるため、2つのインスタンスのクラスが異なる場合は低速な探索を強いられてしまいます。

🔗 オブジェクトシェイプの導入

この問題を（および他のいくつかの問題も）解決するために、Ruby 3.2ではオブジェクトシェイプ（object shape）を実装しました。これは1980年代にSmalltalk言語で開拓された技術です。

本記事を簡潔にとどめるため、ここではオブジェクトシェイプの基本的な概要と動作のみを説明することにします。詳しくは、Chris Seatonによるオブジェクトシェイプの一般的な概念の解説記事か、Jemma IssrofがCRubyでオブジェクトシェイプの実装方法について話している以下の動画を参照することを強くおすすめします。

そういうわけで詳しい説明は省略しますが、オブジェクトシェイプはツリー状の構造になっており、個別のノードがインスタンス変数を表します。たとえば以下のコードがあるとしましょう。

class Person
  def initialize(name)
    @name = name
  end
end

class Employee < Person
end

class Customer < Person
  def initialize(name)
    super
    @balance = 0
  end
end

person = Person.new("Peter")
employee = Employee.new("Steven")
customer = Customer.new(George)

このときのシェイプツリーは以下のようになります。

shape_id ivar index parent_id
+ 12 @name 0 0
+ 42 @balance 1 12

上の例のuserインスタンスとemployeeインスタンスは、お互いのクラスが異なっているにもかかわらず同じシェイプ（12）を持っています。

2つのオブジェクトが、「同じ順序で定義された」「同じインスタンス変数リスト」を持っていれば、両者は必ず同じシェイプを共有します。

そのおかげで、インスタンス変数にアクセスするコードは、このシェイプをキャッシュキーとして使う形で更新されるようになりました。

def ruby_vm_get_instance_variable(object, ivar_name, cache)
  if cache.last_shape_id != object.shape_id
    cache.last_shape_id = object.shape_id
    cache.index = RubyVM.ivar_index(shape_id, ivar_name)
  end

  if cache.index == IVAR_NOT_SET
    return nil
  else
    return object.ivars[cache.index]
  end
end

Ruby 3.2で同じベンチマークを実行してみると、両者のパフォーマンスが同程度になっていることがわかります。

ruby 3.2.2 (2023-03-30 revision e51014f9c0) [arm64-darwin22]

        stable class     13.994M (± 1.2%) i/s -     70.504M in   5.038920s
      unstable class     14.122M (± 1.5%) i/s -     71.367M in   5.054938s

Comparison:
        stable class: 13993825.7 i/s
      unstable class: 14121540.7 i/s - same-ish: difference falls within error

シェイプのおかげで、シンプルなポリモーフィズムが存在する場合にもインラインキャッシュが安定するようになります。

シェイプについてこれ以上詳しくは説明しませんが、シェイプのメリットはこの他にもいろいろあります。

🔗 従来のメモ化イディオム

ただし、シェイプはすべての場合に高速とは限りません。

Rubyを使ったことがあれば知らない人はいないほど非常によく使われる定番の書き方に、以下のような||=によるメモ化（memoization）パターンがあります。

def dynamic_property
  @dynamic_property ||= something_slow_to_compute
end

残念ながら、このメモ化パターンはシェイプとの相性が良くありません。このメモ化イディオムを使うと、同じクラスのインスタンスが異なるシェイプを持つことが増え、インラインキャッシュのヒット率が下がってしまいます。

あるクラスのinitializeで定義されるインスタンス変数は、常に1個のシェイプだけを持ちます。

しかし、余分なインスタンス変数がバラバラの順序で追加定義されると、シェイプの個数がたちまち爆発的に増加します。メモ化された変数を1個持つクラスには2個のシェイプがあり、メモ化された変数を2個持つクラスには4個のシェイプがあり、メモ化された変数を5個持つクラスには121個のシェイプがあり、という具合になります。

はい、この増加は階乗になります。あるクラスが持つシェイプの個数は、1 + !（遅延定義される変数の個数）になります。

しかし、これはどのぐらいまずいのでしょうか？測定してみましょう。

require "benchmark/ips"

class UnstableShape
  attr_reader :name

  def initialize(name)
    @name = name
  end

  def first_name
    @first_name ||= @name.split.first
  end

  def upcased_name
    @upcased_name ||= @name.upcase
  end
end

# 同じシェイプを持つ2個のオブジェクトを生成
stable_1 = UnstableShape.new("Odile Deray")
stable_2 = UnstableShape.new("Simon Jérémi")
stable_1.first_name
stable_1.upcased_name
stable_2.first_name
stable_2.upcased_name

# 異なるシェイプを持つ2個のオブジェクトを生成
unstable_1 = UnstableShape.new("Peter")
unstable_2 = UnstableShape.new("Steven")
unstable_1.first_name
unstable_1.upcased_name
unstable_2.upcased_name
unstable_2.first_name

puts RUBY_DESCRIPTION
Benchmark.ips do |x|
  x.report("stable shape") do
    stable_1.name
    stable_2.name
  end

  x.report("unstable shape") do
    unstable_1.name
    unstable_2.name
  end

  x.compare!(order: :baseline)
end

ruby 3.2.2 (2023-03-30 revision e51014f9c0) [arm64-darwin22]

        stable shape     15.341M (± 0.9%) i/s -     76.755M in   5.003687s
      unstable shape     13.259M (± 1.1%) i/s -     66.385M in   5.007561s

Comparison:
        stable shape: 15340799.2 i/s
      unstable shape: 13258541.5 i/s - 1.16x  slower

速度低下が16%ならさほど悪くありませんが、このオーバーヘッドはシェイプが深くなると直ちに大きくなることにご注意ください。同じベンチマークを実行したとしても、シェイプに多数の変数を追加すればするほど、ベンチマークはその分目に見えて悪化します。

class UnstableShape
  def initialize(name)
    @name = name

    @ivar01 = true
    @ivar02 = true
    @ivar03 = true
    @ivar04 = true
    @ivar05 = true
    @ivar06 = true
    @ivar07 = true
    @ivar08 = true
    @ivar09 = true
    @ivar10 = true
    @ivar11 = true
    @ivar12 = true
    @ivar13 = true
    @ivar14 = true
    @ivar15 = true
    @ivar16 = true
    @ivar17 = true
    @ivar18 = true
    @ivar19 = true
    @ivar20 = true
    @ivar21 = true
    @ivar22 = true
    @ivar23 = true
    @ivar24 = true
    @ivar25 = true
  end
end

ruby 3.2.2 (2023-03-30 revision e51014f9c0) [arm64-darwin22]

        stable shape     14.253M (± 0.9%) i/s -     71.296M in   5.002615s
      unstable shape      5.821M (± 1.8%) i/s -     29.116M in   5.003786s

Comparison:
        stable shape: 14253062.2 i/s
      unstable shape:  5820686.1 i/s - 2.45x  slower

キャッシュミスが発生すると、オブジェクトシェイプのツリーを辿って必要なノードまでたどり着かなければならなくなるので、計算量がO(n)になります。ここでnはオブジェクトシェイプツリーの深さを表し、これはインスタンス変数の個数に相当します。

関心のある方へ: これを担当する関数はrb_shape_get_iv_indexです。疑似Rubyコードで表すと以下のようになります。

def RubyVM.ivar_index(shape_id, ivar)
  shape = SHAPES[shape_id]
  while shape
    if shape.ivar == ivar
      return shape.index
    else
      shape = SHAPES[shape.parent_id]
    end
  end
  IVAR_NOT_SET
end

先ほどのコードで25個のインスタンス変数を使ったのはちょっと多すぎではないかと思われるかもしれません。しかしこの数字を選んだのには意味があります。これはActiveRecord::Baseのインスタンスが持つインスタンス変数の個数なのです。つまり、Railsのモデルでメモ化パターンを使うと、Active Recordのほとんどの操作でパフォーマンスが著しく低下するということを示しています。

🔗 YJITのポリモーフィックキャッシュ

この「不安定なシェイプ」問題の主な原因は、VMのインラインキャッシュがモノモーフィック（monomorphic）であることです。これは、そこにシェイプを1個しか記録できないという意味です。

しかしYJITの最適化にはポリモーフィックなインラインキャッシュの実装も含まれています。Ruby 3.2では、YJITのインラインキャッシュに最大20個の異なるシェイプを記録できます。ただし、メモリ使用量と速度はトレードオフの関係にあるので、Ruby 3.3では記録可能なシェイプの個数が5個に減らされました。

それでもYJITを有効にすれば、この単純なメモ化ベンチマークでも同程度のパフォーマンスを得られます。

ruby 3.2.2 (2023-03-30 revision e51014f9c0) +YJIT [arm64-darwin22]

        stable shape     40.524M (± 1.4%) i/s -    203.140M in   5.013915s
      unstable shape     40.557M (± 1.0%) i/s -    203.056M in   5.007196s

Comparison:
        stable shape: 40523693.8 i/s
      unstable shape: 40557046.2 i/s - same-ish: difference falls within error

ただし上述したように、メモ化を多用するとシェイプの個数がたちまち爆発的に増加する可能性があります。

🔗 SHAPE_TOO_COMPLEX

この問題は、オブジェクトシェイプ実装中のかなり早い時期に指摘されたので、病的なケースに対応するための回避方法が実装されました。異なるシェイプを大量に生成するクラスの存在をVMが検出すると、自動的にそのクラスに「too complex」とマーキングし、以後のすべてのインスタンスがSHAPE_TOO_COMPLEXという一意の特殊シェイプを持つようになります。

この特殊なシェイプを持つオブジェクトは、インスタンス変数を内部配列ではなくハッシュマップに保存するようになります。これによってメモリ使用量が増えてパフォーマンスが落ちますが、アクセス速度が安定するようになります。

これは、先ほどのベンチマークに少し手を加えることで実証できます。

class StableShape
  attr_reader :name

  def initialize(name)
    @name = name
  end
end

class TooComplexShape
  attr_reader :name

  def initialize(name)
    @name = name
  end
end

# このクラスがtoo complexとマーキングされるようにする
10.times do |i|
  TooComplexShape.allocate.instance_variable_set("@iv_#{i}", i)
end

stable = StableShape.new("Test")
too_complex = TooComplexShape.new("George Abitbol")
puts ObjectSpace.dump(too_complex)

puts RUBY_DESCRIPTION
Benchmark.ips do |x|
  x.report("stable shape") do
    stable.name
  end

  x.report("too-complex shape") do
    too_complex.name
  end

  x.compare!(order: :baseline)
end

{"address":"0x104d991d0", "type":"OBJECT", ..., "too_complex_shape":true, ...}

ruby 3.2.2 (2023-03-30 revision e51014f9c0) +YJIT [arm64-darwin22]

        stable shape     45.207M (± 1.0%) i/s -    226.553M in   5.011953s
   too-complex shape     29.952M (± 1.1%) i/s -    150.621M in   5.029290s

Comparison:
        stable shape: 45207185.7 i/s
   too-complex shape: 29952498.7 i/s - 1.51x  slower

そういうわけで、SHAPE_TOO_COMPLEXはいわゆるハッピーパスよりも遅くはなりますが、シェイプツリー内で変数を常に探索しなければならなくなる最悪のシナリオよりは速くなります。

🔗 共通祖先

本記事の執筆中に、Rubyコードを変更することなくメモ化パターンの処理をインラインキャッシュで改善できることを思いつきました。

キャッシュミスが発生すると、最初は変数添字をゼロから探索します。しかしメモ化のせいでインラインキャッシュが不安定になったときに、キャッシュに保存されているシェイプと現在のシェイプにある共通祖先をチェックすることで、シェイプツリーの探索をより早期に終了できるようになるでしょう。

先ほどのUnstableShapeの例では、26個の固定インスタンス変数と、2個のメモ化インスタンス変数がありました。ここで探索するのは最も最初のものなので、少なくとも26個のシェイプを辿らなければならなくなって遅くなります。

しかし、古くなったshape_idを指定すれば、探索するシェイプは最大3個で済むようになり、はるかに高速になります（6133ca3）。

C言語のコードだとわかりにくくなりそうなので、ここでは疑似Rubyコードを示します。

def RubyVM.ivar_index(shape_id, ivar, cached_shape_id, cached_index)
  shape = SHAPES[shape_id]
  while shape
    if cached_shape_id == shape.parent_id
      # 新しいシェイプは、キャッシュ内にある古いシェイプの子孫になるので
      # キャッシュされた添字が引き続き有効であることがわかる
      return cached_index
    elsif shape.ivar == ivar
      return shape.index
    else
      shape = SHAPES[shape.parent_id]
    end
  end
  IVAR_NOT_SET
end

この操作は引き続きO(n)ですが、nはほとんどの場合「変数全体の個数」ではなく「遅延定義された変数の個数」になるので、nは大幅に小さくなります。

私がこのアイデアをRubyコミッターたちと共有したところ、John Hawthornが半年以上前にかなり近いアイデアを出していた（#7429）ことを教えてくれました。

このパッチは本記事執筆時点ではまだマージされていませんが、12月には一部のバージョンがRuby 3.3.0に含まれることを期待しています1。

🔗 祖先の添字を保持する

上述のパッチによって、メモ化パターンを乱用していないユーザーのパフォーマンスに関する懸念はかなりの程度解消するでしょう。

ただし、まったく通用しないパターンが1つあります。それは共有されるシェイプが根本的に異なっている場合です。

module Synchronized
  def initialize
    @mutex = Mutex.new
  end

  def synchronized(...)
    @mutex.synchronize(...)
  end
end

class Car
  include Synchronized

  def initialize(brand, ...)
    super
    @brand = brand
    ...
  end
end

class Animal
  include Synchronized

  def initialize(breed, ...)
    super
    @breed = breed
    ...
  end
end

上の例では、synchronizedメソッド内でアクセスしている@mutexで、シェイプが根本的に異なったものになることが示されており、共通祖先すら見当たらないため、そうしたアクセスはO(n)にとどまります。

この問題はRuby 3.2リリース前から予見されていましたが、時間内にソリューションを実装できませんでした。

可能なソリューションのひとつは、親シェイプの添字を子のシェイプで維持しておくことで、キャッシュミス発生時に属性添字を素早く探索できるようにするというものです。この方法の欠点は、そうした添字が余分にメモリを消費することです。

Aaron Pattersonが#8744でこのアイデアの実装に取り組み、赤黒木
（Red-black tree）添字の利用を選択しました。理由は、親シェイプの添字を手軽に共有可能になり、メモリのオーバーヘッドを抑えられるためです。Aaronの実装では、余分なメモリ使用量をさらに最小化するために、添字の生成を10個のシェイプにつき1回にとどめているので、キャッシュミス発生時にはシェイプを最大で10個たどってから添字を探索することになります。

このパッチはまだマージされていませんが、これもRuby 3.3に取り入れられる予定です2。

🔗 「オブジェクトシェイプに優しいコード」は重要

上のベンチマークで示したように、メモ化パターンを使いすぎるとRubyプログラムのパフォーマンスが悪化するおそれがあります。少なくともホットスポット（実行頻度の高い箇所）では、コンストラクタでインスタンス変数を一括初期化するとメモ化パターンを避けるうえで効果的でしょう。

ただしメモ化パターンの利用頻度が適正であれば、おそらく大して問題にはならないでしょう。また、YJITや今後のRubyバージョンで処理が改善されることでしょう。

ただし、SHAPE_TOO_COMPLEXの利用は、速度が低下するだけでなくメモリ消費も増えるので、なるべく避けるのがベストです。これを解決するために、Ruby 3.3以降はクラスが"too complex"とマーキングされると警告を表示できるようになります（#19538）。設定を有効にするには、Warning[:performance] = trueを設定するか、コマンドラインで-W:performanceを渡して実行します。

$ ruby -W:performance /tmp/too-complex.rb
/tmp/too-complex.rb:19: warning: Maximum shapes variations (8) reached by TooComplexShape, instance variables accesses will be slower.

ただし全般としては、メモ化パターンの利用頻度を適正にとどめ、ホットスポットを避けておけば、パフォーマンス上の大きな懸念にはならないと言えます。

私の経験則では、クラス内のメモ化変数が1〜2個ならば問題ありませんが、それより多くなる場合はコンストラクタで変数を一括でnil初期化する必要が生じる可能性があります。

class StableShape
  def initialize
    @expensive_value = nil
  end

  def expensive_value
    @expensive_value ||= compute_expensive_value
  end
end

このとき、メモ化した値がfalsyになる可能性がある場合は、以下のようにトークンモジュールを利用できます3。

class StableShape
  NOT_SET = Module.new
  private_constant :NOT_SET

  def initialize
    @expensive_value = NOT_SET
  end

  def expensive_value
    return @expensive_value unless @expensive_value == NOT_SET
    @expensive_value = compute_expensive_value
  end
end

関連記事

Rubyオブジェクトの未来をつくる「シェイプ」とは（翻訳）

Ruby: オブジェクトシェイプに優しいコードの書き方（翻訳）

  1. 訳注: その後著者の別のプルリク#8650としてマージされました。 ↩
  2. 訳注: その後#8744はマージされました。 ↩
  3. 訳注: これはNull objectパターンとも呼ばれます。 ↩

タグ
この記事を書いた人

hachi8833

Twitter: @hachi8833、GitHub: @hachi8833 コボラー、ITコンサル、ローカライズ業界、Rails開発を経てTechRachoの編集・記事作成を担当。 これまでにRuby on Rails チュートリアル第2版の監修および半分程度を翻訳、Railsガイドの初期翻訳ではほぼすべてを翻訳。その後も折に触れて更新翻訳中。 かと思うと、正規表現の粋を尽くした日本語エラーチェックサービス enno.jpを運営。 実は最近Go言語が好きで、Goで書かれたRubyライクなGoby言語のメンテナーでもある。 仕事に関係ないすっとこブログ「あけてくれ」は2000年頃から多少の中断をはさんで継続、現在はnote.comに移転。Amazonウィッシュリスト: https://bit.ly/32aAmiI

hachi8833の書いた記事一覧へ

本記事の内容へのお問い合せはTwitterで@techrachoへMentionまたはDMにてご連絡頂くか、運営会社であるBPS株式会社のお問い合せフォームよりお問い合せ下さい。

CONTACT

TechRachoでは、パートナーシップをご検討いただける方からの
ご連絡をお待ちしております。ぜひお気軽にご意見・ご相談ください。
CONTACT FORM