Goのiotaの正体

Go Golang プログラミング

今までよく考えずに使っていのでメモ．

先日，会社のslackで以下のplaygroundがshareされた．

play.golang.org

雑に(0, 2, 4)かなぁと思いつつも(1, 5, 9)で無い確信もなかった． 実行してみると正解は，

A = 0
B = 2
C = 4

なるほど．

そもそもiotaってなんだっけ？とGoの仕様書を読みにいく．

golang.org

Its value is the index of the respective ConstSpec in that constant declaration, starting at zero.

なるほど，これって定数宣言の中の定数リストのindexだったのか． 今まで雑にiota使えばインクリメントされて〜みたいな意識だったので理解を改めた．

その上でさっきのコードや仕様に載ってるサンプルコードを読んでみるとなるほど確かに． そりゃそうなるわ．

const (
    bit0, mask0 = 1 << iota, 1<<iota - 1  // bit0 == 1, mask0 == 0  (iota == 0)
    bit1, mask1                           // bit1 == 2, mask1 == 1  (iota == 1)
    _, _                                  //                        (iota == 2, unused)
    bit3, mask3                           // bit3 == 8, mask3 == 7  (iota == 3)
)

改めて，他の言語仕様で培われた色メガネでGoの仕様を捉えてはいけないなと思った．

自戒を込めて．

味付け煮玉子を作る

あくあたん工房 Advent Calendar 2019 19日目

僕はラーメンが大好きだ．

大学の近くにはラーメン街1があり，友人に「ご飯行こうぜ」と言ったときに「ご飯」が示すものは99%くらいでラーメンである2．

また，僕はラーメンだけでなく卵も大好きである．

ラーメンは麺，スープ，具材，そしてそれらの調和から美味しさが決まるが，そういえばこの具材の中に味付け煮玉子というものがいる．

ラーメンにのっている味付け煮玉子は最高だ．

天天有3のラーメンを食べる時なんて，まるでショートケーキのイチゴのようにいつ食べようかと悩んでいるものである．

ということで，この味付け煮玉子を自宅でも楽しみたいと思うのは必然である．

これはその備忘録．

調査

味玉の構成要素は大きく分けて，

  • ゆで時間
  • タレ
  • 漬け込み時間

の3つであると考える．これのいい感じの組み合わせを模索したい．

といっても普段自炊をしない僕は，美味しい味付け煮玉子の作り方なんて分からないので適当にggってレシピを見繕っていく．

ゆで時間

このサイトの早見表を参考に決定する．

kumiko-jp.com

半熟が好きなので7分でいいだろう．

タレ

適当にggって以下の2つを採用．

www.sirogohan.com

cookpad.com

また，色々なところで言及されていためんつゆも採用． この3種類で作っていく．

漬け込み時間

雑にggった感じ6時間くらいが良さそう．

以上の条件を決定した．

ところで僕は今(12/19)この記事を東京へ向かう新幹線の中で書いている．ぶっちゃけるとアドカレの準備をするのを忘れたまま京都を発ってしまったのである．

苦肉の策だが東京駅からの道すがらスーパーで卵と調味料を買って友人宅へと向かおう．

~ LINE ~

僕「君の家で味玉作っていい？」

友「え，なんで？」

調理

無事友人の家に付いたので「こいつ東京まで来て何してんの？」という視線を無視しながらさっそく調理を開始していく．

タレ作成

めんつゆ

使うのはこれ．

f:id:taxio:20191219200422j:plain
めんつゆ

3倍濃縮だがとくに薄めずこのまま使う．

和風ダレ

f:id:taxio:20191219200544j:plain
和風ダレ

醤油4，水3，みりん2，砂糖1の割合で混ぜる．参考記事では沸騰させていたが面倒くさいのでパス．

ちなみにこのレンゲは友人に「大さじ測るものない？」って聞いた時に渡されたやつ．

中華ダレ

f:id:taxio:20191219200750j:plain
中華ダレ

  • 醤油: 大さじ3
  • 砂糖: 大さじ1
  • ゴマ油: 小さじ1
  • ラー油: 適量
  • ニンニクチューブ: 適量
  • 生姜チューブ: 適量
  • お酢: 大さじ2
  • 鶏ガラ: 小さじ1

他にも白ゴマとか鷹の爪とか長ネギとかあったけど揃えるのが面倒だったのでパス

