はじめに
Learn Ruby With the Edgecase Ruby Koansというものがあります。予め用意されているソースコードの空欄になっているところや空のメソッドやクラスを正しいコードで埋めて、テストを通しながらTDDのような形でRubyの文法や振る舞いについて学ぶものです。全部で282問あり、僕は完走に4時間近くかかりましたが、やってみて「あ、全然Ruby知らなかった」と思って大変勉強になったので、Ruby歴は長いけど、ちゃんとした書籍などを通して読んだことがない人なんかにとてもおすすめです。
さて、僕がそのRuby Koansで初めて知ったこととして、「小さい整数には固定のオブジェクトIDが振られている」というものがあります。これはVALUE埋め込みというそうなのですが、本稿ではそのVALUE埋め込み、特に浮動小数点数の埋め込みについて見てみようと思います。
オブジェクトIDとVALUE埋め込みについて
Rubyはすべてがオブジェクトですから、例えば整数リテラルなんかも全部オブジェクトです。
1.to_s # => "1"
このように「1」をレシーバにしてメッセージを送ることができます。
さて、RubyのオブジェクトにはすべてオブジェクトIDが振られています。例えば適当な文字列を作ってIDを表示させてみましょう。
"test".object_id # => 70171752071600
"test".object_id # => 70171743011980
同じ文字列であっても、毎回作成されているため、作るたびに異なるIDが振られています。このオブジェクトIDの実体は、オブジェクト構造体へのポインタになっており、object_id
はそれを64ビット整数として解釈して表示するものです。
さて、数字はどうでしょうか。
0.object_id # => 1
0.object_id # => 1
1.object_id # => 3
1.object_id # => 3
2.object_id # => 5
2.object_id # => 5
こちらは明らかに特別っぽいIDが振られており、かつ何度object_id
を呼んでもIDは不変です。Twitterで教えていただいたのですが、これはVALUE埋め込みと言って、オブジェクトIDに生の値を埋め込んでしまうことで処理速度を向上させる方法だそうです。
https://t.co/uiGE4xIQU9 のVALUE埋め込みの話ですね。意外と知られてないんですかね
— KOSAKI Motohiro (@kosaki55tea) 2018年8月6日
具体的には、
- 通常のオブジェクトのオブジェクトIDは、必ず4の倍数にする
- 整数については、ある程度の大きさまではオブジェクトIDに生の値を埋め込む。ただし、埋め込むのは2倍して1を足したものとする
ということをします。
これにより、IDの最下位ビットが立っていれば、整数が埋め込まれていることがわかるため、右に1ビットシフトすれば生値が得られます(符号ビットはなんかうまいことやるんだと思います)。
しかし、Rubyはいくらでも大きな整数を扱うことができます。したがって、どこかで生値埋め込みからオブジェクトに切り替えているはずです。実際、
((1<<62)-1).object_id # => 9223372036854775807
((1<<62)).object_id # => 70171747519460
と、62ビットあたりに境目があります。これは64ビットのうち、符号ビットが1ビット、下位1ビットが生値埋め込みフラグに使われるため、残りが62ビットだと理解できます。
浮動小数点数の埋め込み
埋め込みの最大値について
さて、処理速度を稼ぐために整数を埋め込んでいるのだから、浮動小数点数も埋め込んでいるだろう、という予想がつきます。実際、
(1.0).object_id # => -36028797018963966
(2.0).object_id # => 2
(3.0).object_id # => 18014398509481986
と特別っぽいIDになります。これらは何度呼んでも不変です。整数の時と同様に、非常に大きな値については生値埋め込みではなく、オブジェクトに切り替わると推定されます。実際、
1e77.object_id # => 9177515798576495322
1e78.object_id # => 70158934367180
と、微妙なところに境目があります。微妙というのは、IEEE754の64ビット浮動小数点数は1.797693e+308であり、1e77というのはそれに比べてかなり小さいからです。このあたり、「他のオブジェクトIDとかぶってはいけない」という制約から来ていそうです。
前置きが長くなりましたが、この浮動小数点数の埋め込みについて、ソースを見ずに、どのようになっているか推定してみましょう、というのが本稿の趣旨です。
埋め込みとオブジェクトの間
まずは、生値埋め込みとオブジェクトになる値の境目を正確にもとめてみましょう。手抜きの二分探索ではこんな感じになるでしょうか。
s = 1e77
e = 1e78
n = 0.0
old = n.to_s
while ((s+e)*0.5).to_s != old
n = (s+e)*0.5
if n.object_id.to_s.length == 14
e = n
else
s = n
end
old = n.to_s
puts old
end
実行するとこんな感じです。
$ ruby search.rb
5.5e+77
3.25e+77
2.125e+77
2.6875e+77
2.40625e+77
2.2656250000000002e+77
2.3359375e+77
2.3007812500000002e+77
2.3183593750000003e+77
2.3095703125e+77
(snip)
2.3158417847463237e+77
2.315841784746324e+77
2.315841784746324e+77の周辺に境目がありそうです。
浮動小数点数のビットダンプ
さて、生値とオブジェクトの境目のビットパターンを調べてみましょう。こんな感じでしょうか。
#include <cstdio>
void dump(double a) {
printf("%.16e\n", a);
char *b = (char *)(&a);
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (b[7 - i] & (1 << (7 - j))) {
printf("1");
} else {
printf("0");
}
}
}
printf("\n");
}
int main() {
dump(2.3158417847463236e77); //生値埋め込み
dump(2.3158417847463239e77); //オブジェクト
}
実行するとこんな感じです。
$ g++ dump.cpp
$ ./a.out
2.3158417847463237e+77
0100111111111111111111111111111111111111111111111111111111111111
2.3158417847463239e+77
0101000000000000000000000000000000000000000000000000000000000000
生値とオブジェクトの間に、かなりきれいなビットパターンの差がでてきました。
これを踏まえて、Rubyで、適当な浮動小数点数のオブジェクトIDのビットダンプを見てみましょう。
1e77.object_id.to_s(2)
#=> "111111101011101000101011111111010000110101011111111101011011010"
「1e77」のIEEE754におけるビットパターンはこんな感じです。
0100111111101011101000101011111111010000110101011111111101011011
二つを並べてみましょう。
# RubyのオブジェクトID
111111101011101000101011111111010000110101011111111101011011010
# IEEE754のビットパターン
0100111111101011101000101011111111010000110101011111111101011011
RubyのオブジェクトIDを右に3ビットシフトしてみましょう。
0111111101011101000101011111111010000110101011111111101011011010
0100111111101011101000101011111111010000110101011111111101011011
ビットパターンが一致しました。ここから、「Rubyは浮動小数点数の生値を左に3bitシフトして、2を足している」ということが想定されます。
生値との境目は、指数部の上位3ビットが「100」でなくなるところまで、という条件のようです。ここから、(doubleの最大値は1e308なのに対して)Rubyで埋め込む生値の最大が1e77まで、ということが決まっているのでしょう。
ここまでわかったところで、ソースを見て答え合わせ・・・をしようと思いましたが、見てもよくわかりませんでした。まぁ細かいところに抜けはあるかもしれませんが、おおまかには合ってるのでしょう。
まとめ
Rubyの生値埋め込み(VALUE埋め込み)について調べて見ました。オブジェクトIDは基本的にはポインタですが、最下位ビットが1なら整数、下位3ビットが010なら浮動小数点数と判断しているようです。
ちょっと試してみましょう。
def check(obj)
id = obj.object_id
if id & 1 == 1
puts "Integer"
elsif (id & 7) == 2
puts "Float"
else
puts "Others"
end
end
check(1) # => Integer
check(-1) # => Integer
check(1.0) # => Float
check(1e77) # => Float
check(1e78) # => Other
check("") # => Other
実行結果。
$ ruby check.rb
Integer
Integer
Float
Float
Others
Others
できてるっぽいですね。
ところでTwitterで教えていただいたリンクでは、true
のIDは「2」になっています。しかし、これでは2.0.object_id
とぶつかってしまいます。今調べて見ると
true.object_id # => 20
となっており、変更されたようです。ここから想像するに、もともとRubyは整数の埋め込みだけやっていて浮動小数点数の埋め込みはやっていなかったが、あとで浮動小数点数も埋め込むようになり、そのためにtrue
のオブジェクトIDを変更する必要があった、と推定できます。そう思って調べてみると、Ruby2.0でnil.object_idの値が4から8に変わった理由という記事を見つけました。この記事によると、Ruby 2.0より、浮動小数点数d
が
1.72723e-77 < |d| <= 1.15792e+77
のときに埋め込むようになった、とありますね。現在はその2倍まで埋め込まれているので、1ビット分仕様変更があったのでしょうか。
追記
コメント欄で参考リンクを教えていただきました。
笹田さんの日記経由で、Ruby処理系での軽量な浮動小数点数表現(スライド)。これによると、浮動小数点数の埋め込みをやったのは2008年、Ruby 1.9あたりからのようですね。タグのために指数部を2ビット使い、埋め込み条件は、正しくは「62ビット目と61ビット目が異なっていたら」だそうです。そんなん思いつかんわ!また、ビット「シフト」だと、情報が失われるので符号ビットとかどうするんだろと思ってたら、ビット「ローテート」が正しかったようです。うーむ、僕はまだ未熟でした・・・