Block Rockin’ Codes

back with another one of those block rockin' codes

トップ > golang

Golang Error Handling lesson by Rob Pike

go golang gocon error

Intro

この記事は Go Advent Calendar 2014 の 15 日目の記事です。

例えばネットワークのフレーム処理的なものを書いている場合、以下のようなコードがよくでてきます。

There are many codes like this, while writing a Network Frame Parser program.

var type uint8
err = binary.Read(r, binary.BigEndian, &type)
if err != nil {
    return err
}

var length uint32
err = binary.Read(r, binary.BigEndian, &length)
if err != nil {
    return err
}

...

関数の中では、各要素の長さ毎に読み込んで、読み込みに失敗したらエラーを呼び出し元に返す。

each function reads length of value from socket and return error if failed.


書き込む時は、ほぼ逆のコードをおぼ同じように書きます。

same things happens in writing to socket code.


さすがにこれが何個も続くと DRY ではないし、エラーの処理を忘れても気づきにくいという問題がある。

same code appears again and again, it's not DRY. and also you probably forget handle error which you can't notice easily.

Go のエラーの問題点

Go では多値を返して、その最後がエラーになるという形式が、一般的でありかつ型として定義されている。

It's a basic way in go, returning multiple values from function, and error is last value of then.


ただし、問題は戻り値は「処理しなかったとしてもコンパイルが通る」という仕様になっている。

but even if you don't care about return values, it's not compile error.


つまり上の例は、以下のように書いてもコンパイルが通る。

it means that compiler allows code like this.

// ignore return values
binary.Read(r, binary.BigEndian, &type)
binary.Read(r, binary.BigEndian, &length)

これが結構問題で、取り忘れたことがコンパイラだけでは分からない。

there is no notification when you forgot to process returned value even if it inclueds error.


知りたければ、別途ツールを使って検査するしかない。

if you want to fined uncaught error, you need another linter tool.


しかし、例えば戻り値の取得を必須にするとそれもまた問題で、例えば fmt.Println が多値を返すのでプリントデバッグが大変なことになる。

should compiler force programer to handle returned value ? I don't think so, for example fmt.Println returns error too. so its make difficult doing PRINT DEBUG.

_, _ := fmt.Println("print debug")

_, _ := fmt.Println("here")

_, _ := fmt.Println("")

How to solve?

特に Read や Write での処理が増えて行った場合、コードをすっきりさせつつ、 Error を確実に処理する方法について、自分の中では色々と試行錯誤していた。

I tried some practice for make lots of Read/Write proces simple, and make sure process all Errors.


で、先日 http://gocon.connpass.com/event/9748/ のために来日して下さった、 Rob Pike 先生に、この件を聞いてみた。

And I had a chance to ask Mr.Rob Pike about this problem at after party of http://gocon.connpass.com/event/9748/ in Japan last month.


そして Rob 先生は、俺のキーボード(悲しいことに vim しか入ってなかった。。)で、実際に書きながら説明してくれました！！なんという幸運。

and then, Mr.Rob taught me with writting a code on my Mac(unfortunately, I installed only vim...), what's a presious happenig !!

先生が説明しつつ書いてくれたコードがこちら。

Mr.Rob show me the code like this.

type errWriter struct {
    w io.Writer
    err error
}

func (e *errWriter) Write(p []byte) {
    if e.err != nil {
        return
    }
    _, e.err = e.w.Write(p)
}

func (e *errWriter) Err() error {
    return e.err
}

func do() {
    ew := &errWriter{
        w: ...
    }
    ew.Write(buf)
    ew.Write(buf)
    ...
    ...
    if ew.Err() != nil {
        return ew.Err()
    }
    return nil
}

Writer の Wrapper になっていて、エラーが発生した時は内部でそれを保持しつつ、以降の処理は全てパスされる。

Write a wrapper struct of Writer. while processing, hold a error if happened and pass all Write() below.


最後にエラーの有無を確認することで、エラー処理を一カ所にまとめる。

end of the function, check and process the error in struct. this gathers error handling in one place.


とりあえず Writer と Reader について作っておけば、 Write や Read の処理が多くなるほどメリットが大きくなる。

prepare a struct for Writer and Reader has a merit when you write a lot of Write()/Read() process.


素朴だけど Go らしいコードですね。

so simple but powerful as golang way :)

Movie

すっごく見づらいけど、ぶっちゃけ後で人に見せる映像取るよりも、その場でロブ先生の話聞く方が大事だしそれで一杯一杯だったので、まあ雰囲気だけみてください。

Sorry for hard to watch, but it's more important to see and hear Mr Robs Exmplain haha. be patient :)

Mr. Rob Rike taught me about practice of error handling in Go at GoCon 2014 from Jxck on Vimeo.

Special Thanks

thanks Mr.Rob Pike !

from your student Jxck :)

Go のスライスでハマッたところ

go golang Fossil slice

intro

先日 GoのSliceもヤバイ - Qiita こんな記事をみて、別の挙動だけどスライスの内部を理解しきれていなかった頃のことを思い出した。

結構前に謎に思っていた挙動についての話。 以前この挙動を解説しようと思って、前提として書いたスライスの内部構造の記事が、 Go のスライスの内部実装 だったのですが、そっちを書き終わって満足してしまい、本題を忘れていました。

この挙動は、先のブログで説明した内容がわかっていないと、なかなか理解できないかも。わかってしまえば簡単ですが。

やりたいのは、関数側でスライスを操作したときの呼び出し側での結果。 順を追ってみてみます。

配列を関数内で変更する

