GC本を読む ~第1章~

プログラミング Garbage Collection

ふとGarbage Collectionについて気になって調べていた所，ガベージコレクションのアルゴリズムと実装という本がとても参考になるという情報を得たので買ってみました． 買った後に550ページにも及ぶ超大作であることに気がついたのですが，まぁ買ってしまったし，全体をザーッと眺めた感じとても丁寧に説明している印象を受けたので，じっくり読んでいこうと思います．

ただ，こういう分厚い本はなんだかんだ最後まで読まずに積んでしまうのが世の常です．なので，最後まで読むぞという強い気持ちと，もし途中で諦めたとしても，また日が経ったときに続きから読み始めやすいように，こうして1章ごとにブログにまとめていこうと思い筆を取りました．

自分用のメモなので，途中自分が考えたログを残していたり，明らかに知っている内容のメモは飛ばしていたりします．

第1章 GCを学ぶ前に

GCの話を進めていく上で重要になってくる用語や基礎的な理論について説明している章．

オブジェクトやヒープ，ミューテータについて

用語 説明
オブジェクト アプリケーションによって利用されるデータの塊
ヘッダ オブジェクト内に埋め込まれた，オブジェクト自体の情報を保持する部分
フィールド オブジェクトの利用者がアクセス可能な部分
ミューテータ オブジェクトを生成したりポインタを更新したりする機能
HEAP_SIZE ヒープ領域のサイズ
$heap_start ヒープ領域の先頭アドレスを参照するポインタ
$heap_end ヒープ領域の終端の次のアドレスを参照するポインタ

データの塊であるオブジェクトは，そのメタ情報1を保持するヘッダとデータ自体を保持するフィールドによって構成される． オブジェクトの種類って何ぞやと思ったが，後の章で説明されそうな雰囲気．

フィールドはポインタと非ポインタの2種類に分類される．C言語とかのアレ． (でもポインタだって結局メモリの番地を格納するデータ型じゃんって思ったが，3秒考えて，GCだから参照先のデータの生存を考えなきゃいけないし，別種類で扱ったほうがスマートか，そりゃそうだと気づいた．)

この本のアルゴリズム編では1フィールドのサイズを1ワードとしている．オブジェクトの中にフィールドは複数存在可能．

さて，このフィールドがポインタか非ポインタかを判別するというのは少し工夫が必要らしい．これは第6章の保守的GCで詳しく述べられるようだ． とりあえず扱っている言語処理系はポインタかどうかを判別可能であるという前提で話が進む．

このヒープ領域内に配置されたオブジェクトの管理を行う仕組みのことをGCという． (てっきり使用済みのメモリの廃棄だけかと思っていたが，確保なども含めてGCというのか)

ミューテータから参照できるオブジェクトを生きていると表現し，逆に参照できないオブジェクトを死んでいると表現する． GCはこの死んでいるオブジェクト(ゴミ)を廃棄して次のオブジェクトの割り当てに活用する． (ミューテータは生成したオブジェクトのアドレスを辿る連結リスト的なのを持っているっぽい．どうやってそれを更新していくかはまだ謎．)

アロケーションやチャンク，ルートについて

アロケーション時，ミューテータは作りたいオブジェクトのサイズをアロケータに要求する．アロケータはヒープ領域の空き領域から要求を満たすものを見つけてミューテータに返す． 空き領域が足りない場合はGCが行われ，不要なオブジェクトが開放される．それでも足りない場合はエラーを返すかヒープ領域を拡張する． (拡張方法についてこの章では詳しく書いていない)

この空き領域のことをチャンクと呼ぶ．初期状態ではヒープ領域は1つの大きなチャンクで湿られている．アロケーションとGCを繰り返していくと，このチャンクが飛び飛びに存在していくことになる．(これをどう対処していくかがGCアルゴリズムの腕の見せどころ？)

ミューテータはヒープ領域のオブジェクトを連結リスト的に辿っていくことができるため，その先頭アドレスを指すルートが存在する．コールスタックやレジスタ，グローバル変数領域がミューテータにとってのルートにあたるらしい． (関数内で静的に作ってあるポインタ変数に動的にメモリを確保しても，どこかのグローバル変数領域がその参照を持っているということ...??)