茹でる

f:id:taxio:20191219201131j:plain
茹でる

沸騰したお湯にそれぞれのタレに漬ける卵を投入． 1個割れちゃったので4つ入ってる．

7分経ったら冷水で冷やしながら殻を向いていく．

最後にジップロックにタレと茹で卵を入れて終了．

f:id:taxio:20191219201130j:plain
漬ける

6時間後へ...

...

...

...

完成・実食

6時間経った．さてどうなってるかな...

f:id:taxio:20191219201553j:plain
めんつゆ

f:id:taxio:20191219201621j:plain
和風ダレ

f:id:taxio:20191219201700j:plain
中華ダレ

見た目に差は無いが香りは中華ダレがとても良い．というか見た目に差が無さすぎて「これってめんつゆだったっけ？」って言いながら貼り付けてる．間違ってたらごめんなさい．

そんなことは置いといて，さて，味はどうだろうか．実食！！

f:id:taxio:20191219201828j:plain
味玉味噌ラーメン

先の通り，僕はあまり自炊しないので見かねた友人がササッと作ってくれた．マジありがてぇ．

味玉は左からめんつゆ，和風ダレ，中華ダレ．

以下食べてみた感想

めんつゆ

安定した味．いつだったか，金沢の友人の家に遊びに行った時に出してもらった味玉の味がする． 味が濃くてこれ単体で十分美味しい．

和風ダレ

めんつゆの後だと少し物足りない感じがする． しかしラーメンと一緒に食べるならこれくらいの濃さが良いのかもしれない．他の具材・スープの味を邪魔していない． ただ，水はもう少し少なくても良かったかもしれない．

中華ダレ

そこはかとない餃子感． 口に入れた瞬間の香りがいい． 濃すぎないのでこれもまたラーメンに合う．美味しい．

総評

めんつゆは濃くて美味しかったが，それ単体で完結していた． 何かの料理と合わせるなら薄くするか他の2つにした方が良さそう． 和風ダレと中華ダレは好みや状況で変わりそう．

自分が次ラーメンのためにつくるならちょっと濃い目の和風ダレかな．

感想

味玉美味しかったし，いきなり押しかけてきた人間にラーメン作ってくれる友人を持って僕は幸せ．

  1. 一乗寺↩

  2. しらんけど↩

  3. 天天有 本店 （てんてんゆう） - 一乗寺/ラーメン [食べログ]↩

GC本を読む ~第2章 マークスイープGC~

プログラミング Garbage Collection

ガベージコレクションのアルゴリズムと実装を読んだメモ第2弾．

この章から具体的なGCアルゴリズムの話に入っていきます．

マークスイープGC

1960年にJohn McCartyによって発表された最初のGCアルゴリズム1．

基本動作

次の2つのステップによって死んだオブジェクトを再利用可能な状態にする．

  1. マークフェーズ
    • ミューテータのルートから辿れるオブジェクト(のヘッダ)全てに生きていると示すためのマークを付ける．
  2. スイープフェーズ
    • ヒープ全体をスキャンしてマークのついていないオブジェクトを回収する．

処理は至ってシンプル． スイープフェーズでは，$heap_startから$heap_endまで全てのオブジェクトのヘッダを確認している．

ゴミオブジェクトをどうやって回収するのかというと，使われていないオブジェクトの連結リストを作って，そこに追加していっている． p21の擬似コードでは，

sweeping.next = $free_list
$free_list = sweeping

と書かれており，単純に後ろに追加していっているのではなく，追加したオブジェクトがリストの先頭になるように追加していっている．(こうすることで連結リストの末尾を指すポインタが必要無くなるし，$free_listがNULLを指しているときの条件分岐も要らなくなる)

スイープフェーズ時にはただゴミオブジェクトをフリーリストに追加するのではなく，もし前に追加したゴミオブジェクト(既に開放された状態なのでチャンク)とメモリ空間上で連続しているなら，これらを1つのチャンクと見なすという処理をする．こうすることでチャンクが細切れになってしまうのを防ぐ．これを合体(Coalescing)と呼ぶ．

アロケーション時は，このフリーリストを探索して，必要なサイズ以上のチャンクを見つけ次第それを返す． この方式はFirst-fitと呼ばれ，他にはBest-fitやWorst-fitなどがある．

