Rubyではどんなオブジェクトもハッシュキーにできる――Optcarrotに学ぶ重複排除テクニック

Ruby 3x3プロジェクトをフォローしている方なら、Optcarrotという名前を聞いたことがあるかもしれません。Optcarrotは、純粋なRubyだけで書かれたNES(ファミコン)エミュレータです。

最近Optcarrotのソースコードを読んでいて、興味深い実装に行き当たりました。それは、Rubyのハッシュの機能の中でも意外と見落とされがちながら、非常に有用な特徴――「任意のオブジェクトをハッシュキーとして使える」という性質を、ふんだんに活用している点です。

背景：NESのメモリマッピング

高レベル言語でプログラムを書いていると、メモリといえばRAMを思い浮かべがちです。しかし低レベルの世界では、「メモリ」はそれ以外にもさまざまな用途に使われます。

NESのCPUは、「メモリ」への読み書きを通じて、GPU・コントローラ・カートリッジ上の特殊な回路と通信しています。指定されるアドレスによって、write_to_memoryメソッドの呼び出しは、ジョイスティックのリセット、VRAMの切り替え、サウンドの再生など、まったく異なる動作を引き起こすのです。

さて、これをRubyでどう実装するでしょうか?

Optcarrotは、65536個のアドレスそれぞれに対して2つのMethodオブジェクト(ゲッターとセッター)を格納することで実現しています。イメージは次のようなコードです。

@getter_methods[0x0001] = @ram.method(:[])
@setter_methods[0x0001] = @ram.method(:[]=)

問題：重複して生成されるオブジェクト

このようにObject#methodを使うと、中身は完全に同じなのに別々のMethodオブジェクトが大量に生成されてしまうのが難点です。

object_idを見てみると、それがよく分かります。

> a = []
> a.method(:[]=).object_id
=> 70142391223600
> a.method(:[]=).object_id
=> 70142391912420

2つのMethodオブジェクトのobject_idは異なる値です。つまり、やっていることは同じでも、システム上は別物の扱いになるのです。

通常なら数個の余分なオブジェクトなど気にする必要はありませんが、今回は数千個単位の話になります。

解決策：ハッシュによるメモ化

Optcarrotはこの重複問題を、シンプルすぎて逆に見落としてしまいそうなトリックで回避しています。それは、ハッシュを使ったメモ化(キャッシュ)による重複排除です。

簡略化したコードでこのテクニックを見てみましょう。

def initialize
  @setter_methods = []
  @setter_cache = {}
  ...
end

def add_setter(address, setter)
  # 重複は保存されない
  @setter_cache[setter] ||= setter

  # 重複排除済みのオブジェクトを使う
  @setter_methods[address] = @setter_cache[setter]
end

これが機能するのは、Hashがキーとしてどんな種類のオブジェクトを受け取っても問題ないからです。

ピンとこない場合は、まずIRBで文字列を使って試してみてください。

> cache = {}
> cache["foo"] ||= "bar"
=> "bar"
cache["foo"] ||= "baz"
=> "bar"

ここで思い出してほしいのは、Rubyにおいて文字列もまたStringクラスの一インスタンスにすぎないということです。文字列をハッシュキーとして扱う際にRubyが使っている仕組みは、Methodオブジェクトをキーにするときの仕組みと本質的に同じものなのです。

Hashはどのように同値性を判定するのか

文字列以外のオブジェクトをハッシュキーにするとき、こういう疑問が湧きます。「Hashは、2つのオブジェクトが等しいかどうかをどうやって判断するのだろう?」

その答えが、Object#hashメソッドです。このメソッドはオブジェクトの中身をたどり、再帰的にハッシュ値を生成します。

> a.method(:[]=).hash
=> 929915641391564853

同一内容のオブジェクトは必ず同一のハッシュ値を返すため、この値を同値性の判定に使えます。

a.hash == b.hash

興味深いことに、これはeql?メソッドが内部で採用しているのと同じアプローチです。

a.eql?(b)

もちろん、この仕組みは例のMethodオブジェクトに対してもきちんと機能します。

> a.method(:[]=).hash == a.method(:[]=).hash
=> true

まとめ

RubyのWeb開発パターンに慣れきっていると、Optcarrotのソースコードを読んで、リアルタイムに動作する非Webアプリケーションがまったく違う設計パターンを使っていることに、強い新鮮さを感じました。Webアプリで65536要素もの配列を作る機会はまずありませんが、ここでは「デスクトップ」アプリのセットアップ処理の一部として、この手法は非常によく理にかなっています。

ご質問やコメントがある方は、メール(starr@honeybadger.io)またはTwitter(@StarrHorne)でお気軽にご連絡ください。