関数は値渡しで、配列はそれ自体が値なので、まるっとコピーされます。 以下の例は、戻り値で返さないと、呼出側は変化しません。

package main

import (
    "log"
)

func init() {
    log.SetFlags(log.Lshortfile)
}

func increment(a [3]int) {
    // a は配列自体のコピー
    for i := range a {
        a[i] += 1
    }
    log.Println(a) // [2 3 4]
}

func main() {
    a := [3]int{1, 2, 3}
    increment(a)
    log.Println(a) // [1 2 3]
}

スライスを関数内で変更する

スライスは、配列(以下、内部配列という)への参照を持つ構造になっているので、スライスを値渡しして関数内で操作した場合、同じ内部配列を参照しているスライス(つまり同じスライス)にも、変更が反映される。

package main

import (
    "log"
)

func init() {
    log.SetFlags(log.Lshortfile)
}

func increment(a []int) {
    // slice の値渡しなので、参照先の配列は同じ
    for i := range a {
        a[i] += 1 // ここは参照先配列の値を変える
    }
    log.Println(a) // [2 3 4]
}

func main() {
    a := []int{1, 2, 3} // slice
    increment(a)
    log.Println(a) // [2 3 4]
}

関数内でスライスに append() (cap 無し)

しかし、 append() は、 cap のサイズが足らない場合は、内部配列を確保しなおすため、以下は戻り値としてスライスを返さないと、呼び出し側のスライスには変更が反映されない。

func add(a []int) {
    a = append(a, 4) // 新しい内部配列を作る
    log.Println(a)   // [1 2 3 4]
}

func main() {
    a := []int{1, 2, 3} // この時点で cap は 3
    add(a)
    log.Println(a) // [1 2 3]

}

スライス自体のポインタを渡す方法を使うならこう。

func add(a *[]int) {
    *a = append(*a, 4) // 新しい内部配列を作る
    log.Println(*a)    // [1 2 3 4]
}

func main() {
    a := []int{1, 2, 3} // この時点で cap は 3
    add(&a)
    log.Println(a) // [1 2 3 4]
}

スライスを関数内で append() (cap あり)

append() はもし cap に余裕があるなら、新しい内部配列は作りなおさず、そのまま末尾に追加する。内部配列を作り直さない場合、 append() の戻り値は同じスライスらしい。(なので、 append() の戻り値をとらなくてもよさそうだが、戻り値をとらないとコンパイルエラーになる)

func main() {
    a := []int{1, 2, 3}
    log.Printf("%p, %v", a, a) // 0x18244010, [1 2 3]
    a = append(a, 4)
    log.Printf("%p %v", a, a) // 0x18239240 [1 2 3 4]

    a = make([]int, 3, 4)
    a[0], a[1], a[2] = 1, 2, 3 // まだ cap に余裕がある
    log.Printf("%p, %v", a, a) // 0x18244080, [1 2 3]
    a = append(a, 4)
    log.Printf("%p %v", a, a) // 0x18244080 [1 2 3 4]
}

ここまでが前提。

問題の挙動

append() を関数内で行う。 この場合、 cap に余裕があった場合は、内部配列の空き部分にそのまま追加されて、呼び出し側にも反映されるだろうという予想。

しかし、実際はそうならない。

package main

import (
    "log"
)

func init() {
    log.SetFlags(log.Lshortfile)
}

func add(a []int) {
    a = append(a, 4)           // 配列自体は更新されないはず
    log.Printf("%p, %v", a, a) //  0x18244010, [1 2 3 4]
}

func main() {
    a := make([]int, 3, 4)
    a[0], a[1], a[2] = 1, 2, 3 // まだ cap に余裕がある
    log.Printf("%p, %v", a, a) //  0x18244010, [1 2 3]
    add(a)
    log.Printf("%p, %v", a, a) // 0x18244010, [1 2 3]
}

内部配列には余裕があり、そこに追加されているはず。 スライスのアドレスは変わっていないため、間違いなく同じものを表示している。 しかし、関数内では 4 つになっているのに、呼び出し側が更新されていないのはなぜか。またはどうしたら表示されるようになるか。

関数のシグネチャは一切変えず、最後の出力の手前に一行追加するだけで解決できます。

良かったら考えてみてください。

続きを読む

Go 1.3 で入った sync.Pool

go golang

Intro

先週 Go 1.3 が公開されましたが、 sync パッケージに Pool という API が追加されました。 ぱっと見なんだかよくわからなかったので調べてみました。

sync.Pool

sync.Pool

とりあえず、 GoDoc を訳したのでそれは最後に全部掲載します。 要点としては以下。

  • 従来独自に実装していた、 Free List を標準に入れた
  • Weak Map (弱参照)になっている
  • goroutine safe である

用途

一般的な FreeList の役割は、既に割り当て(Allocate)されたメモリが不要になった時、開放する代わりに List に持っておいて、メモリが必要になったらそこから取るというもの。(という理解) もし、不要になったメモリを捨てると、 GC の負荷が上がるし、再割り当ての負荷もあがるので、無駄が多くなる。 Go は C や C++ でやっていたような、システムに近い低レイヤのプログラムを書く用途でも使われるので、 GC はあるものの、こうした細かいメモリ管理を行いチューニングを行うこともあります。

実際に、標準でも fmt と regexp で、こうした用途の実装がなされていました。(go1.2)

多少実装はことなりますが、概ね以下の指針で実装されています。

  • []interface{} に格納
  • Get(), Put() を持つ
  • sync.Mutex などでロックを取る

fmt では具体的にはこんな感じ。

