1

64bit CPU環境のRUBY処理系での軽量な浮動小数点数表現

東京大学大学院 情報理工学系研究科 創造情報学専攻

笹田耕一

agenda
2

実装
概要

背景問題点

関連研究

提案
方式と評価

done?

まとめ

概要
3

問題点

 Rubyの浮動⼩数点数計算は遅い

 主なオーバヘッドはメモリ管理（Alloc + GC）

解決策 64bit CPUにおいて、64bit倍精度浮動⼩数点数（Floatオブジェクト）をタグ付きで表現 精度を犠牲にしない⽅式
 埋め込み⽅を⼯夫して軽量な埋め込み結果 速くなった！
 実装も容易やった！

4

背景
Rubyのオブジェクト表現
RubyのオブジェクトはVALUE型
VALUE型はヒープ上の構造(5 words)へのポインタ* sizeof(word) == sizeof(void *)ヘッダにタイプ、クラスを記録
DATA1-3はTypeによって使い⽅が異なる
VALUE(Object ID)

HEAP
HEAD- Type- Class- etc

DATA1
DATA2
DATA3

背景
例：文字列オブジェクトの場合
5

HEAP
HEAD
- T_STRING- String
- etc

VALUE

PTR
LEN（長さ）

AUX

文字列の実体6

背景
VALUE埋め込みオブジェクト
整数など、⼤量に出てくるオブジェクトはVALUE埋め込みオブジェクトとして表現
ポインタなら、下位２ビットは0のはず→ 0でないVALUE型の値は特別扱い
VALUE埋め込み（タグ付き）オブジェクト例 Fixnum（下位１ビットが1）

 Symbol（下位8ビットが0x0e）

よく使われる⼿法
 ○ ⽣成が速い
 × 制限が多い7

背景
Rubyの浮動小数点数表現
Rubyの浮動⼩数点数→Floatオブジェクト
ヒープに割り当てられる倍精度浮動⼩数点数（IEEE754/double）
VALUE

HEAP
HEAD
- T_FLOAT- Float- etc

IEEE754
Doublenull問題点
メモリ利用効率864bit CPUの場合

32bit CPUの場合
HEADHEAD- T_FLOAT- Float- etc- T_FLOAT- Float
- etc

VALUE
4B x 6W =24バイト利用
16バイトの無駄

IEEE754
Double-VALUE

IEEE754
Double8B x 6W =48バイト利用40バイトの無駄-問題点
実行効率（こちらが本題）
9

数値計算→⼤量の⼀時的なFloatオブジェクトを⽣成
数値計算のオーバヘッドの⼤半はメモリ管理
 オブジェクト⽣成のオーバヘッド オブジェクト回収（ＧＣ）のオーバヘッド

問題点
トイプログラム
10

i = 0; f = 0.0
while i<30_000_000
i += 1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
end

問題点
トイプログラムの実行時間内訳
11

型のある言語では不要なコスト

メモリ管理

これは許せない

実際の計算
oprofileを利用して算出Linux 2.6 (x86_64), Xeon
Ruby 1.9.0 での実行時間内訳

他評価環境は予稿集を参照

関連研究
12関連研究 Ruby の話

 NArray → Float しか扱わない配列で計算 [12]
 Inline Ruby → C 関数で記述 [2] ⼀般的な話

 プログラム・型解析によりUnbox化 [7], …
 正当派

 解析が絶望的なRubyでは困難

 NaN に⾊々埋め込み（Lisp, Lua）

 メモリ番地によってヘッダを不要に [13]
 必要なメモリ消費量を削減

 実⾏時オーバヘッドの解決になっていない

13

復習IEEE 754 倍精度浮動小数点数
64bit 倍精度浮動小数点数b63

b62-b52b51-b0s: 符号（1bit）

e: 指数部（11bit）

m: 仮数部（52bit）

検討
VALUE埋め込みオブジェクトにするには？
14VALUE埋め込みオブジェクトにすれば(unboxed)
メモリ管理オーバヘッド不要
64ビットCPUなら埋め込めそう
みんなもう→ 64bit CPUを前提に64bit CPU
最低、タグを埋め込む 1 bit が必要だよね？
 仮数部（52bit から 1bit）？
 精度が犠牲に Self, Smalltalk の処理系で利⽤したらしい（裏取れず）

 指数部（11bit から 1bit）？
 表現可能な範囲が犠牲に 符号は駄⽬（当たり前）

提案手法
精度を犠牲にしないVALUE埋め込みFloat15

