実行时のデータ型の表现手法
26 likes6,746 views
実行時にデータ型を判別するためのデータ表現 基本的な技法(オブジェクトのヘッダ, tagged pointer, BIBOP)
![BIBOPでの型判別基本操作
?? ページ管理表に型情報を入れておく
?
?? ポインタ値
?x
?からヒープのbaseアドレスを引き，
右にシフトしてページ管理表を引く
?
ヒープのbase
ページ0
x
?-?‐
?base
?
?
?
?
?
?
?
?
?
?
?
?1
ポインタx
ページ番号
オフセット12bit
?
?
?
?
?
?
?
?
?
?
?
?2
ページ管理表
0
?
1
? 補注：文献[3]のマシンは1ワード36bit，
?
?
?
?
?
?
?
?
?
?
?
?
?3
2
? アドレスはワード単位18bitなので，
?
?
?
?
?
?
?
?
?
?
?
?
?4
3
? ?? １ワードにポインタ２個が入る
?
4
?? ポインタ中のbitは全く空きがない
?
（後述のポインタタグには向かない）](https://image.slidesharecdn.com/tags-121123015227-phpapp02/85/-11-320.jpg)
![参考文献
4.? R.
?Kent
?Dybvig,
?David
?Eby,
?Carl
?Bruggeman,
?Don't
?Stop
?the
?BIBOP:
?
Flexible
?and
?E?cient
?Storage
?Management
?for
?Dynamically-?‐Typed
?
Languages.
?Indiana
?University
?Computer
?Science
?Department
?
Technical
?Report
?#400,
?March
?1994
?
hap://www.cs.indiana.edu/cgi-?‐bin/techreports/TRNNN.cgi?trnum=TR400
?
5.? 近山 隆 U`lispシステムの開発 IPSJ
?Journal
?24(5),
?599-?‐604,
?
1983-?‐09-?‐15
?Informa`on
?Processing
?Society
?of
?Japan
?
hap://ci.nii.ac.jp/naid/110002723809
?
上位ビットポインタタグを用いたLispシステム
?
6.? J.
?P.
?Fitch,
?A.
?C.
?Norman
?Implemen`ng
?LISP
?in
?a
?high-?‐level
?
language,
?Sonware:
?Prac`ce
?and
?ExperienceVolume
?7,
?Issue
?6,
?
pages
?713–725,
?November/December
?1977
?
[5]から，上位ビットポインタタグを用いた先行システムとして参照されて
いる
?](https://image.slidesharecdn.com/tags-121123015227-phpapp02/85/-25-320.jpg)
![参考文献
7.? Adele
?Goldberg
?and
?David
?Robson,
?Smalltalk-?‐80:
?The
?Language
?
and
?its
?Implementa`on,
?Addison
?Wesley,
?1983.
?
?
hap://wiki.squeak.org/squeak/64
?
下位１ビットのタグを用いている
?
8.? Glenn
?S.
?Burke,
?George
?J.
?Carreae,
?and
?Christopher
?R.
?Eliot.
?NIL
?
Reference
?Manual
?corresponding
?to
?Release
?0.286.
?Report
?MIT/
LCS/TR-?‐311,
?January
?1984
?
hap://www.sonwarepreserva`on.org/projects/LISP/MIT/Burke_et_al-?‐
NIL_Reference_Manual_0286-?‐1984.pdf/view
?
下位2ビットのタグを用いていると[9]で解説されている処理系NIL(New
?
Implementa`on
?of
?Lisp)のマニュアル．データ表現の解説はない．
?
9.? Richard
?P.
?Gabriel,
?Performance
?and
?Evalua`on
?of
?Lisp
?Systems,
?
The
?MIT
?Press,
?August,
?1985
?
NILを含むさまざまなLispシステムの実装の概要と，有名なGabriel
?
Benchmarkによる性能評価結果
?](https://image.slidesharecdn.com/tags-121123015227-phpapp02/85/-26-320.jpg)
![[db tech showcase Tokyo 2015] B12:カラムストアデータベースの技術と活用法 by 日本電気株式会社 田村稔](https://cdn.slidesharecdn.com/ss_thumbnails/dbts-tokyo-2015b12infoframe-databoosternec-150618053539-lva1-app6891-thumbnail.jpg?width=560&fit=bounds)
More Related Content
Similar to 実行时のデータ型の表现手法 (20)
Recently uploaded (11)
実行时のデータ型の表现手法
- 1. 実行时のデータ型の表现手法 ? Ver. ?1.02 ? 2012-?‐11-?‐24 前田敦司
- 2. このスライドの目的 ?? 64bit ?ARMアーキテクチャのTagged ?Pointer機 能が話題になった ? ?? よい機会なので，実行時にデータ型を判別す るためのデータ表現をまとめておこうと思った ? ?? ホットなトピックというより，大昔からの，いわ ば教科書的な話題だが，教科書にはあんまり 載ってない ? ?? 手法の選択にはGCやメモリ管理との相互作 用も絡むのだが，ほぼバッサリ省略
- 3. 実行時になぜデータ型を判別する ? 必要があるのか？ ?? 動的型付き言語 ? –? 変数に静的な（＝実行前の?コンパイル時の）型 が付いていない ? –? 実行するまで，どんな型のデータが入るかわから ない ? ?? 多相型とGC ? –? 整数のリストも文字列のリストも受け取れる関数 の引数…GCが，ポインタを追跡する手がかり
- 4. 実行時の型判別の基本操作 ?? is_type(x, ?t) ? ? –? データxの型はtか？ ? –? 真偽値を返す．エラーは起きない． ? ?? typecase(x) ?case ?t1=>…; ?case ?t2=>…; ?… ? –? データｘの型に応じて多方向分岐 ? –? エラーは起きない ? ?? 型エラーの動的チェック(check_type) ? –? データxが期待した型(たとえば，整数加算に対して整 数オペランド)なら正常に演算を行う ? –? そうでないならエラー
- 5. 前提：データ表現の一様性 ?? 動的データ型や多相型では，一般に，すべて のデータが一様に表現されている必要がある ? –? 変数の記憶領域はすべて同じサイズ ? –? 配列やリストの要素も同じサイズ ? –? データ型の表現法も標準化 ? –? boxed表現などという(cf. ?boxing, ?unboxing) ? ?? 効率を考えると，サイズは１ワード（CPUが自 然に扱える特定のサイズ)に揃えるのが便利 ? ?? １ワードに収まらないデータは？
- 6. データサイズの一様化とポインタ ?? すべてのデータのサイズを１ワードに揃える 手法の例(仮にオブジェクトタグと呼ぶ）： ? –? 変数や配列にはポインタを入れる ? –? 実際のデータ本体は，別の場所（ヒープ）に置く ? –? 本体のヘッダに，型やサイズの情報を入れる ? 型?サイズ 変数ｘ データ 変数y 型?サイズ データ
- 7. オブジェクトタグでの基本操作 ?? is_type(x, ?t) ? –? xのポインタをたどり，ヘッダの型コードを読みだし てtと照合 ? ?? typecase(x) ? –? xのポインタをたどり，ヘッダの型コードを読みだし て多方向分岐(テーブルジャンプ等) ? ?? check_type ? –? is_type(x, ?t)で型を確認してから演算を実行 ?
- 8. オブジェクトタグの欠点 ?? メモリのオーバーヘッドが大きい –? ポインタとヘッダの領域がオーバーヘッドとなる ? –? 本体が１ワードなら，計３ワードが必要 ? ?? 速度的なオーバーヘッド ? –? 整数をこの形式で表すと，たとえば加算は… ? ?? 左辺のポインタをたどり，ヘッダを読んで整数であることを 確認し，本体の整数データを読み出す ? ?? 右辺も同様 ? ?? 加算命令の結果にヘッダを付けてヒープにアロケートし，そ の領域へのポインタを結果とする…ゴミが大量に出る ?
- 9. 改良手法1：イミディエイトデータのアド レスへのマップ ?? たとえば値の小さな整数などを，ヒープ以外 のアドレスを指すポインタにマップする 例) ? ポインタ値pがboundaryより小さい時，整数 boundary boundary-?‐pを表していると見なす． ? ? ?? メモリの節約：小さい整数は１ワード ? ?? 速度の節約：整数演算は速くなる ? ヒープ ?? その他のデータの操作には「ヒープを指して いる事」を確認するオーバーヘッドがかかる
- 10. 手法２：BIBOP ?? Big ?Bag ?of ?Pagesの略;たぶんビーバップと読む ? ?? ヒープを2のべき乗サイズ(たとえば4KiB)の ページに分ける ? ?? 1つのページには，１つの型のデータだけ入 れる ページ0 ヒープのbase ? ? ? ? ? ? ? ? ? ? ? ?1 整数データが入るページ ? ? ? ? ? ? ? ? ? ? ? ?2 浮動小数点数データが入るページ ? ? ? ? ? ? ? ? ? ? ? ?3 リストデータが入るページ ? ? ? ? ? ? ? ? ? ? ? ?4
- 11. BIBOPでの型判別基本操作 ?? ページ管理表に型情報を入れておく ? ?? ポインタ値 ?x ?からヒープのbaseアドレスを引き， 右にシフトしてページ管理表を引く ? ヒープのbase ページ0 x ?-?‐ ?base ? ? ? ? ? ? ? ? ? ? ? ?1 ポインタx ページ番号 オフセット12bit ? ? ? ? ? ? ? ? ? ? ? ?2 ページ管理表 0 ? 1 ? 補注：文献[3]のマシンは1ワード36bit， ? ? ? ? ? ? ? ? ? ? ? ? ?3 2 ? アドレスはワード単位18bitなので， ? ? ? ? ? ? ? ? ? ? ? ? ?4 3 ? ?? １ワードにポインタ２個が入る ? 4 ?? ポインタ中のbitは全く空きがない ? （後述のポインタタグには向かない）
- 12. BIBOPの利点 ?? メモリ効率はオブジェクトタグよりずっとよい ? –? オブジェクトごとに型情報を保つ必要はない ? ?? 型判別操作の速度もそう遅くない ? –? メモリアクセス回数は１回のまま ? ?? 多種類の型の領域をかなり柔軟に管理できる ? ?? 速度オーバーヘッドは？ ? –? 小さな整数は，あらかじめ順序良く並べて割り当てて おけばアドレスと簡単にマッピングできる(ポインタを たどって普通に本体を取り出すこともできる）
- 13. 手法３：ポインタタグ ?? Tagged ?pointer…ポインタ内に型情報を埋め 込む ? ?? 観察：ポインタのすべてのビットが有効な情報 を表しているわけではない ? –? たとえば，最近のバイトアドレスマシンで，ワード 以上のサイズのデータを指すポインタは，下位の 2?3bitがたいていゼロ ? –? また，64bitマシンでも，アドレス空間はそんなに なかったりする(上位ビットは実際は使ってない) ? ?
- 14. ポインタタグ(Tagged ?Pointer)とは ?? ポインタ中の，使っていないビットに型情報を 埋め込む ? ?? 残りのビットで，データの値を表す ? –? ポインタの指すアドレス ? –? 文字や小さい整数等のイミディエイトデータ ? ?? メモリアクセスなしで型を判別できる事が多い ? ?? イミディエイトデータはヒープに割り当てずに すむ…メモリ効率，速度効率の向上 ?
- 15. バリエーション：ポインタの上位ビット にタグ ?? 例： ?IBM ?System ?360, ?Motorola ?MC68000等は， ポインタが32biｔだが，アドレス空間は24bitで， 上位8bitは無視される ? → ?上位8bitに型を表すコードを入れることができる ? ? 型タグ8bit 有効なアドレス24bit ? typecase操作：シフトして型タグを取り出す ? is_type, ?check_type：比較1回?2回 ?
- 16. 上位ビットポインタタグの比較 型タグ8bit 有効なアドレス24bit ?? 型タグが上位にあるので，シフトは不要で単 に大小比較すればよい ? ?? 符号なし，符号付き比較，型の包含関係を工 夫すれば，多くの場合１回の比較ですむ ?? たとえば「型タグが0x00か」の検査は， 「0x01000000より符号なし比較で小さいか」を 調べれば良い ?
- 17. 上位ビットポインタタグの例 タグの値 型 0x00 小さな整数 Lisp系言語での架空の ? 0x01 Bignum 整数 タグ値の例 ? 数値 ? 0x02 Float ?? 小さな整数は(符号 0x03 複素数 なしで良いなら)変 換なしで演算できる ? … … ?? 整数，数値，配列， 0x7d 多次元配列 １次元配列，文字 0x7e ベクター 配列 列，シンボル，リス ト，リストのノード等 0x7f 文字列 は１回の比較で判 0x80 シンボル 別できる ? 0x81 構造体 ?? (実際は，ベンチ マークでどの型を … … 優先するか決める) 0xfe 空リスト(nil) 0x? リストのノード リスト
- 18. 上位ビットポインタタグの得失 ?? 32bitワード，24bitアドレスの時代には，かな り多くのビットが型判別に使えた ? ?? オブジェクトタグよりメモリアクセスが少ないの は大きな利点 ? ?? 欠点 ? –? 上位bitを無視してくれるCPUでないと，ポインタア クセス毎に比較的大きなオーバーヘッドがかかる ? –? 無視してくれるCPUでも，数年するとアドレス空間 が足りなくなったりする(実際，そうなった)
- 19. バリエーション：ポインタの下位ビット にタグ ?? たとえば32bitのバイトアドレスマシン（１ワー ド４バイト)で，データオブジェクトのサイズが1 ワード以上なら，下位に2bit以上使わないビッ トができる ? –? 間接アクセス時に，インデックスでタグを打ち消す ことにより，マスクしないでアクセス可能 ? 例) ? ?リストのノード(CONS対)のタグが２進数01のとき ２つの要素を読み出すには，それぞれ ?p ?– ?1, ?p ?+ ?3 ? 番地を読み出せばよい
- 20. 下位ビットポインタタグの利点 ?? 小さな整数に下位 ?00 ?(2) ?のタグを割り当てると ? –? 30bit符号付き…加減算はマスクもシフトも不要 ? –? ワードのインデックスに使う際も便利 ? –? SPARCのtadcc ?(tagged ?add ?set ?condi`on ?code)命令は， オペランドの下位２ビットが00(2)でないとトラップを引 き起こす整数加算…check_typeの命令が不要 ? ?? CPUによっては，アラインされていないメモリアク セスをトラップできる(バスエラー等) ? –? タグ付きポインタアクセスのcheck_typeの命令が不要
- 21. 下位ビットポインタタグの得失 ?? is_type, ?type_case ? –? 下位ビットのみマスクして取り出す ? –? 上位ビット ポインタタグより少し手間 ? ?? check_type ? –? 前述のとおり，CPUによっては，事実上コスト無しで行 える場合がある ? ?? 使えるbit数が少ないのが欠点 ? –? 型判別のごく一部にしか使えない ? –? オブジェクトタグを併用する，可変長のタグにするな どの工夫が必要 ?
- 22. 下位ビットポインタタグの例 タグの値 型 架空の処理系の下位ビットポ 000(2) 小さな整数 インタタグの例 ? 001(2) その他の数 010(2) リストのノード ?? データオブジェクトは８バイ 011(2) シンボル ト境界に整列して割り付け 0100(2) 真理値 られるとする(3bitが空き) ? 01100(2) 空リスト 11100(2) 文字 ?? イミディエイトデータは，3bit 101(2) 文字列 より多くのタグを使える ? 110(2) 関数 ?? これ以外の型はオブジェクト 111(2) それ以外 タグで表現 ?
- 23. 64bit ?ARMのTagged ?Pointer機能 ?? ついったーでいろいろ教わったところによると ? –? 64bit ?ARMアーキテクチャのアドレス空間は48bit ? –? しかし，通常は64bitのポインタの上位16bitに，好 き勝手な値を入れられるわけではなく，0x0000か 0xFFFFでないとFaultが起きる ? –? Tagged ?Pointerを設定すると，上位8bitに好きな値 を入れられるようになる…らしい ? –? hap://www.arm.com/ja/?les/downloads/ ARMv8_Architecture.pdf ?(p.16)
- 24. 参考文献 1.? Fred ?W. ?Blair, ?James ?H. ?Griesmer, ?Joseph ?Harry, ?and ?Mark ?Pivovonsky. ? Design ?and ?Development ?Document ?for ?LISP ?on ?Several ?S/360 ?Opera`ng ? Systems. ?IBM ?Research, ?Yorktown ?Heights, ?New ?York, ?revised ?June ?24, ? 1971 ? hap://www.sonwarepreserva`on.org/projects/LISP/ibm/Blair-?‐LISP360.pdf/view ? 手法1の解説がある ? 2.? M. ?Nakanishi, ?C. ?Hishinuma, ?K. ?Yamashita, ?and ?T. ?Sakai. ?A ?Design ?of ?Lisp ? Interpreter ?for ?Minicomputers, ?Proceedings ?of ?the ?IFIP ?TC-?‐2 ?Working ? Conference ?on ?Sonware ?for ?Minicomputers, ?pp.89-?‐95, ?Lake ?Balaton, ? Hungary, ?September ?1975 ? これも手法１を使っていると伝え聞いているが，読んでいない ? 3.? Guy ?Steele, ?Jr. ?Data ?representa`on ?in ?PDP-?‐10 ?MACLISP. ?MIT ?AI ?Memo ? 421, ?Massachuseas ?Ins`tute ?of ?Technology, ?September ?1977. ? ? hap://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/ 19780016892_1978016892.pdf ? BIBOPを使った代表的処理系MacLISPのデータ表現の説明 ?
- 25. 参考文献 4.? R. ?Kent ?Dybvig, ?David ?Eby, ?Carl ?Bruggeman, ?Don't ?Stop ?the ?BIBOP: ? Flexible ?and ?E?cient ?Storage ?Management ?for ?Dynamically-?‐Typed ? Languages. ?Indiana ?University ?Computer ?Science ?Department ? Technical ?Report ?#400, ?March ?1994 ? hap://www.cs.indiana.edu/cgi-?‐bin/techreports/TRNNN.cgi?trnum=TR400 ? 5.? 近山 隆 U`lispシステムの開発 IPSJ ?Journal ?24(5), ?599-?‐604, ? 1983-?‐09-?‐15 ?Informa`on ?Processing ?Society ?of ?Japan ? hap://ci.nii.ac.jp/naid/110002723809 ? 上位ビットポインタタグを用いたLispシステム ? 6.? J. ?P. ?Fitch, ?A. ?C. ?Norman ?Implemen`ng ?LISP ?in ?a ?high-?‐level ? language, ?Sonware: ?Prac`ce ?and ?ExperienceVolume ?7, ?Issue ?6, ? pages ?713–725, ?November/December ?1977 ? [5]から，上位ビットポインタタグを用いた先行システムとして参照されて いる ?
- 26. 参考文献 7.? Adele ?Goldberg ?and ?David ?Robson, ?Smalltalk-?‐80: ?The ?Language ? and ?its ?Implementa`on, ?Addison ?Wesley, ?1983. ? ? hap://wiki.squeak.org/squeak/64 ? 下位１ビットのタグを用いている ? 8.? Glenn ?S. ?Burke, ?George ?J. ?Carreae, ?and ?Christopher ?R. ?Eliot. ?NIL ? Reference ?Manual ?corresponding ?to ?Release ?0.286. ?Report ?MIT/ LCS/TR-?‐311, ?January ?1984 ? hap://www.sonwarepreserva`on.org/projects/LISP/MIT/Burke_et_al-?‐ NIL_Reference_Manual_0286-?‐1984.pdf/view ? 下位2ビットのタグを用いていると[9]で解説されている処理系NIL(New ? Implementa`on ?of ?Lisp)のマニュアル．データ表現の解説はない． ? 9.? Richard ?P. ?Gabriel, ?Performance ?and ?Evalua`on ?of ?Lisp ?Systems, ? The ?MIT ?Press, ?August, ?1985 ? NILを含むさまざまなLispシステムの実装の概要と，有名なGabriel ? Benchmarkによる性能評価結果 ?