type cache struct {
    mu    sync.Mutex
    saved []interface{}
    new   func() interface{}
}

func (c *cache) put(x interface{}) {
    c.mu.Lock()
    if len(c.saved) < cap(c.saved) {
        c.saved = append(c.saved, x)
    }
    c.mu.Unlock()
}

func (c *cache) get() interface{} {
    c.mu.Lock()
    n := len(c.saved)
    if n == 0 {
        c.mu.Unlock()
        return c.new()
    }
    x := c.saved[n-1]
    c.saved = c.saved[0 : n-1]
    c.mu.Unlock()
    return x
}

func newCache(f func() interface{}) *cache {
    return &cache{saved: make([]interface{}, 0, 100), new: f}
}

var ppFree = newCache(func() interface{} { return new(pp) })

しかし、これにはいくつかの問題があります。

  • パッケージごとに同じような実装が必要
  • 気をつけて Lock-UnLock しないと goroutine-safe にならない
  • キャッシュから明示的に参照を消さないと GC されない

そこで、こうした機能自体を Go 標準に持ってはどうかという話を、前回の GoCon にも来日した Bradfiz が提案したのがことの始まりのようです。 そもそもこうした機能を標準に持つのか？ 名前は Cache か Pool か? API はどうするか？ など色々議論が重ねられた末に、今の形に落ち着き、今回 go1.3 に取り込まれたようです。

API

sync.Pool の API は非常にシンプルです。

http://golang.org/pkg/sync/#Pool

// キャッシュが切れたときのメモリ確保の方法を指定
type Pool struct {
    New func() interface{}
}

// キャッシュから取得
func (p *Pool) Get() interface{}

// キャッシュに戻す
func (p *Pool) Put(x interface{})

Put() したオブジェクトと、 Get() で取り出したオブジェクト間に参照関係はないものとして扱う必要があります。(例え 1 個入れて 1 個出したとしても)

WeakMap になっているため、 Get() で取り出したオブジェクトへの参照が切れれば、それは GC の対象になるようです。

実例としては、先ほど紹介した fmt のキャッシュ部分が 1.3 以降ではまさしくこの Pool を使って実装し直されています。

簡単に言うと、以下だけで終わり。あとは get(), put() で実装されていたものが Get(), Put() に変わっただけです。

var ppFree = sync.Pool{
    New: func() interface{} { return new(pp) },
}

探せてないけど、他にもありそう。

注意点というか、よくわかってないところとして、 GoDoc の以下が引っかかっている。

逆に、 寿命の短いオブジェクトの free list を管理する用途では、 Pool は向いていない。
なぜなら、そのシナリオではオーバーヘッドが減らないから。そうしたオブジェクトでは、独自に free list を実装した方が良い。

どの程度から、使い分けるべきなのだろうか。

翻訳

理解のために GoDoc 適当に翻訳したので張っておきます。

A Pool is a set of temporary objects that may be individually saved and retrieved.
Pool は個別に管理され回収される、一時オブジェクトのセット。


Any item stored in the Pool may be removed automatically at any time without notification. If the Pool holds the only reference when this happens, the item might be deallocated.
Pool にストアされたどんなアイテムも、通知なしに自動で消されることがある。
もし、 Pool が参照しか持たない場合にこれが起こると、アイテムはメモリから消去される。（deallocated)


A Pool is safe for use by multiple goroutines simultaneously.
Pool は複数 goroutine から同時に使用可能。


Pool's purpose is to cache allocated but unused items for later reuse, relieving pressure on the garbage collector. That is, it makes it easy to build efficient, thread-safe free lists. However, it is not suitable for all free lists.
Pool は、メモリに割り当てられているがもう不要なアイテムをキャッシュし、後で再利用することで、 GC の負荷を下げることを目的としている。
これにより、効率よくスレッドセーフな free list を作ることができる。しかし、すべての free list に適しているわけではない。


An appropriate use of a Pool is to manage a group of temporary items
silently shared among and potentially reused by concurrent independent clients of a package.
Pool の適した使い方は、並行する独立した、クライアントのパッケージから暗黙的に共有される、
再利用される可能性のある、複数の一時的なアイテムを管理すること。


Pool provides a way to amortize allocation overhead across many clients.
Pool は、複数のクライアントからのメモリ割り当てのオーバーヘッドを削減する方法を提供する。


An example of good use of a Pool is in the fmt package,
which maintains a dynamically-sized store of temporary output buffers.
The store scales under load (when many goroutines are actively printing) and shrinks when quiescent.
例えば、適した用途として、 動的にサイズを割り当てる一時的な出力バッファを管理する（標準出力としての） fmt パッケージがある。
複数の goroutine が頻繁に出力すれば、サイズは増えるし、少なければ縮小する。


On the other hand, a free list maintained as part of a short-lived object is not a suitable use for a Pool, since the overhead does not amortize well in that scenario. It is more efficient to have such objects implement their own free list.
逆に、 寿命の短いオブジェクトの free list を管理する用途では、 Pool は向いていない。
なぜなら、そのシナリオではオーバーヘッドが減らないから。
そうしたオブジェクトでは、独自に free list を実装した方が良い。

Outro

細かいチューニングが必要なプログラム以外では、あまり使うことは無いかもしれないですが、知っておいて損はなさそうです。

Go のスライスの内部実装

golang go slice

History

Intro

Go のスライスは、いわゆる LL 系の言語が持つ可変長配列の実装と似ています。 よって LL のような手軽な扱いをすることもできますが、その内部実装を知ることでより効率の良いメモリハンドリングができ、パフォーマンスを改善や、メモリーリークの防止などに繋がる可能性があります。