評価項目

GCのアルゴリズムの性能は次の4つの項目によって評価される．

項目 詳細
スループット 単位時間あたりの処理能力
最大停止時間 GCによってミューテータの実行が停止する時間の最大値
ヒープ領域の使用効率 -
参照の局所性 参照関係のあるオブジェクト同士をヒープ領域上でどれだけ近く配置しているか

スループットは画一的に評価できない．(大体こういうのは何かしらとトレードオフあるイメージ)． 各GCアルゴリズムによってこのスループットがどういう意味を持つのかは後の章で語られそう．

参照局所性を高めるとキャッシュメモリに読み込まれる確率が上がるので，レイテンシが下がるというやつ．(プログラムの最適化とかでこの話はよく聞く)

今回は以上．

所感

大学の授業で似たような話は既に習ったので特に詰まることはなかった．気になった部分もこの先の章で詳しく語られそう．

読みながら，言語のRuntimeがやるべき部分とハードウェアがやるべき部分の境目がイマイチ分からないなと感じたが，監修者まえがきで．

GC をサポートするハードウェアはほとんどないのが現実です。ハードウェアサポートすれば確実に性能が上がるのに残念です。

という言葉を見たので，ほとんど言語処理系が頑張っているんだろうなと思う．

次回

taxio.hatenablog.com

  1. オブジェクトのサイズや種類↩

Goの静的解析ライブラリでDSMを求めてみる

Go Golang 静的解析 プログラミング

あくあたん工房 Advent Calendar10日目の記事です．taxioが頑張ります．

この記事ではGoの静的解析ライブラリを使ってみながら，簡単なDSMを求める方法を紹介していきます．

Goで静的解析

Goは素晴らしい言語なので，標準ライブラリで静的解析が十分できたりします．1

最近どうやらanalysisというライブラリがgo/toolsに追加されたらしいですが，まだちゃんと情報を追えてません(すいません)．Go Advent Calendarの方で強い人が書いてくれるでしょう．

今回はASTに関する型や関数を提供しているgo/ast，構文解析の機能を提供しているgo/parserを使っていきます．

ASTの生成に使うgo/parserにはいくつかの入力段階が存在し，

  • 式ならparser.ParseFile()
  • ファイルならparser.ParseFile()
  • ディレクトリならparser.ParseDir()

などを使います．

また，ファイルとディレクトリのパースにはパースの対象をどこまでするかなど，いくつか設定を変えられるparser.Modeを渡すことができます．2

parser/Parse*で作成したASTを走査したい場合は，自分でゴリゴリ再帰関数を書いていくのもいいですが，ast.Inspect(),ast.Walk()という深さ優先探索をしてくれる便利な関数があるのでそれを使いましょう．

ただ，これらはin-orderでの深さ優先探索となっています．post-orderやpre-orderでの深さ優先探索をしたい場合はgolang.org/x/tools/go/ast/astutilにあるApplyを使うといいかもしれないです．3

DSMを求めてみる

ここからは実際に簡単なDSMを求める静的解析タスクを行っていきます．

Dependenct Structure Matrix(DSM)とは，システムのモデルの品質を確認する手法の一つです．4

各モジュールの依存を有向グラフと見て，隣接行列で表現します．

本来は製品開発プロセスを最適化するためのメトリクスなのですが，ソースコード解析にも応用できるという論文が出ているので，それを参考にGoで簡単に算出していこうと思います．5

例えば以下のようなすごく簡単なレイヤードっぽいコードがあったとします．

package main

import (
    "fmt"
)

func presen() {
    app()
}

func app() {
    domain()
}