メリット・デメリット

メリットとしては以下の2つが挙げられている．

  • 実装が簡単
  • 保守的GCとの相性が良い

実装が簡単であるから，他のGCアルゴリズムと組み合わせやすいらしい．他のGCアルゴリズムは後の章で紹介されるので，この時点ではまだこのメリット達がどの程度良いのかは分からない．

デメリットとしては以下の3つが挙げられている．

  • フラグメンテーション(断片化)
    • GCを繰り返すうちにチャンクが細分化される
  • アロケーション速度
  • コピーオンライト(Copy-On-Write)との相性
    • ヘッダにmark情報を置いているため，GC時に書き換えが発生することで，そのプロセス用メモリへの全コピーが発生してしまう．

デメリットを解決するためのアプローチ

複数フリーリスト (Multiple free-list)

チャンクのサイズごとにフリーリストを分けておく．(本のリスト2.7のコードで指定のフリーリストにチャンクが余ってなかったときに上位のフリーリストを見に行かないようになっているのはバグかな？)． これによって，基本 O(1)でチャンクが見つかるようになる．

BiBOP法 (Big Bag Of Pages)

ヒープ領域を分割し，特定のブロックに特定のサイズのチャンクを集中させる． これである程度フラグメンテーションが緩和される (完全に解決はしない)．

ビットマップマーキング (Bitmap Marking)

オブジェクトのヘッダではなく，別のデータにそれぞれのオブジェクトのマークビットをテーブル形式でまとめる． これによってGC時にオブジェクトへの書き込みがなくなるのでCoWが働く．

遅延スイープ法

スイープ操作にかかる時間はヒープ領域のサイズに比例して大きくなる． これが大きくなるということは，ミューテータの最大停止時間が増えるということ．

遅延スイープ法は，アロケーションのときに欲しいサイズのチャンクが作れたところでスイープ操作をやめる．これによってミューテータの停止時間を減らしている．(次スイープ処理をするときは続きから見ていくのか？)

しかし，もしスイープ操作時に見ているオブジェクトが連続して生きているオブジェクトだった場合，そのサイズ分だけ停止時間が発生するため，一概にこれで解決するとは言えない．(むしろ生存オブジェクトが固まっているのは局所性の面で良いはず．) このスイープ処理で扱うヒープ領域のサイズを一定に保つ手法は8章で説明されるようだ．

次回

読んでる途中

  1. J.McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, ACM, 1960↩

GoのCLI勉強会を開催しました

Golang プログラミング 勉強会

先日，「GoでCLIツールを作る」というハンズオンを開催しました．

studioaquatan.connpass.com

参加してくださった皆さん，ありがとうございました．

経緯

  • 大学のコミュニティでGoを流行らせたかった
  • Go Conference Spring 2019などでいい感じの話を聞いた
  • CLIツールを作る知見がある程度溜まっていたのでどこかでアウトプットしたかった

などの理由で開催しました．

内容

資料はこれ．

完成形のリポジトリは用意していたのですが，ハンズオンを進めていくうちにちょっと違った記述に行き着いてしまいました． それぞれのステップを友人がcommitレベルでまとめてくれていたので，気になる人はこれを見てください．

github.com

反省・感想

適当に枠は8人，時間は5時間と決めたのですが，みんなで議論しながら置いてけぼりの人があまり出ないような感じで進めれたのでちょうどよかったです．

「Live Coding」と書いたスライドが多くなってしまったのですが，これは書く量が多くてスライドに内容が収まらなかったのとそれをまとめるのがめんどくさかった(主にこっち)のが理由です． ハンズオンを進めながら，「別にerrは_で無視すればいいやん」ってことに気が付き，割と本質のコードだけ眺められるように書けたので，次回からは意識していきたいです．

やはりハンズオンなので，エディタを映す画面と資料を映す画面の2つが必要だなという点と，上記に紹介したとおり，全部の手順をcommitレベルで残しておき，参加者が詰まったときに確認できるリポジトリを作っておくべきだなという点が今回の反省点です． ただ，一度全体の流れを作った後に，それを1つずつ再現してcommitしていくのは面倒です．何かいいサービスは無いのでしょうか...？

ともあれ，無事に終わって良かったです．

内容に不備がある場合は随時資料とこの記事をアップデートしていきます．

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のここらへんの仕様がよくわからない...