この辺は SWrap というライブラリを作りながら勉強したので、今回は、この Go のスライスの内部実装を解説します。

Go の配列

スライスを知るためには、まず配列について知っておく必要があります。

Go の配列は固定長のため、以下のように長さを指定して宣言します。

var arr [4]int

func main() {
    arr = [4]int{1, 2, 3, 4}
    log.Println(arr)
}

配列は長さを含めて型です。 つまり、以下の関数は [4]int のみを引数として許し、 [5]int は型が合わずコンパイルでエラーになります。

func fn(arr [4]int) {
    log.Println(arr)
}

func main() {
    arr4 := [4]int{1, 2, 3, 4}
    arr5 := [5]int{1, 2, 3, 4, 5}
    fn(arr4) // ok
    fn(arr5) // cannot use arr5 (type [5]int) as type [4]int in function argument
}

関数に渡した場合は、値渡しになります。つまり渡した先では配列がまるっとコピーされます。 参照渡しにしたい場合は、ポインタを渡します。

func fnV(arr [4]int) {
    for i, _ := range arr {
        arr[i] = 0
    }
    log.Println(arr) // [0, 0, 0, 0]
}

func fnP(arr *[4]int) {
    for i, _ := range arr {
        arr[i] = 0
    }
    log.Println(arr) // [0, 0, 0, 0]
}

func main() {
    arr := [4]int{1, 2, 3, 4}
    fnV(arr)
    log.Println(arr) // [1, 2, 3, 4]
    fnP(&arr)
    log.Println(arr) // [0, 0, 0, 0]
}

また、配列の長さは変更できないため、長さを増やしたいなどの場合は、長い配列を宣言し自分で移し替える必要があります。(後述する append() や copy() は、配列には使用できません)

Slice

スライスは、可変長配列のようなものです。 その実体は、固定長配列への View として実装されています。

まず、使いかたを見てみます。

配列の宣言から長さの情報を消すと、スライスとして宣言されます。 長さの情報が無いため、関数に渡す際に実際いくつの要素が入っていても、要素の型が同じなら渡すことができます。

関数に渡す場合は、ただスライスを渡せば、渡した先で中身を書き換えることができます。 fnP() のようにスライス自体のポインタを渡すことも可能です。

func fnV(arr []int) {
    for i, _ := range arr {
        arr[i] = 10
    }
    log.Println(arr) // [10, 10, 10, 10]
}

func fnP(a *[]int) {
    arr := *a // 一旦中身をとりだす
    for i, _ := range arr {
        arr[i] = 20
    }
    log.Println(arr) // [20, 20, 20, 20]
}

func main() {
    arr := []int{1, 2, 3, 4}
    fnV(arr)
    log.Println(arr) // [10, 10, 10, 10]
    arr = []int{1, 2, 3, 4}
    fnP(&arr)
    log.Println(arr) // [20, 20, 20, 20]
}

内部実装

内部では、スライスは固定長配列への View として実装されています。 具体的な構造は、以下のようなイメージです。

宣言

まず、以下のようにスライスの宣言と初期化同時に実行してみます。 この時、内部的には固定長配列である [4]int のメモリが確保され、値が入り初期化されます。 スライスはその固定長配列への参照(コメント内の * )を持ちます。 len() を使って、値の数も見てみましょう。

// []int    *
//          |
// [4]int  [1, 2, 3, 4]
arr := []int{1, 2, 3, 4}
log.Println(arr, len(arr)) // [1 2 3 4] 4

make()

次にスライスのもう一つの宣言方法、 make() を使って書きなおしてみます。 make() は第一引数に型を、第二引数に長さ(len)を指定します。 以下の場合は、配列 [4]int のメモリを確保し、型に応じた ゼロ値 で初期化します。 (int の場合は 0 です)

変数 arr は、その配列への参照が格納されます。

// []int    *
//          |
// [4]int  [0, 0, 0, 0]
arr := make([]int, 4)
log.Println(arr, len(arr)) // [0 0 0 0] 4

したがって、値は index 0~3 までは代入可能です。 index 4 は、 index out of range になります。

// []int    *
//          |
// [4]int  [1, 2, 3, 4]
arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr[4] = 5 // index out of range

append

len よりも外側の領域まで値を追加していくためには append() を使います。 apeend() は、スライスの末尾に値を追加し、その結果を返します。 以下は先ほど初期化したサイズの外、 arr[4], arr[5] まで値を格納しています。

arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
arr = append(arr, 5)
arr = append(arr, 6)
log.Println(arr, len(arr)) // [1, 2, 3, 4, 5, 6] 6

では、この時内部の固定長配列はどうなっているのでしょうか？ それを知るためには、 cap() について知る必要があります。

cap

cap() で内部配列のサイズを知ることができます。 まず、以下の例で見てみましょう。

先ほどの make([]int, 4) で生成したスライスの cap() は 4 です。 これは、内部配列の長さが 4 だからです。

よってこのスライスに対し 4 つまでは、値を格納できますが、 append() によって配列のサイズ以上に値を追加する場合は、内部の配列を拡張する必要があります。

Go は append() で内部の配列を拡張する時、必ず現在の配列の 倍の長さ の配列を確保し、そこにコピーするという実装になっています。 実際に確認してみると、最後のスライスは、 len() が 5 で、 cap() は 8 を返しています。

// []int    *
//          |
// [4]int  [0, 0, 0, 0]
arr := make([]int, 4)
log.Println(arr, len(arr), cap(arr)) // [0 0 0 0] 4 4