func domain() {
func infra() {
    fmt.Println("Aquatan!")
}

このコードの関数レベルの依存を解析してみます．

解析用のソースコードはこんな感じです．

package main

import (
    "fmt"
    "go/ast"
    "go/parser"
    "go/token"
    "log"

    "gonum.org/v1/gonum/mat"
)

type Func struct {
    Name  string
    Calls []string
}

func main() {
    fset := token.NewFileSet()

    f, err := parser.ParseFile(fset, "layered.go", nil, 0)
    if err != nil {
        log.Fatal(err)
    }

    funcs := []Func{}
    ast.Inspect(f, func(n ast.Node) bool {
        funcDecl, ok := n.(*ast.FuncDecl)
        if !ok {
            return true
        }

        funcs = append(funcs, Func{
            Name:  funcDecl.Name.Name,
            Calls: parseChild(funcDecl),
        })

        return true
    })

    m := toMat(funcs)
    fa := mat.Formatted(m, mat.Prefix(""), mat.Squeeze())
    fmt.Printf("%v\n", fa)
}

func parseChild(parent ast.Node) []string {
    calls := []string{}

    ast.Inspect(parent, func(n ast.Node) bool {
        callExpr, ok := n.(*ast.CallExpr)
        if !ok {
            return true
        }

        ident, ok := callExpr.Fun.(*ast.Ident)
        if !ok {
            return true
        }

        name := ident.Name
        calls = append(calls, name)

        return true
    })

    return calls
}

func toMat(funcs []Func) mat.Matrix {
    funcList := map[string]int{}
    for i, v := range funcs {
        funcList[v.Name] = i
    }

    ad := mat.NewDense(len(funcs), len(funcs), nil)
    for i, v := range funcs {
        for _, c := range v.Calls {
            ad.Set(i, funcList[c], 1)
        }
    }

    return ad.T()
}

出力はこうなります．

go run main.go

⎡0  0  0  0⎤
⎢1  0  0  0⎥
⎢0  1  0  0⎥
⎣0  0  1  0⎦

参照がある場合は1，無い場合は0としています．各層が一つ下の層しか参照していないというのが見てとれますね．

処理の流れとしては，

  1. parser.ParseFile()によって出力されたASTの根(*ast.File)を走査
  2. 関数の宣言(*ast.FuncDecl)が見つかったらその下に続く部分木を走査
  3. 関数またはメソッド呼び出し(*ast.CallExpr)を見つけたら記録していく
  4. 全ての関数宣言に対して処理を終えるまで2,3を繰り返す
  5. gonumで隣接行列を作成

という感じになっています． 簡単にファイル内の依存関係を表した隣接行列が生成できましたね！！

今回はファイル内の関数の依存関係を出しましたが，プロジェクト単位で算出させるようなツールにすれば品質チェックのメトリクスに使えそうです！

analysisを使ってもう少しいい感じに静的解析したい...(勉強中)

おわりに

Goの標準パッケージを使って簡単な静的解析を行っていきました．新作スマブラの誘惑に負けずにちゃんと記事を公開できてよかったです．

あくあたん工房およびそふらぼでは，Goを書きたい人・静的解析をしたい人を常に(僕が個人的に)大募集しています！ 在校生の人はぜひ！話だけでも！

参考文献

tenntennさんやmotemenさんの資料を大変参考にさせていただきました．

  1. 静的解析を始めよう - Gopherを探せ！Goと静的解析↩

  2. parser - GoDoc↩

  3. 木構造 (データ構造) - Wikipedia↩

  4. Design structure matrix - Wikipedia↩

  5. Using dependency models to manage complex software architecture↩

MacでCP2102を認識

概要

ESP32 開発ボードを使おうと思ったけど，なぜかシリアルポートとして認識してもらえなかった問題を解決した．

環境は

やったこと

まず公式からドライバをインストールした．

システムレポートのハードウェア->USBを確認すると，CP2102 USB to UART Bridge Controllerが認識されていたが，Arduino IDEのシリアルポートからは見えない． /dev以下にもcu.SLAB_USBtoUARTの文字はなかった．

調べてると，それっぽい解決法があった．

システム環境設定->セキュリティとプライバシーから許可を押したらシリアルポートとして認識してくれた．

最初は許可ボタンがなかったけど，再起動とかしてたら現れた． Macのここらへんの仕様がよくわからない...