2019-05-04

ID (4)

ID は 2²⁹ = 約 500M と言ったな、あれは嘘だ。というわけで、4 bit フラグで使っていたので、2²⁸ = 268,435,456 = 約 250M 個でした。

下 1 ビットは、ID_STATIC_SYM というフラグを埋め込むためのものみたいだけど、知らないなあ。今度調べます。

ID の種類の話。これは 3bit = 最大 8 通り。ID は、パーサで使うことがあるので、この ID で表されるシンボルが、どのような種類であるかがわかっていると便利。というわけで、id_type(ID) を使う。

さらに、こんな感じのマクロで情報が取れる。

#define is_local_id(id) (id_type(id)==ID_LOCAL)
#define is_global_id(id) (id_type(id)==ID_GLOBAL)
#define is_instance_id(id) (id_type(id)==ID_INSTANCE)
#define is_attrset_id(id) ((id)==idASET||id_type(id)==ID_ATTRSET)
#define is_const_id(id) (id_type(id)==ID_CONST)
#define is_class_id(id) (id_type(id)==ID_CLASS)
#define is_junk_id(id) (id_type(id)==ID_JUNK)

ローカル変数だったり、グローバル変数だったり、インスタンス変数だったりが、ID 値に埋め込まれている。しかし、この辺、パーサはさっと取れると、そりゃいいだろうけど、別の構造に入れてもいいよなぁ。その分、ID の数を増やした方が良いと思うのだが...。

2019-05-03

ID (3)

さて、IDの種類を見るには、symbol.h に定義してある id_type(ID) 関数を使う。

static inline int
id_type(ID id)
{
    if (is_notop_id(id)) {
    return (int)(id&ID_SCOPE_MASK);
    }
    else {
    return -1;
    }
}

is_notop_id() の詳細はおいといて、とりあえずこれが大抵選ばれる。id&ID_SCOPE_MASK が本体。

enum ruby_id_types {
    RUBY_ID_STATIC_SYM  = 0x01,
    RUBY_ID_LOCAL       = 0x00,
    RUBY_ID_INSTANCE    = (0x01<<1),
    RUBY_ID_GLOBAL      = (0x03<<1),
    RUBY_ID_ATTRSET     = (0x04<<1),
    RUBY_ID_CONST       = (0x05<<1),
    RUBY_ID_CLASS       = (0x06<<1),
    RUBY_ID_JUNK        = (0x07<<1),
    RUBY_ID_INTERNAL    = RUBY_ID_JUNK,
    RUBY_ID_SCOPE_SHIFT = 4,
    RUBY_ID_SCOPE_MASK  = (~(~0U<<(RUBY_ID_SCOPE_SHIFT-1))<<1)
};

template/id.h.tmpl という不思議なファイルに、この定義が書いてある。RUBY_ID_SCOPE_SHIFT - 1 は 3 で、(~0U<<(RUBY_ID_SCOPE_SHIFT-1)) は 0b1...1_1000。これの not なので 0b0...0_0111にして、1 bit ずらして 0b0...01110 が mask。あれ、type は 3bit のようだけど（id_type() で返す）、shift してるのは 4 bit だぞ？

2019-05-02

ID (2)

ID は 29 bit と紹介したが、では

(1) 32 bit 限定なの？
(2) 3 bit はどこいった？

という疑問が生じる。回答を述べると、(1) は、Yesで、(2) は ID の種類に使っている。

32ビットの理由。一般的な辞書的テーブルには key と value にそれぞれ VALUE が入る幅になっているので、それぞれ 64bitだ（64 bit CPUなら）。MRI には、ID を key にするデータ構造が沢山あるので、rb_id_table という特別なハッシュテーブルがある。このとき、key を 32 bit に限定してしまうと、速度的に嬉しい。で、2²⁹ 個くらいしかできないだろう、と考えて、このようにしている。