arr[0] = 1
arr[1] = 2
arr[2] = 3
arr[3] = 4
log.Println(arr, len(arr), cap(arr)) // [1 2 3 4] 4 4
arr = append(arr, 5) // 内部で [8]int が確保され、そこに 5 つの値がコピーされる
log.Println(arr, len(arr), cap(arr)) // [1 2 3 4 5] 5 8
// []int    *
//          |
// [8]int  [1, 2, 3, 4, 5, , , ,]

最後の状態は、内部的には [8]int があり、そのうちの index 0~4 までが使われている状態です。 len() は値の入っている数、 cap() は内部配列のサイズ、 append() は末尾への追加と、足らない場合の配列の拡張を行っています。

make() で cap の指定

スライスに最初から沢山の値を入れることがわかっている場合、 append() で何度も配列を拡張するより、最初から大きな配列を内部に確保すれば、メモリ確保の回数を減らすことができます。

この、最初に確保する配列のサイズは、 make() の第三引数で指定できます。

例えば、 cap = 0 でスライスを確保し 5 個の値を append() していくと、合計で 5 回の配列確保(allocate) が行われます。

func Append1() {
    arr := make([]int, 0, 0) // 0, 0 (alloc)
    arr = append(arr, 0)    // 1, 1 (alloc)
    arr = append(arr, 1)    // 2, 2 (alloc)
    arr = append(arr, 2)    // 3, 4
    arr = append(arr, 3)    // 4, 4 (alloc)
    arr = append(arr, 4)    // 5, 8 (alloc)
}

cap を最初から 5 にしておけば alloc は最初だけで済みます。

func Append2() {
    arr := make([]int, 0, 5) // 0, 5 (alloc)
    arr = append(arr, 0)    // 1, 5
    arr = append(arr, 1)    // 2, 5
    arr = append(arr, 2)    // 3, 5
    arr = append(arr, 3)    // 4, 5
    arr = append(arr, 4)    // 5, 5
}

make() の第一引数 len を 0 にしているのは、値を初期化しないためです。 初期化してしまうと、その範囲は添字アクセス、それ移行は append() と使い分ける必要もあるため、こうした指定をしています。

// []int    *
//          |
// [10]int  [ , , , , , , , , , ]
arr := make([]int, 0, 10)
log.Println(arr, len(arr), cap(arr)) // [] 0 10

ちなみに以下のような宣言では、暗黙的に len=0, cap=0 になります。

var arr []int // 0, 0

このように、スライスの下にある実配列を意識することで、効率の良いメモリ確保が可能になる場合があります。 具体的には、一度確保(Allocate)したメモリを使い回し、確保の回数を減らすことで処理を高速化するといった場合です。

メモリの使い回し

上記を踏まえて次の「スライスの連結」を考えてみましょう。

以下のような実装の、メモリ確保面での効率を考えてみます。

func Merge1(a, b []int) []int {
    for i := range b {
        a = append(a, b[i])
    }
    return b
}

筋は悪そうですが、もし a の cap に b の len 分の余裕が必ずあるなら、配列の再確保は行われないため、これでも問題ないでしょう。 しかし、 b の len が大きく、 a の cap が小さい場合は、再確保が何度も起こる可能性があります。

毎回、必ず一回確保することを選ぶのであれば、こうなります。 copy() は、第二引数のスライスの内容を、第一引数のスライスに移します。 最初から、必要な長さを確保しているので、 alloc は一回で済みます。

func Merge2(a, b []int) []int {
    c := make([]int, len(a)+len(b))
    copy(c, a)
    copy(c[len(a):], b)
    return c
}

といいつつ実は append() はこんな書き方ができます。

func Merge3(a, b []int) []int {
    return append(a, b...)
}

配列確保も 1 回で最適化されるので、基本的にこの方法を使うのが良いでしょう。

GC

スライスから見える値が消えていても、内部配列に残っていることで GC されず値が残る場合があります。 例えば、スライスから指定したインデックスの値を削除し、その分前に詰めて返す del() 関数を考えてみます。 既にある内部配列内の移動だけで済ませれば、再確保はいらないので、以下のようにしてみます。

func del(a []int, i int) []int {
    copy(a[i:], a[i+1:])
    a = a[:len(a)-1]
    return a
}

func main() {
    a := []int{1, 2, 3, 4, 5}
    a = del(a, 2)
    log.Println(a, len(a), cap(a)) // [1 2 4 5] 4 5
}

メモリの Allocate も無く、スライス側から見ると値は消えています。

しかし、内部配列はどうでしょうか。 del() の後は、以下のようになっています。 (実際に a[:cap(a)] で確認できます。)

// []int    *
//          |
// [5]int  [1, 2, 4, 5, 5]
log.Println(a[:cap(a)])

このように、スライスからは見えない値が、内部の配列に残っている場合があります。 例えば大きなサイズの構造体の参照を持つスライスなどの場合は、内部配列に参照が残っていることにより、 GC されない可能性もあります。

万全を期すためには、 del() を以下のようにし、末尾の値に、型に応じたゼロ値(宣言して初期化しないことで生成可能)を代入しておく方法があります。 int の場合は 0 ですが、参照型のスライスの場合は、ここが nil になります。

var zero int // ゼロ値
func del(a []int, i int) []int {
    copy(a[i:], a[i+1:])
    a[len(a)-1] = zero // ゼロ値, nil の代入
    a = a[:len(a)-1]
    return a
}