仮数部から1bit捻出
ただし、範囲外は従来通りヒープに保存→ 精度および範囲を制限しない
仮数部 e の範囲（0 〜 2047）から捻出

 だいたい、01000000000b〜10111111111b あたりをよく利⽤（）

 数値計算で範囲外の数はあまり出現しない（らしい）→ 現実的な解 この範囲だったらタグをb61に埋め込み
 そうでなければ、ヒープに保存

 NaN, ±Inf はヒープに保存される範囲に存在 ブログでこの⽅法⾃体は紹介されていたらしい [3]提案手法
実際のプログラム161) eの範囲チェック（512〜1535）
2) 数値のエンコード（埋め込み）
3) 数値のデコード（値の取り出し）提案手法
タグ付き表現可能かのチェック
17

e: 10000000000b〜01111111111b
よく⾒ると b62 != b61 だったら埋め込み可
Rubyでは、タグは下位ビットに埋め込む→ 3bit 左に rotate すればよい
下位ビットの演算に持ち込む（64bit計算不要）
b63 b62 b61 b60 … b0 → 3 bit rotate
b60 … b0 b63 b62 b61
このとき、下位2bitが異なれば埋め込み可能
埋め込めるときには b61 を 1 に（タグ）値を取り出すときは逆提案手法
エンコードのコード
18

VALUE rb_float_new(double dbl) {VALUE v1 = BIT_DOUBLE2VALUE(dbl);
VALUE v2 = BIT_ROTL(v1, 3);if ((v2 + 1) & 0x02) // 下位2bitの判定
return v2 | 0x01;// タグ埋め込み
else {
if (dbl == 0) // 0 の場合
return ruby_float_zero;else// ヒープから取り出し
return rb_float_new_in_heap(dbl);
}}

提案手法
デコードのコード19

double RFLOAT_VALUE(VALUE v) {if (v & 1) {VALUE v1 = v ^ ((v >> 1) & 1);
VALUE v2 = BIT_ROTR(v1, 3);
return BIT_VALUE2DOUBLE(v2);}elsereturn RFLOAT(v)->float_value;
}

実装
20

Ruby 1.9.0-0 に実装
実装の変更点はごく⼀部（実装が容易）

 Float の⽣成、Float からdouble値の取り出し Fixnum の範囲を犠牲に（63bit → 61bit）
 Fixnum の実装に依存していた部分の変更
 特化命令を埋め込みFloatに対応

仕様の変更点もごく⼀部（ほぼ影響なし）
 Floatに特異メソッドが追加不可

 FloatのオブジェクトIDの仕様が変更

評価
トイプログラム実行時間の改善
21

9メモリ管理の時間削減
9エンコード・デコード
実行時間は見えない・ビット演算増・メモリ間接アクセス減

22

評価（マイクロベンチマーク）
Ruby 1.9.0 と比較した速度向上比

ベンチマークは Comp. Lang. Shootout [4] より

評価
他言語との比較23

他⾔語で下記と同じようなコードで評価
ただし、C/Java では変数に volatile 付加
i = 0; f = 0.0
while i<30_000_000
i += 1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
f += 0.1; f -= 0.1
end評価
他言語との比較（実行時間）
24

欠点・課題25⽋点

 64bit CPUでしか使えない ⼿元のラップトップで追加の評価が出来ない…

 整数計算が若⼲遅い(下位１ビットを譲ったため)

 具体的には「２つのオブジェクトが整数か？」というチェックの実⾏時間の増加（トレードオフ）

課題：特化命令で遅くなる場合がある 何らかの⼯夫が必要

増えた！

「＋」の特化命令(1) 整数かチェック(2) 埋め込みFloatかチェック（詳細略）(3) 文字列かチェック(4) 一般的な「+」メソッド呼び出し

方式比較
26

32bit CPUでは優等⽣的shiro⽅式
64bit CPUでは単純なko1⽅式

方式比較
実行効率
メモリ効率
可搬性

(1) shiro
○○○

開発

大変

(2) ko1◎◎×- 64bit CPU- IEEE754 表現
簡単まとめ27

64bit CPU上で精度や範囲を犠牲にしない軽量なFloatオブジェクト表現⼿法を提案
 単純な発想 開発は容易

Rubyで実装・評価

 実⾏効率改善を確認

 Rubyの次のリリースに取り込む予定

他⾔語でも多分適⽤可能おしまい28

ご静聴ありがとうございました。
謝辞
発表した⼿法はRubyコミュニティ、とくに三浦英樹⽒との議論を参考にしております。
この場を借りてお礼申し上げます。
東京⼤学⼤学院 情報理⼯学系研究科 創造情報学専攻
ささだこういちko1@atdot.net