ちょっと計算してみると、600M 個の ID で、それぞれ 8B の名前が必要とすると、600M x (4B (sizeof(ID) + 8B (sizeof(name)) = 7GB。単に ID の管理だけで 7GB も食うような Ruby プログラムは、とりあえず現在は考えづらいので、このような制限にしている。

rb_id_table については、また後日。

2019-05-01

ID

ID は、インタプリタプロセス寿命の中で、文字列に一意な数値をつけるもの、と述べた。例えば "hello" に 100 という数値を付けたら、プロセスが再起動するまでずっと 100 になる。

何に使うかというと、いろいろなところで使うのだけれど、例えばメソッド名などの探索で、いちいち文字列一致を行うと、比較の度に文字数 n に比例するコストがかかることになるが、メソッド名をすべて数値に置き換えておけば、数値の比較、すなわち O(1) の比較で済むことになる。論理的には Bignum に拡張するようなことになれば、O(n) になるけど、インタプリタ内であれば、まぁ常識的に考えて、そうはならない。なお、現在 ID は、たしか 29 bit （つまり 2²⁹ = 536,870,912）の上限がある。例えば、600M 個のメソッドを作るとインタプリタプロセスが死ぬ。

2019-04-30

静的SymbolとID

静的 Symbol の話。基本的には、ID に tag bits を含ませて VALUE にする。

#define RB_STATIC_SYM_P(x) (((VALUE)(x)&~((~(VALUE)0)<<RUBY_SPECIAL_SHIFT)) == RUBY_SYMBOL_FLAG)

RB_STATIC_SYM_P(x) は、静的 Symbol であれば真になる。

ちょっと複雑なので解説しておくと、0b111... を RUBY_SPECIAL_SHIFT だけシフトするので、0b111...111_0000_0000 ができる（下位 8 bit が 0）。これの否定なので、0b000...000_1111_1111 を x と & した結果が RUBY_SYMBOL_FLAG であるか調べている。まとめると、下位 8 bit が RUBY_SYMBOL_FLAG と一致するかを調べている。

上位 54 bit は ID を示す。では、ID とは何か。MRI が内部で利用する、文字と一対一対応する数値のことである。

2019-04-26

RubyKaigi 2019 を振り返る

RubyKaigi2019 が終わったので、振り返っておく。

前日に before-RubyKaigi 開発者会議を開いた https://bugs.ruby-lang.org/issues/15459
- アジェンダをきちんと作って、30分のスロットにしてみた。時間足りないかな？　と思ったけど、結構ぎゅっと詰まって良かったのではないか。
- 来年は、午前をミーティング、午後を個別のハックにするとどうか、と言われているので、そうしてみよう。
今年は妻の実家に泊めて貰った。RubyKaigi に参加する他の2家族と合同で、3人の2歳児が集まるとハレーションを起こして大変なことになることがわかった。
初日
- Ruby 3 Progress Report のために、通訳打ち合わせ
- Matz keynote を聞く。Concurrency の話をする、といっていたが、あんまり踏み込んだ話はしていない。auto-fiber を入れると言ってた。誰が入れるか？
- Ruby 3 Progress Report で話す。まつもとさんに、前に座って貰ったけど、あんまりうまくパスが出せなかった。
- ランチは屋台並べなかったので、食堂でちゃんぽん。
- 国分さんは元気だなあという発表を聞く。
- 自分の発表。やっぱり英語で言葉が出ない。ごめん。内容については RubyKaigi 2019: Write a Ruby interpreter in Ruby for Ruby 3 - クックパッド開発者ブログを参照のこと。発表する内容をすべて書き出したんだけど、聴衆の数はどうだったんだろうね？
- ブースで Q&A セッションをやったけど、あんまり来なかったな。まぁ、あの内容だとな。ブースの位置も、みんながよく通る場所でもなかったしな（全体発表だと、通るところだったが）。
- Falcon の話。ちょっと Fiber で scale について、盛りすぎでは？　とは思う。楽観的には良いものだと思うけど。
- パターンマッチの発表で謝辞にはいっていた。
- 懇親会、子連れにはひたすらつらかった。
- 義実家で夕飯の続き。
二日目
- 近永さんのいい話だった。
- Noah のは、なんというか、あまり得るものがなかった。
- ので、途中で抜け出して、屋台を2軒巡った。
- その後、concurrent-ruby の人と、Guild の話をずっとしてた。
- vlad の話は凄かった。馬力が。さすがすぎる。
- Chrome でデバッガの話。protocol が15個くらいだそうで、なんとかなるかも？
- LT、みんなうまいね。
- 義実家で肉を頂いた。
三日目
- 大喜利と言われる Ruby Committers vs. the World。司会、ちゃんとできてたかしらん。
- ふらふらして、ランチ
- ランチ、結構あるいて目当ての水炊きがたべられずしょんぼりしながら、別の店でカレー食べた。
- ちょっと soutarou さんの話を聞いた
- ブレイク中に、主に遠藤さんが作ったパズルの解説。沢山集まったね。
- 中田さんが珍しく発表するというのでちょっと覗きにいった。
- 卜部君の話を聞いて、中身をやっと理解した。
- Jeremy の話は、なんというか、凄いなあ。でも、性能特性変わったら一瞬で使えなくなるよな。
- 終わった後、RubyKaigi 子供会、と称して21人（うち子供8人）集まって宴会。大変だった。
四日目（after rubykaigi hack）
- eric wong のコードを読もうと思ったけど無理だった。バグフィックスとか git 対応とかしてた
- がんばって東京に戻った

という感じだった。自分の関わった話でいうと、

登壇
- Ruby 3 Progress Report
- Write a Ruby interpreter in Ruby for Ruby 3
- Ruby Committers vs. the World
- （ロビーで）パズル解説
手伝った
- Before RubyKaigi Ruby-dev meeting
- Matz keynote（Concurrency の話）
- Pattern matchの話
- 型システムの話（x 3）
- GC の話
- VM 関連の話
- LT のアレ
- After hack（もともとはコミッタだけの予定だったのを拾って貰った）
- RubyKaigi 子供会
- クックパッドのブース

イッパイがんばった。RubyKaigi の種は俺が育てたと言っても過言ではない（過言しかない）。

2019-04-26

いつの間にか平成が終わる

Symbol の続き書かなきゃなあ、と思いながら、1月で止まっていた。

その間、

PPL2019 が終わった
ISMM に論文をだした → 通った！（RubyKaigi 前日に通知が来た）
RubyKaigi 2019 が終わった
Web+DB Press の連載が始まった

と、色々あって忙しかったけど、なんとなく筆を置いてしまうと続かないもので、またのんびり進めていきたい。