削除する範囲が大きい場合は、一旦別のスライスに対比することで GC を促す方法もあるでしょう。 この辺の話は、 Slice Tricks や Arrays, slices (and strings): The mechanics of 'append' - The Go Blog、 Go Slices: usage and internals - The Go Blog などで紹介されています。

まとめ

Go のスライスの内部実装について、色々と細かい解説をしましたが、そういったことを抽象化して全て len=0, cap=0 で宣言したスライスを append() だけで拡張していくこともできるのが Go の手軽な部分です。カジュアルな用途では、それで十分でしょう。

しかし、スライスを多用したり、そこにサイズの大きい構造体を格納したり、詰替えや拡張をよく行うようになると、こうしたことを知っておくだけで効率が数倍変わることもあります。

処理の速度やメモリ確保については testing パッケージを用いたベンチマークを記述し、 go test コマンドにある、 -benchmem オプションを用いてベンチマークを実行すると、以下の様な感じで実行時間とともに alloc 回数を知ることができます。

PASS
BenchmarkAppend1   5000000         741 ns/op       120 B/op        4 allocs/op
BenchmarkAppend2  50000000        48.8 ns/op         0 B/op        0 allocs/op
ok    jxck  6.825s

あらかじめ、おおよそのサイズを見積もり、テストやベンチで測定と検証を繰り返しながらチューニングすることで、より効率の良いプログラムの作成に繋がると思います。

何か間違いなどありましたら、遠慮なく指摘頂けると幸いです。

そうだ、と思い立って京都で Go のハンズオンしてきました。 #gokyoto

golang

Intro

東京であったとある勉強会で、 @ さんに「京都に来てください」と言われたので、「高倉二条連れてってくれるならいいです」 と二つ返事で引き受けたので、タイトルの通り京都にいって Go のハンズ・オンしてきました。

Go勉強会 そうだ京都、行こう

ハンズオン資料

想定レベルは、他の言語経験はあるけど Go は初心者であること。 前提としては、環境構築済みで Tour Of Go の演習以外をひと通りやってること。 として、資料を作成しました。

基本的には、各言語仕様を細かく見るというより、とにかく手を動かして動くものを作っていくパターンです。 その方がやってて面白いしね。

テーマはタスク管理ですが、それはおまけで、 Go の言語仕様と標準モジュールをガンガン触りながら、イディオムや考え方を解説していきました。

資料は以下に公開しています。

https://gist.github.com/Jxck/9551539

京都観光

初日ハンズオンの前に、なんとかたつさんが行く行く詐欺し続けたことで有名な高倉二条に。

ネットの怖い人からムチャぶりが。

二日目は初心者になりすましてハンズオンに混ざっていた @ さんの紹介で、はてなの @ さん、 @ さん達とお会いしてきました。

京都といえばはてな。よく考えると自分はかなりお世話になっているサービスの一つ。 あと、今のはてなは思っていた以上に平均年齢が低いようだ。

とりあえず高倉二条と似た「すがり」というお店に。ラーメンの写真は撮り忘れた。

その後、はてなのオフィスにおじゃますることに。初はてな。

途中で東京で JAWS に出ていると思っていた @ さんが出社してきてびっくりしたなど。

良くある京都観光的なことは一切しなかったけど、良い旅でした。 @ さん、参加者のみなさん、はてなのみなさんありがとうございました！

Log

Go の Generator を channel と closure で速度比較(または Go でのアトミック処理イディオム)

golang bench

追記

この記事は元々 Go のイディオムとして、いわゆるジェネレータの実装がどうできるのかを軽い気持ちで書いただけで、速いから「Closure を使いましょう」などと一言も言ってなかったのですが、一方が channel であったため原子性についての言及がいくつかありました。

自分としては、ローカルのちょっとしたツール(shell の代わりくらい) の中で使ってただけなので、並行性には言及するつもりがそもそも無かったのですが、自分もそうした前提を書いていなかったのにも原因があります。

例えばこの記事が「グローバルシーケンス」の実装例として参考にされ Web アプリにでもコピペされて、バグの原因になったりでもしたらマズイので大幅に追記します。 (正直ロックを使った排他制御はあまり得意では無いですが。。)

Intro

無限に連番を生成するロジックをジェネレータとして組むときに、 Go の場合は二つの方法が考えられます。 Closure を使う方法と Channel を読みだす方法です。

Closure (goroutine unsafe)

まずは Closure を用いた単純な実装をしてみます。

func Closure() func() int {
    i := 0
    return func() int {
        i = i + 1
        return i
    }
}

今回のベンチマークではこの実装が最速です(後述)。 ただし、この実装は複数の Goroutine から呼び出される場合、インクリメントと取得の部分がクリティカルセクションになっています。 スレッドモデルの場合 "スレッドセーフ" といいますが、 Go ではスレッドではないので "Goroutine セーフ" と呼ぶことにします。この例は Goroutine セーフではない実装です。

Closure (mutex locked)

クリティカルセクションを守る方法としては、ロックを取る方法が多くの言語で使われてきました。 Go では、 sync.Mutex を用いてそれが実現できます。

func MutexClosure() func() int {
    var mutex = new(sync.Mutex)
    i := 0
    return func() int {
        mutex.Lock()
        defer mutex.Unlock()
        i = i + 1
        return i
    }
}

sync.Mutex を用いると Lock() と Unlock() を用いて排他制御が実行できます。 操作の前に Lock() を取得し、defer を用いて関数終了時に Unlock() を実行しています。

一般的に、ロックを用いた排他制御を実施する場合、必ずデッドロックに注意する必要があります。 上記の実装では使っていませんが、 Lock()、 Unlock() などが別の Goroutine で実行されていたり、その間に Channel による同期などを別途行っているような場合は特に注意が必要です。

