今回は第３章、st_tableについて。
とりあえず、以下が1.8と1.9の大きな違いだと思われる。
- 挿入順を保持するようになった
- entries_packedが追加された
entries_packedは要素数が少ないときに配列を使って
キー、値、キー、値…
という感じで、単純にキーと値を並べたデータ構造で値を保持する仕組みらしい。探索は線形。要素数が少ないとこっちほうが良いらしい。
何が良いかというと「キャッシュヒットしやすいデータ構造じゃないか？」という吉岡さん説に対して「メモリ量を減らすのが目的ではなかったか？」とartonさんからツッコミが。
これを読むと、メモリ節約と高速化が目的なのかな？
entries_packedなんかの手動で実装が1.8より複雑になってたけど、「マイクロベンチマークじゃなく、ちゃんとしたベンチマークで計りたいよね」(Yuguiさん)とのこと。
ハッシュサイズが指定サイズより少し大きい素数を使っているのは「そのほうが要素がバラけるからではないか？」ということだったけど、いまいち分からず…
いくつか細かいツッコミも。
- Callocという名前はどうなの？
- よくよく考えるとコードの作者の趣味かなぁ？
- strhashはなんでunsigned intを返さない
Yuguiさんの発表の後、時間が余ったので吉岡さんがおなじ範囲について発表。
IDとシンボルについても説明。parse.cのrb_intern3関数を眺める。
文字列に対応するハッシュ値を生成してシンボルのテーブルに入れておく…と。
それから、発表者のさわださんがHashの順序の保持について、詳しく説明。このへんのやりとりのやつですね。
artonさんによる、st.cが拡張でつかえるよ、という小話。これはあとで実験してみる予定。
で、４章をすこし予習して終了。
今回は予習をサボったせいであんまりついていけなかった。とほほん。
次回はしっかりやっていこう。
