Flonum のビットレイアウト
double から VALUE の話を考える。
Flonum は下位 2 bit を 0b0010 にする、という話だった。では、その 2 bit はどこから来るか、というと、指数部 11 bit の上位 2 bit を使う、ということだった。指数部の上位 2 bit は 61, 62 bit 目にあるので、さて VALUE にはどうやってエンコードするか？
s xx eeeeeeeee m...m (m: 52bit) s: 符合 x: 使わない e: 指数部 (9bit) m: 仮数部 (52bit)
いくつか選択肢がある。一番素直なのは、0, 1 bit 目の仮数部を、61, 62 bit 目にコピーしてしまうことだ。
s mm eeeeeeeee m...m 10
このようにエンコードすれば、62 bit で表現できる。が、ビットの移動はちょっと計算が面倒だ。もうちょっとなんとかならいだろうか。
ビットのローテートを考えてみよう。ビットをぐるーっと回す奴。左に 3 bit 回してみると、こんな感じになる。
e...e m...m s 01
戻すときは、右に 3 bit 回せば良い。簡単そうだ。CPU によっては（というか、x86 には） rot 命令があるので、1命令で実現できる。
bias = 1024 p 0b00000000000 - bias # -1024 p 0b01000000000 - bias # -512 p 0b01100000000 - bias # -256 Flonum p 0b10000000000 - bias # 0 Flonum p 0b10011111111 - bias # 255 Flonum p 0b10100000000 - bias # 256 p 0b11000000000 - bias # 512 p 0b11111111111 - bias # 1023
Flonum になるのは、指数部が -256～255 の間だから、どうやら、Flonum になるのは、先頭 bit が 011 or 100 の時だけらしい。ここで、e のビット列の最上位ビットを e10, その下位ビットを e9、... と名付けることにする。このとき、e10, e9 は 01 or 10 であり、e8 が 1 の時は 01、0 の時は 11 であることがわかる。
さて、ここまでわかったら、実際にコードを見てみよう。実装しているのが次のコード（ruby/internal.h at trunk · ruby/ruby · GitHub）：
static inline VALUE
rb_float_new_inline(double d)
{
#if USE_FLONUM
union {
double d;
VALUE v;
} t;
int bits;
t.d = d;
bits = (int)((VALUE)(t.v >> 60) & 0x7);
/* bits contains 3 bits of b62..b60. */
/* bits - 3 = */
/* b011 -> b000 */
/* b100 -> b001 */
if (t.v != 0x3000000000000000 /* 1.72723e-77 */ &&
!((bits-3) & ~0x01)) {
return (RUBY_BIT_ROTL(t.v, 3) & ~(VALUE)0x01) | 0x02;
}
else if (t.v == (VALUE)0) {
/* +0.0 */
return 0x8000000000000002;
}
/* out of range */
#endif
return rb_float_new_in_heap(d);
}
bits = (int)((VALUE)(t.v >> 60) & 0x7) で bits に e10, e9, e8 を入力している。で、3 を引いてやると、0b011 (3) か 0b0100 (4) は 0 or 1 になる。つまり、下位 1 bit を 0 にすれば、0 になるはずである。それを計算しているのが (bits-3) & ~0x01)。0 以外であれば、Flonum 対象外ということだ。rb_float_new_in_heap() に処理を逃がしている（実装方法はまた今度）。
t.v != 0x3000000000000000 /* 1.72723e-77 */ の部分はよくわからないんだけど、どうやら、e の先頭が 0b011 であっても、その中でも最小の値は、これだとうまくいかないらしい。なんでだろう？ うーん、なくてもうまくいきそうなんだけどな。ログを見ても、最初からこのチェックがあったようだ。うーん、なんでだろ？ 自分で書いたのにね。
逆に、Flonum value -> double に変換するのは次のコード https://github.com/ruby/ruby/blob/trunk/internal.h#L1737：
static inline double
rb_float_flonum_value(VALUE v)
{
#if USE_FLONUM
if (v != (VALUE)0x8000000000000002) { /* LIKELY */
union {
double d;
VALUE v;
} t;
VALUE b63 = (v >> 63);
/* e: xx1... -> 011... */
/* xx0... -> 100... */
/* ^b63 */
t.v = RUBY_BIT_ROTR((2 - b63) | (v & ~(VALUE)0x03), 3);
return t.d;
}
#endif
return 0.0;
}
e8 を見ると、e9, e10 に何を補完すれば良いかわかる、ってのが、コメントに書いてあること。つまり、b63 ってのは e8 のことだけど、それが 0 なら e10 e9 は 0b10 で、1 なら 0b01 である。これは、2 （0b10 - e8）で計算できるわけで、それが (2 - b63) | (v & ~(VALUE)0x03)。それをぐるっと右に 3bit 回せば元の double ができあがり。
ちょっと面倒だったね。
あー、今気づいたんだけど、t.v != 0x3000000000000000 /* 1.72723e-77 */ のチェックって、Flonum VALUE 0x8000000000000002 を double 0.0 に対応づけるための仕組みかー。うーん。なるほど。0.0 はよく使うので、Flonum でなんとか表現したかったんですよね。
Flonum
Fixnum を紹介したので、次は Flonum を紹介する。
Flonum は聞き慣れない言葉ではないかと思うのだが、Float オブジェクト（浮動小数点数オブジェクト）を Immediate として表現するためのものだ。 Fixnum は Integer の一部（63bit で表現できる整数値）だったが、Flonum も同様に、浮動小数点数の一部を軽量に表現するものになる。
64bit CPU 限定で動作する（32bit CPU では有効にならない）。
Ruby の浮動小数点数は IEEE 754 - Wikipedia 倍精度浮動小数点数で表現されるので、64 bit 幅が必要になる。VALUE 幅は 64bit CPU だと 64 bit なので、だいぶ近い。少し頑張れば入りそうではないか？ と思って頑張って入れたのが Flonum。
さて、どうやって入れるか。まず、Immediate でなければならず、さらに Flonum であることを示さなければならないため、下位 2 bit は 0b10 となっている。つまり、(v & 0x03) == 0x02 であれば、Flonum ということになる。
次は、64bit 倍精度小数点数（面倒だから、double と書こう）をどうやって 62 bit に押し込むか。
IEEE 754 double の表現は、次のようになっている。
- s: 符号 1 bit
- e: 指数 11 bit
- m: 仮数 52 bit
の合計 64 bit で構成されている（s から上位ビット）。数値は、-1s * 2e-1024 * m (m = 1 + Σ i=0; 51; bi/(252-i)) で得られる。数式は適当に書いているし、なんか難しそうだけれど、e がどれくらい大きいか、m がどれくらい精度を持つか、で覚えておけばいい。
さて、どこから2ビットを削るか、というのが問題。仮数部が一番ビット数多いんだけど、仮数部を2ビット減らすと、つまり精度が落ちることになる。「Ruby で計算すると、なんか変な値になる」（変、とは...）、ってなるのは嫌だ。
それなら、e を削る方がいいかな、ということで、e から 2 bit 拝借することにした。double は指数部として 2^-1024 ~ 21023 の範囲を表すことができるが、2^-256~2255 の範囲だけ Flonum で表現できればいいか、と考える。実際、その範囲はどれくらいよ、ということなんだけど、2256 = 1.1579208923731619542357098500869e+77 らしく、まぁ、普通の人はこんなに大きな数も使わないよな、ということで、多分大丈夫なんだと思う。
e は 11 bit なので 0～2047 の範囲が表現できるが、バイアス 1024 を引くので、指数として表現出来るのは -1024 ～ 1023 になる。今回は、指数が -256 ～ 255 なので、
if (e >= -256 && e<= 255) {
// flonum
}
else {
// flonum じゃない格納方法
}
みたいに分けることになる。さて、2ビットを削った Flonum のビットレイアウトはどのようにすれば良いか。続きは次回。
Fixnum
IMMEDIATE_P(v) でもっともポピュラーなものは Fixnum だろう。下位 1 bit が 1 であれば（v&1 であれば）Fixnum だ。
さて、そもそも Fixnum ってなんだっけ。Ruby 2.4 で消滅したクラスだった。範囲つき整数であり、範囲を超えると Bignum になった。Bignum は、メモリがある限り、（絶対値が）大きな整数を表現できる。Ruby 2.4 では、Fixnum と Bignum は消滅し、Integer に統合された。実装が違うだけで、同じ整数を表現するため、そこに別々のクラスを用意するのは、あまり意味が無いだろう、ということで統合された（もともと、Bignum と Fixnum の親クラスとして Integer クラス自体は存在していた）。Ruby プログラマからみると、Fixnum と Bignum はシームレスに変換されるため、意識することはない、と思う。厳密には、同じ値なのに別々の object_id が帰ってくることがあったりするのが Bignum が Fixnum と同じところだ。
Bignum と Fixnum は Integer に統合されたが、実装レベルでは依然としてこの二つは残っている。Bignum はメモリを確保するので毎回メモリアロケーションするが、Fixnum は special const なので、VALUE に埋め込まれるのでメモリ確保は不要である。
さて、Fixnum の範囲は何かというと、63bit か 31 bit で表現できる値となる。LSB 1 bit を識別のために利用するので、63 or 31 bit しか利用できないのだ。
#define RB_INT2FIX(i) (((VALUE)(i))<<1 | RUBY_FIXNUM_FLAG) #define INT2FIX(i) RB_INT2FIX(i)
C の int の値を、Fixnum でその値を表現する VALUE に変換するには、この INT2FIX(v) を利用する。1 bit 左シフとして（2倍して）、RUBY_FIXNUM_FLAG つまり 0x01 を or する。簡単。同じく、Fixnum から int に変換するには 1 bit 右シフトすれば良い。
VALUE に埋め込む値なので、Fixnum として存在できるオブジェクトの数は決まっている。逆の言い方をすると、Fixnum オブジェクトは、起動時にすでにすべて作成されているとも言える。1 という数値リテラルは、MRI から検索し、存在した Fixnum オブジェクトを取り出した、とも言える。
true
IMMEDIATE_P(v) は、いくつかの種類のオブジェクトであると紹介した。もっとも簡単なものは true であり、Qtrue というマクロで値を参照できる。実際には 0x14 == 0b0001_0100 という値になる（64bit CPU の場合）。
#define RB_IMMEDIATE_P(x) ((VALUE)(x) & RUBY_IMMEDIATE_MASK) #define IMMEDIATE_P(x) RB_IMMEDIATE_P(x)
という定義だったのを思い出すと、immediate mask は 0b0111 なので、0x14 & 0b0111 はちゃんと !0 であることがわかる。つまり、IMMEDIATE_P(Qtrue) は真である。
ここまでで、true, false, nil が出揃った。
- true: Qtrue == 0x14
- false: Qfalse == 0x00
- nil: Qnil == 0x08
RB_TEST_P(x)
https://github.com/ruby/ruby/blob/ruby_2_6/include/ruby/ruby.h#L478
#define RB_TEST(v) !(((VALUE)(v) & (VALUE)~RUBY_Qnil) == 0) #define RB_NIL_P(v) !((VALUE)(v) != RUBY_Qnil) #define RTEST(v) RB_TEST(v) #define NIL_P(v) RB_NIL_P(v)
RB_TEST(v) の定義はこれだった。これは、x が false か nil 以外だったら真、というもの。Ruby では nil もしくは false だったら偽、という定義と同じものだ。C コード中で if (RB_TEST(v)) {...} みたいに、Ruby 的に真だったら、みたいに書く時に使う。
ついでに、NIL_P(v) の定義もある。Qnilそれと等しいかどうか、をチェックしている。いちいち、!(v != Qnil) と二重否定にしているのは、... なんで？
https://github.com/ruby/ruby/commit/8497a7b9187a05210a4f6b842d06d1268d704d35
if NIL_P(x) { ... } と（if RTEST(x) { ... } だったっけ？ という話も）C で書いたパッチが来たから、括弧を省略できないようにしたらしい...。
そういえば、例によって RB_TEST に RTEST、RB_NIL_P に NIL_P、RUBY_Qnil には Qnil という別名がついている。歴史的には逆で、先に RTEST とかがあった。Ruby の API であることを強調するために RB_ prefix を付けている。
さて、RB_TEST(v) の実装に戻ると、!((v & ~Qnil) == 0) だったら真らしい。このビット演算は何をしているのか？
Ruby において、偽の値は fales と nil で、それぞれ C では Qfalse、Qnil という値である。つまり、素直に書くと、!((v) == Qnil) || (v) == Qfalse) とすれば良い。それがなぜ論理演算になるのか？
実は、Qfalse は 0 で、Qnil は 0b0100 == 0x08 という値である。展開すると !(v == 0x08 || v == 0x00) こうなる。つまり、v が 0b0000 もしくは 0b0100 であれば偽ということになる。この二つの違いは 0b0100 の 1 bit だけなので、この bit 以外が 0 であれば、Qfalse もしくは Qnil である、と言える。つまり、v の 3 bit 目を 0 にしておけば、あとは全体が 0 であるかをチェックすれば偽であると言える。これを実装するのが (v & ~Qnil) == 0 という式である。
なぜ論理式にするか、というと、分岐が1個減って、もしかしたらちょっと速くなるかも、ということで、こういう式になっている。
ちなみに、gcc では、最適化オプションによって、素直に (v == Qnil || v == Qfalse) と書いても (v & ~Qnil) == 0 と同じコードが出力される。賢い。clang では、真面目に2回チェックしていた。
