# 概要

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