GCと1bit 2018-06-24 GC # GCと1bit ---------------------- [TCFMミートアップ](https://techplay.jp/event/680870) <!-- .slide: class="center" --> === # About Me ---------  <!-- .element: style="position:absolute;right:0;z-index:-1" width="20%" --> * κeen * [@blackenedgold](https://twitter.com/blackenedgold) * Github: [KeenS](https://github.com/KeenS) * [Idein Inc.](https://idein.jp/)のエンジニア * Lisp, ML, Rust, Shell Scriptあたりを書きます * 言語処理系が好き === # GCと(メタ)情報 -------------- * レジスタ/スタック上の値のpointer or not * Mark and Sweepのマーク * ヒープ上オブジェクトの「どこにポインタがいるか」 これらを節約する話 === # レジスタ中のポインタ ------------- * レジスタ上の値がポインタか数値か + GCのrootsetなので判断が必要 + 1bitの情報量が必要 * 多くはLSBをタグに使う + ポインタは0 + 4バイトアラインメントされてると自然にそうなる + 数値は1にする - 数値が31bit/63bitになる - タグを外して計算して戻すので遅い * bit stealしない方法は？ === ## レジスタ分別 --------------- * レジスタを半分に分ける + 片方はポインタ用 + もう片方は値用 * 物理的に1bit取らなくても1bitの情報量が確保できる * ただしレジスタが多いアーキじゃないと死ぬ === # Mark Bit ---------- * マーク済みかどうかのメタデータ + 1bitの情報量 * 素朴にはセルのメタデータに1byte確保 ``` +---+-------+---+-------+-- | 0 | ... | 1 | ... | +---+-------+---+-------+-- +---+-------+---+-------+-- | 1 | ... | 0 | ... | +---+-------+---+-------+-- ``` * 1bitに1byte？ * 1byteって中途半端では？ + 4byteアラインメントすると3byteのpadが入るのでは === ## BitMap --------- * MarkBitだけを集めて効率化 ``` +------+-------+-------+-- | 0110 | ... | ... | +------+-------+-------+-- +-------+-------+-- | ... | ... | +-------+-------+-- ``` * 省スベース * キャッシュ効率がいい * bit演算で扱える * allocatedフラグも同じ仕組みで出来る === ## BitMap --------- * どうやってオブジェクトからマークを探す？ * ページを $2^n$ バイトアラインメント * オブジェクトアドレスの下位 $n$ bitをクリア * いつでもページの先頭に飛べる ``` 0xab00 0xab08 +------+-------+-------+-- | 0110 | ... | ... | +------+-------+-------+-- +-------+-------+-- | ... | ... | +-------+-------+-- ``` === # オブジェクト中のポインタ<!-- .element: style="font-size: calc(var(--title-font-size) * 0.8)"--> ----------------------- * オブジェクトをマークするときにどこにポインタがあるか？ ```standard-ml type t = {a: string, b: int, c: int list} ``` ↓ ``` +--------+ | 20byte | +--------+ ``` === ## Type Id ---------- * Typeデータをランタイムにも持っておき、メタデータにIDを付ける ``` {1 = {a: string, b: int, c: int list}} +------+--------+------+--------+-- | id=1 | 20byte | id=1 | 20byte | +------+--------+------+--------+-- ``` * 素直 * 動的型付言語やオブジェクト指向言語なら自然 * リフレクションに使える * GCにしたら少し遠回り === ## Big Bag of Pages ------------------- * ヒープページ全体で1つの型のみを扱う ``` {1 = {a: string, b: int, c: int list}} +------+--------+--------+-- | id=1 | 20byte | 20byte | +------+--------+--------+-- ``` * ページが無駄になるかも？ * アロケーションが遅いかも？ === ## 双方向レイアウト ------------- * オブジェクトのフィールドをポインタと値に分ける * ポインタをオブジェクトポインタの前、値を後に置く + 物理で1bit使わなくても情報を持てる ``` +-- ptr v +-------+---+ | a | c | b | +---+---+---+ ``` === # まとめ -------- * 情報の持ち方は色々あるよ * ランタイムの表現も工夫が色々あるよ * ランタイムとデータ表現面白いよ