おまけ Closure (atomic increment)

より低レベルの操作については、 sync/atomic パッケージも提供されています。 例えば CAS やアトミックなインクリメントなどが提供されています。

今回の場合、ここまでは int で実装していますが、 int の API はないために int32 を使うことを許容できるなら、今回のクリティカルセクションのロジックが単なるインクリメントであることから、 AddInt32 を用いることができるかも。と思いましたが、これは return がロックされていないのでダメですね。 これを使うなら、ユーザランドでグローバルにある値を直接インクリメントすればいいのかな。

func AtomicClosure() func() int32 {
    var n int32 = 0
    var i int32 = 1
    return func() int32 {
        return atomic.AddInt32(&n, i)
    }
}

また、このパッケージのドキュメント冒頭には以下の説明があります。

These functions require great care to be used correctly.
Except for special, low-level applications,
synchronization is better done with channels or the facilities of the sync package.
Share memory by communicating; don't communicate by sharing memory.

要するに、普通にアプリやツールを書くような用途での使用には推奨されておらず、(明示はされていませんが)より高度な実装で必要なケースに向けて提供されています。

Channel

sync パッケージを全く使用しなくてもアトミックな処理を実装することができます。 Go には channel という言語に組み込まれた MQ のような機能があり、 この channel を使用して、メッセージングにより同期をとる方法です。

func Channel() <-chan int {
    ch := make(chan int)
    go func() {
        i := 1
        for {
            ch <- i
            i = i + 1
        }
    }()
    return ch
}

この実装では外側の Channel() は読み取り専用の channel を返しており、これを持つ側は channel の読み出しを行うことで数値を取得できます。 この i は Channel() 実行時に生成される goroutine の中にしか存在せず、その goroutine と唯一繋がった channel に対しても書込することはできないため、外からは一切操作できません。

また、 channel には make 時に buffer を設定していないため、当時に一つの値しかそこを通ることができません。 つまり、channel に値があればそれが読み出されるまで書き込みはブロックし、 channle に値がなければ書き込まれるまでは読み出しはブロックします。

大量の goroutine がこの channel を保持していて、同時に読み出しでブロックしていても、書き込まれた値は一番最初に読み出しブロックに入った goroutine にしか読み出されません。

こうして、ロックを一切使わずにアトミックな処理が実現できるのです。

ベンチ

ベンチマークを取ってみます。

func BenchmarkClosure(b *testing.B) {
    cl := Closure()
    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        cl()
    }
}

func BenchmarkMutexClosure(b *testing.B) {
    cl := MutexClosure()
    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        cl()
    }
}

func BenchmarkChannel(b *testing.B) {
    ch := Channel()
    b.ResetTimer()

    for i := 0; i < b.N; i++ {
        <-ch
    }
}

実行結果

Mac Book Air (OSX 10.7.5) 1.6 GHz Intel Core i5 Memory 4GB

$ go test -bench .
PASS
BenchmarkClosure        100000000    11.5 ns/op
BenchmarkMutexClosure   50000000     35.3 ns/op
BenchmarkChannel        5000000      251 ns/op
ok  /path/to/bench  6.747s

ベンチマークの実行回数は、ベンチマークソースの中の b.N の値の部分になり、 関数の実行時間に応じて go test コマンドが適宜調整してくれます。 いずれも十分回数実行されているとみなし、 ns/op に注目して一実行あたりの平均実行時間を比較します。 (数回実行したところ、だいたい同じでした)

implimentation time (ns/op) ratio
closure 11.5 1
mutex 35.3 3.07
channel 251 21.8

最後の列が、 closure 実装を 1 とした場合の比率です。 (書き直す前は channel は 50 倍だったのですが、 channel の速度は変わらないのに closure の速度が何故が落ちたので、 20 倍に縮まりました。 元々の記事は、この結果が予想していたよりも大きかったなぁという趣旨でした。)

考察

ちょっとしたツールなどで、 1 つの Goroutine の中でしか使わないような実装であればどれでも構いませんが、 複数の Goroutine が共有する、いわゆるグローバルシーケンサを実装するような場合には、今回の Closure 実装は使えません。

同じことは、シーケンサでなくともグローバルカウンタや、もっと広く言えば複数の goroutine で共有するロジックでは共通です。 しかし、途中で解説したように sync/atomic は、理由がない限り積極的に使うべきでは無いでしょう。

mutex と channel の実装については、今回 7 倍の速度差が出ていますが、 mutex にはロックを伴う排他制御につきものな種々の難しさが、他の言語同様に伴います。

sync/atomic のドキュメントでも出ていた以下はその選択の指針になります。

Share memory by communicating;
don\'t communicate by sharing memory.

これは、意訳すると「メモリの共有(sync) ではなく、メッセージング(channle) でデータの共有をしましょう」という意味で、 Go はこうしたメッセージングによるイディオムを強く推奨しています。

一般的にロックでの排他制御は難易度が高く、デバッグもしづらいという経験則があり、メッセージングを用いた実装がシンプルで堅牢かつ柔軟なプログラミングが可能であるという理由からです。

同様な主張を元にした、 Go の並行処理については以下の様にドキュメント群でも散々言及されています。

一方で channel も、読み出しが競合してデッドロックするなど、慣れないと上手く書けない場合はあるでしょう。 そうした場合は、この辺が参考になると思います。

過去にこのブログでも言及しています。

