
json.RawMessage を使うと，一部のフィールドを見てから payload の型を決定することができます

## 問題

WebSocket でやりとりするサーバを書いていて，一つのコネクション上でいくつかの種類のコマンドを JSON として受け付けるような仕組みが欲しくなりました．

```json
{
  "action": "increment",
  "payload": {
    "value": 3
  }
}
```

と

```json
{
  "action": "greet",
  "payload": {
    "name": "World"
    "language": "English"
  }
}
```

のように， `action` フィールドに応じて `payload` の構造が変わるという構成です．

golang でふつうに JSON を受け取って構造体にマップする際には，下のようにします．

```go
type Message struct {
  Action string `json:"action"`
  Payload struct {
    Value int `json:"value"`
  } `json:"payload"`
}
var msg Message
json.Unmarshal(body, &msg)
```

この方法では， `action` の値に応じて `payload` の構造が変わることを表現できません．無理やり `Payload` の struct を大きくして

```go
struct {
  Value int `json:"value"`
  Name string `json:"name"`
  Language string `json:"language"`
}
```

のようにすることも出来ますが，どの action の時にどのフィールドが使えるのかわかりにくい上に， `value` のような汎用的な名前のフィールドが複数の型を取るケースを表現できません．( `{ "value": 1 }` と `{ "value": "World" }` など）

## 解決方法

`json.RawMessage` を使って，動的な部分の unmarshal を遅延します．

```go
type Message struct {
  Action string `json:"action"`
  Payload json.RawMessage `json:"payload"`
}
var msg Message
json.Unmarshal(body, &msg)
```

このようにすると， `msg.Payload` には `` []byte(`{"value": 1}`) `` がそのまま残ります．

そこで，それぞれの action ごとの payload 型を定義しておき

```go
type IncrementPayload struct {
  Value int `json:"value"`
}
type GreetPayload struct {
  Name string `json:"name"`
  Language string `json:"language"`
}
```

`msg.Action` に応じて， `msg.Payload` をどう unmarshal するか決定します．

```go
switch msg.Action {
case "increment":
  var p IncrementPayload
  json.Unmarshal(msg.Payload, &p)
  // do increment action
case "greet":
  var p GreetPayload
  json.Unmarshal(msg.Payload, &p)
  // do greet action
}
```

## まとめ

- 動的に構造が決定する JSON を受け付けたかった
- json.RawMessage を使うと，一部のフィールドだけ unmarshal 操作を遅延できる
- 構造の決定に必要な部分だけ先に unmarshal して，そこを見てから残りを unmarshal する

動的に構造が決定する部分を何かしらの interface として抽象化できる場合は，特にこの手法が有効そうです．

そもそも `{ "action": "increment", "increment_payload": { "value": 1 } }` ， `{ "action": "greet", "greet_payload": { "name": "world", "language": "English" } }` のようにフィールド名を変えてしまうという手もありますね．


Go で構造の一部が動的に変わる JSON を扱いたい

# HTTP サーバと context.Context

golang で HTTP サーバを書く際に，どう context.Context を活用したら良いか，今考えていることをまとめておきます

## はじめに

golang における強力な道具の一つに `context.Context` interface というのがあります．キャンセルをサブルーチンに伝搬したり，限られたスコープ内で一貫してアクセスできるインメモリ KV ストア的な役目を担っています．

サーバにおいても，リクエストがキャンセルされたら handler の内部で行う高コストな計算や外部リソースへのアクセスもキャンセルできるようにしておくのが望ましいはずです．また，リクエストスコープに閉じる値を保持するインメモリ KV ストアとしての役割も context で担えます．

そこで，HTTP サーバを書く際にどのように`context.Context` を活用するのが良いかをまとめたいと思います．

## キャンセルの伝搬

`http.Request` は `func(*Request) Context() context.Context` というメソッドを持っています．これは，サーバから見た場合以下のようなケースにおいて，リクエストのキャンセルを伝えるために使われています．(ref: [https://golang.org/pkg/net/http/#Request.Context](https://medium.com/r/?url=https%3A%2F%2Fgolang.org%2Fpkg%2Fnet%2Fhttp%2F%23Request.Context))

1. コネクションが切断された場合
2. リクエストがキャンセルされた場合（HTTP/2）
3. 一つの Handler の `ServeHTTP` に渡され，return してきた場合（= Handler によって適切にハンドリングされた場合）

したがって， `http.Handler.ServeHTTP` の中ではこの context を見ることで，その Request の処理を続ける必要があるか判定することができます．

```go
func doSomething(ctx context.Context, body io.ReadCloser) error {
	// 重たい処理 (DB アクセス，外部 API，...）
	select {
	case <-ctx.Done():
		return ctx.Err()
	default:
		// ...
	}
	return nil
}

type Server struct{}

func (s *Server) ServeHTTP(w http.ResponseWriter, r *http.Request) {
	ctx := r.Context()
	if err := doSomething(ctx, r.Body); err != nil {
		// ...
	}
}
```

## インメモリ KVS

context をインメモリ KVS 的に扱いたい場合， `context.WithValue` を使います． これは，ベースとなる context をもとに，エントリを追加した新しい context を返す関数です．

すでにある context を mutate するのではなく，新しい context を生成するため， `context.WithValue(req.Context(), key, value)` としても `req.Context()` にはなんの変化も起こりません．新しく作られた context を使うようにして上げる必要があります．

そこで `http.Request.WithContext` を使います．引数に新しい context をとって，その context がセットされたリクエストの shallow copy を返します．

どんなケースに使われるかというと，middleware パターンを使ったケースが挙げられます． `func (h http.Handler) http.Handler` のような関数を定義しておくことで，組み合わせて使用可能な機能の部品を作れます．典型的にはログ出力や認証，panic ハンドリングなどが middleware として実装されることが多いです．

```go
func findUser(name string) (id int, found bool) {
	return 123, true
}

type Middleware func(h http.Handler) http.Handler

func Authentication(h http.Handler) http.Handler {
	return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
		user, ok := findUser(r.URL.Query().Get("name"))
		if ok {
			ctx := context.WithValue(r.Context(), "user-id", user)
			r = r.WithContext(ctx)
		}
		h.ServeHTTP(w, r)
	})
}
```

Type caption for embed (optional)

このような形で， Request に紐づく context に値を追加し，再度 `Request.WithContext` で紐付け直すようにします．

値を Get する側は， `r.Context().Value("user-id")`でアクセスすることができます．

通常は package private な const として key を定義しておき，Get/Set を行う utility 関数を用意することで，直接ハンドラ内で `ctx.Value` や `context.WithValue` を呼ばないようにします．（でないと実質なんでも入る静的型情報もないグローバル変数になり，管理できなくなるため）

## context をどう渡すか

context の生まれた経緯が原因なのか，context を Request から取得するのではなく，明示的に渡す形にしている WAF やライブラリが結構あったりします．

`type HandlerCtx func(ctx context.Context, w http.ResponseWriter, r *http.Request)` を基本のハンドラに据えて，middleware も `func(h HandlerCtx) HandlerCtx` のように定義しているといったものです．

個人的には今から書くプログラムは，この形式の context 伝搬は避けるべきだと思っています． `http.Request.Context()` がすでにあるのに，それとは異なる context を渡すということは，context の階層構造の分岐を招きます．実際には `handler(r.Context(), w, r)` のように呼び出すことで分岐は避けることが出来ますが，それでも混乱は生じるはずです．

`context.WithDeadline` や `context.WithCancel` によって作られた context が第一引数に渡った場合，handler 内部ではその context の親に `http.Request.Context()` が含まれているかどうか判断することができません．そのため，第一引数の context と `r.Context()` の両方をチェックしなければならないのでは，という疑問を生じてしまいます．

middleware は `func(h http.Handler) http.Handler` として定義し，新しく context を使いたい場合は必ず `r.Context()` を親に context を作り， `r.WithContext` でセットしなおすようにしたほうが良いはずです．

## context に何を保存するか

context にはリクエストローカルなオブジェクトだけを入れるようにします．典型的にはユーザ認証の結果などです．

ユーザ認証は様々なエンドポイントで行いたいので DRY にするべく middleware として実装するのにもってこいな一方で，権限のチェックはエンドポイントごとに違う処理が必要になるため middleware 内で行うことは出来ません．

そこで認証の結果であるユーザオブジェクトを `r.Context()` の中に入れておくことで，ハンドラ側で簡単に取り出して任意のチェックをすることができます．

一方，リクエストをまたぐデータには，例えばロガーや newrelic などの外部サービスのクライアント，DB クライアントなどが挙げられます．

このようなリクエストを跨いてサーバ起動中にはずっと生かしておきたいオブジェクトは，素直に `http.Handler` を実装する構造体のなかに入れておくのがいいと思います．

```go
type Server struct {
	db *sql.DB
	logger *log.Logger
}

func (s *Server) ServeHTTP(w http.ResponseWriter, r *http.Request) {
 s.db.Exec("...")
 // ...
}
```

Type caption for embed (optional)

## まとめ

実は今まで `http.Request.Context()` がサーバから見た時にどういう振る舞いをするのかあまり把握していませんでした．クライアントから見た場合，「この context にキャンセルを通知するとリクエストをキャンセルしてくれる」という役割であることは知っていましたが，サーバ側では使ったことがありませんでした．

context とサーバの話は今更感の強い話ではあるなぁと正直思いましたが，意外と `func(ctx context.Context, w http.ResponseWriter, r *http.Request)` 形式で書かれたサンプルも見つかったのと，[https://github.com/gin-gonic/gin](https://medium.com/r/?url=https%3A%2F%2Fgithub.com%2Fgin-gonic%2Fgin) のようなフレームワークを使っていると忘れがちな部分だと思ったのでまとめてみることにしました．

HTTPサーバとcontext.Context


現在時刻に依存するコードをテストするとき，golang で `time.Now` を普通に使っているとモックできずうまくテストが書けないという問題があります．
時間の操作は time パッケージをそのまま使えば良いのですが，time.Now だけはモックできるようにしたいところです．

解決方法としては，グローバル変数に `var NowFunc func() time.Time` を置いておいて，テスト時に入れ替えるという方法があり，ORM である gorm などが実際にこれを行っています．

[gorm/utils.go at 2a1463811ee1dc85d168fd639a2d4251d030e6e5 · jinzhu/gorm · GitHub](https://github.com/jinzhu/gorm/blob/2a1463811ee1dc85d168fd639a2d4251d030e6e5/utils.go#L21)

例:

```
var NowFunc = time.Now

func Do() string {
    return NowFunc().String()
}

func TestDo(t *testing.T) {
    now := time.Date(2009, time.November, 10, 23, 0, 0, 0, time.UTC)
    NowFunc = func() time.Time {
        return now
    }
    got := Do()
    if got != now.String() {
        t.Fail()
    }
}

```

golang の使用上，Ruby の timecop のようなことは出来ないので，こういう工夫をするしかありません．

なんとなくグローバル変数をテストのために置いて書き換えるのが嫌なのと，なんにも考えずに `t.Parallel()` を置けなくなるのがちょっと嫌だなと思っていました．
また，時間経過をシミュレーションしたい場合は，そういう `NowFunc` を毎回書く必要があり，結構面倒です．
あとパッケージをまたぐと厄介だし毎回書くのも嫌．

そこで，Ruby の timecop のように現在時刻をいじくり回せるようにするライブラリを作ってみました．

[github.com](https://github.com/agatan/timejump)

[godoc.org](https://godoc.org/github.com/agatan/timejump)

使用する際は `time.Now` をすべて `timejump.Now` に置き換える必要があります．（ Ruby と違って `time.Now` を直接上書きできないので...）
普段は `timejump.Now` と `time.Now` は `if !active { ... }` が一段挟まるだけなのでパフォーマンスに影響はほとんどないはずです．

テスト時は，`timejump.Now` の挙動を変えたいテストの頭で

```
func TestDo(t *testing.T) {
    timejump.Activate()
    defer timejump.Deactivate()
    ...
}

```

とします．

`timejump.Activate` な区間はロックをとっているので，テストを並列で走らせても並列に走らなくなります．

`timejump.Stop()` で時間停止，`timejump.Jump` で時間移動，`timejump.Move` でタイムゾーンの移動，`timejump.Scale` で時間の経過速度をいじれます．

時間を止めたいだけの場合はグローバル変数に `NowFunc` を持っておいて `t.Parallel` を間違って置かないように気をつけるほうが正直楽だとは思いますが，時間経過をテストしたい場合にはちょっと楽になるはずです．

もともとあるパッケージのテストをするために書いたパッケージだったのですが，目的だったテストを書く前にテストしたいパッケージが御役御免になってしまったので，timejump も御役御免になってしまいました．
いつか使う日が来る気がするので，ここに寝かせておきます．

---

---


golang でテストのために時間を操作するライブラリ timejump


[https://github.com/golang/mock](https://github.com/golang/mock) は `mockgen` というコマンドを提供しています．
これは，interface から mock を自動生成するコマンドで `go generate` と合わせて使うと interface に追従する mock がとても簡単に作れます．

他にも yacc とかリソースをバイナリに埋め込むとか，色々便利ツールがあり，`go generate` でコード生成をするのは golang のアプリケーションではよくあることだと思います．

しかし，golang の `vendor/` の仕組みは基本的に package として使うことを考えて作られているので，プロジェクトごとに `mockgen` などの生成コマンドのバージョンを固定するためには使えません．

ここで，`go generate` で使うバイナリのバージョンが固定されていないと起こりうる問題として

- 生成されたコードに毎回 diff が出る
  - 気軽に `git add .` 出来ないし，コミット漏れや無駄コミットにつながる
- バージョン A のコマンドとバージョン B のコマンドによって生成されたコードが混ざる
- ライブラリのバージョンと生成コマンドのバージョンが一致しないためバグる
  - `github.com/golang/mock/mockgen` は `github.com/golang/mock/gomock` というライブラリとセットで使うので，`gomock` package と `mockgen` バイナリのバージョンは揃えたい

などがあります．

これ結構嫌な問題だと思ったのですが，パッとぐぐってみてもあまり困っている声を聞かないので普通どうやって解決しているのか気になっています．
(もしかして僕が知らないだけで普通に解決されている問題だったりするのだろうか…)

とりあえず `vendor` 以下の package をビルドしたり固定されたバージョンのバイナリをぱぱっと実行するために

[github.com](https://github.com/agatan/bindor)

を作ってみました．

shell script で書けそうな単純な仕事しかしていませんが，go で実装されています．

`bindor build github.com/golang/mock/mockgen` で `./.bindor/mockgen` というバイナリが出来ます．
`bindor exec command args...` とやると `PATH=./.bindor:$PATH` した環境下で `command args...` を実行します．

```
$ glide get github.com/golang/mock
$ bindor build github.com/golang/mock/mockgen
$ bindor exec which mockgen
/path/to/current/.bindor/mockgen

```

という感じです．

`//go:generate bindor mockgen` としてもいいですが，`bindor exec go generate` とすればソースコードを書き換えなくても `.bindor` 以下のバイナリを使うようになるはずです．

`bindor` 自体にバージョンを固定する仕組みは入れていません．glide とかがやってくれている仕事を分散させても管理が面倒になるだけでメリットがなさそうだし，ライブラリとしても使う package の場合はどうせ glide で管理するので，`vendor` 以下のディレクトリの奪い合いになってしまいます．

というわけでバイナリを vendoring する `bindor` を作った話でした．もっといい解決方法があったら教えてください．

---

---


go generate する時のバイナリのバージョンを固定したい

先日はてぶに [興味深いデータ構造：BK 木 | プログラミング | POSTD](http://postd.cc/bk-tree/) という翻訳記事 ( 元記事 [http://signal-to-noise.xyz/post/bk-tree/](http://signal-to-noise.xyz/post/bk-tree/)) があがっているのをみて初めて BK-tree というものを知ったので，golang で実装してみました．

[github.com](https://github.com/agatan/bktree)

## BK-tree とは

先程の記事に全部書いてあるのですが…
BK-tree は，ある距離空間内で近傍点探索を効率的に行えるデータ構造です．利用例としてはスペルチェックや類似画像検索などがあります．

距離空間とは，なにかしらの距離を計算することができる空間のことで，距離としてハミング距離やマンハッタン距離，レーベンシュタイン距離，ユークリッド距離などなどが挙げられます．
例えば，いわゆる普通の 3 次元の空間は，ユークリッド距離を距離関数に持つ距離空間と考えられます．

近傍点探索は，要するにある点に対して，近くにある点を探すことです．

![f:id:agtn:20170513183241p:plain](/i/20170513183241.png "f:id:agtn:20170513183241p:plain")

ものすごく単純に近傍点探索をやろうと思うと，全要素を線形に探索して距離を計算していく必要があります．
そこで BK-tree を使うともっと計算量が減らせるというわけなのです．(ちなみに僕は BK-tree を使った場合の計算量がよくわかっていません．実験的に速いことを確認しただけです．正確な計算量は考えてもよくわかりませんでした…)

構造や仕組みは元記事などをご参照ください．

golang での bk-tree 実装は実はいくつかあったのですが，単純にアルゴリズムを理解するために実装したかったのと，レーベンシュタイン距離を距離関数として使うことを前提にしていたりとちょっと自分の用途に合っていない気がしたので，別で作ってみました．

このパッケージでは，スペルチェックそのものや距離関数を提供していません．BK-tree というデータ構造だけを提供しています．

## 使用例

16 bit 整数を要素，ハミング距離を距離関数とした例です．

要素となる型は `bktree.Entry` interface を満たす必要があります．これは `Distance(Entry) int` を要求する interface です．

本当は `distance<T: Entry>(x: T) -> int` みたいな形にしたいのですが，golang だと出来ないので，実装側で `e.(hashValue)` のように型アサーションする必要があります．

ここでは `uint16` に戻してハミング距離を計算しています．

要素の追加は `Add(e Entry)` です．

ここでは 0 ~ 0xffff までを突っ込んでいます．

探索は `Search(e Entry, tolerance int) []*Result` です．
第一引数がキー，第二引数が許容する距離の最大値です．

```
package main

import (
 "fmt"

 "github.com/agatan/bktree"
)

type hashValue uint16

// Distance calculates hamming distance.
func (h hashValue) Distance(e bktree.Entry) int {
 a := uint16(h)
 b := uint16(e.(hashValue))

 d := 0
 var k uint16 = 1
 for i := 0; i < 16; i++ {
 if a&k != b&k {
 d++
 }
 k <<= 1
 }
 return d
}

func main() {
 var tree bktree.BKTree

 // add 0x0000 to 0xffff to the tree.
 for i := 0; i < 0xffff; i++ {
 tree.Add(hashValue(i))
 }

 // search neighbors of 0x0000 whose distances are less than or equal to 1.
 results := tree.Search(hashValue(0), 1)
 for \_, result := range results {
 fmt.Printf("%016b (distance: %d)\n", result.Entry.(hashValue), result.Distance)
 }
}

```

これを実行すると，

```
0000000000000000 (distance: 0)
0000000000000001 (distance: 1)
0000000000000010 (distance: 1)
0000000000000100 (distance: 1)
0000000000001000 (distance: 1)
0000000000010000 (distance: 1)
0000000000100000 (distance: 1)
0000000001000000 (distance: 1)
0000000010000000 (distance: 1)
0000000100000000 (distance: 1)
0000001000000000 (distance: 1)
0000010000000000 (distance: 1)
0000100000000000 (distance: 1)
0001000000000000 (distance: 1)
0010000000000000 (distance: 1)
0100000000000000 (distance: 1)
1000000000000000 (distance: 1)
```

という感じで 0x0000 とのハミング距離が 0 ~ 1 である要素がとれます．

## パフォーマンス

単純な線形探索との比較をするベンチマークをおいてあります．

64 bit 整数，距離関数はハミング距離，データ量 1,000,000 件での結果が以下のようになりました．

| ベンチマーク | 実行時間 |
| ---------------------- | --------------- |
| BK-tree (完全一致) | 1108 ns/op |
| BK-tree (fuzziness 1) | 29468 ns/op |
| BK-tree (fuzziness 2) | 328753 ns/op |
| BK-tree (fuzziness 4) | 5490888 ns/op |
| BK-tree (fuzziness 8) | 68182122 ns/op |
| BK-tree (fuzziness 32) | 353715305 ns/op |
| Linear Search | 4132926 ns/op |

fuzziness が小さければ小さいほど ( = tolerance が小さければ小さいほど ) 高速に探索できることが分かります．

また，データ量が増えるほど Linear Search より有利になるので，距離に対してデータが十分に大量にある場合はかなり有効といえそうです．

## おまけ

tree の構築にかかるコストがそこそこ大きかったので pprof で見つつチューニングする必要がありました．
学びとして，「map が重い」「interface が重い」というのがありました．

各ノードの部分木は，そのノードからの距離 d を key として，`map[int]*Node` としていました．
tree を構築する際には，allocate + read + write をかなりの回数行うのですが，これがまぁ遅い．

最終的にこの部分はスライスでもっておいて，d を key として部分木をとりたい時は線形探索をするようにしました．

`next, ok := n.children[d]` としていた部分が

```
type elem struct
 distance int
 node *node
}

for \_, c := range n.children {
 if c.distance == d {
 return c.node
 }
}
return nil

```

という感じになります．あんまりきれいではないんですが，こっちの方がほとんどのケース倍以上速かったので，こちらを採用しました．

部分木の数が増えてくると，map のほうが速いと思われるのですが，ハミング距離の場合最大でも bit 数までしか部分木が増えないので．

レーベンシュタイン距離を用いたスペルチェックの場合でも，単語の最大文字数以上の距離にはなりません．
2 次元 / 3 次元程度の距離空間なら kd-tree などもっと他に良い方法があるきがするので，レーベンシュタイン距離やハミング距離を使うケースをメインに考えました．

その結果，実行時間のかなりの割合が `Entry` interface を介した関数呼び出しのオーバヘッドとか，inteface の allocation になってしまいました．

データ構造を golang で提供する以上このオーバヘッドは避けられないです．( もちろん BK-tree そのものを，自分の利用形態に特化して作れば回避できますが… )

ちょっと Rust や C++ で書きたくなりました．十分速いし書きやすいので良いんですが…

---

---

BK-tree を golang で実装した

必要に迫られて、HTML ページ内の改行位置をいい感じにするツールを作ってみました。

[github.com](https://github.com/agatan/japawrap)

HTML に長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロー
ド問題が挙げられます。

`japawrap` を使うと、それっぽく日本語を解釈して `` でくくるみたいなことができます。`inline-block` を適用すれば改行がそれっぽく入るようにできます。

## Install

`go get github.com/agatan/japawrap/...`

で `japawrap` コマンドが使えるようになります。

## Usage

### CLI

ファイル名を指定するか標準入力から流し込みます。

```bash
$ echo "今日も元気です" | japawrap
今日も元気です
```

このように適宜いい感じに wrap してくれます。

オプションとして `-open string` と `-close string` をサポートしているので、

```bash
$ echo "今日も元気です" | japawrap -open '' -close ""
今日も元気です
```

みたいなことができます。

### Library

一応 `japawrap` はライブラリとしても使用できるようになっています。

```go
w := japawrap.New(open, close)
s := "今日も元気です"
fmt.Println("%s => %s", s, w.Do(s))
```

これだけです。

## Example

では実際に使った結果を下に記したいと思います。 文章は、上の方に自分で書いた文章をそのまま使います。

---

#### before

HTML に長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロード問題が挙げられます。

#### after

HTMLに長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。
しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。
最も有名な問題として、今すぐダ
ウンロード問題が挙げられます。

---

こんな感じになります。猛烈に効果がわかりにくくて驚いていますが、一応効果はちゃんと出ているのではないでしょうか？ HTML を直接見ていただければどうなっているかはわかると思います。

次に青空文庫から夏目漱石「こころ」の序文を抜粋してみたのが下の画像たちです。

![f:id:agtn:20161029131814p:plain](https://cdn-ak.f.st-hatena.com/images/fotolife/a/agtn/20161029/20161029131814.png "f:id:agtn:20161029131814p:plain")![f:id:agtn:20161029131817p:plain](https://cdn-ak.f.st-hatena.com/images/fotolife/a/agtn/20161029/20161029131817.png "f:id:agtn:20161029131817p:plain")![f:id:agtn:20161029131820p:plain](https://cdn-ak.f.st-hatena.com/images/fotolife/a/agtn/20161029/20161029131820.png "f:id:agtn:20161029131820p:plain")

レスポンシブ！それなりになっている気がします。

#### あとがき

この問題へのアプローチとして、[https://github.com/google/budou](https://github.com/google/budou) が有名だと思います。

`budou` は　[Cloud Natural Language API](https://cloud.google.com/natural-language/) を内部で使っていて、しっかり日本語の文章を構文解析しているようです。 なので非常に精度は高いと思うのですが、今僕の GCP アカウントがごにょごにょしていてぱぱっと試せる状況ではなかったので自作しました。

`budou` と違ってしっかり構文解析などはしていなくて、形態素解析した後、それっぽく分割しているだけです。なので精度は落ちると思います。 一方、`budou` は GCP の credentails が必要だったりと準備が必要になるので、お手軽に試せるというのは悪くないかなと思っています。

日本語の改行を適当にいい感じにするツールを作りました

# まず結論

`append` しよう. `bytes.Buffer` はそんなに速くない.

# きっかけ

こんな記事を見かけました.

[Go では文字列連結はコストの高い操作 - Qiita](http://qiita.com/ruiu/items/2bb83b29baeae2433a79)

`buf += "abc"` はコストが高いよーっていうお話ですね. これは golang にかぎらず, Java とかでもよく話題になる一般的な問題だと思います.

Java だと `StringBuilder` を使うのが良いとされていたと思いますが, golang だと解法がいくつかあるようです.

そこで, 解法をそれぞれ紹介した後, ベンチマーク結果を載せてみたいと思います.

## 1. 普通に `+=`

まずは普通に `+=` で連結していく方法です.

```
func AddString(n int) string {
 base := "abc"
 buf := ""
 for i := 0; i < n; i++ {
 buf += base
 }
 return buf
}

```

こんな感じですね.

これだと, 確実に n 回メモリ割り当てが発生するので遅いというのが問題となります.

## 2. `append` する

golang の `string` は, メモリ上では `[]byte` と同等の表現を持ちます.

そこで, `string` を `[]byte` として扱い, golang のスライスを伸長する `append` 関数を用いるという方法があります.

```
func AppendString(n int) string {
 base := "abc"
 buf := make([]byte, 0)
 for i := 0; i < n; i++ {
 buf = append(buf, base...)
 }
 return string(buf)
}

```

`make([]byte, 0)` によって, 長さ 0 のスライスを作って, それを伸長していく方法となっています.

このあたりは golang のスライスの表現について知っていないとわかりづらいと思うのですが, わかりやすい説明がいろいろなところで読めるので, ここでは説明しません.
`append` 関数は, スライスの len を必要な分だけ大きくします. また, その結果 len が スライスの cap を超える長さになる場合は, スライスの cap を必要以上に大きくすします.

これは, `append` を繰り返し適用するような場合(今回のように)に, メモリ割り当ての回数を最小にするためです. 一度の `append` で大きめにメモリを確保しておくことで, 次の `append` ではメモリ割り当てをしなくても済む可能性が生まれます.

イメージとしては,

| append の回数 | 0 | 1 | 2 | 3 |
| ------------- | --- | --- | --- | --- |
| len | 0 | 3 | 6 | 9 |
| cap | 0 | 8 | 8 | 16 |

こんな感じでしょうか(あくまでイメージですが)

`append` は 3 回呼ばれていますが, メモリ割り当ては 2 回に抑えられています.

その分, `+=` よりも速いだろうということですね.

### 2'. `cap` を十分量確保しておく

`make` によるスライスの作成の際には, 長さだけでなくキャパシティを指定することが出来ます.

したがって, はじめから `append` していった後の最終的なスライスの長さがわかっているのであれば, それをキャパシティに指定することで, メモリ割り当てを最小限に抑えることが可能になります.

```
func AppendStringWithCap(n int) string {
 base := "abc"
 buf := make([]byte, 0, 3*n)
 for i := 0; i < n; i++ {
 buf = append(buf, base...)
 }
 return string(buf)
}

```

## 3. `bytes.Buffer` を使う

Java の `StringBuilder` に近い解法ですね.

`bytes.Buffer` は文字通りバイト列のバッファリングを行ってくれます.

`bytes.Buffer` に文字列やバイト列を書き込んでいくと, 自動的にメモリ割り当てを減らすように計らってくれます.

```
func BufferString(n int) string {
 base := "abc"
 var buf bytes.Buffer
 for i := 0; i < n; i++ {
 buf.WriteString(base)
 }
 return buf.String()
}

```

こんな感じです.

# ベンチマーク結果

golang にはベンチマークをとる機能も標準で付いているので, それを利用しました.

```
package main

import "testing"

const N = 1000

func BenchmarkAddString(b *testing.B) {
 for i := 0; i < b.N; i++ {
 AddString(N)
 }
}

func BenchmarkAppendString(b *testing.B) {
 for i := 0; i < b.N; i++ {
 AppendString(N)
 }
}

func BenchmarkAppendStringWithCap(b *testing.B) {
 for i := 0; i < b.N; i++ {
 AppendStringWithCap(N)
 }
}

func BenchmarkBufferString(b *testing.B) {
 for i := 0; i < b.N; i++ {
 BufferString(N)
 }
}

func TestEquality(t *testing.T) {
 base := AddString(N)
 tests := []string{
 AppendString(N),
 AppendStringWithCap(N),
 BufferString(N),
 }
 for \_, test := range tests {
 if base != test {
 t.Fatal("not fair")
 }
 }
}

```

`TestEquality` は, すべての方法で正しく文字列を生成できていることを確認するためのテストです. ベンチマークには関係ありません.

## 結果

上記のファイルを用意した後, `go test -bench . -benchmem` とした結果を以下に示します.

```
PASS
BenchmarkAddString-8 5000 348347 ns/op 1592481 B/op 999 allocs/op
BenchmarkAppendString-8 200000 7346 ns/op 13056 B/op 12 allocs/op
BenchmarkAppendStringWithCap-8 300000 5461 ns/op 6144 B/op 2 allocs/op
BenchmarkBufferString-8 100000 16847 ns/op 12256 B/op 8 allocs/op
ok github.com/agatan/bench 6.881s
```

というわけで, `make` の時点で十分なメモリを確保しておく 2' の方法が最も速く最もメモリを消費しないことがわかりました.

まぁ当たり前ですねｗｗ

より注目すべきは, 2 と 4 の結果です. 今回の結果だと, 最終的な文字列の長さがわからない場合, `bytes.Buffer` よりも `append` を使ったほうが速いという結果になっています (メモリ使用量は若干 `bytes.Buffer` のほうが小さい)

メモリ割り当ての回数も `bytes.Buffer` のほうが少なく済んでいるため, `[]byte` と `string` の変換など, 文字列連結以外の部分でのオーバーヘッドが大きいため, このような結果になった可能性があります. そこで, `N` の値を変えて実行してみました.

## N = 10 の場合

```
PASS
BenchmarkAddString-8 2000000 613 ns/op 224 B/op 9 allocs/op
BenchmarkAppendString-8 5000000 270 ns/op 96 B/op 4 allocs/op
BenchmarkAppendStringWithCap-8 10000000 142 ns/op 64 B/op 2 allocs/op
BenchmarkBufferString-8 5000000 251 ns/op 144 B/op 2 allocs/op
ok github.com/agatan/bench 6.581s
```

## N = 10000 の場合

```
PASS
BenchmarkAddString-8 50 28544042 ns/op 160274378 B/op 10039 allocs/op
BenchmarkAppendString-8 20000 71285 ns/op 160768 B/op 20 allocs/op
BenchmarkAppendStringWithCap-8 30000 55262 ns/op 65536 B/op 2 allocs/op
BenchmarkBufferString-8 10000 151665 ns/op 109280 B/op 11 allocs/op
ok github.com/agatan/bench 7.393s
```

# 結論

連結する文字列の長さや連結の回数にもよるが, おおよそ `append` のほうが速い！！

`bytes.Buffer` はいつ使えばいいの...

---

---

Golang での文字列連結に関するベンチマーク


最近 golang が気になります

golang の特徴はもはやわざわざここに書くまでも無いことだと思うので書きませんが, 気になっている理由を書いてみます.

- バイナリ(しかもポータビリティが非常に高いバイナリ)にコンパイルされること
- C/C++ には及ばずとも実行が非常に速いこと
- C/C++ ほど低レイヤーいじり放題なわけではないが, ある程度低レイヤーまで降りていけること
- コマンドラインツールから Web アプリケーションのような高レイヤーまで十分得意であること
- `interface` による抽象化が, 過度でなく調度良く感じられること

こんな感じでしょうか.

Compiled Python っていう感じが非常に良さそうだなーと思っています.

というわけで Haskell に引き続き golang でも echo サーバを書いてみました

```
package main

import (
    "fmt"
    "io"
    "net"
)

func main() {
    listener, err := net.Listen("tcp", ":8080")
    if err != nil {
        panic(err)
    }
    for {
        conn, err := listener.Accept()
        if err != nil {
            panic(err)
        }
        go func(conn net.Conn) {
            defer conn.Close()
            echo(conn)
        }(conn)
    }
}

func echo(conn net.Conn) {
    buf := make([]byte, 256)
    for {
        n, err := conn.Read(buf)
        if err != nil {
            if err == io.EOF {
                break
            }
            panic(err)
        }
        if n == 0 {
            break
        }
        wn, err := conn.Write(buf[0:n])
        if err != nil {
            panic(err)
        }
        if wn != n {
            panic(fmt.Errorf("could not send all data"))
        }
    }
}

```

さすがは golang というかなんというか. ものすごく普通な空気を感じますね.

golang はこういう普通さが売りの１つだと思っています.

---

---


↗ agatan blog ↗

#Go