# 概要 Ruby インタプリタのデータ構造についての協力者を募集します。具体的には、 特定のテーブルデータ構造の高速化、およびベンチマークの作成です。題目にコ ンテストと書いていますが、とくに賞品はありません。 # 詳細 Ruby インタプリタでは、テーブルデータ構造を使っています。テーブルデータ 構造だと曖昧ですが、Ruby だと Hash クラスに代表される、あるキーに対して 特定の値が返る、というデータ構造と考えてください。キーに重複はないことと します。 Ruby インタプリタのテーブルデータ構造には、st というデータ構造が利用され ており、似たようなデータ構造はすべてこの st によって管理されています。st は、非常に高機能で、一般化されたもので、具体的にはチェインハッシュ構造に なっています。一般化するために、各操作を関数ポインタで渡すような形になっ ています。詳細は RHG のこちら: http://i.loveruby.net/ja/rhg/book/name.html でも、RHG の時代よりも、もっと高機能になっていて、具体的には順序を付ける ために、各エントリに双方向ポインタを持つようになっています。 さて、一般化された形の st は、使い勝手が良いのですが、「順序は気にしな い」とか、「特定の値の組に特化する」と、さらに効率の良いデータ構造を作る ことができます。Ruby インタプリタ内では、ID -> VALUE という、数値 -> 何 か、という組み合わせがよく利用されます。具体的には、メソッドテーブル（メ ソッド名 -> メソッドの実体）とか、インスタンス変数の管理（@foo とかの名 前 -> インスタンス変数の値）とかです。 ID は、何か数値だと思ってください。 http://i.loveruby.net/ja/rhg/book/object.html によると、「このIDは任意の 文字列と一対一対応する整数だ」ということです。メソッド名とかに番号を振っ たものとお考えください。 VALUE は、Ruby オブジェクトを表すものですが、void * として考えて貰っても 良いと思います（そう使っているところもあります、というか、現状はそうとし か使っていなかった）。 なお、少し細かいことをいうと、今回はキーに ID 直接ではなく、各IDに連番で 番号を振っており、その番号を使っています。ID -> 番号、番号 -> ID という のは簡単に交換可能です。 さっき、Ruby インタプリタの trunk に、この「ID -> VALUE」に特化した、 struct rb_id_table というデータ構造を取り込みました。導入の詳細は https://bugs.ruby-lang.org/issues/11420 をご覧下さい。 インターフェース https://github.com/ruby/ruby/blob/trunk/id_table.h 実装 https://github.com/ruby/ruby/blob/trunk/id_table.c まぁ、細かいことは良いとして、ある ID（数値）を入れると、登録済みの値が 返ってくるものであればよく、それが効率が良いと嬉しいわけです。 現状、このテーブルの実装として、おおまかに分けて4つ実装しています。 (1) これまで通り st を使う (2) 配列を使う (2-1) ただの配列を使う (2-2) ソート済みの配列を使う (3) ハッシュデータ構造を使う (4) 配列とハッシュデータ構造を混ぜる（要素数が小さい時には配列を使う） デフォルトでは、(4) を使うようになっています。それぞれの特質について、少 しまとめます（格納している要素数を N とします）。データ構造の教科書に書 いてありそうな話です。 (1) st を使うのは、今まで動いていたからちゃんと動くという確信が あります。ただ、色々冗長です。 (2-1) ただの配列 挿入：何も考えないので、実は他の構造に比べて一番速いです。 探索：要素数が少なければ、線形探索で高速に要素を発見出来ます。 要素数が多いと、線形探索は遅いです（O(N)）。 削除：線形探索が必要です（O(N)）。 (2-2) ソート済みの配列 挿入：ソートを気にしないといけないので若干遅いです（O(N)）。 探索：バイナリサーチを使うことができるので速いです（O(log N)）。 削除：削除箇所はバイナリサーチを使うことができるのですが、 削除後にソートを気にしないといけないので若干遅いです（O(N)）。 ただし、削除マークを付けるだけの実装なら、O(log N)。 (3) ハッシュ（議論を簡単しています。本当はもっと複雑） 挿入：速いです（O(1)） 探索：速いです（O(1)） 削除：速いです（O(1)） ただし、どれも十分な空きが無いと遅くなります。 運が悪いと遅いです。 また、最悪実行時間の見積もりが困難です。 N が十分小さい時、たとえば、探索対象が L1 キャッシュに乗っている時には、 余計なことをしない線形探索が一番速いです。メモリ効率は配列で管理するのが 一番有利です。 配列については、よくテーブルは struct { key; value } みたいな構造を並べ ますが、今回は探索時にキャッシュをヒットさせるために、キーだけ、値だけ、 にまとめています。なので、qsort 関数が使えなくて面倒くさかった。 とりあえず、現状作っているのはこんな感じですが、もっと改良する点もありそ うな気がします。 対象とする、ID → 値のテーブルは、メソッドテーブルを考えてみると、 - あまり沢山の要素を持たないことが多い - 多分、あまり削除しない - 多分、追加は一度に沢山行なうことが多い（クラスによるメソッド定義など） - 多分、探索が多い という特徴があるんじゃないかなぁ、と思います（インスタンス変数とかも、同 じような感じじゃないかなぁ）。もちろん、これは Ruby アプリケーションに よっても違うし、人為的にそうじゃないケースを作るのは容易です。なので、最 悪時もそこそこ動くと嬉しいです。 # お願い 21世紀にもなって、自分でデータ構造を実装するのもどうかと思うのですが、と りあえずこんな課題があるので、誰かぼくのかんがえたさいきょうのテーブル データ構造を考えてみませんか。 あと、優劣を比較するためのベンチマークが不足しています。もちろん、Ruby インタプリタに組み込んでいるので、Ruby インタプリタ上の Ruby プログラム で速度を比較してもいいのですが、他のオーバヘッドが大きすぎて、テーブルだ けの速度比較がやりづらいところがあります。そこで、このテーブルデータ構造 だけで比較するものがあると嬉しいなと思います。自分で書けばいいのですが、 面倒くさくて。 興味がある方がいらっしゃいましたら、何か考えてみてください。 -- // SASADA Koichi at atdot dot net