結論

  • Goroutine をまたがないで、とにかく速度が欲しい場合: Closure
  • 複数の Goroutine から使い、ロックのプログラミングに慣れている場合: Mutex
  • 複数の Goroutine から使い、 Go の思想に則りたい、プログラムをシンプルにしたいetc: Channel
  • 筆者のおすすめ: Channel
  • 前提を書かずに記事を書かない

おまけ

実は Slice や Map の操作もアトミックではありません。 なので、今回行ったようなことを用いて、 Slice や Map の操作を自分でアトミックにする必要があります。 それを含むロジック全体をアトミックにすることもできますが、単体の追加/削除などをアトミックにするライブラリをいくつか作っているので、そのうちそれを紹介します。

ソースコード

使用したコードは以下にあります。

https://gist.github.com/Jxck/9184764

Go でベンチマーク

golang bench test

Intro

Go にはベンチマークを取る仕組みが標準で備わっています。


テストを書く仕組みも標準で備わっており、
testing モジュールと go test コマンドで行いますが、
ベンチも同じような形で実行することができます。


今回は簡単なベンチ取り方を紹介します。
テストについては、そのうちちゃんと触れます。


参考ソースとして、こちらを使います。

https://github.com/Jxck/swrap

対象のコード

例えば以下のようなコードがあって、そのベンチを取るとします。

// swrap.go

type SWrap []byte

func (sw *SWrap) Add(a byte) {
	*sw = append(*sw, a)
}

func (sw *SWrap) Len() int {
	return len(*sw)
}

Slice にメソッドを生やしただけです。

ベンチマーク関数

ベンチマークは、 *_test.go ファイルに書きます。
関数名は Bench で始め、引数として *testing.B を渡す関数として定義します。
(このへんはテストと同じです。)

// swrap_test.go

import (
	"testing"
)

func BenchmarkAdd(b *testing.B) {
	for i := 0; i < b.N; i++ {
		sw := New(Fixture())
		sw.Add(0xFF)
	}
}

func BenchmarkLen(b *testing.B) {
	sw := New(Fixture())
	b.ResetTimer()

	for i := 0; i < b.N; i++ {
		sw.Len()
	}
}

b.N が勝手に設定されるので、それをループの条件とするだけです。
ループにかかる時間を測るので、ループに入る前の準備処理などに時間がかかる場合は、
ループの前に b.ResetTimer() を呼ぶと準備処理分を引くことができます。

実行方法

実行は go test にオプションを追加するだけです。($GOPATH を通しておいて下さい)

$ go test -bench Add   # Add とつくものだけ実行
$ go test -bench .     # 全て実行

全ての実行例はこんな感じです。(インデントだけ整形済み)

$ go test -bench .
PASS
BenchmarkNew      2000000000   0.64 ns/op
BenchmarkBytes    2000000000   1.09 ns/op
BenchmarkLen      2000000000   1.23 ns/op
BenchmarkAdd      5000000      334 ns/op
BenchmarkMerge    10000000     254 ns/op
BenchmarkDelete   20000000     148 ns/op
BenchmarkCompare  50000000     32.8 ns/op
BenchmarkPush     5000000      354 ns/op
BenchmarkPop      10000000     114 ns/op
BenchmarkShift    10000000     234 ns/op
BenchmarkUnShift  20000000     109 ns/op
BenchmarkReplace  5000000      614 ns/op
ok    swrap 27.847s

実行回数が違うのは、 b.N の値が変わっているからですね。
この b.N は直接指定するのではなく、ベンチの実行時間からの逆算です。
デフォルトは 1 秒間実行しているようです。
この実行時間は -benchtime で指定できます。
十分な時間を指定し、性能自体は ns/op で見るのが良さそうです。

benchmem

"-benchmem" オプションをつけるとメモリアロケート回数がわかります。
変数をポインタに変更するなどの改善ポイントが見つけられます。

PASS
BenchmarkLen	2000000000	0.95 ns/op	0 B/op	0 allocs/op
BenchmarkAdd	 5000000	370 ns/op	48 B/op	2 allocs/op

比較

実はこの結果を比較するツールがひっそりと同梱されています。

まったくいいサンプルが無いんだけど手元にあったもので、
例えば以下の様な超地味なチューニングに成功したとします。

PASS
BenchmarkNew	2000000000	0.47 ns/op	0 B/op	0 allocs/op
ok  	swrap	1.000s
PASS
BenchmarkNew	2000000000	0.44 ns/op	0 B/op	0 allocs/op
ok  	swrap	0.954s

それぞれ before after で保存して
これを misc 以下にある benchcmp に渡します。

$ $GOROOT/misc/benchcmp before after
benchmark       old ns/op    new ns/op    delta
BenchmarkNew            0            0   +6.82%

こうした値をパッチに添えて PR とかすると話が速くていいかもしれませんね。

オプション

オプションを簡単(適当)に訳しておきます。
(まだ使ったことがないものが多いです)

http://golang.org/cmd/go/#hdr-Description_of_testing_flags

-bench regexp       対象の指定
-benchmem           メモリアロケーションの表示
-benchtime          ベンチ実行時間
-blockprofile       goroutine のブロックプロファイルを出力
-blockprofilerate   runtime.SetBlockProfileRate の値を指定
-cpu                GOMAXPROCS の値を指定
-cpuprofile         CPU プロファイルを出力
-memprofile         メモリプロファイルを出力
-memprofilerate     runtime.MemProfileRate の値を指定
-parallel           並列実行の指定(デフォルトは GOMAXPROCS)
-run                テストと example の実行対象指定
-short              時間を短縮して簡易実行
-timeout            タイムアウト
-v                  詳細出力